Community Detection in Social Networks: Relating the Louvain Method to Centrality Measures

• Victoria P. S. Aires UFAM
• Fabiola G. Nakamura UFAM

Abstract

In this project, the focus is on algorithms for the problem of detecting communities in social networks, especially the Louvain method. The goal is to relate the method to the concepts of centrality measures in complex networks, proposing their use to modify the greedy criterion of the method and verifying if this change increases the quality of the communities found. We showed that the construction of communities from the less central vertices improved the quality of communities obtained by the method in large and sparse networks, but did not bring significant gains in small and dense networks.

References

Bedi, P. and Sharma, C. (2016). Community detection in social networks. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 6(3):115–135.

Blondel, V. D., Guillaume, J.-L., Lambiotte, R., and Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008(10):P10008.

Brandes, U., Delling, D., Gaertler, M., Görke, R., Hoefer, M., Nikoloski, Z., and Wagner, D. (2007). On finding graph clusterings with maximum modularity. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 121–132. Springer.

Clauset, A., Newman, M. E., and Moore, C. (2004). Finding community structure in very large networks. Physical review E, 70(6):066111.

Dehmer, M. and Emmert-Streib, F. (2009). Analysis of complex networks: from biology to linguistics. John Wiley & Sons.

Gehrke, J., Ginsparg, P., and Kleinberg, J. (2003). Overview of the 2003 kdd cup. ACM SIGKDD Explorations Newsletter, 5(2):149–151.

Girvan, M. and Newman, M. E. (2002). Community structure in social and biological networks. Proceedings of the national academy of sciences, 99(12):7821–7826.

Hofstad, R. V. D. (2016). Random graphs and complex networks, volume 1. Cambridge University Press.

Knuth, D. E. (1993). The Stanford GraphBase: a platform for combinatorial computing, volume 37. Addison-Wesley Reading.

Leskovec, J. and Mcauley, J. J. (2012). Learning to discover social circles in ego networks. In Advances in neural information processing systems, pages 539–547.

Motta, R., de Alneu Andrade Lopes, and de Oliveira, M. C. F. (2009). Centrality measures from complex networks in active learning. In International Conference on Discovery Science, pages 184–196. Springer.

Odent, J. and Saint-Guillain, M. (2012). Automatic detection of community structure in networks. Technical report, Université catholique de Louvain.

Özturk, K. (2014). Community detection in social networks. PhD thesis, Middle East Technical University.

Perra, N. and Fortunato, S. (2008). Spectral centrality measures in complex networks. Physical Review E, 78(3):036107.

Scholz, M. (2009). Node degree distribution. Disponível em: [link]. Acessado em: 01/2017.

Scott, J. and Carrington, P. J. (2011). The SAGE handbook of social network analysis. SAGE publications.

Shen, H.-W. (2013). Community structure of complex networks. Springer Science & Business Media.

Zachary, W. W. (1977). An information flow model for conflict and fission in small groups. Journal of anthropological research, 33(4):452–473.