Uncovering the nucleus of a massive reciprocal network

Braulio Dumba, Zhi Li Zhang

Research output: Contribution to journalArticlepeer-review

Abstract

Google+ is a directed online social network where nodes have either reciprocal (bidirectional) edges or parasocial (one-way) edges. As reciprocal edges play an important role in the structural properties, formation and evolution of online social networks, we study the core structure of the subgraph formed by them, referred to as the reciprocal network of Google+ — in a sense, a reciprocal network can be viewed as the stable “skeleton” network of a directed online social network that holds it together. We develop an effective three-step procedure to hierarchically extract and unfold the core structure of a network by building up and generalizing ideas from the existing k-shell decomposition and clique percolation approaches. Our scheme produces higher-level representations of the core structure of the Google+ reciprocal network and it reveals that there are ten subgraphs (“communities”) comprising of dense clusters of cliques lying at the center of the core structure of the Google+ reciprocal network. Together they form the core to which “peripheral” sparse subgraphs are attached. Furthermore, our analysis shows that the core structure of the Google+ reciprocal network is very stable as the network evolves. Our results have implications in the design of algorithms for information flow, and in development of techniques for analyzing the vulnerability or robustness of online social networks.

Original languageEnglish (US)
Pages (from-to)3021-3046
Number of pages26
JournalWorld Wide Web
Volume22
Issue number6
DOIs
StatePublished - Nov 1 2019

Bibliographical note

Funding Information:
This research was supported in part by DoD ARO MURI Award W911NF-12-1-0385, DTRA grant HDTRA1- 14-1-0040, NSF grant CNS-1411636, CNS-1618339 and CNS-1617729.

Keywords

  • Dependence
  • Google+
  • Hypergraph
  • K-Shell decomposition
  • Network core
  • Reciprocal network

Fingerprint Dive into the research topics of 'Uncovering the nucleus of a massive reciprocal network'. Together they form a unique fingerprint.

Cite this