An Overlapping Local Community Detection Algorithm Based on Node Transitivity and Modularity Density | SpringerLink
Skip to main content
Springer Nature Link
Log in

An Overlapping Local Community Detection Algorithm Based on Node Transitivity and Modularity Density

  • Conference paper
  • First Online:
Computer Supported Cooperative Work and Social Computing (ChineseCSCW 2020)

Part of the book series: Communications in Computer and Information Science ((CCIS,volume 1330))

  • 1183 Accesses

Abstract

The local community detection (LCD) method can discover the local community structure in which the seed node is located. Compared with global community detection, local community detection is characterized by its low cost and high efficiency. However, most existing LCD methods only return a non-overlapping community. Individuals in the real world may participate in multiple communities, which can only be discovered by using overlapping local community detection methods. In this study, an overlapping local community detection algorithm based on modularity and node transitivity. First, the scope and structure information of the overlapping communities are obtained according to the node transitivity. Second, NMF is used to obtain the number of overlapping communities. Finally, the local modularity density based on edge weights is used to refine the detected local communities. The experimental results validate the high performance of our method to the other method in comparison.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 16015
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 20019
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Gregory, S.F.: Finding overlapping communities in networks by label propagation. New J. Phys. 12(10), 103018 (2010)

    Article  Google Scholar 

  2. Clauset, A.F.: Finding local community structure in networks. Phys. Rev. E 72(2), 026132 (2005)

    Article  Google Scholar 

  3. Chen, Q.F., Wu, T.S., Fang, M.S.: Detecting local community structures in complex networks based on local degree central nodes. Phys. A: Stat. Mech. Appl. 392(3), 529–537 (2013)

    Article  Google Scholar 

  4. Luo, F.F., Wang, J.S., Promislow, E.T.: Exploring local community structures in large networks. In: 2006 IEEE/WIC/ACM International Conference on Web Intelligence, pp. 233–239. IEEE, Hong Kong (2006)

    Google Scholar 

  5. Luo, W.F., Zhang, D.S., Jiang, H.T.: Local community detection with the dynamic membership function. IEEE Trans. Fuzzy Syst. 26(5), 3136–3150 (2018)

    Article  Google Scholar 

  6. Meng, T.F., Cai, L.S., He, T.T.: Local higher-order community detection based on fuzzy membership functions. IEEE Access 7, 128510–128525 (2019)

    Article  Google Scholar 

  7. Luo, W.F., Lu, N.S., Ni, L.T.: Local community detection by the nearest nodes with greater centrality. Inf. Sci. 517, 377–392 (2020)

    Article  MathSciNet  Google Scholar 

  8. Jian, Z.F., Ma, H.S., Huang, J.T.: CLOSE: local community detection by LOcal structure expansion in a complex network. In: 2019 International Conference on Technologies and Applications of Artificial Intelligence, pp. 1–6. IEEE, Taiwan (2019)

    Google Scholar 

  9. He, K.F., Shi, P.S., Bindel, D.T.: Krylov subspace approximation for local community detection in large networks. ACM Trans. Knowl. Discov. Data (TKDD) 13(5), 1–30 (2019)

    Article  Google Scholar 

  10. Li, X.F., Xu, G.S., Lian, W.T.: Multi-layer network local community detection based on influence relation. IEEE Access 7, 89051–89062 (2019)

    Article  Google Scholar 

  11. Hollocou, A.F., Bonald, T.S., Lelarge, M.T.: Multiple local community detection. ACM SIGMETRICS Perform. Eval. Rev. 45(3), 76–83 (2018)

    Article  Google Scholar 

  12. Ni, L.F., Luo, W.S., Zhu, W.T.: Local overlapping community detection. ACM Trans. Knowl. Discov. Data 14(1), 1–25 (2019)

    Article  Google Scholar 

  13. Kamuhanda, D.F., He, K.S.: A nonnegative matrix factorization approach for multiple local community detection. In: 2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pp. 642–649. IEEE, Barcelona (2018)

    Google Scholar 

  14. Binesh, N.F., Rezghi, M.S.: Fuzzy clustering in community detection based on nonnegative matrix factorization with two novel evaluation criteria. Appl. Soft Comput. 69, 689–703 (2018)

    Article  Google Scholar 

  15. Liu, X.F., Wang, W.S., He, D.T.: Semi-supervised community detection based on non-negative matrix factorization with node popularity. Inf. Sci. 381, 304–321 (2017)

    Article  Google Scholar 

  16. Dohleman, B.F.: Exploratory social network analysis with Pajek. Psychometrika 71(3), 605 (2018)

    Article  Google Scholar 

  17. Zachary, W.F.: An information flow model for conflict and fission in small groups. J. Anthropol. Res. 33(4), 452–473 (1977)

    Article  Google Scholar 

  18. Lusseau, D.F., Schneider, K.S., Boisseau, O.T.: The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations. Behav. Ecol. Sociobiol. 54(4), 396–405 (2003)

    Article  Google Scholar 

  19. Political books network. http://www.orgnet.com. Accessed 28 June 2020

  20. Rossi, R.F., Ahmed, N.S.: The network data repository with interactive graph analytics and visualization. In: Twenty-Ninth AAAI Conference on Artificial Intelligence, pp. 4292–4293. AAAI, Texas (2015)

    Google Scholar 

  21. Girvan, M.F., Newman, M.S.: Community structure in social and biological networks. Proc. Natl. Acad. Sci. 99(12), 7821–7826 (2002)

    Article  MathSciNet  Google Scholar 

  22. Yin, H.F., Benson, A.S., Leskovec, J.T.: Local higher-order graph clustering. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 555–564. ACM, Halifax (2017)

    Google Scholar 

  23. Yang, J.F., Leskovec, J.S.: Defining and evaluating network communities based on ground-truth. Knowl. Inf. Syst. 42(1), 181–213 (2015)

    Article  Google Scholar 

  24. Lancichinetti, A.F., Fortunato, S.S., Radicchi, F.T.: Benchmark graphs for testing community detection algorithms. Phys. Rev. E 78(4), 046110 (2008)

    Article  Google Scholar 

  25. Schütze, H.F., Manning, C.S., Raghavan, P.T.: Introduction to Information Retrieval. Cambridge University Press, Cambridge (2008)

    MATH  Google Scholar 

