Recursive filtration method for detecting community structure in networks |
| |
Authors: | Yi Shen Wenjiang Pei Kai Wang Tao Li Shaoping Wang |
| |
Institution: | Information Science and Technology College, Southeast University, Nanjing 210096, People’s Republic of China |
| |
Abstract: | Community detection is a topic of considerable recent interest within complex networks, but most methods proposed so far are divisive and agglomerative methods which delete only one edge each time to split the network, or agglomerating only one node each time until no individual node remains. Unlike those, we propose a method to split networks in parallel by deleting many edges in each filtration operation, and propose a community recursive coefficient (CRC) denoted by M instead of Q (modularity) to quantify the effect of the splitting results in this paper. We proved that recursive optimizing of the local M is equivalent to acquiring the maximal global Q value corresponding to good divisions. For a network with m edges, c communities and arbitrary topology, the method split the network at most c+1 times and detected the community structure in time O(m2+(c+1)m). We give several example applications, and show that the method can detect local communities according to the densities of external links to them in increasing order especially in large networks. |
| |
Keywords: | Complex networks Filtration operation Recursive coefficient Community structure |
本文献已被 ScienceDirect 等数据库收录! |
|