IDEAS home Printed from https://ideas.repec.org/a/plo/pone00/0072908.html
   My bibliography  Save this article

Correlations between Community Structure and Link Formation in Complex Networks

Author

Listed:
  • Zhen Liu
  • Jia-Lin He
  • Komal Kapoor
  • Jaideep Srivastava

Abstract

Background: Links in complex networks commonly represent specific ties between pairs of nodes, such as protein-protein interactions in biological networks or friendships in social networks. However, understanding the mechanism of link formation in complex networks is a long standing challenge for network analysis and data mining. Methodology/Principal Findings: Links in complex networks have a tendency to cluster locally and form so-called communities. This widely existed phenomenon reflects some underlying mechanism of link formation. To study the correlations between community structure and link formation, we present a general computational framework including a theory for network partitioning and link probability estimation. Our approach enables us to accurately identify missing links in partially observed networks in an efficient way. The links having high connection likelihoods in the communities reveal that links are formed preferentially to create cliques and accordingly promote the clustering level of the communities. The experimental results verify that such a mechanism can be well captured by our approach. Conclusions/Significance: Our findings provide a new insight into understanding how links are created in the communities. The computational framework opens a wide range of possibilities to develop new approaches and applications, such as community detection and missing link prediction.

Suggested Citation

  • Zhen Liu & Jia-Lin He & Komal Kapoor & Jaideep Srivastava, 2013. "Correlations between Community Structure and Link Formation in Complex Networks," PLOS ONE, Public Library of Science, vol. 8(9), pages 1-10, September.
  • Handle: RePEc:plo:pone00:0072908
    DOI: 10.1371/journal.pone.0072908
    as

    Download full text from publisher

    File URL: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0072908
    Download Restriction: no

    File URL: https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0072908&type=printable
    Download Restriction: no

    References listed on IDEAS

    as
    1. David Liben‐Nowell & Jon Kleinberg, 2007. "The link‐prediction problem for social networks," Journal of the American Society for Information Science and Technology, Association for Information Science & Technology, vol. 58(7), pages 1019-1031, May.
    2. Tao Zhou & Linyuan Lü & Yi-Cheng Zhang, 2009. "Predicting missing links via local information," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 71(4), pages 623-630, October.
    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. Sheykhali, Somaye & Darooneh, Amir Hossein & Jafari, Gholam Reza, 2020. "Partial balance in social networks with stubborn links," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 548(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. Andreas Spitz & Anna Gimmler & Thorsten Stoeck & Katharina Anna Zweig & Emőke-Ágnes Horvát, 2016. "Assessing Low-Intensity Relationships in Complex Networks," PLOS ONE, Public Library of Science, vol. 11(4), pages 1-17, April.
    2. Rafiee, Samira & Salavati, Chiman & Abdollahpouri, Alireza, 2020. "CNDP: Link prediction based on common neighbors degree penalization," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 539(C).
    3. Chengjun Zhang & Jin Liu & Yanzhen Qu & Tianqi Han & Xujun Ge & An Zeng, 2018. "Enhancing the robustness of recommender systems against spammers," PLOS ONE, Public Library of Science, vol. 13(11), pages 1-14, November.
    4. Zhou, Tao & Lee, Yan-Li & Wang, Guannan, 2021. "Experimental analyses on 2-hop-based and 3-hop-based link prediction algorithms," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 564(C).
    5. Bütün, Ertan & Kaya, Mehmet, 2019. "A pattern based supervised link prediction in directed complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 525(C), pages 1136-1145.
    6. Park, Ji Hwan & Chang, Woojin & Song, Jae Wook, 2020. "Link prediction in the Granger causality network of the global currency market," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 553(C).
    7. Wang, Jun & Zhang, Qian-Ming & Zhou, Tao, 2019. "Tag-aware link prediction algorithm in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 523(C), pages 105-111.
    8. Najari, Shaghayegh & Salehi, Mostafa & Ranjbar, Vahid & Jalili, Mahdi, 2019. "Link prediction in multiplex networks based on interlayer similarity," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 536(C).
    9. Sanda Martinčić-Ipšić & Edvin Močibob & Matjaž Perc, 2017. "Link prediction on Twitter," PLOS ONE, Public Library of Science, vol. 12(7), pages 1-21, July.
    10. Sho Tsugawa & Hiroyuki Ohsaki, 2013. "Effectiveness of Link Prediction for Face-to-Face Behavioral Networks," PLOS ONE, Public Library of Science, vol. 8(12), pages 1-14, December.
    11. Chen, Xing & Wu, Tao & Xian, Xingping & Wang, Chao & Yuan, Ye & Ming, Guannan, 2020. "Enhancing robustness of link prediction for noisy complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 555(C).
    12. Lingling Zhang & Jing Li & Qiuliu Zhang & Fan Meng & Weili Teng, 2019. "Domain Knowledge-Based Link Prediction in Customer-Product Bipartite Graph for Product Recommendation," International Journal of Information Technology & Decision Making (IJITDM), World Scientific Publishing Co. Pte. Ltd., vol. 18(01), pages 311-338, January.
    13. Wahid-Ul-Ashraf, Akanda & Budka, Marcin & Musial, Katarzyna, 2019. "How to predict social relationships — Physics-inspired approach to link prediction," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 523(C), pages 1110-1129.
    14. Chen, Guangfu & Xu, Chen & Wang, Jingyi & Feng, Jianwen & Feng, Jiqiang, 2020. "Robust non-negative matrix factorization for link prediction in complex networks using manifold regularization and sparse learning," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 539(C).
    15. Emöke-Ágnes Horvát & Michael Hanselmann & Fred A Hamprecht & Katharina A Zweig, 2012. "One Plus One Makes Three (for Social Networks)," PLOS ONE, Public Library of Science, vol. 7(4), pages 1-8, April.
    16. Jeong, Yujin & Park, Inchae & Yoon, Byungun, 2019. "Identifying emerging Research and Business Development (R&BD) areas based on topic modeling and visualization with intellectual property right data," Technological Forecasting and Social Change, Elsevier, vol. 146(C), pages 655-672.
    17. Shang, Ronghua & Zhang, Weitong & Jiao, Licheng & Stolkin, Rustam & Xue, Yu, 2017. "A community integration strategy based on an improved modularity density increment for large-scale networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 469(C), pages 471-485.
    18. Chen, Ling-Jiao & Zhang, Zi-Ke & Liu, Jin-Hu & Gao, Jian & Zhou, Tao, 2017. "A vertex similarity index for better personalized recommendation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 466(C), pages 607-615.
    19. Xu, Hua & Wang, Minggang & Jiang, Shumin & Yang, Weiguo, 2020. "Carbon price forecasting with complex network and extreme learning machine," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 545(C).
    20. Liu, Chuang & Zhou, Wei-Xing, 2012. "Heterogeneity in initial resource configurations improves a network-based hybrid recommendation algorithm," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(22), pages 5704-5711.

    More about this item

    Statistics

    Access and download statistics

    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:plo:pone00:0072908. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (plosone). General contact details of provider: https://journals.plos.org/plosone/ .

    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 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.

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.