Fast graph clustering with a new description model for community detection

详细信息    查看全文

• 作者：Liang Bai ; ^a ; ^b ; ^c ; ^{sxbailiang@hotmail.com} ; Xueqi Cheng^b ; ^{cxq@ict.ac.cn} ; Jiye Liang^a ; ^{ljy@sxu.edu.cn} ; Yike Guo^c ; ^{y.guo@imperial.ac.uk}
• 关键词：Graph clustering ; Community detection ; Community description model ; Evaluation criterion ; Iterative algorithm
• 刊名：Information Sciences
• 出版年：2017
• 出版时间：May 2017
• 年：2017
• 卷：388-389
• 期：Complete
• 页码：37-47
• 全文大小：583 K
• 卷排序：388

文摘

Efficiently describing and discovering communities in a network is an important research concept for graph clustering. In the paper, we present a community description model that evaluates the local importance of a node in a community and its importance concentration in all communities to reflect its representability to the community. Based on the description model, we propose a new evaluation criterion and an iterative search algorithm for community detection (ISCD). The new algorithm can quickly discover communities in a large-scale network, due to the average linear-time complexity with the number of edges. Furthermore, we provide an initial method of input parameters including the number of communities and the initial partition before algorithm implementation, which can enhance the local-search quality of the iterative algorithm. The proposed algorithm with the initial method is called ISCD+. Finally, we compare the effectiveness and efficiency of the ISCD+ algorithm with six representative algorithms on several real network data sets. The experimental results illustrate that the proposed algorithm is suitable to address large-scale networks.