|
This article is cited in 6 scientific papers (total in 6 papers)
Algorithms and Software
Game-theoretic methods for finding communities in academic Web
N. A. Ermolina, V. V. Mazalovb, A. A. Pechnikovb a Petrozavodsk State University (PetrSU)
b Institute of Applied Mathematical Research Karelian Research Centre of Russian Academy of Science
Abstract:
We consider the problem of community detection for the graph which is a fragment of the academic Web. The nodes of the graph are the sites of the scientific organizations, and its arcs are hyperlinks. We propose a new approach based on the methods of coalition game theory to derive the Nash-stable coalition partition. This is determined by a function of preferences for any pair of vertices in the graph. The problem of finding a stable partition is connected with finding a maximum of potential function. The algorithm for searching stable partitioning and evaluating its complexity is presented. The proposed method was compared with two well-known methods of finding communities. The efficiency of the new method is demonstrated on the fragment of the Web which consists of the official sites of the Siberian and Far East branches of RAS.
Keywords:
web space; graph; community; modularity; coalition game theory.
Citation:
N. A. Ermolin, V. V. Mazalov, A. A. Pechnikov, “Game-theoretic methods for finding communities in academic Web”, Tr. SPIIRAN, 55 (2017), 237–254
Linking options:
https://www.mathnet.ru/eng/trspy984 https://www.mathnet.ru/eng/trspy/v55/p237
|
Statistics & downloads: |
Abstract page: | 205 | Full-text PDF : | 68 |
|