Download references

Acknowledgements

This work is partly supported by the National Natural Science Foundation of China under Grant No. 61672159, No. 61672158, No. 62002063 and No. 61300104, the Fujian Collaborative Innovation Center for Big Data Applications in Governments, the Fujian Industry-Academy Cooperation Project under Grant No. 2017H6008 and No. 2018H6010, the Natural Science Foundation of Fujian Province under Grant No. 2019J01835 and No.2020J01230054, and Haixi Government Big Data Application Cooperative Innovation Center.

Author information

Authors and Affiliations

  1. College of Mathematics and Computer Sciences, Fuzhou University, Fuzhou, 350116, China

    Xintong Huang, Ling Wu & Kun Guo

  2. Fujian Provincial Key Laboratory of Network Computing and Intelligent Information Processing, Fuzhou, China

    Xintong Huang, Ling Wu & Kun Guo

  3. Key Laboratory of Spatial Data Mining and Information Sharing, Ministry of Education, Fuzhou, 350116, China

    Kun Guo

Authors
  1. Xintong Huang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ling Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Kun Guo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Kun Guo .

Editor information

Editors and Affiliations

  1. Shandong University, Jinan, China

    Yuqing Sun

  2. Guangdong University of Technology, Guangzhou, China

    Dongning Liu

  3. Shenzhen University, Shenzhen, China

    Hao Liao

  4. Tongji University, Shanghai, China

    Hongfei Fan

  5. University of Shanghai for Science and Technology, Shanghai, China

    Liping Gao

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Singapore Pte Ltd.

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Huang, X., Wu, L., Guo, K. (2021). An Overlapping Local Community Detection Algorithm Based on Node Transitivity and Modularity Density. In: Sun, Y., Liu, D., Liao, H., Fan, H., Gao, L. (eds) Computer Supported Cooperative Work and Social Computing. ChineseCSCW 2020. Communications in Computer and Information Science, vol 1330. Springer, Singapore. https://doi.org/10.1007/978-981-16-2540-4_35

Download citation

  • DOI: https://doi.org/10.1007/978-981-16-2540-4_35

  • Published:

  • Publisher Name: Springer, Singapore

  • Print ISBN: 978-981-16-2539-8

  • Online ISBN: 978-981-16-2540-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation