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

Fuzzy analysis of community detection in complex networks

Author

Listed:
  • Zhang, Dawei
  • Xie, Fuding
  • Zhang, Yong
  • Dong, Fangyan
  • Hirota, Kaoru

Abstract

A snowball algorithm is proposed to find community structures in complex networks by introducing the definition of community core and some quantitative conditions. A community core is first constructed, and then its neighbors, satisfying the quantitative conditions, will be tied to this core until no node can be added. Subsequently, one by one, all communities in the network are obtained by repeating this process. The use of the local information in the proposed algorithm directly leads to the reduction of complexity. The algorithm runs in O(n+m) time for a general network and O(n) for a sparse network, where n is the number of vertices and m is the number of edges in a network. The algorithm fast produces the desired results when applied to search for communities in a benchmark and five classical real-world networks, which are widely used to test algorithms of community detection in the complex network. Furthermore, unlike existing methods, neither global modularity nor local modularity is utilized in the proposal. By converting the considered problem into a graph, the proposed algorithm can also be applied to solve other cluster problems in data mining.

Suggested Citation

  • Zhang, Dawei & Xie, Fuding & Zhang, Yong & Dong, Fangyan & Hirota, Kaoru, 2010. "Fuzzy analysis of community detection in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(22), pages 5319-5327.
    • Handle: RePEc:eee:phsmap:v:389:y:2010:i:22:p:5319-5327
    DOI: 10.1016/j.physa.2010.07.016
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437110006436
    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.2010.07.016?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. Zhang, Peng & Wang, Jinliang & Li, Xiaojia & Li, Menghui & Di, Zengru & Fan, Ying, 2008. "Clustering coefficient and community structure of bipartite networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 387(27), pages 6869-6875.
    2. Chen, Duanbing & Fu, Yan & Shang, Mingsheng, 2009. "A fast and efficient heuristic algorithm for detecting community structures in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 388(13), pages 2741-2749.
    3. Fan, Ying & Li, Menghui & Zhang, Peng & Wu, Jinshan & Di, Zengru, 2007. "Accuracy and precision of methods for community identification in weighted networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 377(1), pages 363-372.
    4. Zarei, Mina & Samani, Keivan Aghababaei, 2009. "Eigenvectors of network complement reveal community structure more accurately," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 388(8), pages 1721-1730.
    5. Capocci, A. & Servedio, V.D.P. & Caldarelli, G. & Colaiori, F., 2005. "Detecting communities in large networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 352(2), pages 669-676.
    6. Shen, Yi & Pei, Wenjiang & Wang, Kai & Li, Tao & Wang, Shaoping, 2008. "Recursive filtration method for detecting community structure in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 387(26), pages 6663-6670.
    7. Wang, Xutao & Chen, Guanrong & Lu, Hongtao, 2007. "A very fast algorithm for detecting community structures in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 384(2), pages 667-674.
    8. Zhang, Shihua & Wang, Rui-Sheng & Zhang, Xiang-Sun, 2007. "Identification of overlapping community structure in complex networks using fuzzy c-means clustering," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 374(1), pages 483-490.
    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. 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.
    2. Wu, Jianshe & Lu, Rui & Jiao, Licheng & Liu, Fang & Yu, Xin & Wang, Da & Sun, Bo, 2013. "Phase transition model for community detection," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(6), pages 1287-1301.
    3. 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.
    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. Shang, Ronghua & Liu, Huan & Jiao, Licheng, 2017. "Multi-objective clustering technique based on k-nodes update policy and similarity matrix for mining communities in social networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 486(C), pages 1-24.
    6. Cai, Biao & Wang, Yanpeng & Zeng, Lina & Hu, Yanmei & Li, Hongjun, 2020. "Edge classification based on Convolutional Neural Networks for community detection in complex network," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 556(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. Chen, Duanbing & Shang, Mingsheng & Lv, Zehua & Fu, Yan, 2010. "Detecting overlapping communities of weighted networks via a local algorithm," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(19), pages 4177-4187.
    2. Zhou, Kuang & Martin, Arnaud & Pan, Quan, 2015. "A similarity-based community detection method with multiple prototype representation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 438(C), pages 519-531.
    3. Li, Junqiu & Wang, Xingyuan & Cui, Yaozu, 2014. "Uncovering the overlapping community structure of complex networks by maximal cliques," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 415(C), pages 398-406.
    4. Shen, Yi & Pei, Wenjiang & Wang, Kai & Li, Tao & Wang, Shaoping, 2008. "Recursive filtration method for detecting community structure in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 387(26), pages 6663-6670.
    5. 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.
    6. Jing Wang & Jing Wang & Jingfeng Guo & Liya Wang & Chunying Zhang & Bin Liu, 2023. "Research Progress of Complex Network Modeling Methods Based on Uncertainty Theory," Mathematics, MDPI, vol. 11(5), pages 1-27, March.
    7. Zhang, Yun & Liu, Yongguo & Li, Jieting & Zhu, Jiajing & Yang, Changhong & Yang, Wen & Wen, Chuanbiao, 2020. "WOCDA: A whale optimization based community detection algorithm," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 539(C).
    8. Shang, Jiaxing & Liu, Lianchen & Li, Xin & Xie, Feng & Wu, Cheng, 2016. "Targeted revision: A learning-based approach for incremental community detection in dynamic networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 443(C), pages 70-85.
    9. Angelito Calma & José Martí-Parreño & Martin Davies, 2019. "Journal of the Academy of Marketing Science 1973–2018: an analytical retrospective," Scientometrics, Springer;Akadémiai Kiadó, vol. 119(2), pages 879-908, May.
    10. Zhang, Zhiwei & Wang, Zhenyu, 2015. "Mining overlapping and hierarchical communities in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 421(C), pages 25-33.
    11. Fuqiang Zhao & Lichao Zhang & Guijun Yang & Li He & Fengyu Yan, 2017. "Application Of Cut Algorithm Based On Algebraic Connectivity To Community Detection," Advances in Complex Systems (ACS), World Scientific Publishing Co. Pte. Ltd., vol. 20(01), pages 1-18, February.
    12. Chen, Lei & Kou, Yingxin & Li, Zhanwu & Xu, An & Wu, Cheng, 2018. "Empirical research on complex networks modeling of combat SoS based on data from real war-game, Part I: Statistical characteristics," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 490(C), pages 754-773.
    13. Wu, Jianshe & Wang, Xiaohua & Jiao, Licheng, 2012. "Synchronization on overlapping community network," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(3), pages 508-514.
    14. Badie, Reza & Aleahmad, Abolfazl & Asadpour, Masoud & Rahgozar, Maseud, 2013. "An efficient agent-based algorithm for overlapping community detection using nodes’ closeness," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(20), pages 5231-5247.
    15. Li, Jianyu & Zhou, Jie, 2007. "Chinese character structure analysis based on complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 380(C), pages 629-638.
    16. Wang, Wenjun & Liu, Dong & Liu, Xiao & Pan, Lin, 2013. "Fuzzy overlapping community detection based on local random walk and multidimensional scaling," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(24), pages 6578-6586.
    17. Chang, Zhenhai & Yin, Xianjun & Jia, Caiyan & Wang, Xiaoyang, 2018. "Mixture models with entropy regularization for community detection in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 496(C), pages 339-350.
    18. Tugrul Temel & Paul Phumpiu, 2021. "Pathways to recovery from COVID-19: characterizing input–output linkages of a targeted sector," Journal of Economic Structures, Springer;Pan-Pacific Association of Input-Output Studies (PAPAIOS), vol. 10(1), pages 1-24, December.
    19. Lan Huang & Guishen Wang & Yan Wang & Enrico Blanzieri & Chao Su, 2013. "Link Clustering with Extended Link Similarity and EQ Evaluation Division," PLOS ONE, Public Library of Science, vol. 8(6), pages 1-18, June.
    20. Gong, Maoguo & Ma, Lijia & Zhang, Qingfu & Jiao, Licheng, 2012. "Community detection in networks by using multiobjective evolutionary algorithm with decomposition," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(15), pages 4050-4060.

    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:389:y:2010:i:22:p:5319-5327. 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.