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