Fast determination of structurally cohesive subgroups in large networks.


Journal Article

Structurally cohesive subgroups are a powerful and mathematically rigorous way to characterize network robustness. Their strength lies in the ability to detect strong connections among vertices that not only have no neighbors in common, but that may be distantly separated in the graph. Unfortunately, identifying cohesive subgroups is a computationally intensive problem, which has limited empirical assessments of cohesion to relatively small graphs of at most a few thousand vertices. We describe here an approach that exploits the properties of cliques, k-cores and vertex separators to iteratively reduce the complexity of the graph to the point where standard algorithms can be used to complete the analysis. As a proof of principle, we apply our method to the cohesion analysis of a 29,462-vertex biconnected component extracted from a 128,151-vertex co-authorship data set.

Full Text

Duke Authors

Cited Authors

  • Sinkovits, RS; Moody, J; Oztan, BT; White, DR

Published Date

  • November 2016

Published In

Volume / Issue

  • 17 / Pt 1

Start / End Page

  • 62 - 72

PubMed ID

  • 28503215

Pubmed Central ID

  • 28503215

International Standard Serial Number (ISSN)

  • 1877-7503

Digital Object Identifier (DOI)

  • 10.1016/j.jocs.2016.10.005


  • eng