Searching Graph Communities by Modularity Maximization via Convex Optimization

被引：1

作者：

Zhu, Yuqing ^{[1
]}

Sun, Chengyu ^{[1
]}

Li, Deying ^{[2
]}

Chen, Cong ^{[3
]}

Xu, Yinfeng ^{[3
]}

机构：

[1] Calif State Univ Los Angeles, Dept Comp Sci, Los Angeles, CA 90032 USA

[2] Renmin Univ China, Sch Informat, Beijing 100872, Peoples R China

[3] Xi An Jiao Tong Univ, Sch Management, Xian 710049, Shaanxi, Peoples R China

来源：

COMBINATORIAL OPTIMIZATION AND APPLICATIONS, (COCOA 2015) | 2015年 / 9486卷

关键词：

D O I：

10.1007/978-3-319-26626-8_51

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

Communities in networks are the densely knit groups of individuals. Newman suggested modularity - a natural measure of the quality of community partition, and several community detection strategies aiming on maximizing the modularity have been proposed. In this paper, we give a new combinatorial model for modularity maximization problem, and introduce a convex optimization based rounding algorithm. Importantly, even given the maximum number of wanted communities, our solution is still capable of maximizing the modularity and obtaining the upper bound on the best possible solution.

引用

页码：701 / 708

页数：8

共 50 条

[21] Using graph partitioning for efficient network modularity optimization [J].

Djidjev, Hristo ;

Onus, Melih .

GRAPH PARTITIONING AND GRAPH CLUSTERING, 2013, 588 :103-+

[22] Modularity Optimization as a Training Criterion for Graph Neural Networks [J].

Murata, Tsuyoshi ;

Afzal, Naveed .

COMPLEX NETWORKS IX, 2018, :123-135

[23] Scaling and Quality of Modularity Optimization Methods for Graph Clustering [J].

Ghosh, Sayan ;

Halappanavar, Mahantesh ;

Tumeo, Antonino ;

Kalyanaraman, Ananth .

2019 IEEE HIGH PERFORMANCE EXTREME COMPUTING CONFERENCE (HPEC), 2019,

[24] Graph Bayesian Optimization for Multiplex Influence Maximization [J].

Yuan, Zirui ;

Shao, Minglai ;

Chen, Zhiqian .

THIRTY-EIGHTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOL 38 NO 20, 2024, :22475-22483

[25] Graph Analysis and Modularity of Brain Functional Connectivity Networks: Searching for the Optimal Threshold [J].

Bordier, Cecile ;

Nicolini, Carlo ;

Bifone, Angelo .

FRONTIERS IN NEUROSCIENCE, 2017, 11

[26] Comparing local modularity optimization for detecting communities in networks [J].

Xiang, Ju ;

Wang, Zhi-Zhong ;

Li, Hui-Jia ;

Zhang, Yan ;

Chen, Shi ;

Liu, Cui-Cui ;

Li, Jian-Ming ;

Guo, Li-Juan .

INTERNATIONAL JOURNAL OF MODERN PHYSICS C, 2017, 28 (06)

[27] Detecting Overlapping Communities in Modularity Optimization by Reweighting Vertices [J].

Tsung, Chen-Kun ;

Ho, Hann-Jang ;

Chen, Chien-Yu ;

Chang, Tien-Wei ;

Lee, Sing-Ling .

ENTROPY, 2020, 22 (08)

[28] Analyzing modularity maximization in approximation, heuristic, and graph neural network algorithms for community detection [J].

Aref, Samin ;

Mostajabdaveh, Mahdi .

JOURNAL OF COMPUTATIONAL SCIENCE, 2024, 78

[29] Improving Graph Matching via Density Maximization [J].

Wang, Chao ;

Wang, Lei ;

Liu, Lingqiao .

2013 IEEE INTERNATIONAL CONFERENCE ON COMPUTER VISION (ICCV), 2013, :3424-3431

[30] A modularity-maximization-based approach for detecting multi-communities in social networks [J].

Chen-Kun Tsung ;

Sing-Ling Lee ;

Hann-Jang Ho ;

ShengKai Chou .

Annals of Operations Research, 2021, 303 :381-411

← 1 2 3 4 5 →