Humboldt-Universität zu Berlin - High Dimensional Nonstationary Time Series

IRTG1792DP2019 006

Adaptive Nonparametric Community Detection

Larisa Adamyan
Kirill Efimov
Vladimir Spokoiny

Abstract:
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:
Adaptive weights, Gap coefficient, Graph clustering, Nonparametric, Overlapping
communities

JEL Classification:
C00