Unfolding the core structure of the reciprocal graph of a massive online social network

Braulio Dumba; Zhi Li Zhang

doi:10.1007/978-3-319-48749-6_58

Unfolding the core structure of the reciprocal graph of a massive online social network

Braulio Dumba, Zhi Li Zhang

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Scopus citations

Abstract

Google+ (G+ in short) is a directed online social network where nodes have either reciprocal (bidirectional) edges or parasocial (one-way) edges. As reciprocal edges represent strong social ties, we study the core structure of the subgraph formed by them, referred to as the reciprocal network of G+. We develop an effective three-step procedure to hierarchically extract and unfold the core structure of this reciprocal network. This procedure builds up and generalizes ideas from the existing k-shell decomposition and clique percolation approaches, and produces higher-level representations of the core structure of the G+ reciprocal network. Our analysis shows that there are seven subgraphs (“communities”) comprising of dense clusters of cliques lying at the center of the core structure of the G+ reciprocal network, through which other communities of cliques are richly connected. Together they form the core to which “peripheral” sparse subgraphs are attached.

Original language	English (US)
Title of host publication	Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Proceedings
Editors	Minming Li, Lusheng Wang, T-H. Hubert Chan
Publisher	Springer Verlag
Pages	763-771
Number of pages	9
ISBN (Print)	9783319487489
DOIs	https://doi.org/10.1007/978-3-319-48749-6_58
State	Published - 2016
Event	10th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2016 - Hong Kong, China Duration: Dec 16 2016 → Dec 18 2016

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10043 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	10th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2016
Country/Territory	China
City	Hong Kong
Period	12/16/16 → 12/18/16

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 and NSF grant CNS-1411636. We thank the authors of [] for the datasets.

Publisher Copyright:
© Springer International Publishing AG 2016.

Keywords

Google+
Network core
Reciprocal network
Reciprocity

Publisher link

10.1007/978-3-319-48749-6_58

Find It

Find It at U of M Libraries

Cite this

Dumba, B., & Zhang, Z. L. (2016). Unfolding the core structure of the reciprocal graph of a massive online social network. In M. Li, L. Wang, & T.-H. H. Chan (Eds.), Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Proceedings (pp. 763-771). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10043 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-48749-6_58

Unfolding the core structure of the reciprocal graph of a massive online social network. / Dumba, Braulio; Zhang, Zhi Li.
Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Proceedings. ed. / Minming Li; Lusheng Wang; T-H. Hubert Chan. Springer Verlag, 2016. p. 763-771 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10043 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Dumba, B & Zhang, ZL 2016, Unfolding the core structure of the reciprocal graph of a massive online social network. in M Li, L Wang & T-HH Chan (eds), Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10043 LNCS, Springer Verlag, pp. 763-771, 10th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2016, Hong Kong, China, 12/16/16. https://doi.org/10.1007/978-3-319-48749-6_58

Dumba B, Zhang ZL. Unfolding the core structure of the reciprocal graph of a massive online social network. In Li M, Wang L, Chan THH, editors, Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Proceedings. Springer Verlag. 2016. p. 763-771. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-48749-6_58

Dumba, Braulio ; Zhang, Zhi Li. / Unfolding the core structure of the reciprocal graph of a massive online social network. Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Proceedings. editor / Minming Li ; Lusheng Wang ; T-H. Hubert Chan. Springer Verlag, 2016. pp. 763-771 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b5c347532201478497b88e492edfdc2b,

title = "Unfolding the core structure of the reciprocal graph of a massive online social network",

abstract = "Google+ (G+ in short) is a directed online social network where nodes have either reciprocal (bidirectional) edges or parasocial (one-way) edges. As reciprocal edges represent strong social ties, we study the core structure of the subgraph formed by them, referred to as the reciprocal network of G+. We develop an effective three-step procedure to hierarchically extract and unfold the core structure of this reciprocal network. This procedure builds up and generalizes ideas from the existing k-shell decomposition and clique percolation approaches, and produces higher-level representations of the core structure of the G+ reciprocal network. Our analysis shows that there are seven subgraphs (“communities”) comprising of dense clusters of cliques lying at the center of the core structure of the G+ reciprocal network, through which other communities of cliques are richly connected. Together they form the core to which “peripheral” sparse subgraphs are attached.",

