Network community detection using modified modularity criterion

Authors

DOI:

https://doi.org/10.15587/1729-4061.2024.318452

Keywords:

Abstract

The object of this study is complex networks whose model is undirected weighted ordinary (without loops and multiple edges) graphs. The task to detect communities, that is, partition the set of network nodes into communities, has been considered. It is assumed that such communities should be non-overlapped. At present, there are many approaches to solving this task and, accordingly, many methods that implement it. Methods based on the maximization of the network modularity function have been considered. A modified modularity criterion (function) has been proposed. The value of this criterion explicitly depends on the number of nodes in the communities. The partition of network nodes into communities with maximization by such a criterion is significantly more prone to the detection of small communities, or even singleton-node communities. This property is a key characteristic of the proposed method and is useful if the network being analyzed really has small communities. In addition, the proposed modularity criterion is normalized with respect to the current number of communities. This makes it possible to compare the modularity of network partitions into different numbers of communities. This, in turn, makes it possible to estimate the number of communities that are formed, in cases when this number is not known a priori. A method for partitioning network nodes into communities based on the criterion of maximum modularity has been devised. The corresponding algorithm is suboptimal, belongs to the class of greedy algorithms, and has a low computational complexity – linear with respect to the number of network nodes. As a result, it is fast, so it can be used for network partitioning. The method devised for detecting network communities was tested on classic datasets, which confirmed the effectiveness of the proposed approach

Author Biographies

Vadim Shergin, Kharkiv National University of Radio Electronics

PhD, Associate Professor

Department of Artificial Intelligence

Sergiy Grinyov, Kharkiv National University of Radio Electronics

Department of Artificial Intelligence

Larysa Chala, Kharkiv National University of Radio Electronics

PhD, Associate Professor

Department of Artificial Intelligence

Serhii Udovenko, Simon Kuznets Kharkiv National University of Economics

Doctor of Technical Scienses, Professor

Department of Informatics and Computer Engineering

References

  1. Newman, M. E. J. (2003). Mixing patterns in networks. Physical Review E, 67 (2). https://doi.org/10.1103/physreve.67.026126
  2. Cinelli, M., Peel, L., Iovanella, A., Delvenne, J.-C. (2020). Network constraints on the mixing patterns of binary node metadata. Physical Review E, 102 (6). https://doi.org/10.1103/physreve.102.062310
  3. Hamdaqa, M., Tahvildari, L., LaChapelle, N., Campbell, B. (2014). Cultural scene detection using reverse Louvain optimization. Science of Computer Programming, 95, 44–72. https://doi.org/10.1016/j.scico.2014.01.006
  4. Girvan, M., Newman, M. E. J. (2002). Community structure in social and biological networks. Proceedings of the National Academy of Sciences, 99 (12), 7821–7826. https://doi.org/10.1073/pnas.122653799
  5. Pascual‐García, A., Bell, T. (2020). functionInk: An efficient method to detect functional groups in multidimensional networks reveals the hidden structure of ecological communities. Methods in Ecology and Evolution, 11 (7), 804–817. https://doi.org/10.1111/2041-210x.13377
  6. Newman, M. E. J. (2004). Detecting community structure in networks. The European Physical Journal B - Condensed Matter, 38 (2), 321–330. https://doi.org/10.1140/epjb/e2004-00124-y
  7. Karrer, B., Newman, M. E. J. (2011). Stochastic blockmodels and community structure in networks. Physical Review E, 83 (1). https://doi.org/10.1103/physreve.83.016107
  8. Cohen-Addad, V., Kosowski, A., Mallmann-Trenn, F., Saulpic, D. (2020). On the Power of Louvain in the Stochastic Block Model. Advances in Neural Information Processing Systems (NeurIPS 2020). Vancourer, 4055–4066. Available at: https://hal.science/hal-03140367
  9. Newman, M. E. J. (2006). Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103 (23), 8577–8582. https://doi.org/10.1073/pnas.0601602103
  10. Blondel, V. D., Guillaume, J.-L., Lambiotte, R., Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008 (10), P10008. https://doi.org/10.1088/1742-5468/2008/10/p10008
  11. Raskin, L., Sira, O. (2021). Devising methods for planning a multifactorial multilevel experiment with high dimensionality. Eastern-European Journal of Enterprise Technologies, 5 (4 (113)), 64–72. https://doi.org/10.15587/1729-4061.2021.242304
  12. Fortunato, S., Barthélemy, M. (2007). Resolution limit in community detection. Proceedings of the National Academy of Sciences, 104 (1), 36–41. https://doi.org/10.1073/pnas.0605965104
  13. Orgnet. Available at: http://www.orgnet.com/
  14. Piraveenan, M., Prokopenko, M., Zomaya, A. Y. (2012). On congruity of nodes and assortative information content in complex networks. Networks and Heterogeneous Media, 7 (3), 441–461. https://doi.org/10.3934/nhm.2012.7.441
  15. Shergin, V., Udovenko, S., Chala, L. (2020). Assortativity Properties of Barabási-Albert Networks. Data-Centric Business and Applications, 55–66. https://doi.org/10.1007/978-3-030-43070-2_4
  16. Shergin, V., Chala, L., Udovenko, S. (2019). Assortativity Properties of Scale-Free Networks. 2019 IEEE International Scientific-Practical Conference Problems of Infocommunications, Science and Technology (PIC S&T), 723–726. https://doi.org/10.1109/picst47496.2019.9061369
  17. Shergin, V., Chala, L., Udovenko, S., Pohurska, M. (2018). Assortativity of an elastic network with implicit use of information about nodes degree. CEUR Workshop Proceedings, 131–140. Available at: https://ceur-ws.org/Vol-3018/Paper_12.pdf
  18. Noldus, R., Van Mieghem, P. (2015). Assortativity in complex networks. Journal of Complex Networks, 3 (4), 507–542. https://doi.org/10.1093/comnet/cnv005
  19. Network data. Available at: https://public.websites.umich.edu/~mejn/netdata/
Network community detection using modified modularity criterion

Downloads

Published

2024-12-27

How to Cite

Shergin, V., Grinyov, S., Chala, L., & Udovenko, S. (2024). Network community detection using modified modularity criterion. Eastern-European Journal of Enterprise Technologies, 6(4 (132), 6–13. https://doi.org/10.15587/1729-4061.2024.318452

Issue

Vol. 6 No. 4 (132) (2024): Mathematics and Cybernetics - applied aspects

Section

Mathematics and Cybernetics - applied aspects

License

Copyright (c) 2024 Vadim Shergin, Sergiy Grinyov, Larysa Chala, Serhii Udovenko

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.