Model for generating artificial social networks having community structures with small-world and scale-free properties | Social Network Analysis and Mining Skip to main content
Springer Nature Link
Log in

Model for generating artificial social networks having community structures with small-world and scale-free properties

  • Original Article
  • Published:
Social Network Analysis and Mining Aims and scope Submit manuscript

Abstract

Recent interest in complex systems and specially social networks has catalyzed the development of numerous models to help understand these networks. A number of models have been proposed recently where they are either variants of the small-world model, the preferential attachment model or both. Three fundamental properties attributed to identify these complex networks are high clustering coefficient, small average path length and the vertex connectivity following power-law distribution. Different models have been presented to generate networks having all these properties. In this study, we focus on social networks and another important characteristic of these networks, which is the presence of community structures. Often misinterpret with the metric called clustering coefficient, we first show that the presence of community structures is indeed different from having high clustering coefficient. We then define a new network generation model which exhibits all the fundamental properties of complex networks along with the presence of community structures.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Notes

  1. http://www.math.utah.edu/~beebe/bibliographies.html.

  2. http://vlado.fmf.uni-lj.si/pub/networks/data/.

  3. http://www.imdb.com/.

References

  • Almeida H, Neto G, Meira W Jr, Zaki MJ (2012) Towards a better quality metric for graph cluster evaluation. J Inf Data Manag 3(3):378–393

    Google Scholar 

  • Archambault D, Munzner T, Auber D (2007) grouse: feature-based, steerable graph hierarchy exploration. In: EuroVis, pp 67–74

  • Auber D, Chiricota Y, Jourdan F, Melancon G (2003) Multiscale visualization of small world networks. In: INFOVIS ’03: Proceedings of the IEEE Symposium on Information Visualization, pp 75–81

  • Barabási AL, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509–512

    Article  MathSciNet  Google Scholar 

  • Boccaletti S et al (2006) Complex networks: structure and dynamics. Phys Reports 424:175–308

    Google Scholar 

  • Brandes U, Erlebach T (2005) Network analysis: methodological foundations. Lecture Notes in Computer Science. Springer, Berlin

  • Catanzaro M, Caldarelli G, Pietronero L (2004) Assortative model for social networks. Phys Rev E (Statist Nonlinear Soft Matter Phys) 70(3):1–4

    Google Scholar 

  • Coleman JS (1964) An introduction to mathematical sociology. Collier-Macmillan, London

    Google Scholar 

  • Condon A, Karp RM (1999) Algorithms for graph partitioning on the planted partition model. Random Struct Algorithms 18(2):116–140

    Article  MathSciNet  Google Scholar 

  • Cross R, Parker A, Borgatti SP (2000) A bird’s-eye view: using social network analysis to improve knowledge creation and sharing. Knowl Dir 2(1):48–61

    Google Scholar 

  • Dorogovtsev SN, Mendes JFF (2002) Evolution of networks. Adv Phys 51:1079–1187

    Article  Google Scholar 

  • Erdos P, Renyi A (1960) On the evolution of random graphs. Publ Math Inst Hung Acad Sci 5:17–61

    MathSciNet  Google Scholar 

  • Everitt BS, Landau S, Leese M (2009) Cluster analysis, 4th edn. Wiley, New York

    Google Scholar 

  • Freeman LC (2004) The development of social network analysis: a study in the sociology of science. Empirical Press, Vancouver

    Google Scholar 

  • Fu P, Liao K (2006) An evolving scale-free network with large clustering coefficient. In: ICARCV, IEEE, pp 1–4

  • Gilbert F, Simonetto P, Zaidi F, Jourdan F, Bourqui R (2011) Communities and hierarchical structures in dynamic social networks: analysis and visualization. Soc Netw Anal Min 1:83–95. doi:10.1007/s13278-010-0002-8

  • Girvan M, Newman MEJ (2002) Community structure in social and biological networks. Proc Natl Acad Sci USA 99:8271–8276

    Article  MathSciNet  Google Scholar 

  • Gordon AD (1981) Classification: methods for the exploratory analysis of multivariate data. Chapman & Hall Ltd., London

    MATH  Google Scholar 

  • Guillaume J-L, Latapy M (2005) Bipartite graphs as models of complex networks. In: Workshop on Combinatorial and Algorithmic Aspects of Networking (CAAN), Lecture Notes in Computer Science, vol 3405. Springer, pp 127–139

  • Holme P, Kim BJ (2002) Growing scale-free networks with tunable clustering. Phys Rev E 65:026107

    Article  Google Scholar 

  • Jain AK, Murty MN, Flynn PJ (1999) Data clustering: a review. ACM Comput Surv 31(3):264–323

    Article  Google Scholar 

  • Jia Y, Garland M, Hart JC (2011) Social network clustering and visualization using hierarchical edge bundles. Comput Gr Forum 30(8):2314–2327

    Article  Google Scholar 

  • Jung CJ (1921) Psychologischen typen. Volume Translation Baynes HG, 1923. Rascher, Zurich

    Google Scholar 

  • Klemm K, Eguiluz VM (2002) Growing scale-free networks with small world behavior. Physical Review E 65:057102

    Article  Google Scholar 

  • Lilijeros F, Edling C, Amaral L, Stanley E, åberg Y (2001) The web of human sexual contacts. Nature 411:907–908

    Article  Google Scholar 

  • Liu J-G, Dang Y-Z, tuo Wang Z (2005) Multistage random growing small-world networks with power-law degree distribution. Chin Phys Lett 23(3):746 (Comment: 3 figures, 4 pages)

    Google Scholar 

  • Milgram S (1967) The small world problem. Psychol Today 1:61–67

    Google Scholar 

  • Newman M (2003) Mixing patterns in networks. Phys Rev E 67:026126

    Article  MathSciNet  Google Scholar 

  • Newman M (2004) Detecting community structure in networks. Eur Phys J B-Condens Matt 38(2):321–330

    Article  Google Scholar 

  • Newman MEJ (2002) Assortative mixing in networks. Phys Rev Lett 89(20):208701

    Article  Google Scholar 

  • Newman MEJ (2003) The structure and function of complex networks. SIAM Rev 45:167

    Article  MathSciNet  MATH  Google Scholar 

  • Newman MEJ (2006) Finding community structure in networks using the eigenvectors of matrices. Phys Rev E (Statist Nonlinear Soft Matter Phys) 74(3):036104

    Article  Google Scholar 

  • Päivinen N (2007) A quest for the hidden knowledge. PhD thesis, University of Kuopio, Kuopio

  • Rapoport A (1957) Contribution to the theory of random and biased nets. Bull Math Biophys 19:257–277

    Article  MathSciNet  Google Scholar 

  • Schaeffer SE (2007) Graph clustering. Comput Sci Rev 1(1):27–64

    Article  MathSciNet  Google Scholar 

  • Scott J (2011) Social network analysis: developments, advances, and prospects. Soc Netw Anal Min 1:21–26

    Article  Google Scholar 

  • Scott JP (2000) Social network analysis: a handbook. SAGE Publications, New York

    Google Scholar 

  • Simmel G, Wolff KH (1950) The sociology of Georg Simmel/translated and edited with an introduction by Wolff KH. Free Press, Glencoe

    Google Scholar 

  • Tryon RC (1939) Cluster analysis. Edwards Brothers, Ann Arbor

    Google Scholar 

  • Virtanen S (2003) Properties of nonuniform random graph models. Research Report A77, Helsinki University of Technology, Laboratory for Theoretical Computer Science, Espoo

  • Wang J, Rong L (2008) Evolving small-world networks based on the modified ba model. Inf Technol Int Conf Comput Sci 0:143–146

    Google Scholar 

  • Wang L, Du F, Dai HP, Sun YX (2006) Random pseudofractal scale-free networks with small-world effect. Eur Phys J B—Condens Matter Complex Syst 53:361–366

    Article  MATH  Google Scholar 

  • Wasserman S, Faust K (1994) Social network analysis: methods and applications. Cambridge University Press, Cambridge

    Book  Google Scholar 

  • Watts DJ, Strogatz SH (1998) Collective dynamics of ’small-world’ networks. Nature 393:440–442

    Article  Google Scholar 

  • Xu R, Wunsch D (2005) Survey of clustering algorithms. IEEE Trans Neural Netw 16(3):645–678

    Article  Google Scholar 

  • Zaidi F (2012) Small world networks and clustered small world networks with random connectivity. Soc Netw Anal Min, pp 1–13. doi:10.1007/s13278-012-0052-1

  • Zaidi F, Melançon G (2010) Identifying the presence of communities in complex networks through topological decomposition and component densities. In: EGC 2010, Extraction et Gestion de Connaissance, vol E-19, RNTI, pp 163–174

Download references

Author information

Authors and Affiliations

  1. University of California, San Francisco, USA

    Arnaud Sallaberry

  2. Karachi Institute of Economics and Technology, Karachi, Pakistan

    Faraz Zaidi

  3. CNRS UMR 5800 LaBRI and INRIA Bordeaux–Sud-Ouest, Talence Cedex, France

    Guy Melançon

Authors
  1. Arnaud Sallaberry
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Faraz Zaidi
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Guy Melançon
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Faraz Zaidi.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Sallaberry, A., Zaidi, F. & Melançon, G. Model for generating artificial social networks having community structures with small-world and scale-free properties. Soc. Netw. Anal. Min. 3, 597–609 (2013). https://doi.org/10.1007/s13278-013-0105-0

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s13278-013-0105-0

Keywords