Fast determination of structurally cohesive subgroups in large networks.
J Comput Sci
; 17(Pt 1): 62-72, 2016 Nov.
Article
in En
| MEDLINE
| ID: mdl-28503215
ABSTRACT
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:
1
Collection:
01-internacional
Database:
MEDLINE
Language:
En
Journal:
J Comput Sci
Year:
2016
Document type:
Article
Affiliation country:
United States