Research On Algorithm Of Community Detection In Dynamic Networks

A large number of complex systems existing in nature can be modeled through networks, and community structure is one of the common structural properties in various types of network. Nodes in the network are divided into different groups or communities, showing such a phenomenon:nodes within communities are closely linked while associations between communities are relatively sparse. Mining the community structures of networks plays an important role in understanding the functions and behaviors of the networks. In addition, the traditional analysis approaches of the social network always treat the network as a static graph, which neglects an important feature of the networks, that is, the dynamic evolution of networks. If the evolution features are ignored, the evolution process of community structures would be concealed over time. Based on the changing nature of the networks, it is of great practical significances to discover the communities in dynamic networks.For the evolutionary characteristics of the networks, a community evolution algorithm FEDN is proposed to find the community structures and track the evolutionary patterns of dynamic networks. First of all， a structure similarity based algorithm CDA is presented to mine the community structures of static networks. The process of the algorithm CDA appears as below:first finding out one corresponding node that forms a compact pair with the original node; then combining these two nodes as a new one if the value of the modularity gain of the combination is positive; after that, repeating the steps above till all the qualified nodes are divided into their own communities. The evolving networks are formalized into static snapshots at different time stamps and then CDA is used to obtain the interim communities. Secondly, FEDN calculates the similarities between interim communities and previous time sequence community sets and then gets the evolving mode according to the evolutionary patterns which is established on the basis of the characteristics of community evolutionary events. Ultimately, FEDN gains the stable community sets and multiple evolving traces of the communities. The experimental results on the real and synthetic datasets show that FEDN is practical and effective.