Research On Community Detecting And Evolution Analysis In Social Network

The rapid development of information technology makes human so-ciety quickly enter into the network age, a large number of network structures have sprung up in various fields, such as Internet, WWW, power networks, biological networks, social networks, economy networks, etc. These networks can be modeled by Complex Network. The nodes in a complex network represent the element, with connections between them represented as edges. Complex network research focuses on the com-monness of networks from different fields and the solution to solve these problems.Social netowrk is a group of individuals in society, with complex in-teractions with them. Social network mainly includes traditional offline social network and online social network from social media. Community structure usually refers to the compact connected sub-graph, which is the compression representation of networks. Community analysis and re-search have attract much reserachers from sociology, computer and phys-ics fields. Meanwhile, community structure as the medium characteristics of networks becomes the basis of other research. The thesis mainly fo-cuses on community detection and network evolution model in social network.The emergence of social media has brought new characteristics, which challenges the community discovery algorithms, to social networks with traditional social networks. Online social networks have large-scale, complex connection, rich content and time varying characteristics. In so-cial media, users build social relationship according to interesting, friends and the recommendation of friends, which reduces the cost of making friends and facilitates the transimission of information between users. Therefore, the social networks are becoming larger and larger. The rela-tionships between users are not simple friendship but it includes many types of relationship, such as following relationship, fans relationship, and friendship, etc. So, the relationships of networks become more com-plex. In social media, users generate rich contents with the relationship between them, such as posts, shared photos and comments. The connec-tions of social network is not only complex, but also constantly evolves over time. In social media, there are users and connections create and de-lete everyday. From the point of microcosmic, nodes exhibit complex time evolution behavior. On the contrary, the macroscopic network struc-ture change smoothly. These two aspect of changes will have an effect on community structure.Above all, communtiy structure detection and community evolution model analysis from increasingly complex social networks become the research hotspot. This thesis focuses on the overlapping community de-tection and evolution model analysis from two aspects of theory and en-gineering, the research problems mainly include:in the theory aspect, de-sign efficient and accurate overlapping community detection algorithms, analyze the practical significance of the overlapping structure between community; make full use of the rich information content in network to discover community structure, discuss the role of information content during the community formation; community evolution is closely related with the dyanmic change of network, which reflects the highly dynamic nature of nodes and embodies the stability of network from the mac-ro angle. By analyzing the characteristics and rules of community evolu-tion in social network, we can predict the trend of social network evolu-tion. In engineering aspect, huge amounts of social network da-ta challenges to the performance of the network analysis algorithms. Ac-cording to the iterative of social network analysis algorithms, a complex network analysis systerm was developed which can deal with large scale networks.This paper has the following contributions: 1. This paper proposes a topic model based overlapping community detection algorithm-LBLP (Latent Dirichlet Allocation-Based Link Parti-tion). LBLP proposes an adjustable-parameter partitioning strategy, which addresses the issue of divding the edge between community into commu-nity. It promotes the accuracy of community detecting. LBLP has been evaluated by large scale of artificial networks and real networks. There experiments validate the accuracy and reliability of LBLP.2. In consideration of real social networks including many types of information, this paper proposes a feature integration based overlapping community detection algorithm-LBLP-FI (LBLP Feature Integration). LBLP-FI takes both the topology and content information of networks into consideration. It fuses the topology and text content of edges as the features of edges to mine the structure of overlapping community. Be-sides, it proposes two fusion strategies:LBLP-FI-V and LBLP-FI-W. By analyzing the content information of community, it can explore the se-mantic information of community structure, then it discover the formation mechanism of community structure. In order to deal with the large-scale data of networks, it extends the algorithm to MapReduce developing model, which enable the parallelization of algorithm. The results of eval-uative experiments indicate that the proposed algorithm can detect the overlapping community structure of network effectively, and balance the issues of accuracy and operating efficiency.3. It proposes an evolutionary clustering based community evolution analysis method, which considers the fact that the community structure is influenced by both current networks and historical networks in real dy-namic networks. It builts the node-node matrix according the static net-work at each moment, and then takes the time dimension into account to build the node-node-time tensor. By the analyzing of similar tensor, it ensures the continuity of community networks during the evoluation of networks, and then discovers the potential principle of networks evolu-ation. It proposes two evaluation indicators based on tensor decomposi-tion, namely, Community Condensation and Community Activity. They are employed to analyze the evoluation information of community struc-ture over time. By the comparative experiment of artificial testing net- works and real networks, it validates the accuracy and reliability of algo-rithm.4. We has developed a cloud based data analyzing system S-PDM (Saas Parallel Data Mining System), which implements rich social net-work analysis algorithms parallely. This system make full use of distrib-uted computing power and storage space and provide users with data mining analysis in the way of workflow service. S-PDM provides an im-proved chain workflow mode which can integrate cloud transaction dy-namicly. This chain workflow mode improve the performance of S-PDM.In a word, the thesis discusses the models, algorithms and practice of overlapping community detection and community evolution in social networks from two aspects of the theory and engineering,repectively.