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