SCIENCE CHINA Information Sciences, Volume 59 , Issue 12 : 123101(2016) https://doi.org/10.1007/s11432-015-0790-x

Structural properties and generative model of non-giant connected components in social networks

More info
  • ReceivedMay 31, 2016
  • AcceptedSep 12, 2016
  • PublishedNov 3, 2016


Most previous studies have mainly focused on the analyses of one entire network (graph) or the giant connected components of networks. In this paper, we investigate the disconnected components (non-giant connected component) of some real social networks, and report some interesting discoveries about structural properties of disconnected components. We study three diverse, real networks and compute the significance profile of each component. We discover some similarities in the local structure between the giant connected component and disconnected components in diverse social networks. Then we discuss how to detect network attacks based on the local structure properties of networks. Furthermore, we propose an empirical generative model called iFriends to generate networks that follow our observed patterns.

Funded by

the National Natural Science Foundation of China(61572060)

the National Natural Science Foundation of China(61190125)

the National Natural Science Foundation of China(61472024)

CERNET Innovation Project 2015(NGII20151004)



This work was supported by the National Natural Science Foundation of China (Grant Nos. 61572060, 61190125, 61472024) and CERNET Innovation Project 2015 (Grant No. NGII20151004).


[1] Faloutsos M, Faloutsos P, Faloutsos C. On power-law relationships of the internet topology. SIGCOMM Comput Commun Rev, 1999, 29: 251-262 CrossRef Google Scholar

[2] Leskovec J, Kleinberg J, Faloutsos C. Graphs over time: densification laws, shrinking diameters and possible explanations. In: Proceedings of the 11th International Conference on Knowledge Discovery and Data Mining, Chicago, 2015. 177--187. Google Scholar

[3] Ahn Y Y, Han S, Kwak H, et al. Analysis of topological characteristics of huge online social networking services.\linebreak In: Proceedings of the 16th international conference on World Wide Web, Banff, 2007. 835--844. Google Scholar

[4] Kumar R, Novak J, Tomkins A. Structure and evolution of online social networks. In: Proceedings of the 12th International Conference on Knowledge Discovery and Data Mining, Philadelphia, 2006. 611--617. Google Scholar

[5] McGlohon M, Akoglu L, Faloutsos C. Weighted graphs and disconnected components: patterns and a generator. In: Proceedings of the 14th International Conference on Knowledge Discovery and Data Mining, Las Vegas, 2008. 524--532. Google Scholar

[6] Niu J, Peng J, Tong C, et al. Evolution of disconnected components in social networks: patterns and a generative model. In: Proceedings of the 31st International Performance Computing and Communications Conference, Austin, 2012. 305--313. Google Scholar

[7] Yan G H. Peri-Watchdog: Hunting for hidden botnets in the periphery of online social networks. Comput Netw, 2013, 57: 540-555 CrossRef Google Scholar

[8] Shrivastava N, Majumder A, Rastogi R. Mining (social) network graphs to detect random link attacks. In: Proceedings of the 24th International Conference on Data Engineering, Cancun, 2008. 486--495. Google Scholar

[9] Leskovec J, Adamic L, Huberman B. The dynamics of viral marketing. ACM Trans Web, 2007, 1: 1-39 CrossRef Google Scholar

[10] Yan D, Cheng J, Lu Y, et al. Effective techniques for message reduction and load balancing in distributed graph computation. In: Proceedings of the 24th International Conference on World Wide Web, Florence, 2015. 1307--1317. Google Scholar

[11] Dong Y, Zhang J, Tang J, et al. CoupledLP: Link prediction in coupled networks. In: Proceedings of the 21th SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, 2015. 199--208. Google Scholar

[12] Yang J, Leskovec J. Defining and evaluating network communities based on ground-truth. Knowl Inf Syst, 2105, 42: 181-213 Google Scholar

[13] Broder A, Kumar R, Maghoul F, et al. Graph structure in the web. Comput Netw, 2000, 33: 309-320 CrossRef Google Scholar

[14] Ugander J, Backstrom L, Marlow C, et al. Structural diversity in social contagion. Proc Natl Acade Sci, 2012, 109: 5962-5966 CrossRef Google Scholar

[15] Milo R, Itzkovitz S, Kashtan N, et al. Superfamilies of evolved and designed networks. Science, 2004, 303: 1538-1542 CrossRef Google Scholar

[16] Carlson J M, Doyle J. Complexity and robustness. Proc Natl Acade Sci, 2002, 99: 2538-2545 CrossRef Google Scholar

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备17057255号       京公网安备11010102003388号