Modularity-Maximizing Network Communities via Mathematical Programming

Abstract

In many networks, it is of great interest to identify "communities", unusually densely knit groups of individuals. Such communities often shed light on the function of the networks or underlying properties of the individuals. Recently, Newman suggested "modularity" as a natural measure of the quality of a network partitioning into communities. Since then, various algorithms have been proposed for (approximately) maximizing the modularity of the partitioning determined. In this paper, we introduce the technique of rounding mathematical programs to the problem of modularity maximization, presenting two novel algorithms. More specifically, the algorithms round solutions to linear and vector programs. Importantly, the linear programing algorithm comes with an a posteriori approximation guarantee: by comparing the solution quality to the fractional solution of the linear program, a bound on the available "room for improvement" can be obtained. The vector programming algorithm provides a similar bound for the best partition into two communities. We evaluate both algorithms using experiments on several standard test cases for network partitioning algorithms, and find that they perform comparably or better than past algorithms.

Submitted to EPJB. 9 pages, 3 EPS figures

References in corpus (19)

• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• Finding community structure in very large networks
• Fast algorithm for detecting community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• The large-scale organization of metabolic networks
• Functional cartography of complex metabolic networks
• Resolution limit in community detection
• Comparing community structure identification
• Who is the best connected scientist? A study of scientific coauthorship networks
• Community detection in complex networks using Extremal Optimization
• Self-similar community structure in organisations
• Community Structure in Jazz
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Finding local community structure in networks
• Extracting the hierarchical organization of complex systems
• Finding instabilities in the community structure of complex networks

Cited by in corpus (46)

• Community detection in graphs
• The performance of modularity maximization in practical contexts
• Line Graphs, Link Partitions and Overlapping Communities
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Community Detection via Maximization of Modularity and Its Variants
• A Classification for Community Discovery Methods in Complex Networks
• Advanced modularity-specialized label propagation algorithm for detecting communities in networks
• Robust network community detection using balanced propagation
• Clique Graphs and Overlapping Communities
• Estimating the number of communities in a network
• Improved community structure detection using a modified fine tuning strategy
• Z-score-based modularity for community detection in networks
• Data-driven Computational Social Science: A Survey
• Ubiquitousness of link-density and link-pattern communities in real-world networks
• On the Complexity of Newman's Community Finding Approach for Biological and Social Networks
• Network Clustering via Maximizing Modularity: Approximation Algorithms and Theoretical Limits
• Multi-resolution community detection based on generalized self-loop rescaling strategy
• Detecting Overlapping Temporal Community Structure in Time-Evolving Networks
• Walk modularity and community structure in networks
• Enhancing community detection by local structural information
• Identifying multi-scale communities in networks by asymptotic surprise
• Maximizing Barber's bipartite modularity is also hard
• Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar
• Community detection based on significance optimization in complex networks
• A Study on Modularity Density Maximization: Column Generation Acceleration and Computational Complexity Analysis
• Mathematical and Algorithmic Analysis of Network and Biological Data
• On the relationship between Gaussian stochastic blockmodels and label propagation algorithms
• Multi-level algorithms for modularity clustering
• Secure Friend Discovery via Privacy-Preserving and Decentralized Community Detection
• Additive Approximation Algorithms for Modularity Maximization
• Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
• Discovering Nested Communities
• The Asymptotic Distribution of Modularity in Weighted Signed Networks
• Extending modularity by capturing the similarity attraction feature in the null model
• Subnetwork Constraints for Tighter Upper Bounds and Exact Solution of the Clique Partitioning Problem
• Identifying robust features of community structure in complex networks
• A Spectral Representation of Power Systems with Applications to Adaptive Grid Partitioning and Cascading Failure Localization
• Finding Community Structure with Performance Guarantees in Complex Networks
• Localized Algorithm of Community Detection on Large-Scale Decentralized Social Networks
• Multi-Scale Link Prediction
• A Projection Method for Metric-Constrained Optimization
• Large Scale Training of Graph Neural Networks for Optimal Markov-Chain Partitioning Using the Kemeny Constant
• Optimizing Edge Sets in Networks to Produce Ground Truth Communities Based on Modularity
• Environmental versatility promotes modularity in genome-scale metabolic networks
• Botnet Detection using Social Graph Analysis
• Generic criticality of community structure in random graphs