A Framework for Fast Community Extraction of Large-Scale Networks
Most of the faster community extraction algorithms are based on the Clauset, Newman and Moore (CNM), which is em-ployed for networks with sizes up to 500,000 nodes. The modi cation proposed by Danon, Diaz and Arenas (DDA) obtains better modularity among CNM and its variations, but there is no improvement in speed as its authors ex-pressed. In this paper, we identify some ineciencies in the data structure employed by former algorithms. We pro-pose a new framework for the algorithm and a modi cation of the DDA to make it applicable to large-scale networks. For instance, the community extraction of a network with 1 million nodes and 5 million edges was performed in about 14 minutes in contrast to former CNM that required 45 hours (192 times the former CNM, obtaining better modularity). The scalability of our improvements is shown by applying it to networks with sizes up to 10 million nodes, obtaining the best modularity and execution time compared to the former algorithms.
Community analysis Clustering Large-scale networks
Yutaka I. Leon-Suematsu Kikuo Yuta
NiCT/ATR 2-2-2 Hikaridai, Seika-cho, Souraku-gun Kyoto 619-0288, Japan
国际会议
第十七届国际万维网大会(the 17th International World Wide Web Conference)(WWW08)
北京
英文
2008-04-21（万方平台首次上网日期，不代表论文的发表时间）