首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号