Modular Community Detection in Networks

Summary

This paper proposes an iterative rounding strategy for identifying the partition decisions that is coupled with a fast constrained power method that sequentially achieves tighter spectral relaxations and demonstrates consistent and sometimes dramatic improvements in the modularity of the communities discovered.

Keywords

Rounding, Modularity (biology), Partition (number theory), Computer science, Modular design

References

Modularity-Maximizing Graph Communities via Mathematical ProgrammingXuan Ying — 2009
Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problemsLisa Fleischer, Kamal Jain, David P. Williamson — 2006
Community structure in social and biological networksMichelle Girvan, M. E. J. Newman — 2001
Networks, Crowds, and Markets: Reasoning about a Highly Connected World (Easley, D. and Kleinberg, J.; 2010) [Book Review]Chen Hongsong — 2013
Data clustering: a reviewAnil K. Jain, M. Narasimha Murty, Patrick J. Flynn — 1999
GLANCEAndrew Goodman, Howard Rossman, Amit Bar‐Or — 2009
An Effective Heuristic Algorithm for the Traveling-Salesman ProblemSimon Lin, Brian W. Kernighan — 1973
Modularity-maximizing graph communities via mathematical programmingGunjan Agarwal, David Kempe — 2007
The Stanford GraphBase: a platform for combinatorial algorithmsDonald E. Knuth — 1993
The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associationsDavid Lusseau, Karsten Schneider, Oliver Boisseau — 2003
Empirical comparison of algorithms for network community detectionJure Leskovec, Kevin Lang, Michael W. Mahoney — 2010
Collective dynamics of ‘small-world’ networksDuncan J. Watts, Steven H. Strogatz — 1998
An Information Flow Model for Conflict and Fission in Small GroupsKonstantin Avrachenkov, Aleksei Y. Kondratev, Vladimir V. Mazalov — 1977
The structure of scientific collaboration networks.M. E. J. Newman — 2000
Normalized cuts and image segmentationJianbo Shi, Jitendra Malik — 1997
Modularity and community structure in networks.M. E. J. Newman — 2006
The political blogosphere and the 2004 U.S. election: divided they blogLada A. Adamic, Natalie Glance — 2005
Fast normalized cut with linear constraintsLinli Xu, Wenye Li, Dale Schuurmans — 2009
On Spectral Clustering: Analysis and an algorithmAndrew Y. Ng, Michael I. Jordan, Yair Weiss — 2001
On Modularity - NP-Completeness and BeyondUlrik Brandes, Daniel Delling, Marco Gaertler — 2006

Cited by

Finding Community Structures In Social Activity DataChengbin Peng — 2015
Visualizing network communities with a semi-definite programming methodWenye Li — 2015
A Constrained Power Method for Community Detection in Complex NetworksWenye Li — 2014
A parallel Probabilistic Latent Semantic Analysis method on MapReduce platformZhao Liang, Wenye Li, Yuxi Li — 2013
Automated text categorization by generalized kernel machinesJiaqi Tan, Wenye Li, Haoming Li — 2014
Highlighting data clusters by graph embeddingWenye Li — 2015
Automated network analysis by projected power methodZi Wang, Wenye Li, Yan Sun — 2012
Modularity-based community detection in large networks: An empirical evaluationHaoming Li, Wenye Li, Jiaqi Tan — 2014
Modularity maximization in networks by variable neighborhood searchDaniel Aloise, Gilles Caporossi, Pierre Hansen — 2011
A scalable community detection algorithm for large graphs using stochastic block modelsChengbin Peng, Zhihua Zhang, Ka‐Chun Wong — 2015
A New Relaxation Approach to Normalized Hypergraph CutCong Xie, Wu-Jun Li, Zhihua Zhang — 2015
An Empirical Study of Spectral Social Network Partition on GPGPU PlatformsHongguan Chen, Wenye Li — 2015
An Analysis for the Detection of Network Communities in Dynamic EnvironmentsK. SendilKumar, K. Suganthi, C. Suchitra — 2013
Scalable inference for stochastic block modelsChengbin Peng, Zhihua Zhang, Ka‐Chun Wong — 2017
Network Community Detection with A Successive Spectral Relaxation MethodWenye Li — 2018
A Self Fixing Intelligent Ant Clustering Algorithm For GraphsYing Ying Liu, Parimala Thulasiraman, Ruppa K. Thulasiram — 2018
Three Essays on Network Dynamics and LiminalityD. F. Leal — 2018
A possibilistic framework for the detection of terrorism‐related Twitter communities in social mediaMohamed Moussaoui, Montaceur Zaghdoud, Jalel Akaichi — 2018
Forecasting, forewarning weather and disasters in the social web: A network studySelvaraj Mahalakshmi, K Sunitha — 2018
Co-Association Matrix-Based Multi-Layer Fusion for Community Detection in Attributed NetworksSheng Luo, Zhifei Zhang, Yuanjian Zhang — 2019

Related papers

Modularity and community structure in networks.M. E. J. Newman — 2006
Community structure in social and biological networksMichelle Girvan, M. E. J. Newman — 2001
Fast unfolding of communities in large networksVincent D. Blondel, Jean‐Loup Guillaume, Renaud Lambiotte — 2008
Finding and evaluating community structure in networks.Michelle G. Newman, Michelle Girvan — 2003
Finding community structure in very large networks.Aaron Clauset, M. E. J. Newman, Cristopher Moore — 2004
Revealing network communities with a nonlinear programming methodWenye Li — 2013
Fast normalized cut with linear constraintsLinli Xu, Wenye Li, Dale Schuurmans — 2009
An Effective Heuristic Algorithm for the Traveling-Salesman ProblemSimon Lin, Brian W. Kernighan — 1973
Data clustering: a reviewAnil K. Jain, M. Narasimha Murty, Patrick J. Flynn — 1999
Networks: An IntroductionMark Newman — 2010