Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
A New Randomized Algorithm for Community Detection in Large Networks. / Kirianovskii, Ilia; Granichin, Oleg; Proskurnikov, Anton.
в: IFAC Proceedings Volumes (IFAC-PapersOnline), Том 49, № 13, 2016, стр. 31-35.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - A New Randomized Algorithm for Community Detection in Large Networks
AU - Kirianovskii, Ilia
AU - Granichin, Oleg
AU - Proskurnikov, Anton
PY - 2016
Y1 - 2016
N2 - The problem of community detection role in analysis of complex large-scale networks and behavioral and engineering sciences. Examples of sue clustering) in graphs plays an important big data structures, arising in natural works include, but are not limited World Wide Web (WWW) and Internet, social networks, ecological networks and food webs, cellular and molecular ensembles. A community (or a module) in a graph is a subset of its nodes, whose members are "densely" connected to each other yet have relatively few connections with nodes outside this subset. A number of algorithms to subdivide the nodes of large scale graphs into communities have recently been proposed; Many of them Hint for the graph's partitions of maximal modularity. One of the most, efficient, graph clustering algorithms of this type is the Multi-Level Aggregation (or "Louvain") method. In this paper, a randomized counterpart of this algorithm is proposed, which provides a comparable "quality" of graph's clustering, being however much faster on huge graphs. We demonstrate the efficiency of our algorithm, comparing its performance On several "benchmark" large-scale graphs with existing methods. (C) 2016, IFAC (International Federation of Automatic Control) Hosting by Elsevier Ltd. All rights reserved.
AB - The problem of community detection role in analysis of complex large-scale networks and behavioral and engineering sciences. Examples of sue clustering) in graphs plays an important big data structures, arising in natural works include, but are not limited World Wide Web (WWW) and Internet, social networks, ecological networks and food webs, cellular and molecular ensembles. A community (or a module) in a graph is a subset of its nodes, whose members are "densely" connected to each other yet have relatively few connections with nodes outside this subset. A number of algorithms to subdivide the nodes of large scale graphs into communities have recently been proposed; Many of them Hint for the graph's partitions of maximal modularity. One of the most, efficient, graph clustering algorithms of this type is the Multi-Level Aggregation (or "Louvain") method. In this paper, a randomized counterpart of this algorithm is proposed, which provides a comparable "quality" of graph's clustering, being however much faster on huge graphs. We demonstrate the efficiency of our algorithm, comparing its performance On several "benchmark" large-scale graphs with existing methods. (C) 2016, IFAC (International Federation of Automatic Control) Hosting by Elsevier Ltd. All rights reserved.
KW - Networked systems
KW - distributed parameter systems
KW - sequential learning
KW - IDENTIFICATION
KW - ORGANIZATION
KW - MODULARITY
U2 - 10.1016/j.ifacol.2016.07.922
DO - 10.1016/j.ifacol.2016.07.922
M3 - статья
VL - 49
SP - 31
EP - 35
JO - IFAC-PapersOnLine
JF - IFAC-PapersOnLine
SN - 2405-8963
IS - 13
Y2 - 29 June 2016 through 1 July 2016
ER -
ID: 7608583