Login Register Cart 0
Generic placeholder image

Recent Advances in Computer Science and Communications

Editor-in-Chief

ISSN (Print): 2666-2558
ISSN (Online): 2666-2566

Back
Journal Home About Journal Editorial Board Current Issue Volumes/Issues
Subscribe
Research Article

Determining Network Communities Based on Modular Density Optimization

Author(s): Seema Rani* and Monica Mehrotra

Volume 13, Issue 2, 2020

Page: [128 - 136] Pages: 9

DOI: 10.2174/2213275912666181205153024

Price: $65

Abstract

Background: In today’s world, complex systems are conceptually observed in the form of network structure. Communities inherently existing in the networks have a recognizable elucidation in understanding the organization of networks. Community discovery in networks has grabbed the attention of researchers from multi-discipline. Community detection problem has been modeled as an optimization problem. In broad-spectrum, existing community detection algorithms have adopted modularity as the optimizing function. However, the modularity is not able to identify communities of smaller size as compared to the size of the network.

Methods: This paper addresses the problem of the resolution limit posed by modularity. Modular density measure succeeds in countering the resolution limit problem. Finding network communities with maximum modular density is an NP-hard problem In this work, the discrete bat algorithm with modular density as the optimization function is recommended.

Results: Experiments are conducted on three real-world datasets. For determining the consistency, ten independent runs of the proposed algorithm has been carried out. The experimental results show that our proposed algorithm produces high-quality community structure along with small size communities.

Conclusion: The results are compared with traditional and evolutionary community detection algorithms. The final outcome shows the superiority of discrete bat algorithm with modular density as the optimization function with respect to number of communities, maximum modularity, and average modularity.

Keywords: Social network, community detection, evolutionary optimization, bat algorithm, modularity, modular density.

Graphical Abstract

