Adaptive Nonparametric Community Detection - Larisa Adamyan; Kirill Efimov; Vladimir Spokoiny (Humboldt-Universität zu Berlin, International Research Training Group 1792 "High Dimensional Nonstationary Time Series", 2019)
Understanding the topological structure of real world networks is of huge interest in a variety of fields. One of the way to investigate this structure is to find the groups of densely connected nodes called communities. This paper presents a new non-parametric method of community detection in networks called Adaptive Weights Community Detection. The idea of the algorithm is to associate a local community for each node. On every iteration the algorithm tests a hypothesis that two nodes are in the same community by comparing their local communities. The test rejects the hypothesis if the density of edges between these two local communities is lower than the density inside each one. A detailed performance analysis of the method shows its dominance over state-of- the-art methods on well known artificial and real world benchmarks.
Keywords: C00; 330; Adaptive weights; Gap coefficient; Graph clustering; Nonparametric; Overlapping communities