NETWORK COMMUNITY DETECTION USING MODIFIED MODULARITY CRITERION.

Shergin, Vadim; Larysa Chala, Sergiy Grinyov; Udovenko, Serhii

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.

GREEDY algorithms; COMPUTATIONAL complexity; SOCIAL problems; ALGORITHMS; A priori

Eastern-European Journal of Enterprise Technologies, 2024, Vol 132, Issue 4, p6

1729-3774

Academic Journal

10.15587/1729-4061.2024.318452