Structural and algorithmic properties of 2-community structures

DOI10.1007/S00453-017-0283-7MaRDI QIDQ1635716zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Cristina Bazgan, Thomas Pontoizeau, Janka Chlebíková

Publication date 1 June 2018

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00453-017-0283-7

zbMATH Keywords

clusteringsocial networkscomplexitygraph partitioningcommunity structure

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Social networks; opinion dynamics (91D30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• New insight into 2-community structures in graphs with applications in social networks
• An improved algorithm for generalized community structure inference in complex networks
• Quantitative function and algorithm for community detection in bipartite networks

Cites work

• scientific article; zbMATH DE number 6843424 (Why is no real title available?)
• scientific article; zbMATH DE number 2104820 (Why is no real title available?)
• A general view on computing communities
• Approximating the Maximally Balanced Connected Partition Problem in graphs
• Approximation of satisfactory bisection problems
• Balanced graph partitioning
• Balanced partitions of trees and applications
• Degree-constrained decompositions of graphs: Bounded treewidth and planarity
• Graph clustering
• Satisfactory graph partition, variants, and generalizations
• The satisfactory partition problem
• Unfriendly partitions of a graph

Cited in

(7)

• Finding a potential community in networks
• New insight into 2-community structures in graphs with applications in social networks
• A general view on computing communities
• Finding \(k\)-community structures in special graph classes
• Proportionally dense subgraph of maximum size: complexity and approximation
• Graphs without a partition into two proportionally dense subgraphs
• On the complexity of finding a potential community

This page was built for publication: Structural and algorithmic properties of 2-community structures

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