Large-scale community detection based on a new dissimilarity measure

被引：7

作者：

Asmi K. ^{[1
]}

Lotfi D. ^{[1
]}

El Marraki M. ^{[1
]}

机构：

[1] LRIT, Associated Unit to CNRST (URAC No 29)-Faculty of Sciences, Mohammed V University in Rabat, B.P.1014 RP, Rabat

来源：

Social Network Analysis and Mining | 2017年 / 7卷 / 01期

关键词：

Clustering coefficient; Community detection; Modularity; Normalized mutual information; Social network; Unweighted graph;

D O I：

10.1007/s13278-017-0436-3

中图分类号：

学科分类号：

摘要：

The process of the community reveal has become such a major problem in different fields, in particular for the social networks that have seen a growth over the last decade. Diverse ways of several methods have been proposed to resolve this inference problem. Nevertheless, the computational run time and the used space become a real handicap especially, when the networks are large. In this paper, we introduce a new approach of community detection that relies greatly on a new dissimilarity measure which allows to find the edges having more tendency to be between two communities. Then, we suppress them to have some preliminary communities. After that, we merge the induced subgraphs without using the modularity optimization to avoid its resolution limit. Finally, we evaluate our proposed method on real and artificial networks. The experiments show that our way of detecting communities outperforms or as effective as the existing algorithms (CNM, WalkTrap, InfoMap) while the used space and time complexity are better. © 2017, Springer-Verlag Wien.

引用

共 18 条

[1]

Aggarwal C.C., Xie Y., Philip S.Y., Towards community detection in locally heterogeneous networks, SDM, Jan, 2011, pp. 391-402, (2008)

[2]

Arab M., Afsharchi M., Community detection in social networks using hybrid merging of sub-communities, J Netw Comput Applic, 40, pp. 73-84, (2014)

[3]

Basuchowdhuri P., Anand S., Srivastava D.R., Mishra K., Saha S.K., Detection of communities in social networks using spanning tree, Adv Comput Netw Inf, 2, pp. 589-597, (2014)

[4]

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

[5]

Chen M., Kuzmin K., Szymanski B.K., Community detection via maximization of1 modularity and its variants, IEEE Trans Comput Soc Syst, 1, 1, pp. 46-65, (2014)

[6]

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

[7]

Donetti L., Detecting network communities: a new systematic and efficient algorithm, J Stat Mech Theory Exp, 2004, 10, (2004)

[8]

Fortunato S., Barthelemy M., Resolution limit in community detection, Proc Natl Acad Sci, 104, 1, pp. 36-41, (2007)

[9]

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

[10]

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

← 1 2 →