Incremental Dynamic Community Discovery Algorithm Based On Density

In real life,many real systems can be regarded as some kinds of topological ion of complex networks,such as the cooperative networks of scientists,the dynamic molecular networks,the communication networks,and so on.Research shows that the community structure can be thought of as one of the most important characteristics of the complex networks,the connections of the nodes inside a community are close while the connections of the nodes among different communities are sparse.The purpose of community discovery is to explore and analyze the community structure of the networks,so that the behavior and activity of the objects in the networks can be predicted.At present,research on communities has become an important part of the research on complex networks.It not only has a high theoretical value,but also has a broad application prospects.At the present stage,the community discovery algorithm can be divided into two categories:the static community discovery algorithms and dynamic community discovery algorithms.The static community discovery algorithms can be divided into the algorithms based on graph partitioning,the algorithms based on modularity optimization,and so on.There are many excellent algorithms that can identify the community structures effectively.However,they are difficult to adapt to the frequent changes of the nodes and edges in the real network because of ignoring the dynamic time slices of the networks.As a result,the research on the dynamic community discovery algorithms gradually earn people's concerns.The dynamic social networks can be regarded as static community networks composed of a series of continuous time slices.The goal of the common dynamic community discovery is to detect the snapshot of each time slice,and analyze the relationship between the adjacent moments.The design often results in the difference in the community partitions of the adjacent time slices,the inefficiency of running speed,and incapability of handling the large-scale social networks.The dynamic community discovery algorithms based on network increment are able to reduce the time complexity of the algorithms by referring to the information of the previous time,which avoids the clustering of the whole networks.Therefore,the time complexity of the algorithm can be effectively reduced.On the basis of the analysis on the traditional community discovery algorithms,this paper proposes a new algorithm of incremental dynamic community discovery based on density.The main research results are as follows:(1)A community discovery algorithm based on link-density is proposed,which is used to find the initial time of clustering in dynamic community.First,the networks are divided into a number of sub-units to identify and filter out the isolated edges to form the community structures.Then,the nodes in the community are separated to form node communities.If there is a common intersection between two edges,the nodes of the edges are regarded as overlapping nodes.Finally,experiments show that the proposed algorithm can effectively improve the quality of communities and find the overlapping communities.(2)An incremental dynamic community discovery algorithm based on link-density and improved modularity is proposed.First,the initial network is clustered by the link-density algorithm.At the same time,the influence of the neighboring time increment to the neighbor node community attribution change is taken into account to improve the existing community node attribution decision method and avoid he complexity and uncertainty of the artificial parameters setting.Then,the improved modularity is used as a community evaluation index,and the structure of the community is adjusted by considering the changes of the nodes in the local areas and the changes of the current increment.Finally,experiments show that the proposed algorithm can obtain better community discovery results while its time complexity is the same as the incremental approaches.