IDEAS home Printed from https://ideas.repec.org/a/eee/phsmap/v371y2006i2p795-813.html
   My bibliography  Save this article

Bipartite graphs as models of complex networks

Author

Listed:
  • Guillaume, Jean-Loup
  • Latapy, Matthieu

Abstract

It appeared recently that the classical random graph model used to represent real-world complex networks does not capture their main properties. Since then, various attempts have been made to provide accurate models. We study here a model which achieves the following challenges: it produces graphs which have the three main wanted properties (clustering, degree distribution, average distance), it is based on some real-world observations, and it is sufficiently simple to make it possible to prove its main properties. This model consists in sampling a random bipartite graph with prescribed degree distribution. Indeed, we show that any complex network may be viewed as a bipartite graph with some specific characteristics, and that its main properties may be viewed as consequences of this underlying structure. We also propose a growing model based on this observation.

Suggested Citation

  • Guillaume, Jean-Loup & Latapy, Matthieu, 2006. "Bipartite graphs as models of complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 371(2), pages 795-813.
    • Handle: RePEc:eee:phsmap:v:371:y:2006:i:2:p:795-813
    DOI: 10.1016/j.physa.2006.04.047
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437106004638
    Download Restriction: Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000
    File URL: https://libkey.io/10.1016/j.physa.2006.04.047?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Réka Albert & Hawoong Jeong & Albert-László Barabási, 1999. "Diameter of the World-Wide Web," Nature, Nature, vol. 401(6749), pages 130-131, September.
    2. Réka Albert & Hawoong Jeong & Albert-László Barabási, 2000. "Error and attack tolerance of complex networks," Nature, Nature, vol. 406(6794), pages 378-382, July.
    3. Barabási, Albert-László & Ravasz, Erzsébet & Vicsek, Tamás, 2001. "Deterministic scale-free networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 299(3), pages 559-564.
    4. Cristopher Moore & M. E. J. Newman, 2000. "Epidemics and Percolation in Small-World Networks," Working Papers 00-01-002, Santa Fe Institute.
    5. H. Jeong & B. Tombor & R. Albert & Z. N. Oltvai & A.-L. Barabási, 2000. "The large-scale organization of metabolic networks," Nature, Nature, vol. 407(6804), pages 651-654, October.
    6. Steven H. Strogatz, 2001. "Exploring complex networks," Nature, Nature, vol. 410(6825), pages 268-276, March.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Mukherjee, Animesh & Choudhury, Monojit & Ganguly, Niloy, 2011. "Understanding how both the partitions of a bipartite network affect its one-mode projection," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 390(20), pages 3602-3607.
    2. Jorge Peña & Yannick Rochat, 2012. "Bipartite Graphs as Models of Population Structures in Evolutionary Multiplayer Games," PLOS ONE, Public Library of Science, vol. 7(9), pages 1-13, September.
    3. Erik M Volz & Joel C Miller & Alison Galvani & Lauren Ancel Meyers, 2011. "Effects of Heterogeneous and Clustered Contact Patterns on Infectious Disease Dynamics," PLOS Computational Biology, Public Library of Science, vol. 7(6), pages 1-13, June.
    4. STANKOVA, Marija & MARTENS, David & PROVOST, Foster, 2015. "Classification over bipartite graphs through projection," Working Papers 2015001, University of Antwerp, Faculty of Business and Economics.
    5. Rita Strohmaier & Marlies Schuetz & Simone Vannuccini, 2019. "A systemic perspective on socioeconomic transformation in the digital age," Economia e Politica Industriale: Journal of Industrial and Business Economics, Springer;Associazione Amici di Economia e Politica Industriale, vol. 46(3), pages 361-378, September.
    6. Hao-Nan Yang & Xin-Jian Xu & Haili Liang & Xiaofan Wang, 2020. "A comparative study of online communities and popularity of BBS in four Chinese universities," PLOS ONE, Public Library of Science, vol. 15(6), pages 1-16, June.
    7. Ben Curran & Kyle Higham & Elisenda Ortiz & Demival Vasques Filho, 2018. "Look who’s talking: Two-mode networks as representations of a topic model of New Zealand parliamentary speeches," PLOS ONE, Public Library of Science, vol. 13(6), pages 1-16, June.
    8. Liu, Chengliang & Duan, Dezhong, 2020. "Spatial inequality of bus transit dependence on urban streets and its relationships with socioeconomic intensities: A tale of two megacities in China," Journal of Transport Geography, Elsevier, vol. 86(C).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Laurienti, Paul J. & Joyce, Karen E. & Telesford, Qawi K. & Burdette, Jonathan H. & Hayasaka, Satoru, 2011. "Universal fractal scaling of self-organized networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 390(20), pages 3608-3613.
    2. Dan Braha & Yaneer Bar-Yam, 2004. "Information Flow Structure in Large-Scale Product Development Organizational Networks," Industrial Organization 0407012, University Library of Munich, Germany.
    3. Dan Braha & Yaneer Bar-Yam, 2007. "The Statistical Mechanics of Complex Product Development: Empirical and Analytical Results," Management Science, INFORMS, vol. 53(7), pages 1127-1145, July.
    4. Chen, Qinghua & Shi, Dinghua, 2006. "Markov chains theory for scale-free networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 360(1), pages 121-133.
    5. Pagani, Giuliano Andrea & Aiello, Marco, 2013. "The Power Grid as a complex network: A survey," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(11), pages 2688-2700.
    6. Long Ma & Xiao Han & Zhesi Shen & Wen-Xu Wang & Zengru Di, 2015. "Efficient Reconstruction of Heterogeneous Networks from Time Series via Compressed Sensing," PLOS ONE, Public Library of Science, vol. 10(11), pages 1-12, November.
    7. Blagus, Neli & Šubelj, Lovro & Bajec, Marko, 2012. "Self-similar scaling of density in complex real-world networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(8), pages 2794-2802.
    8. Biggiero, Lucio & Angelini, Pier Paolo, 2015. "Hunting scale-free properties in R&D collaboration networks: Self-organization, power-law and policy issues in the European aerospace research area," Technological Forecasting and Social Change, Elsevier, vol. 94(C), pages 21-43.
    9. Chen, Qinghua & Shi, Dinghua, 2004. "The modeling of scale-free networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 335(1), pages 240-248.
    10. Selen Onel & Abe Zeid & Sagar Kamarthi, 2011. "The structure and analysis of nanotechnology co-author and citation networks," Scientometrics, Springer;Akadémiai Kiadó, vol. 89(1), pages 119-138, October.
    11. Zhang, Zhongzhi & Rong, Lili & Comellas, Francesc, 2006. "High-dimensional random Apollonian networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 364(C), pages 610-618.
    12. Gong, Pulin & van Leeuwen, Cees, 2003. "Emergence of scale-free network with chaotic units," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 321(3), pages 679-688.
    13. P.B., Divya & Lekha, Divya Sindhu & Johnson, T.P. & Balakrishnan, Kannan, 2022. "Vulnerability of link-weighted complex networks in central attacks and fallback strategy," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 590(C).
    14. Tachimori, Yutaka & Iwanaga, Hiroaki & Tahara, Takashi, 2013. "The networks from medical knowledge and clinical practice have small-world, scale-free, and hierarchical features," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(23), pages 6084-6089.
    15. Foti, Nicholas J. & Pauls, Scott & Rockmore, Daniel N., 2013. "Stability of the World Trade Web over time – An extinction analysis," Journal of Economic Dynamics and Control, Elsevier, vol. 37(9), pages 1889-1910.
    16. Salcedo-Sanz, S. & Cuadra, L., 2019. "Quasi scale-free geographically embedded networks over DLA-generated aggregates," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 523(C), pages 1286-1305.
    17. Heath Henderson & Arnob Alam, 2022. "The structure of risk-sharing networks," Empirical Economics, Springer, vol. 62(2), pages 853-886, February.
    18. Wu, Jianshe & Jiao, Licheng, 2007. "Synchronization in complex delayed dynamical networks with nonsymmetric coupling," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 386(1), pages 513-530.
    19. Wang, Li-Na & Wang, Kai & Shen, Jiang-Long, 2020. "Weighted complex networks in urban public transportation: Modeling and testing," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 545(C).
    20. Emmert-Streib, Frank & Dehmer, Matthias, 2009. "Fault tolerance of information processing in gene networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 388(4), pages 541-548.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:phsmap:v:371:y:2006:i:2:p:795-813. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.journals.elsevier.com/physica-a-statistical-mechpplications/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.