[1]
J. Hopcroft, O. Khan, B. Kulis, and B. Selman, "“Natural Communities In Large Linked Networks,” In Proceedings Of The Ninth ACM SIGKDD International Conference On Knowledge Discovery And Data Mining", KDD, vol. 03, p. 541, 2003.
[2]
U. Brandes, D. Delling, M. Gaertler, R. Gorke, M. Hoefer, Z. Nikoloski, and D. Wagner, "On modularity clustering", IEEE Trans. Knowl. Data Eng., vol. 20, no. 2, pp. 172-188, 2008.
[http://dx.doi.org/10.1109/TKDE.2007.190689]
[3]
M.E.J. Newman, "Fast algorithm for detecting community structure in networks", Phys. Rev. E Stat. Nonlin. Soft Matter Phys.,. Vol. 69,no. 6 Pt 2, pp. 066133, 2004.
[http://dx.doi.org/10.1103/PhysRevE.69.066133] [PMID: 15244693]
[4]
Q. Cai, M. Gong, B. Shen, L. Ma, and L. Jiao, "Discrete particle swarm optimization for identifying community structures in signed social networks", Neural Netw., vol. 58, pp. 4-13, 2014.
[http://dx.doi.org/10.1016/j.neunet.2014.04.006] [PMID: 24856248]
[5]
D. Zhou, and X. Wang, "A neighborhood-impact based community detection algorithm via discrete PSO", Math. Probl. Eng., vol. 2016, pp. 1-15, 2016.
[http://dx.doi.org/10.1155/2016/3790590]
[6]
M.E.J. Newman, "Modularity and community structure in networks", Proc. Natl. Acad. Sci. USA, vol. 103, no. 23, pp. 8577-8582, 2006.
[http://dx.doi.org/10.1073/pnas.0601602103] [PMID: 16723398]
[7]
M. Tasgin, and H. Bingol, "Community detection in complex networks using genetic algorithm", Proc. Natl. Acad. Sci., . Vol. 103.2006, no. 23, pp. 8577-8582.
[8]
Z. Shi, Y. Liu, and J. Liang, "PSO-Based community detection in complex networks", 2009 Second International Symposium on Knowledge Acquisition and Modeling. Vol. 3, pp. 114-119. IEEE, 2009.
[http://dx.doi.org/10.1109/KAM.2009.195]
[9]
Y. Chen, and X. Qiu, Detecting community structures in social networks with particle swarm optimization.Front. Intern. Technol., Springer: Berlin, Heidelberg, pp. 266-275. 2013
[http://dx.doi.org/10.1007/978-3-642-53959-6_24]
[10]
A. Fallis, "An ant colony optimization method to detect communities in social networks", J. Chem. Inf. Model., vol. 53, no. 9, pp. 1689-1699, 2013.
[11]
R. Guimerà, and L.A.N. Amaral, "Functional cartography of complex metabolic networks", Nature, vol. 433, no. 7028, pp. 895-900, 2005.
[http://dx.doi.org/10.1038/nature03288] [PMID: 15729348]
[12]
J. Liu, and T. Liu, "Detecting community structure in complex networks using simulated annealing with k-means algorithms", Phys. A Stat. Mech. its Appl.,. Vol. 389, No. 11, pp. 2300-2309,2010.
[http://dx.doi.org/10.1016/j.physa.2010.01.042]
[13]
J. Kennedy, and R. Eberhart, "Particle swarm optimization", In: Proceedings of ICNN’95-International Conference on Neural Networks IEEE.. Vol.4, pp. 1942-1948,1995
[14]
J. Kennedy, and R.C. Eberhart, "A discrete binary version of the particle swarm algorithm", 1997 IEEE International conference on systems, man, and cybernetics. Computational cybernetics and simulation. Vol. 5, 1997, pp. 4104-4108
[http://dx.doi.org/10.1109/ICSMC.1997.637339]
[15]
Z. Li, S. Zhang, R.S. Wang, X.S. Zhang, and L. Chen, "Quantitative function for community detection ", Phys. Rev. E Stat.Nonlin. Soft Matter Phys.,. Vol. 77, no. 3 Pt 2, pp. 036109, 2008.
[http://dx.doi.org/10.1103/PhysRevE.77.036109] [PMID: 18517463]
[16]
X.S. Yang, "A new metaheuristic Bat-inspired Algorithm", Stud. Comput. Intell., vol. 284, pp. 65-74, 2010.
[17]
S. Mirjalili, "Dragonfly algorithm: A new meta-heuristic optimization technique for solving single-objective, discrete, and multi-objective problems", Neural Comput. Appl., vol. 27, no. 4, pp. 1053-1073, 2016.
[http://dx.doi.org/10.1007/s00521-015-1920-1]
[18]
S. Mirjalili, "The ant lion optimizer", Adv. Eng. Softw., vol. 83, pp. 80-98, 2015.
[http://dx.doi.org/10.1016/j.advengsoft.2015.01.010]
[19]
S. Mirjalili, S.M. Mirjalili, and X.S. Yang, "Binary bat algorithm", Neural Comput. Appl., vol. 25, pp. 1-19, 2013.
[20]
J. Holland, Adaptation in natural and artificial systems: an introductory analysis with application to biology., Control Artif. Intell, 1975.
[21]
P. Kora, and S.R. Kalva, "Improved Bat algorithm for the detection of myocardial infarction", Springerplus, vol. 4, no. 1, p. 666, 2015.
[http://dx.doi.org/10.1186/s40064-015-1379-7] [PMID: 26558169]
[22]
U.M. Salma, "A binary bat inspired algorithm for the classification of breast cancer data", Int. J. Soft Comput. Artif. Intell. Appl., vol. 53, no. 2, pp. 1-21, 2016.
[23]
X. Huang, X. Zeng, and R. Han, Dynamic inertia weight binary bat algorithm with neighborhood search.Comput. Intell. Neurosci, . Vol. 2017, 2017
[24]
E. Ali, H. Hussein, A. Hafez, A.E. Hassanien, and A. Fahmy, "A discrete bat algorithm for the community detection problem", Hyb. Arti. Intell. Syst., vol. 9121, pp. 188-199, 2015.
[25]
W. Chunyu, and P. Yun, Discrete bat algorithm and application in community detection., Open Cybernet. System. J., 2015, pp. 967-972.
[26]
A. Song, M. Li, X. Ding, W. Cao, and K. Pu, "Community detection using discrete bat algorithm", Int. J. Comput. Sci.. Vol. 43(1),pp.37-43, 2016.
[27]
M.E.J. Newman, "Fast algorithm for detecting community structure in networks", Phys. Rev. E.. Vol. 69. 2004, pp. 1-5
[28]
M.E.J. Newman, "Community detection and graph partitioning", EPL, vol. 103, p. 28003, 2013.
[http://dx.doi.org/10.1209/0295-5075/103/28003]
[29]
C. Pizzuti, "GA-Net: A genetic algorithm for community detection in social networks", In: Lect. Notes Comput. Sci. (including Subser.Lect. Notes Artif. Intell. Lect. Notes Bioinformatics). Vol. 5199 LNCS. 2008, pp. 1081-1090
[30]
W.W. Zachary, "An information flow model for conflict and fission in small groups", J. Anthropol. Res..Vol. 33, No. 4, pp. 452-473, 1977. Available from: , http://www.jstor.org/stable/3629752
[31]
M. Girvan, and M.E.J. Newman, "Community structure in social and biological networks", Proc. Natl. Acad. Sci. USA, vol. 99, no. 12, pp. 7821-7826, 2002.
[http://dx.doi.org/10.1073/pnas.122653799] [PMID: 12060727]

Rights & Permissions Print Cite
Article Metrics
3
© 2024 Bentham Science Publishers | Privacy Policy