The maximum likelihood method for detecting communities in communication networks

V. V. Mazalov   ; N. N. Nikitina

Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, Tome 14 (2018) no. 3, pp. 200-214

Résumé

The community detection in social and communication networks is an important problem in many applied fields: biology, sociology, social networks. This is especially true for networks that are represented by large graphs. In this paper, we propose a method for community detection based on the maximum likelihood method for the random formation of a network with given parameters of the tightness of connections within the community and between different communities. A numerical algorithm for finding the maximum of the objective function over all possible network partitions is described. The algorithm is implemented and tested on real networks of small dimension.

Détail

Keywords: network communities, detecting communities in a network, maximum likelihood method, Gibbs sampling.

Bibliographie

[1] Freeman L. C., “A set of measures of centrality based on betweenness”, Sociometry, 40 (1977), 35–41 | DOI

[2] Levin D. A., Peres Y., Markov chains and mixing times, Amer. Mathematical Soc., Providence, Rhode Island, 2017, 447 pp. | MR | Zbl

[3] Page L., Brin S., Motwani R., Winograd T., The PageRank citation ranking: Bringing order to the web, technical report, Stanford InfoLab, Stanford, 1998, 17 pp. | Zbl

[4] Pons P., Latapy M., “Computing communities in large networks using random walks”, Journal of Graph Algorithms and Applications, 10:2 (2006), 191–218 | DOI | MR | Zbl

[5] Avrachenkov K. E., Mazalov V. V., Tsynguev B. T., “Beta current flow centrality for weighted networks”, Proceedings of CSoNET-2015, LNCS, 9197, 2015, 216–227

[6] Brandes U., Fleischer D., “Centrality measures based on current flow”, Proceedings of the 22nd annual conference on Theoretical Aspects of Computer Science, 2005, 533–544 | MR | Zbl

[7] Mazalov V., Tsynguev B., “Kirchhoff centrality measure for collaboration network”, CSoNet-2016, LNCS, 9795, 2016, 147–157

[8] Bogomolnaia A., Jackson M. O., “The stability of hedonic coalition structures”, Games and Economic Behavior, 38:2 (2002), 201–230 | DOI | MR | Zbl

[9] Mazalov V. V., Avrachenkov K. E., Trukhina L. I., Tsynguev B. T., “Game-theoretic centrality measures for weighted graphs”, Fundamenta Informaticae, 145:3 (2016), 341–358 | DOI | MR | Zbl

[10] Fortunato S., Barthelemy M., “Resolution limit in community detection”, Proceedings of the National Academy of Sciences USA, 104:1 (2007), 36–41 | DOI | MR

[11] Girvan M., Newman M. E. J., “Community structure in social and biological networks”, Proceedings of the National Academy of Sciences USA, 99:12 (2002), 7821–7826 | DOI | MR | Zbl

[12] Fortunato S., “Community detection in graphs”, Physics Reports, 486:3 (2010), 75–174 | DOI | MR

[13] Zachary W. W., “An information flow model for conflict and fission in small groups”, Journal of Anthropological Research, 33:4 (1977), 452–473 | DOI

[14] Jackson M. O., Social and economic networks, Princeton University Press, Princeton, 2010, 520 pp. | MR | Zbl

[15] Kaur R., Singh S., “A survey of data mining and social network analysis based anomaly detection techniques”, Egypt Inf. Journal, 17:2 (2016), 199–216 | MR

[16] Newman M. E., Girvan M., “Finding and evaluating community structure in networks”, Physical Review E, 69:2 (2004), 026113 | DOI | MR

[17] Meila M., Shi J., “A Random walks view of spectral segmentation”, Proceedings of AISTATS, 2001, 1–6 | MR

[18] Myerson R. B., “Graphs and cooperation in games”, Math. Oper. Res., 2 (1977), 225–229 | DOI | MR | Zbl

[19] Avrachenkov K., Kondratev A., Mazalov V., “Cooperative Game Theory approaches for network partitioning”, Computing and Combinatorics, COCOON 2017, LNCS, 10392, eds. Y. Cao, J. Chen, 2017, 591–603 | MR

[20] Copic J., Jackson M., Kirman A., “Identifying community structures from network data via maximum likelihood methods”, The B. E. Journal of Theoretical Economics, 9:1 (2009), 1635–1704 | DOI | MR

[21] Mathematica Online, , Wolfram Research, Inc., Champaign, IL., 2018 www.wolfram.com | MR

[22] Vinh N. X., Epps J., Bailey J., “Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance”, Journal of Machine Learning Research, 11 (2010), 2837–2854 | MR | Zbl

[23] Kvalseth T. O., “Entropy and correlation: Some comments”, IEEE Transactions on Systems, Man and Cybernetics, 17:3 (1987), 517–519 | DOI | MR

[24] Strehl A., Ghosh J., “Cluster ensembles – a knowledge reuse framework for combining multiple partitions”, Journal of Machine Learning Research, 3 (2002), 583–617 | MR

[25] Hubert L., Arabie P., “Comparing partitions”, Journal of Classification, 2:1 (1985), 193–218 | DOI

[26] Steinley D., “Properties of the Hubert-Arabie adjusted Rand index”, Psychol. Methods, 9:3 (2004), 386–396 | DOI

[27] Lusseau D., Schneider K., Boisseau O. J. et al., “The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations”, Behav. Ecol. Sociobiol., 54 (2003), 396–405 | DOI