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
General Research Article

A New Method for Community Detection in the Complex Network on the Basis of Similarity

Author(s): Munawar Hussain* and Awais Akram

Volume 15, Issue 2, 2022

Published on: 31 August, 2020

Page: [256 - 265] Pages: 10

DOI: 10.2174/2666255813999200831104857

Price: $65

Abstract

Introduction: Regarding complex network, to find optimal communities in the network has become a key topic in the field of network theory. It is crucial to understand the structure and functionality of associated networks. In this paper, we propose a new method of community detection that works on the Structural Similarity of a Network (SSN).

Methods: This method works in two steps, in the first step, it removes edges between the different groups of nodes which are not very similar to each other. As a result of edge removal, the network is divided into many small random communities, which are referred to as main communities.

Results: In the second step, we apply the Evaluation Method (EM), it chooses the best quality communities, from all main communities which are already produced in the first step. Lastly, we apply evaluation metrics to our proposed method and benchmarking methods, which show that the SSN method can detect comparatively more accurate results than other methods in this paper.

Discussion: This approach is defined on the basis of the unweighted network, so in further research, it could be used on weighted networks and can explore some new deep-down attributes. Furthermore, it will be used for Facebook and twitter weighted data with the artificial intelligence approach.

Conclusion: In this article, we proposed a novel method for community detection in networks, called Structural Similarity of Network (SSN). It works in two steps. In the first step, it randomly removes low similarity edges from the network, which makes several small disconnected communities, called as main communities. Afterward, the main communities are merged to search for the final communities, which are near to actual existing communities of the network.

Keywords: Community detection, complex network, normalized mutual information, modularity, SSN, commerece.

Graphical Abstract

