Modularity-maximizing graph communities via mathematical programming
From MaRDI portal
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.
Recommendations
- Toward optimal community detection: from trees to general weighted networks
- Searching graph communities by modularity maximization via convex optimization
- A cutting plane algorithm for modularity maximization problem
- On Finding Graph Clusterings with Maximum Modularity
- scientific article; zbMATH DE number 6180551
Cites work
- scientific article; zbMATH DE number 1670532 (Why is no real title available?)
- scientific article; zbMATH DE number 437527 (Why is no real title available?)
- scientific article; zbMATH DE number 1168330 (Why is no real title available?)
- scientific article; zbMATH DE number 1839431 (Why is no real title available?)
- Algorithms – ESA 2005
- Significance-Driven Graph Clustering
- The structure and dynamics of networks
Cited in
(62)- Multilevel local search algorithms for modularity clustering
- Modularity based community detection in hypergraphs
- Community structure detection for directed networks through modularity optimisation
- Anti-modularity and anti-community detecting in complex networks
- Community detection in networks via a spectral heuristic based on the clustering coefficient
- Modularity density of network community divisions
- scientific article; zbMATH DE number 6180551 (Why is no real title available?)
- Redundant constraints in the standard formulation for the clique partitioning problem
- Using graph partitioning for efficient network modularity optimization
- Improving heuristics for network modularity maximization using an exact algorithm
- Mixed-integer linear programming formulations and column generation algorithms for the minimum normalized cuts problem on networks
- A near-optimal adaptive algorithm for maximizing modularity in dynamic scale-free networks
- On Finding Graph Clusterings with Maximum Modularity
- A DC Programming Approach for Finding Communities in Networks
- Maximizing Barber's bipartite modularity is also hard
- A doubly nonnegative relaxation for modularity density maximization
- Modularity maximization using completely positive programming
- A cutting plane algorithm for modularity maximization problem
- A novel mixed integer linear programming model for clustering relational networks
- Optimal containment of misinformation in social media: a scenario-based approach
- A Lagrangian relaxation algorithm for modularity maximization problem
- A modularity-maximization-based approach for detecting multi-communities in social networks
- A combinatorial model and algorithm for globally searching community structure in complex networks
- Enhancing community detection by using local structural information
- Simplified energy landscape for modularity using total variation
- Subnetwork constraints for tighter upper bounds and exact solution of the clique partitioning problem
- A dimensionality reduction framework for detection of multiscale structure in heterogeneous networks
- Efficient modularity density heuristics for large graphs
- The maximum balanced subgraph of a signed graph: applications and solution approaches
- Identifying multi-scale communities in networks by asymptotic surprise
- Partition network into communities based on group action on sets
- A note on graphs whose largest eigenvalues of the modularity matrix equals zero
- Revealing network communities with a nonlinear programming method
- Exhaustive community enumeration in parallel
- Exact computational solution of modularity density maximization by effective column generation
- Optimizing edge sets in networks to produce ground truth communities based on modularity
- Modified modularity density maximization and density ratio heuristic
- Additive approximation algorithms for modularity maximization
- Maximum modular graphs
- Additive approximation algorithms for modularity maximization
- Adding cohesion constraints to models for modularity maximization in networks
- Community detection by modularity maximization using GRASP with path relinking
- Community detection based on significance optimization in complex networks
- Clustering of high throughput gene expression data
- Divisive heuristic for modularity density maximization
- Reformulation of a model for hierarchical divisive graph modularity maximization
- A hybrid artificial immune network for detecting communities in complex networks
- Social network optimization for cluster ensemble selection
- Fractional interaction of financial agents in a stock market network
- Community structures of networks
- On the relationship between Gaussian stochastic blockmodels and label propagation algorithms
- A classification for community discovery methods in complex networks
- Post-processing partitions to identify domains of modularity optimization
- Searching graph communities by modularity maximization via convex optimization
- Comparing different modularization criteria using relational metric
- A study on modularity density maximization: column generation acceleration and computational complexity analysis
- Metric-Constrained Optimization for Graph Clustering Algorithms
- A vector partitioning approach to detecting community structure in complex networks
- Using Mathematical Programming to Refine Heuristic Solutions for Network Clustering
- Toward optimal community detection: from trees to general weighted networks
- The maximum community partition problem in networks
- A constrained power method for community detection in complex networks
This page was built for publication: Modularity-maximizing graph communities via mathematical programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q977873)
