Step-by-step community detection in volume-regular graphs

Description

Spectral techniques have proved amongst the most effective approaches to graph clustering. However, in general they require explicit computation of the main eigenvectors of a suitable matrix (usuallythe Laplacian matrix of the graph).Recent work (e.g., Becchetti et al., SODA 2017) suggests that observing the temporal evolutionof the power method applied to an initial random vector may, at least in some cases, provide enoughinformation on the space spanned by the first two eigenvectors, so as to allow recovery of a hiddenpartition without explicit eigenvector computations. While the results of Becchetti et al. applyto perfectly balanced partitions and/or graphs that exhibit very strong forms of regularity, weextend their approach to graphs containing a hiddenkpartition and characterized by a milderform of volume-regularity. We show that the class ofk-volume regulargraphs is the largest class ofundirected (possibly weighted) graphs whose transition matrix admitsk"stepwise" eigenvectors (i.e.,vectors that are constant over each set of the hidden partition). To obtain this result, we highlight aconnection between volume regularity and lumpability of Markov chains. Moreover, we prove that ifthe stepwise eigenvectors are those associated to the firstkeigenvalues and the gap between thek-th and the (k+1)-th eigenvalues is sufficiently large, theAveragingdynamics of Becchetti et al.recovers the underlying community structure of the graph in logarithmic time, with high probabil

Abstract

International audience

Additional details