Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
New Insight into 2-Community Structures in Graphs with Applications in Social Networks
verfasst von : Cristina Bazgan, Janka Chlebíková, Thomas Pontoizeau
Erschienen in: Combinatorial Optimization and Applications
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
We investigate the structural and algorithmic properties of 2-community structure in graphs introduced by Olsen [13]. A 2-community structure is a partition of vertex set into two parts such that for each vertex of the graph number of neighbours in/outside own part is in correlation with sizes of parts. We show that every 3-regular graph has a 2-community structure which can be found in polynomial time, even if the subgraphs induced by each partition must be connected. We introduce a concept of a 2-weak community and prove that it is NP-complete to find a balanced 2-weak community structure in general graphs even with additional request of connectivity for both parts. On the other hand, the problem can be solved in polynomial time in graphs of degree at most 3.