Research On Community Detection And Dynamic Evolution In Social Networks

Recently, the study on community structure has attracted more attentions than other properties like small-world, scale-free, power-law in social networks. Detecting community structure plays an important role in researching the social networks. The growing and dynamic properties in social networks present a significant challenge to classical community detection algorithms. Therefore, this paper focuses on detecting community structure in large-scale social networks and researches the dynamic evolution.The community detection in this paper is converted into optimization process. A layered optimization framework is designed to improve the optimization process, reduce network scale and increase the quality of solution. The framework consists of three layers:finding clusters (core areas) in networks, repairing isolated nodes and optimizing in a new constructed weighted network which is compressed from the original one. Furthermore, a combined algorithm of community detection named DBPSO including similarity-based clustering, isolated nodes repair strategies and a modified particle swarm optimization (PSO) is proposed according to the layered optimization framework. Meanwhile, the equivalency of modularity optimization in the new compressed weighted network and the original one with fixed combination of nodes in the same cluster (core area) is proved. In addition, suitable mutation strategies for particle swarm optimization are introduced to guarantee the convergence and global search ability. Finally, the experiments are conducted to evaluate the performance of DBPSO by using the synthetic networks and many real-world networks with different size. The experimental results show that DBPSO can effectively extract the intrinsic community structure of social networks and is suitable for large-scale networks.Community detection and evolutionary analysis of dynamic networks can be helpful for understanding the whole network’s characteristics and development trend. For analyzing in dynamic networks, this paper proposes an Incremental Label Propagation algorithm (ILPA) which adjusts label propagation with analyzing increment related vertexes. The algorithm takes the advantage of slowly change in communities of the adjacent timestamps. Static community detection algorithm is only used to the first timestamp of the network, the research on current timestamp analyzes the increment related vertexes based on the community structure in previous timestamp. The Incremental Label Propagation algorithm has the high efficiency of classical incremental analysis method in dynamic social networks, and do not need the apriori knowledge of community numbers. It is adaptive to different network structure, and has a good behavior in the emergent of networks. The experimental results in synthetic and real-world network show that ILPA can effectively extract the intrinsic community structure in dynamic social networks and it is more stable and effective.