Skip to main content
SpringerLink
Log in

Relationship Between Community Structure and Clustering Coefficient

  • Conference paper
  • First Online:
Intelligent Computing and Applications

Part of the book series: Advances in Intelligent Systems and Computing ((AISC,volume 1172))

  • 1048 Accesses

Abstract

Overlapping community is a phenomenon often observed in numerous real-world networks. Fire-spread (Pattanayak et al. in Swarm Evol Comput. 44: 1–48 (2019) [11]) community detection algorithm is an efficient algorithm to detect overlapping community structures. In this work, the Fire-spread algorithm is modified to establish a relationship between community structure and clustering coefficient. By using different networks and executing the modified Fire-spread algorithm, it is found that the clustering coefficient is highly correlated with community structure. Finally, a simpler community detection algorithm, derived from the fire-spread algorithm, is proposed, where the clustering coefficient is used as a threshold value. To validate the proposed algorithm, it is compared with some state of art community detection algorithms based on the NMI score.

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
$34.99 /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
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 169.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 219.99
Price excludes VAT (USA)
  • 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. S. Wasserman, K. Faust, Social Network Analysis: Methods and Applications (Cambridge University Press, 1994)

    Google Scholar 

  2. J. Leskovec, A. Krevl, https://snap.stanford.edu/data/

  3. M.S. Granovetter, The strength of weak ties. Am. J. Sociol. 78, 1360–1380 (1973)

    Article  Google Scholar 

  4. G. Flake, S. Lawrence, C. Giles, Efficient identification of web communities, in KDD’00: Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2000), pp 150–160

    Google Scholar 

  5. G. Palla, I. Derényi, I. Farkas, T. Vicsek, Uncovering the overlapping community structure of complex networks in nature and society. Nature 435(7043), 814–818 (2005)

    Article  Google Scholar 

  6. R. Pastor-Satorras, A. Vespignani, Epidemic spreading in scale-free networks. Phys. Rev. Lett. 86(14), 3200 (2001)

    Article  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  8. A. Gog, D. Dumitrescu, B. Hirsbrunner, Community detection in complex networks using collaborative evolutionary algorithms. Adv. Artifi. Life 886–894 (2007)

    Google Scholar 

  9. M.S. Ahuja, J. Singh, Neha practical applications of community detection. Int. J. Adv. Res. Comput. Sci. Softw. Eng. 6(4) (2016)

    Google Scholar 

  10. H.S. Pattanayak, H.K. Verma, A.L. Sangal, Community detection metrics and algorithms in social networks, in 2018 First International Conference on Secure Cyber Computing and Communication (ICSCCC). IEEE (2018, December), (pp. 483–489)

    Google Scholar 

  11. H.S. Pattanayak, A.L. Sangal, H.K. Verma, Community detection in social networks based on fire propagation. Swarm Evol. Comput. 44, 31–48 (2019)

    Article  Google Scholar 

  12. V.D. Blondel, J.L. Guillaume, R. Lambiotte, E. Lefebvre, Fast unfolding of communities in large networks. J. Stat. Mech: Theory Exp. 2008, P10008 (2008)

    Article  Google Scholar 

  13. A. Clauset, M.E.J. Newman, C. Moore, Finding community structure in very large networks. Phys. Rev. E 70, 066111 (2004)

    Article  Google Scholar 

  14. P. Ronhovde, Z. Nussinov, Multiresolution community detection for mega scale networks by information-based replica correlations. Phys. Rev. E 80, 16109 (2009)

    Article  Google Scholar 

  15. S. Boettcher, A.G. Percus, Extremal optimization for graph partitioning. Phys. Rev. E 64 (2001). (Article ID: 026114)

    Google Scholar 

  16. D. Fisher, J. Artif, Iterative optimization and simplification of hierarchical clusterings. J. Artif. Intell. Res. 4, 147–180 (1996)

    Article  Google Scholar 

  17. D. He, J. Liu, D. Liu, D. Jin, Z. Jia, Ant colony optimization for community detection in large-scale complex networks, in Proceedings of 7th International Conference on Natural Computation (ICNC 2011), vol. 2 (IEEE Press, 2011), pp. 1151–1155

    Google Scholar 

  18. T. Herlau, M. Mørup, M.N. Schmidt, L.K. Hansen, Detecting hierarchical structure in networks, in Proceedings of 3rd International Workshop on Cognitive Information Processing (CIP 2012) (IEEE Press, 2012), pp. 1–6

    Google Scholar 

  19. Z. Zhao, C. Li, X. Zhang, F. Chiclana, E.H. Viedma, An incremental method to detect communities in dynamic evolving social networks. Knowl. Based Syst. 163, 404–415 (2019)

    Article  Google Scholar 

  20. Z. Gao, N. Jin, Detecting community structure in complex networks based on k-means clustering and data field theory, in Proceedings of 20th Chines Control and Decision Conference (CCDC 2008) (IEEE Press, 2008), pp. 4411–4416

    Google Scholar 

  21. W. Li, 229 (2013) Revealing network communities with a nonlinear programming method, Inform. Sci. 18–28

    Google Scholar 

  22. J. Liu, T. Liu, Detecting community structure in complex networks using simulated annealing with k-means algorithms. Phys. A: Stat. Mech. Appl. 389(11), 2300–2309 (2010)

    Article  Google Scholar 

  23. J.B. MacQueen, Some methods for classification and analysis of multivariate observations, in Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, vol. 1 (1967), pp. 281–297

    Google Scholar 

  24. Z.Y. Zhang, Community structure detection in complex networks with partial background information, EPL 101 (4), 6 (2013). Article No. 48005

    Google Scholar 

  25. A. Ghasemian, H. Hosseinmardi, A. Clauset, Evaluating overfit and underfit in models of network community structure. IEEE Trans. Knowl. Data Eng. (2019)

    Google Scholar 

  26. B. Amiri et al., Community detection in complex networks: multi–objective enhanced firefly algorithm. Knowl. Based Syst. 46, 1–11 (2013)

    Google Scholar 

  27. X.S. Yang, Firefly Algorithms for Multimodal Optimization (Foundations and Applications, Stochastic Algorithms, 2009), pp. 169–178

    MATH  Google Scholar 

  28. X. Duan, C. Wang, X. Liu, Y. Lin, Web community detection model using particle swarm optimization, in Proceedings of IEEE Congress on Evolutionary Computation (CEC 2008) (IEEE Press, 2008), pp. 1074–1079

    Google Scholar 

  29. R.J. Kuo, Y.D. Huang, C.C. Lin, Y.H. Wu, F.E. Zulvia, Automatic kernel clustering with bee colony optimization algorithm. Inform. Sci. 283, 107–122 (2014)

    Article  Google Scholar 

  30. Q. Cai, M. Gong, L. Ma, S. Ruan, F. Yuan, L. Jiao, Greedy discrete particle swarm optimization for large-scale social network clustering. Inform. Sci. 2014 (2014). Available online 7 October

    Google Scholar 

  31. C. Pizzuti, GA-Net: a genetic algorithm for community detection in social networks, in Proceedings of 10th International Conference on Parallel Problem Solving from Nature (PPSN 2008), Lecture Notes in Computer Science, vol. 5199 (2008) pp. 1081–1090

    Google Scholar 

  32. A.I. Hafez, N.I. Ghali, A.E. Hassanien, A.A. Fahmy, Genetic algorithms for community detection in social networks, in Proceedings of 12th International Conference on Intelligent Systems Design and Applications (ISDA 2012) (IEEE Press, 2012), pp. 460–465

    Google Scholar 

  33. V. Estivill-Castro, Why so many clustering algorithms: a position paper. ACM SIGKDD Explor. Newslett. 4(1), 65–75 (2002)

    Article  Google Scholar 

  34. D.J. Watts, P.S. Dodds, M.E.J. Newman, Identity and search in social networks. Science 296(5571), 1302–1305 (2002)

    Article  Google Scholar 

  35. L. Wang, J. Wang, Y. Bi, W. Wu, W. Xu, B. Lian, Noise-tolerance community detection and evolution in dynamic social networks. J. Comb. Optimiz. 28(3), 600–612 (2014)

    Article  MathSciNet  Google Scholar 

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

    Google Scholar 

  37. D. Lusseau, K. Schneider, O.J. Boisseau, P. Haase, E. Slooten, S.M. Dawson, The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations. Behav. Ecol. Sociobiol. 54, 396–405 (2003)

    Article  Google Scholar 

  38. V. Krebs. http://www.orgnet.com/

  39. M.E.J. Newman, Phys. Rev. E 74, 036104 (2006)

    Article  MathSciNet  Google Scholar 

  40. D.J. Watts, Small Worlds (Princeton University Press, 1999)

    Google Scholar 

  41. L. Danon, A. Diaz-Guilera, J. Duch, A. Arenas, Comparing community structure identification. J. Stat. Mech.: Theory Exp. 2005, P09008 (2005)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of CSE, NIT Jalandhr, Jalandhr, India

    Himansu Sekhar Pattanayak, Harsh K. Verma & A. L. Sangal

Authors
  1. Himansu Sekhar Pattanayak
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Harsh K. Verma
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. A. L. Sangal
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Himansu Sekhar Pattanayak .

Editor information

Editors and Affiliations

  1. Dpt of Electrical and Electronics Engg, Government College of Engineering, Keonjhar, India

    Subhransu Sekhar Dash

  2. Electronics and Communication Sciences, Indian Statistical Institute, Kolkata, West Bengal, India

    Swagatam Das

  3. Indian Institute of Technology, New Delhi, Delhi, India

    Bijaya Ketan Panigrahi

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

Pattanayak, H.S., Verma, H.K., Sangal, A.L. (2021). Relationship Between Community Structure and Clustering Coefficient. In: Dash, S.S., Das, S., Panigrahi, B.K. (eds) Intelligent Computing and Applications. Advances in Intelligent Systems and Computing, vol 1172. Springer, Singapore. https://doi.org/10.1007/978-981-15-5566-4_18

Download citation

Publish with us

Policies and ethics

Search

Navigation