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

Stepping community detection algorithm based on label propagation and similarity

Author

Listed:
  • Li, Wei
  • Huang, Ce
  • Wang, Miao
  • Chen, Xi

Abstract

Community or module structure is one of the most common features in complex networks. The label propagation algorithm (LPA) is a near linear time algorithm that is able to detect community structure effectively. Nevertheless, when labeling a node, the LPA adopts the label belonging to the majority of its neighbors, which means that it treats all neighbors equally in spite of their different effects on the node. Another disadvantage of LPA is that the results it generates are not unique. In this paper, we propose a modified LPA called Stepping LPA-S, in which labels are propagated by similarity. Furthermore, our algorithm divides networks using a stepping framework, and uses an evaluation function proposed in this paper to select the final unique partition. We tested this algorithm on several artificial and real-world networks. The results show that Stepping LPA-S can obtain accurate and meaningful community structure without priori information.

Suggested Citation

  • Li, Wei & Huang, Ce & Wang, Miao & Chen, Xi, 2017. "Stepping community detection algorithm based on label propagation and similarity," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 472(C), pages 145-155.
    • Handle: RePEc:eee:phsmap:v:472:y:2017:i:c:p:145-155
    DOI: 10.1016/j.physa.2017.01.030
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437117300225
    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.2017.01.030?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. Lu, Hu & Wei, Hui, 2012. "Detection of community structure in networks based on community coefficients," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(23), pages 6156-6164.
    2. Wu, Jianshe & Hou, Yunting & Jiao, Yang & Li, Yong & Li, Xiaoxiao & Jiao, Licheng, 2015. "Density shrinking algorithm for community detection with path based similarity," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 433(C), pages 218-228.
    3. Liu, X. & Murata, T., 2010. "Advanced modularity-specialized label propagation algorithm for detecting communities in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(7), pages 1493-1500.
    4. Shang, Ronghua & Bai, Jing & Jiao, Licheng & Jin, Chao, 2013. "Community detection based on modularity and an improved genetic algorithm," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(5), pages 1215-1231.
    5. 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.
    6. Lou, Hao & Li, Shenghong & Zhao, Yuxin, 2013. "Detecting community structure using label propagation with weighted coherent neighborhood propinquity," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(14), pages 3095-3105.
    7. Jiao, Qing-Ju & Huang, Yan & Shen, Hong-Bin, 2015. "Community mining with new node similarity by incorporating both global and local topological knowledge in a constrained random walk," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 424(C), pages 363-371.
    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. Dabaghi Zarandi, Fataneh & Kuchaki Rafsanjani, Marjan, 2018. "Community detection in complex networks using structural similarity," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 503(C), pages 882-891.
    2. Deng, Zheng-Hong & Qiao, Hong-Hai & Song, Qun & Gao, Li, 2019. "A complex network community detection algorithm based on label propagation and fuzzy C-means," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 519(C), pages 217-226.
    3. Moradi, Mehdi & Parsa, Saeed, 2019. "An evolutionary method for community detection using a novel local search strategy," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 523(C), pages 457-475.
    4. 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).
    5. Fang, Wenyi & Wang, Xin & Liu, Longzhao & Wu, Zhaole & Tang, Shaoting & Zheng, Zhiming, 2022. "Community detection through vector-label propagation algorithms," Chaos, Solitons & Fractals, Elsevier, vol. 158(C).
    6. Sun, Hong-liang & Ch’ng, Eugene & Yong, Xi & Garibaldi, Jonathan M. & See, Simon & Chen, Duan-bing, 2018. "A fast community detection method in bipartite networks by distance dynamics," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 496(C), pages 108-120.

    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. Shang, Ronghua & Luo, Shuang & Zhang, Weitong & Stolkin, Rustam & Jiao, Licheng, 2016. "A multiobjective evolutionary algorithm to find community structures based on affinity propagation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 453(C), pages 203-227.
    2. Laassem, Brahim & Idarrou, Ali & Boujlaleb, Loubna & Iggane, M’bark, 2022. "Label propagation algorithm for community detection based on Coulomb’s law," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 593(C).
    3. Dušan Džamić & Daniel Aloise & Nenad Mladenović, 2019. "Ascent–descent variable neighborhood decomposition search for community detection by modularity maximization," Annals of Operations Research, Springer, vol. 272(1), pages 273-287, January.
    4. 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.
    5. Lin, Zhen & Zheng, Xiaolin & Xin, Nan & Chen, Deren, 2014. "CK-LPA: Efficient community detection algorithm based on label propagation with community kernel," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 416(C), pages 386-399.
    6. Garza, Sara E. & Schaeffer, Satu Elisa, 2019. "Community detection with the Label Propagation Algorithm: A survey," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 534(C).
    7. Aghaalizadeh, Saeid & Afshord, Saeid Taghavi & Bouyer, Asgarali & Anari, Babak, 2021. "A three-stage algorithm for local community detection based on the high node importance ranking in social networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 563(C).
    8. Shang, Ronghua & Luo, Shuang & Li, Yangyang & Jiao, Licheng & Stolkin, Rustam, 2015. "Large-scale community detection based on node membership grade and sub-communities integration," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 428(C), pages 279-294.
    9. Lin, Dan & Wu, Jiajing & Xuan, Qi & Tse, Chi K., 2022. "Ethereum transaction tracking: Inferring evolution of transaction networks via link prediction," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 600(C).
    10. 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.
    11. Weihua Lei & Luiz G. A. Alves & Luís A. Nunes Amaral, 2022. "Forecasting the evolution of fast-changing transportation networks using machine learning," Nature Communications, Nature, vol. 13(1), pages 1-12, December.
    12. Rizman Žalik, Krista & Žalik, Borut, 2014. "A local multiresolution algorithm for detecting communities of unbalanced structures," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 407(C), pages 380-393.
    13. 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).
    14. Wang, Zuxi & Wu, Yao & Li, Qingguang & Jin, Fengdong & Xiong, Wei, 2016. "Link prediction based on hyperbolic mapping with community structure for complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 450(C), pages 609-623.
    15. Lee, Yan-Li & Zhou, Tao, 2021. "Collaborative filtering approach to link prediction," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 578(C).
    16. Moradabadi, Behnaz & Meybodi, Mohammad Reza, 2016. "Link prediction based on temporal similarity metrics using continuous action set learning automata," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 460(C), pages 361-373.
    17. Yichi Zhang & Zhiliang Dong & Sen Liu & Peixiang Jiang & Cuizhi Zhang & Chao Ding, 2021. "Forecast of International Trade of Lithium Carbonate Products in Importing Countries and Small-Scale Exporting Countries," Sustainability, MDPI, vol. 13(3), pages 1-23, January.
    18. Li, Yafang & Jia, Caiyan & Li, Jianqiang & Wang, Xiaoyang & Yu, Jian, 2018. "Enhanced semi-supervised community detection with active node and link selection," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 510(C), pages 219-232.
    19. Wang, Zuxi & Li, Qingguang & Xiong, Wei & Jin, Fengdong & Wu, Yao, 2016. "Fast community detection based on sector edge aggregation metric model in hyperbolic space," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 452(C), pages 178-191.
    20. Liu, Jin-Hu & Zhu, Yu-Xiao & Zhou, Tao, 2016. "Improving personalized link prediction by hybrid diffusion," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 447(C), pages 199-207.

    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:472:y:2017:i:c:p:145-155. 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.