Divisive heuristic for modularity density maximization

DOI10.1016/J.COR.2016.01.009MaRDI QIDQ342346zbMATH OpenOpenAlexFDO

Authors Sergey Kushnarev, Leo Liberti, Zeyu Sun, Alberto Costa

Publication date 17 November 2016

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.cor.2016.01.009

zbMATH Keywords

clusteringheuristicmodularity density maximizationmultilinear termsreformulation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Reformulation of a model for hierarchical divisive graph modularity maximization
• A locally optimal hierarchical divisive heuristic for bipartite modularity maximization
• A partitioning-based divisive clustering technique for maximizing the modularity
• An enhanced MILP-based branch-and-price approach to modularity density maximization on graphs
• MILP formulations for the modularity density maximization problem

Cites work

• A k-Sample Model in Order Statistics
• A convex envelope formula for multilinear functions
• A cutting plane algorithm for a clustering problem
• A locally optimal hierarchical divisive heuristic for bipartite modularity maximization
• A mixed integer linear model for clustering with variable selection
• Adding cohesion constraints to models for modularity maximization in networks
• Branching and bounds tighteningtechniques for non-convex MINLP
• Community detection by modularity maximization using GRASP with path relinking
• Community structure in social and biological networks
• Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
• Existence and sum decomposition of vertex polyhedral convex envelopes
• Fast unfolding of communities in large networks
• Finding community structures in complex networks using mixed integer optimisation
• MILP formulations for the modularity density maximization problem
• Modularity-maximizing graph communities via mathematical programming
• On the impact of symmetry-breaking constraints on spatial branch-and-bound for circle packing in a square
• Redundant constraints in the standard formulation for the clique partitioning problem
• Reformulation of a model for hierarchical divisive graph modularity maximization
• Reformulations in Mathematical Programming: Definitions and Systematics
• The Structure and Function of Complex Networks

Cited in

(12)

• Exact computational solution of modularity density maximization by effective column generation
• An enhanced MILP-based branch-and-price approach to modularity density maximization on graphs
• Complete mixed integer linear programming formulations for modularity density based clustering
• Efficient modularity density heuristics for large graphs
• Modified modularity density maximization and density ratio heuristic
• A doubly nonnegative relaxation for modularity density maximization
• A locally optimal hierarchical divisive heuristic for bipartite modularity maximization
• MILP formulations for the modularity density maximization problem
• Improving heuristics for network modularity maximization using an exact algorithm
• Reformulation of a model for hierarchical divisive graph modularity maximization
• A partitioning-based divisive clustering technique for maximizing the modularity
• A study on modularity density maximization: column generation acceleration and computational complexity analysis

Describes a project that uses

Uses Software

• CPLEX
• BARON

This page was built for publication: Divisive heuristic for modularity density maximization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q342346)