keywords = "Google+, Network core, Reciprocal network, Reciprocity",

author = "Braulio Dumba and Zhang, {Zhi Li}",

note = "Funding Information: This research was supported in part by DoD ARO MURI Award W911NF-12-1-0385, DTRA grant HDTRA1- 14-1-0040 and NSF grant CNS-1411636. We thank the authors of [] for the datasets. Publisher Copyright: {\textcopyright} Springer International Publishing AG 2016.; 10th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2016 ; Conference date: 16-12-2016 Through 18-12-2016",

year = "2016",

doi = "10.1007/978-3-319-48749-6_58",

language = "English (US)",

isbn = "9783319487489",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "763--771",

editor = "Minming Li and Lusheng Wang and Chan, {T-H. Hubert}",

booktitle = "Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Proceedings",

}

TY - GEN

T1 - Unfolding the core structure of the reciprocal graph of a massive online social network

AU - Dumba, Braulio

AU - Zhang, Zhi Li

N1 - Funding Information: This research was supported in part by DoD ARO MURI Award W911NF-12-1-0385, DTRA grant HDTRA1- 14-1-0040 and NSF grant CNS-1411636. We thank the authors of [] for the datasets. Publisher Copyright: © Springer International Publishing AG 2016.

PY - 2016

Y1 - 2016

N2 - Google+ (G+ in short) is a directed online social network where nodes have either reciprocal (bidirectional) edges or parasocial (one-way) edges. As reciprocal edges represent strong social ties, we study the core structure of the subgraph formed by them, referred to as the reciprocal network of G+. We develop an effective three-step procedure to hierarchically extract and unfold the core structure of this reciprocal network. This procedure builds up and generalizes ideas from the existing k-shell decomposition and clique percolation approaches, and produces higher-level representations of the core structure of the G+ reciprocal network. Our analysis shows that there are seven subgraphs (“communities”) comprising of dense clusters of cliques lying at the center of the core structure of the G+ reciprocal network, through which other communities of cliques are richly connected. Together they form the core to which “peripheral” sparse subgraphs are attached.

AB - Google+ (G+ in short) is a directed online social network where nodes have either reciprocal (bidirectional) edges or parasocial (one-way) edges. As reciprocal edges represent strong social ties, we study the core structure of the subgraph formed by them, referred to as the reciprocal network of G+. We develop an effective three-step procedure to hierarchically extract and unfold the core structure of this reciprocal network. This procedure builds up and generalizes ideas from the existing k-shell decomposition and clique percolation approaches, and produces higher-level representations of the core structure of the G+ reciprocal network. Our analysis shows that there are seven subgraphs (“communities”) comprising of dense clusters of cliques lying at the center of the core structure of the G+ reciprocal network, through which other communities of cliques are richly connected. Together they form the core to which “peripheral” sparse subgraphs are attached.

KW - Google+

KW - Network core

KW - Reciprocal network

KW - Reciprocity

UR - http://www.scopus.com/inward/record.url?scp=85007241893&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85007241893&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-48749-6_58

DO - 10.1007/978-3-319-48749-6_58

M3 - Conference contribution

AN - SCOPUS:85007241893

SN - 9783319487489

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 763

EP - 771

BT - Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Proceedings

A2 - Li, Minming

A2 - Wang, Lusheng

A2 - Chan, T-H. Hubert

PB - Springer Verlag

T2 - 10th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2016

Y2 - 16 December 2016 through 18 December 2016

ER -

Unfolding the core structure of the reciprocal graph of a massive online social network

Abstract

Publication series

Other

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this