Compressing Networks with Super Nodes

Probability Seminar

Natalie Stanley (UNC)

Thursday, October 26, 2017 -
4:15pm to 5:15pm
UNC Hanes Hall 125

Abstract: Community detection is a commonly used technique for identifying cohesive groups of nodes in a network, based on similarities in connectivity patterns. To facilitate community detection in large networks, we recast the original network as a smaller network of 'super nodes', where each super node is comprised of one of more nodes of the original network. We can then use this super node representation as the input into standard community detection algorithms. To define the seeds, or centers, of our super nodes, we apply to 'CoreHD' ranking technique, which has been previously shown to be effective in network dismantling and decycling problems. We test our approach through the analysis of two common methods for community detection: modularity maximization with the Louvain algorithm, and maximum likelihood optimization for fitting a stochastic block model. Out results highlight that applying community detection to the compressed network of super nodes is significantly faster, while successfully producing partitions that are more aligned with local network connectivity, more stable across multiple (stochastic) runs within and between community detection algorithms, and overlap well with the results obtained using the full network.

Last updated: 2017/10/23 - 4:21am