Community detection based on minimum-cut graph partitioning

Yashen Wang*, Heyan Huang, Chong Feng, Zhirun Liu

*此作品的通讯作者

科研成果: 书/报告/会议事项章节会议稿件同行评审

4 引用 (Scopus)

摘要

One of the most useful measurements of community detection quality is the modularity, which evaluates how a given division deviates from an expected random graph. This article demonstrates that (i) modularity maximization can be transformed into versions of the standard minimum-cut graph partitioning, and (ii) normalized version of modularity maximization is identical to normalized cut graph partitioning. Meanwhile, we innovatively combine the modularity theory with popular statistical inference method in two aspects: (i) transforming such statistical model into null model in modularity maximization; (ii) adapting the objective function of statistical inference method for our optimization. Based on the demonstrations above, this paper proposes an efficient algorithm for community detection by adapting the Laplacian spectral partitioning algorithm. The experiments, in both real-world and synthetic networks, show that both the quality and the running time of the proposed algorithm rival the previous best algorithms.

源语言英语
主期刊名Web-Age Information Management - 16th International Conference, WAIM 2015, Proceedings
编辑Yizhou Sun, Jian Li
出版商Springer Verlag
57-69
页数13
ISBN(电子版)9783319210414
DOI
出版状态已出版 - 2015
活动16th International Conference on Web-Age Information Management, WAIM 2015 - Qingdao, 中国
期限: 8 6月 201510 6月 2015

出版系列

姓名Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
9098
ISSN(印刷版)0302-9743
ISSN(电子版)1611-3349

会议

会议16th International Conference on Web-Age Information Management, WAIM 2015
国家/地区中国
Qingdao
时期8/06/1510/06/15

指纹

探究 'Community detection based on minimum-cut graph partitioning' 的科研主题。它们共同构成独一无二的指纹。

引用此