CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

Community Detection in Complex Network via BGLL Algorithm

by Pooja Chaturvedi, Mousumi Dhara, Deepak Arora
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 48 - Number 1
Year of Publication: 2012
Authors: Pooja Chaturvedi, Mousumi Dhara, Deepak Arora
10.5120/7315-9916

Pooja Chaturvedi, Mousumi Dhara, Deepak Arora . Community Detection in Complex Network via BGLL Algorithm. International Journal of Computer Applications. 48, 1 ( June 2012), 32-42. DOI=10.5120/7315-9916

@article{ 10.5120/7315-9916,
author = { Pooja Chaturvedi, Mousumi Dhara, Deepak Arora },
title = { Community Detection in Complex Network via BGLL Algorithm },
journal = { International Journal of Computer Applications },
issue_date = { June 2012 },
volume = { 48 },
number = { 1 },
month = { June },
year = { 2012 },
issn = { 0975-8887 },
pages = { 32-42 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume48/number1/7315-9916/ },
doi = { 10.5120/7315-9916 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:43:00.506627+05:30
%A Pooja Chaturvedi
%A Mousumi Dhara
%A Deepak Arora
%T Community Detection in Complex Network via BGLL Algorithm
%J International Journal of Computer Applications
%@ 0975-8887
%V 48
%N 1
%P 32-42
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

A large number of networks in nature, society and technology are defined by a mesoscopic level of organization, in which groups of nodes form tightly connected units, called communities, that are sparsely inter-linked to each other . Identifying this community structure is one of the most important problems in understanding of functions and structures of real world complex systems, which is still a challenging task. Various methods proposed so far are not efficient and accurate for large networks which comprise of millions of nodes because of their high computational cost. In this manuscript we will provide the implementation and behavioral analysis of BGLL algorithm for determining the structure of complex networks. This method is a variant of hierarchical agglomerative clustering approach, which finds the communities which are nested within one another. This method emphasizes on the idea of building the communities by combining the initial partition into super networks by repeatedly optimizing the modularity. In this work we will implement the BGLL Algorithm on various large networks which exhibit the community structure . We will also determine the optimal modularity at every pass and determine the hierarchical structure of large complex systems that comprise of millions of nodes. We will also provide a brief comparison of BGLL algorithm with some methods.

References
  1. L. Euler, Solutio problematis ad geometriam situs pertinentis, Commentarii Academiae Petropolitanae 8 (1736) 128-140.
  2. R. Albert, A. -L. Barabási, Statistical mechanics of complex networks, Rev. Mod. Phys. 74 (1) (2002) 47-97.
  3. M. E. J. Newman, The structure and function of complex networks, SIAM Rev. 45 (2) (2003) 167-256. University Press, Cambridge, UK, 2008.
  4. P. Erdös, A. Rényi, On random graphs. I. , Publ. Math. Debrecen 6 (1959) 290297.
  5. S. Fortunato, C. Castellano, Community structure in graphs, in: R. A. Meyers (Ed. ), Encyclopedia of Complexity and Systems Science, vol. 1, Springer,Berlin, Germany, 2009, eprint arXiv:0712. 2716.
  6. G. W. Flake, S. Lawrence, C. Lee Giles, F. M. Coetzee, Self-organization and identification of web communities, IEEE Computer 35 (2002) 6671.
  7. R. S. Weiss, E. Jacobson, A method for the analysis of the structure of complex organizations, Am. Sociol. Rev. 20 (1955) 661668.
  8. S. A. Rice, The identification of blocs in small political bodies, Am. Polit. Sci. Rev. 21 (1927) 619627.
  9. G. C. Homans, The Human Groups, Harcourt, Brace & Co, New York, 1950.
  10. M. E. J. Newman, M. Girvan, Finding and evaluating community structure in networks, Phys. Rev. E 69 (2) (2004) 026113.
  11. E. A. Leicht, M. E. J. Newman, Community structure in directed networks, Phys. Rev. Lett. 100 (11) (2008) 118703.
  12. M. Latapy, P. Pons, Lect. Notes Comput. Sci. 3733 (2005) 284293.
  13. B. H. Good, Y. de Montjoye, A. Clauset, The performance of modularity maximization in practical contexts, eprint arXiv:0910. 0165.
  14. M. E. J. Newman, Finding community structure in networks using the eigenvectors of matrices, Phys. Rev. E 74 (3) (2006) 036104.
  15. B. W. Kernighan, S. Lin, An efficient heuristic procedure for partitioning graphs, Bell Syst. Tech. J. 49 (1970) 291307.
  16. G. W. Flake, S. Lawrence, C. L. Giles, Efficient identification of web communities, in: Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM Press, Boston, USA, 2000, pp. 150160.
  17. M. E. J. Newman, A measure of betweenness centrality based on random walks, Soc. Netw. 27 (2005) 3954.
  18. M. E. J. Newman, Analysis of weighted networks, Phys. Rev. E 70 (5) (2004) 056131.
  19. M. E. J. Newman, Fast algorithm for detecting community structure in networks, Phys. Rev. E 69 (6) (2004) 066133.
  20. A. Clauset, M. E. J. Newman, C. Moore, Finding community structure in very large networks, Phys. Rev. E 70 (6) (2004) 066111.
  21. K. Wakita, T. Tsurumi, Finding community structure in mega-scale social networks, eprint arXiv:cs/0702048.
  22. V. D. Blondel, J. -L. Guillaume, R. Lambiotte, E. Lefebvre, Fast unfolding of communities in large networks, J. Stat. Mech. P10008 (2008).
  23. S. White, P. Smyth, A spectral clustering approach to finding communities in graphs, in: Proceedings of SIAM International Conference on Data Mining, 2005, pp. 7684.
  24. M. E. J. Newman, From the cover: Modularity and community structure in networks, Proc. Natl. Acad. Sci. USA 103 (2006) 85778582.
  25. M. E. J. Newman, The structure of scientific collaboration networks, Proc. Natl. Acad. Sci. USA 98 (2) (2001) 404409.
  26. J. G. White, E. Southgate, J. N. Thompson, and S. Brenner, "The structure of the nervous system of the nematode C. Elegans", Phil. Trans. R. Soc. London 314, 1-340 (1986).
  27. D. J. Watts and S. H. Strogatz, "Collective dynamics of `small-world' networks", Nature 393, 440-442 (1998).
  28. D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, and S. M. Dawson, The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations, Behavioral Ecology and Sociobiology 54, 396-405 (2003).
  29. D. Lusseau, The emergent properties of a dolphin social network,Proc. R. Soc. London B (suppl. ) 270, S186-S188 (2003).
  30. D. Lusseau, Evidence for social role in a dolphin social network,Preprint q-bio/0607048 (http://arxiv. org/abs/q-bio. PE/0607048).
  31. M. Girvan and M. E. J. Newman,Community structure in social and biological networks,Proc. Natl. Acad. Sci. USA 99, 7821-7826 (2002).
  32. M. E. J. Newman, SIAM Review 45, 167-256 (2003) and S. Boccaletti et al. , Physics Reports 424, 175-308 (2006),Lada A. Adamic and Natalie Glance, "The political blogosphere and the 2004 US Election", in Proceedings of the WWW-2005 Workshop on the Weblogging Ecosystem (2005).
  33. Identifying and evaluating community structure in complex networks Karsten Steinhaeuser, Nitesh V. Chawla *University of Notre Dame, Department of Computer Science and Engineering, Interdisciplinary Center for Network Science and Applications (iCeNSA), Notre Dame, IN 46556, USAvan Dongen, S. , 2000. Graph Clustering by Flow Simulation, Ph. D. Thesis, University of Utrecht, Netherlands.
  34. Pons, P. , Latapy, M. , 2006. Computing communities in large networks using random walks. J. Graph Algorithms Appl. 10 (2), 191–218.
  35. M. E. J. Newman, The structure and function of complex networks".
  36. Zenklusen Rico,Complex networks:An overview.
  37. Benjamin Lam,Data mining with clustering and classification,springer,2007.
  38. Santo Fortunato ,Community detection in graphs, Physics Reports 486 (2010) 75-174.
  39. Xu Liu a, Jeffrey Yi-Lin Forrest a,b, Qiang Luoc, Dong-Yun Yi a,,? Detecting community structure using biased random merging.
  40. M. E. J Newman,The structure and function of complex networks, arXiv:cond-mat/0303516v1 [cond-mat. stat-mech] 25 Mar 2003.
  41. Milligan, G. , Cooper, M. , 1986. A study of the comparability of external criteria for hierarchical cluster analysis. Multivar. Behav. Res. 21 (4),441–458.
  42. Merrian Webster,Online Dictionary,2008. Cluster Analysis. http://www. merriam-webster-online. com.
  43. Steinhaus,H. ,1956. Sur la division des corp materials en parties. Bull. Acad. Polon. Sci. ,C1,III IV,801-804.
  44. Berkhin,P. ,2009. Survey of clustering data mining techniques,http://www. ee. ucr. edu/barth/EE242/.
  45. Code of the BGLL is used from the link http://findcommunities. googlepages. com.
Index Terms

Computer Science
Information Sciences

Keywords

Complex Networks Community Structure

Powered by PhDFocusTM