A doubly nonnegative relaxation for modularity density maximization

DOI10.1016/J.DAM.2018.09.023MaRDI QIDQ2297659zbMATH OpenOpenAlexWikidataFDO

Authors Yoichi Izunaga, Tomomi Matsui, Yoshitsugu Yamamoto

Publication date 20 February 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://tsukuba.repo.nii.ac.jp/?action=repository_uri&item_id=37087

zbMATH Keywords

community detectiondoubly nonnegative relaxationmodularity density0-1 semidefinite programming

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Deterministic network models in operations research (90B10) Dynamic programming (90C39) Semidefinite programming (90C22)

Recommendations

• A Lagrangian relaxation algorithm for modularity maximization problem
• Community detection in networks via nonlinear modularity eigenvectors
• A sparse completely positive relaxation of the modularity maximization for community detection
• Finding network communities using modularity density
• Modularity-maximizing graph communities via mathematical programming

Cites work

• scientific article; zbMATH DE number 3681933 (Why is no real title available?)
• scientific article; zbMATH DE number 2222601 (Why is no real title available?)
• A branch-and-bound algorithm for maximizing the sum of several linear ratios
• An enhanced MILP-based branch-and-price approach to modularity density maximization on graphs
• Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
• Depth-First Search and Linear Graph Algorithms
• Divisive heuristic for modularity density maximization
• Global optimization algorithm for the nonlinear sum of ratios problem
• MILP formulations for the modularity density maximization problem
• On Nonlinear Fractional Programming
• SCIP: solving constraint integer programs

Cited in

(5)

• A Lagrangian relaxation algorithm for modularity maximization problem
• A sparse completely positive relaxation of the modularity maximization for community detection
• Community detection in networks via nonlinear modularity eigenvectors
• Modified modularity density maximization and density ratio heuristic
• A study on modularity density maximization: column generation acceleration and computational complexity analysis

Describes a project that uses

Uses Software

• Pajek datasets
• Pajek
• SCIP

This page was built for publication: A doubly nonnegative relaxation for modularity density maximization

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