[1]
J.P. Onnela, J. Saramäki, J. Hyvönen, G. Szabó, D. Lazer, K. Kaski, J. Kertész, and A.L. Barabási, "Structure and tie strengths in mobile communication networks", Proceedings of the National Academy of Sciences, vol. 104, no. 18, pp. 7332-7336, 2007.
[http://dx.doi.org/10.1073/pnas.0610245104] [PMID: 17456605]
[2]
M.E. Newman, "The structure of scientific collaboration networks", Proceedings of the National Academy of Sciences, vol. 98, no. 2, pp. 404-409, 2001.
[http://dx.doi.org/10.1073/pnas.98.2.404] [PMID: 11149952]
[3]
J. Chen, and B. Yuan, "Detecting functional modules in the yeast protein-protein interaction network", Bioinformatics, vol. 22, no. 18, pp. 2283-2290, 2006.
[http://dx.doi.org/10.1093/bioinformatics/btl370] [PMID: 16837529]
[4]
M. Girvan, and M.E. Newman, "Community structure in social and biological networks", Proceedings of the National Academy of Sciences, vol. 99, no. 12, pp. 7821-7826, 2002.
[http://dx.doi.org/10.1073/pnas.122653799] [PMID: 12060727]
[5]
V.D. Blondel, J.L. Guillaume, R. Lambiotte, and E. Lefebvre, "Fast unfolding of communities in large networks", J. Stat. Mech. Theory Exp., vol. 2008, no. 10, p. 10008, 2008.
[http://dx.doi.org/10.1088/1742-5468/2008/10/P10008]
[6]
S. Fortunato, "Community detection in graphs", Phys. Rep., vol. 486, no. 3, pp. 75-174, 2010.
[http://dx.doi.org/10.1016/j.physrep.2009.11.002]
[7]
M.T. Schaub, J.C. Delvenne, M. Rosvall, and R. Lambiotte, "The many facets of community detection in complex networks", Appl. Netw. Sci., vol. 2, no. 1, p. 4, 2017.
[http://dx.doi.org/10.1007/s41109-017-0023-6] [PMID: 30533512]
[8]
M. E. Newman, and M. Girvan, "Finding and evaluating community structure in networks", Phys. Rev. E Stat. Nonlin. Soft Matter. Phys., vol. 69, no. 2(2), pp. 026113-2004, 2004.
[http://dx.doi.org/10.1103/PhysRevE.69.026113] [PMID: 14995526]
[9]
J. Camacho, A. Pérez-Villegas, P. García-Teodoro, and G. Maciá-Fernández, "PCA-based multivariate statistical network monitoring for anomaly detection", Comput. Secur., vol. 59, pp. 118-137, 2016.
[10]
T. Wang, L. Yin, and X. Wang, "A community detection method based on local similarity and degree clustering information", Physica A, vol. 490, pp. 1344-1354, 2018.
[http://dx.doi.org/10.1016/j.physa.2017.08.090]
[11]
C. Piccardi, "Finding and testing network communities by lumped Markov chains", PLoS One, vol. 6, no. 11, p. 27028, 2011.
[http://dx.doi.org/10.1371/journal.pone.0027028] [PMID: 22073245]
[12]
D. Jin, B. Yang, C. Baquero, D. Liu, D. He, and J. Liu, "A Markov random walk under constraint for discovering overlapping communities in complex networks", J. Stat. Mech. Theory Exp., vol. 2011, no. 05, p. 05031, 2011.
[http://dx.doi.org/10.1088/1742-5468/2011/05/P05031]
[13]
J. Reichardt, and S. Bornholdt, "Statistical mechanics of community detection", Phys. Rev. E Stat. Nonlin. Soft Matter Phys., vol. 74, no. 1(2), p. 016110, 2006.
[http://dx.doi.org/10.1103/PhysRevE.74.016110] [PMID: 16907154]
[14]
B. Karrer, and M. E. Newman, "Stochastic blockmodels and community structure in networks", Phys. Rev. E Stat. Nonlin. Soft Matter. Phys., vol. 83, no. 1(2), p. 016107, 2011.
[http://dx.doi.org/10.1103/PhysRevE.83.016107] [PMID: 21405744]
[15]
J.P. Bagrow, "Evaluating local community methods in networks", J. Stat. Mech. Theory Exp., vol. 2008, no. 05, p. 05001, 2008.
[http://dx.doi.org/10.1088/1742-5468/2008/05/P05001]
[16]
M. Arab, and M. Afsharchi, "Community detection in social networks using hybrid merging of sub-communities", J. Netw. Comput. Appl., vol. 40, pp. 73-84, 2014.
[http://dx.doi.org/10.1016/j.jnca.2013.08.008]
[17]
B. Saoud, and A. Moussaoui, "Community detection in networks based on minimum spanning tree and modularity", Physica A, vol. 460, pp. 230-234, 2016.
[http://dx.doi.org/10.1016/j.physa.2016.05.014]
[18]
W. Li, C. Huang, M. Wang, and X. Chen, "Stepping community detection algorithm based on label propagation and similarity", Physica A, vol. 472, pp. 145-155, 2017.
[http://dx.doi.org/10.1016/j.physa.2017.01.030]
[19]
W.W. Zachary, "An information flow model for conflict and fission in small groups", J. Anthropol. Res., vol. 33, pp. 452-473, 1977.
[http://dx.doi.org/10.1086/jar.33.4.3629752]
[20]
M. E. J. Newman, Mark Newman’s network data collection, 2016.
[21]
L. Danon, A. Diaz-Guilera, J. Duch, and A. Arenas, "Comparing community structure identification", J. Statist. Mech. Theory Exp., vol. 2005, no. 09, p. 09008, 2005.
[http://dx.doi.org/10.1088/1742-5468/2005/09/P09008]
[22]
M. Stojcic, and A. Stjepanovic, "ANFIS model for the prediction of generated electricity of photovoltaic modules", Decis. Mak. Appl. Manag. Eng., vol. 2, no. 1, pp. 35-48, 2019.
[23]
S. Sremac, I. Tanackov, M. Kopic, and D. Radovic, "ANFIS model for determining the economic order quantity", Decision Making: Applications in Management and Engineering, vol. 1, no. 2, pp. 81-92, 2018.
[http://dx.doi.org/10.31181/dmame1802079s]
[24]
G. Salton, and M. J. McGill, Introduction to Modern Information Retrieval., MuGraw–Hill: New York, 1983.
[25]
P. Jaccard, "Étude comparative de la distribution florale dans une portion des alpes et des jura", Bulletin De La Societe Vaudoise Des Science Naturelles, vol. 37, pp. 547-579, 1901.
[26]
L. Lü, and T. Zhou, "Link prediction in complex networks: A survey", Physica A, vol. 390, no. 6, pp. 1150-1170, 2011.
[http://dx.doi.org/10.1016/j.physa.2010.11.027]
[27]
T. J. Srensen, "A method of establishing groups of equal amplitude in plant sociology based on similarity of species content and its application to analyses of the vegetation on Danish commons", Videnski Selsk Biol. Skr., vol. 5, 1948.
[28]
E. Ravasz, A.L. Somera, D.A. Mongru, Z.N. Oltvai, and A.L. Barabási, "Hierarchical organization of modularity in metabolic networks", Science, vol. 297, no. 5586, pp. 1551-1555, 2002.
[http://dx.doi.org/10.1126/science.1073374] [PMID: 12202830]
[29]
A.L. Barabasi, and R. Albert, "Emergence of scaling in random networks", Science, vol. 286, no. 5439, pp. 509-512, 1999.
[http://dx.doi.org/10.1126/science.286.5439.509] [PMID: 10521342]
[30]
L. Adamic, and E. Adar, "Friends and neighbors on the web", Soc. Networks, vol. 25, no. 3, pp. 211-230, 2003.
[http://dx.doi.org/10.1016/S0378-8733(03)00009-1]
[31]
T. Zhou, L. Lü, and Y.C. Zhang, "Predicting missing links via local information", Eur. Phys. J. B, vol. 71, p. 623, 2009.
[http://dx.doi.org/10.1140/epjb/e2009-00335-8]

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