Research On Adaptive Community Detection Algorithm In Dynamic Networks

Networks exist in our real world. Like everything else, they have a universal law of their own, such as small world network, power-law distribution, community structure and so on. The networks can be described by a graph, the individual in networks is abstracted a node, the relationship between individuals is abstracted an edge. Community structure often represents division series of nodes, those nodes with denser connections are divided into a group (or community), and those nodes which come from different communities contact less each other. Mining community structure of the network can help people master the internal structure of the network, and make the networks better serve us. Therefore, community structure detection in network has important practical significance, and is a hot domain of study.The networks in real life often change over time because of those events that are due to the random entry of the new nodes and edges. The dynamic changes of networks also lead to dynamic change of community structure. Therefore, community detecting in a dynamic network face more difficulties than in a static networks. At present, there are two kinds of methods to detect community structure:one is that we sample the network at different times,obtain a series of snapshots,and take the snapshots ordered as a dynamic network, and then use the traditional algorithms of community detection in static networks to detect every snapshots. The other is based on the increment of the networks from time t-1 to t, depend on the community structure at time t-1, only adjusting nodes which may remove to another community. The former is time-consuming because of dealing with all nodes, and doesn't meet the need of community structure detection in large-scale networks. On the contrary, if we use the latter method, we only need to deal with those nodes that may remove to another community because of changes, which can avoid the hassle of recomputing from scratch. we propose an adaptive community detection algorithm(ACD) which belongs to the latter.This paper holds the fact changes of network are caused by the four basic events: entry of new nodes, remove of old nodes, entry of new edges, and remove of old edges. We amply analyze all kinds of results which is generated by those event, and propose the corresponding algorithm for adjusting community structure when an event occurs. Because, changes of network from t-1 to time t can decompose a series of time-ordered basic events, we can find the community structure by respectively processing these basic events. To adjust community structure when a basic event happens, we use the Community Gravity to determine the community ownership of a node,and use the Kernel Node Set to identify the importance of edges or nodes which will be removed. If the nodes or edges have much importance, we believe that the community will be split, so our algorithm does not require the same number of communities at adjacent moment.In this paper, we use real networks and LFR benchmark network to test ACD algorithm. Experimental results show that the proposed algorithm can quickly and accurately find the current community structure on the basis of previous community structure and obtain better time efficiency.