Structured Analysis And Applications Of Online Social Networks

Following the footstep of scientific computing and life computing,researches on social computing and network society have been a hot spot and a cutting-edge topic among researchers.Structured analysis in social networks is one of the core issues in social computing,understanding the structured characteristics of social systems in-depth will help improve social productivity,ease social conflicts,improve social benefits and solve social problems,which has broad application prospects.Most of the existing structure analysis method,however,can only deal with the static network but not the evolutionary ones.In addition,some inherent technical difficulties,such as the high time complexity of the algorithm,priori knowledge dependent,structured shape constraint,high data dimension,limits the development of the field.In response to the deficiency of the traditional methods,this dissertation make efforts to improve,complete and develop the existing methods.On one hand,we study how to design the dynamic structured analysis framework in order to meet the real-time requirement of online network.On the other hand,we study how to design more forward-looking approachs to solve the technical difficulties which exists in the social network motif detection task.Finally,we solve a concrete problem exists in social application system by using the structured characteristics of network motif.In conclusion,the contents of this dissertation includes the following four aspects:(1)Researchs on community detection in multi-relational social networks.Compared with the community structure in homogeneous networks,the one in multi-relational social networks is connotative and undetectable.Previous methods mostly adopted global optimization methods and treat heterogeneous community detection problem as a structure representation issue.This kind of methods may have advantages in some specific networks but lack of universality.For example,if the social relations between different network layers in heterogeneous social system are quite different,the community structure generated by global optimization method will deviate from the real ones,which caused lower precision.Furthermore,global optimization ignore the correlations of each network layers,so the community structure may lose its practical significance as the interaction of nodes inside such communities are weaker.In this paper,the heterogeneous community detection problem is modeled as a locally selection process in social networks.First,we present heterogeneous random walk model by measuring the attraction between each layers and the transition probability between nodes in homogeneous networks.Then,we model the similarity of nodes as the mutual transition probability inside communities by constrain the reachability of random walker.Finally,we extand the similarity function to hierarchical clustering and the multi-relational community structure can be obtained iteratively in a relatively short period of time.(2)Researchs on community detection in online social networks.Under the condition of dynamic networks,solving problems such as community overlapping,parameter dependent,shape constraint which ubiquitous in static community detection task seems more diffcult.On one hand,most existing methods or theories for static community detection are not suitable for dynamic networks.On the other hand,some parameter variation may cause unpredictable changes to community structure when network evolves,which seriously affect the real-time performance and accuracy in dynamic community detection task.To solve these problems,we present the concept of community stability as a replacement of traditional structure-based community defination.The stability of community structure depends on the homogeneous attraction of nodes,therefore nodes inside stable community structure are attractive to each other,more than to anybody else outside the community.This defination avoids the structured constraints of traditional community defination,so the structure can have various shapes.In addition,the naturality of community stability free the algorithm from parameter dependent.As nodes lies on the periphery of the communities could be attracted by different stable core,so the community structure will be overlapped.As for dynamic community detection,we translate online detection problem to the calibrating of community stability,so the dynamic community can be obtained by adjusting history records.(3)Researchs on compressing online social networks.From the standpoint of data storage,social network compression can be divided into lossless compression and lossy compression.Lossless compression can avoid compression loss but is unable to meet the actual needs of users as there is a limit to compression ratio.This paper focus on lossy compression as the dimension of the adjacent matrix of the network could eventually be reduced.In summary,we solve three outstanding issues in this field include high computational complexity,weak structure expression and low matching to dynamic networks.We present a two-phase adaptive framework for dynamically compressing online social networks based on structure integration.First,we proved that optimizing compression loss is equivalent to optimizing the local selection of nodes in merging process,based on which the static compression process can be ended in near-linear time complexity.Next,on the premise of stabilizing compression loss,we adjust the previous compression expression by reference to the changes of the topological structure in each snapshot,and avoiding redundantly compressing while achieving high efficiency.(4)Researchs on applications of community detection in online social networks.In the applications of structured analysis,we focus on worm containment in mobile internet.Most of the existing worm containment scheme desighed for homogeneous network,unable to contain worm hybrid propagation.Besides,the structure changes caused by network evolving makes the containment task more difficulty.To solove these problems,we propose a comminuty-based bidirectional feedback system for hybrid worm containment.Our approach maintains a set of community structure which represents the most likely propagation path of worm,and contains worm propagation by distributed worm signature to the guard nodes selected from the periphery of each community.For those nodes connects different communities while geographic proximity,we evaluate the communication credibility between them based on user's communication records,GPS location data and the security histories,and limit communications towards unreliable ones so as to avoid worm spread across communities.We also design an efficient worm signature forwarding strategy that enables most of the nodes being immunized in the network before being infected while avoiding unnecessary redundancy.Extensive real-trace driven simulation results have proved that the method proposed by this paper has feasibility and effectiveness.