About Modularity Properties and Actual Adjustments of the
Blondel Algorithm

doi:DOI 10.25205/1818-7900-2017-15-3-64-73

Novosibirsk State University Journal of Information Technologies
Scientic Journal
ISSN 2410-0420 (Online), ISSN 1818-7900 (Print)

Switch to
Russian

All Issues >> Contents: Volume 15, Issue No 3 (2017)

About Modularity Properties and Actual Adjustments of the Blondel Algorithm
A. O. Orlov, A. A. Chepovskiy

National Research University "Higher School of Economics"

DOI: DOI 10.25205/1818-7900-2017-15-3-64-73
UDC code: 004.421.2:519.178

Abstract
One of the tasks related to the study of the of complex networks is the task of revealing communities structure – splitting all vertices into groups (communities), so that the vertices of each group are more closely related to each other than to the rest of the graph. A popular algorithm for detecting communities is the Blondel, based on the maximization of Newman-Girvan modularity, a common criterion for assessing the quality of community divisions. This article is devoted to the analysis of its features and work results, as well as possible modifications. The test results are analyzed both on the generated graphs and on real data.

Key Words
graph structure, social network analysis, community detection, big data

How to cite:
Orlov A. O., Chepovskiy A. A. About Modularity Properties and Actual Adjustments of the Blondel Algorithm // Vestnik NSU Series: Information Technologies. - 2017. - Volume 15, Issue No 3. - P. 64–73. - DOI 10.25205/1818-7900-2017-15-3-64-73. - ISSN 1818-7900. (in Russian).

Full Text in Russian

Available in PDF

References
1. Girvan M., Newman M. E. J. Community structure in social and biological networks // Proc. Natl. Acad. Sci. USA. 2002. Vol. 99, № 12. P. 7821–7826.
2. Newman M. E. J., Girvan M. Finding and evaluating community structure in networks // Physical Review. E 69. 2004. Р. 026113.
3. Newman M. E. J. Modularity and community structure in networks // Proc. Natl. Acad. Sci. USA. 2006. Vol. 103, № 23. P. 8577–8582.
4. Brandes U., Delling D., Gaertler M., Goerke R., Hoefer M., Nikoloski Z., Wagner D. Maximizing Modularity is hard // arXiv:physics/0608255. 2006.
5. Blondel V., Guillaume J., Lambiotte R., Lefebvre E. Fast unfolding of communities in large networks // Journal of Statistical Mechanics: Theory and Experiment. 2008. Vol. 10. P. 10008.
6. Dugue N., Perez A. Directed Louvain: maximizing modularity in directed networks. Research Report. Uni. d`Orleans Press, 2015.
7. Fortunato S., Barthélemy M. Resolution limit in community detection // Proc. Natl. Acad. Sci. USA. 2007. Vol. 104. № 36.
8. Lancichinetti A., Fortunato S. Benchmark graphs for testing community detection algorithms // Physical Review. E 78. 2008. Р. 046110.
9. Danon L., Duch J., Diaz-Guilera A., Arenas A. Comparing community structure identification // arXiv:cond-mat/0505245. 2005.

Publication information
Main title Vestnik NSU Series: Information Technologies, Volume 15, Issue No 3 (2017).
Parallel title: Novosibirsk State University Journal of Information Technologies Volume 15, Issue No 3 (2017).

Key title: Vestnik Novosibirskogo gosudarstvennogo universiteta. Seriâ: Informacionnye tehnologii
Abbreviated key title: Vestn. Novosib. Gos. Univ., Ser.: Inf. Tehnol.
Variant title: Vestnik NGU. Seriâ: Informacionnye tehnologii

Year of Publication: 2017
ISSN: 1818-7900 (Print), ISSN 2410-0420 (Online)
Publisher: Novosibirsk State University Press
DSpace handle