Min-max communities in graphs: complexity and computational properties

DOI10.1016/J.TCS.2015.11.034MaRDI QIDQ899313zbMATH OpenOpenAlexFDO

Authors Miriam Di Ianni, Giorgio Gambosi, Gianluca Rossi, Paola Vocca

Publication date 28 December 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.11.034

zbMATH Keywords

graph partitioningcommunity discovery

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• A general view on computing communities
• The maximum community partition problem in networks
• Toward optimal community detection: from trees to general weighted networks
• Community detection by modularity maximization using GRASP with path relinking
• Community detection with the weighted parsimony criterion

Cites work

• scientific article; zbMATH DE number 1933255 (Why is no real title available?)
• scientific article; zbMATH DE number 944226 (Why is no real title available?)
• scientific article; zbMATH DE number 2104729 (Why is no real title available?)
• Algorithmic approach to the satisfactory graph partitioning problem
• Algorithms and Computation
• Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
• Assessing the quality of multilevel graph clustering
• Community structure in social and biological networks
• Complex networks: structure and dynamics
• Detecting the Structure of Social Networks Using (α,β)-Communities
• Distributed Community Detection in Dynamic Graphs
• Graph Clustering and Minimum Cut Trees
• Graph clustering
• Network analysis. Methodological foundations.
• Networks, crowds and markets. Reasoning about a highly connected world.
• The satisfactory partition problem

Cited in

(8)

• A note on the satisfactory partition problem: constant size requirement
• A robust multi-view clustering method for community detection combining link and content information
• Complete graph model for community detection
• Detecting communities is hard (and counting them is even harder)
• New insight into 2-community structures in graphs with applications in social networks
• The maximum community partition problem in networks
• Finding \(k\)-community structures in special graph classes
• A general view on computing communities

This page was built for publication: Min-max communities in graphs: complexity and computational properties

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