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

Complete graph model for community detection

Author

Listed:
  • Sun, Peng Gang
  • Sun, Xiya

Abstract

Community detection brings plenty of considerable problems, which has attracted more attention for many years. This paper develops a new framework, which tries to measure the interior and the exterior of a community based on a same metric, complete graph model. In particular, the exterior is modeled as a complete bipartite. We partition a network into subnetworks by maximizing the difference between the interior and the exterior of the subnetworks. In addition, we compare our approach with some state of the art methods on computer-generated networks based on the LFR benchmark as well as real-world networks. The experimental results indicate that our approach obtains better results for community detection, is capable of splitting irregular networks and achieves perfect results on the karate network and the dolphin network.

Suggested Citation

  • Sun, Peng Gang & Sun, Xiya, 2017. "Complete graph model for community detection," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 471(C), pages 88-97.
    • Handle: RePEc:eee:phsmap:v:471:y:2017:i:c:p:88-97
    DOI: 10.1016/j.physa.2016.12.014
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437116309955
    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.2016.12.014?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. Martin Rosvall & Carl T Bergstrom, 2011. "Multilevel Compression of Random Walks on Networks Reveals Hierarchical Organization in Large Integrated Systems," PLOS ONE, Public Library of Science, vol. 6(4), pages 1-10, April.
    2. Du, Wen-Bo & Zhou, Xing-Lian & Lordan, Oriol & Wang, Zhen & Zhao, Chen & Zhu, Yan-Bo, 2016. "Analysis of the Chinese Airline Network as multi-layer networks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 89(C), pages 108-116.
    3. Sun, Peng Gang, 2016. "Imbalance problem in community detection," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 457(C), pages 364-376.
    4. Du, Wen-Bo & Gao, Yang & Liu, Chen & Zheng, Zheng & Wang, Zhen, 2015. "Adequate is better: particle swarm optimization with limited-information," Applied Mathematics and Computation, Elsevier, vol. 268(C), pages 832-838.
    5. Sun, Peng Gang, 2014. "Weighting links based on edge centrality for community detection," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 394(C), pages 346-357.
    6. Steven H. Strogatz, 2001. "Exploring complex networks," Nature, Nature, vol. 410(6825), pages 268-276, March.
    7. Sun, Peng Gang & Yang, Yang, 2013. "Methods to find community based on edge centrality," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(9), pages 1977-1988.
    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. Manuel Guerrero & Consolación Gil & Francisco G. Montoya & Alfredo Alcayde & Raúl Baños, 2020. "Multi-Objective Evolutionary Algorithms to Find Community Structures in Large Networks," Mathematics, MDPI, vol. 8(11), pages 1-18, November.
    2. Zhang, Yuan & Li, Lu & Zhang, Wenbo & Cheng, Qixiu, 2022. "GATC and DeepCut: Deep spatiotemporal feature extraction and clustering for large-scale transportation network partition," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 606(C).
    3. Wang, Tao & Chen, Shanshan & Wang, Xiaoxia & Wang, Jinfang, 2020. "Label propagation algorithm based on node importance," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 551(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. Sun, Peng Gang, 2015. "Community detection by fuzzy clustering," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 419(C), pages 408-416.
    2. Lawford, Steve & Mehmeti, Yll, 2020. "Cliques and a new measure of clustering: With application to U.S. domestic airlines," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 560(C).
    3. Jiang, Zhongzhou & Liu, Jing & Wang, Shuai, 2016. "Traveling salesman problems with PageRank Distance on complex networks reveal community structure," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 463(C), pages 293-302.
    4. Xiao, Guanping & Zheng, Zheng & Wang, Haoqin, 2017. "Evolution of Linux operating system network," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 466(C), pages 249-258.
    5. Yang, Han-Xin & Tang, Ming & Wang, Zhen, 2018. "Suppressing epidemic spreading by risk-averse migration in dynamical networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 490(C), pages 347-352.
    6. Tian, Lin-Lin & Li, Ming-Chu & Wang, Zhen, 2016. "Cooperation enhanced by indirect reciprocity in spatial prisoner’s dilemma games for social P2P systems," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 462(C), pages 1252-1260.
    7. Gao, Cai & Wei, Daijun & Hu, Yong & Mahadevan, Sankaran & Deng, Yong, 2013. "A modified evidential methodology of identifying influential nodes in weighted networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(21), pages 5490-5500.
    8. Zhang, Xue-Jun & Xu, Guo-Qiang & Zhu, Yan-Bo & Xia, Yong-Xiang, 2016. "Cascade-robustness optimization of coupling preference in interconnected networks," Chaos, Solitons & Fractals, Elsevier, vol. 92(C), pages 123-129.
    9. Wang, Qiang & He, Nanrong & Chen, Xiaojie, 2018. "Replicator dynamics for public goods game with resource allocation in large populations," Applied Mathematics and Computation, Elsevier, vol. 328(C), pages 162-170.
    10. A. Tabrizi, Shayan & Shakery, Azadeh & Asadpour, Masoud & Abbasi, Maziar & Tavallaie, Mohammad Ali, 2013. "Personalized PageRank Clustering: A graph clustering algorithm based on random walks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(22), pages 5772-5785.
    11. Xinxin Xu & Sheng Ma & Ziqiang Zeng, 2019. "Complex network analysis of bilateral international investment under de-globalization: Structural properties and evolution," PLOS ONE, Public Library of Science, vol. 14(4), pages 1-16, April.
    12. Sun, Peng Gang, 2016. "Imbalance problem in community detection," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 457(C), pages 364-376.
    13. Bombelli, Alessandro & Santos, Bruno F. & Tavasszy, Lóránt, 2020. "Analysis of the air cargo transport network using a complex network theory perspective," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 138(C).
    14. Wang, Bi & Su, Qin & Chin, Kwai Sang, 2021. "Vulnerability assessment of China–Europe Railway Express multimodal transport network under cascading failures," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 584(C).
    15. Sun, Peng Gang & Ma, Xiaoke & Chi, Juan, 2017. "Dominating complex networks by identifying minimum skeletons," Chaos, Solitons & Fractals, Elsevier, vol. 104(C), pages 182-191.
    16. Du, Yuxian & Gao, Cai & Hu, Yong & Mahadevan, Sankaran & Deng, Yong, 2014. "A new method of identifying influential nodes in complex networks based on TOPSIS," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 399(C), pages 57-69.
    17. Zhang, Xuejun & Pang, Wenbo & Xia, Yongxiang, 2018. "An intermediary probability model for link prediction," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 512(C), pages 902-912.
    18. Jiang, Zhong-Yuan & Liu, Zhi-Quan & He, Xuan & Ma, Jian-Feng, 2018. "Cascade phenomenon against subsequent failures in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 499(C), pages 472-480.
    19. Emerson, Isaac Arnold & Amala, Arumugam, 2017. "Protein contact maps: A binary depiction of protein 3D structures," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 465(C), pages 782-791.
    20. Thi-Phuong Nguyen, 2021. "Assess the Impacts of Discount Policies on the Reliability of a Stochastic Air Transport Network," Mathematics, MDPI, vol. 9(9), pages 1-13, April.

    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:471:y:2017:i:c:p:88-97. 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.