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 (usually the Laplacian matrix of the graph). Recent work (e.g., Becchetti et al., SODA 2017) suggests that observing the temporal evolution of the power method applied to an initial random vector may, at least in some cases, provide enough information on the space spanned by the first two eigenvectors, so as to allow recovery of a hidden partition without explicit eigenvector computations. While the results of Becchetti et al. apply to perfectly balanced partitions and/or graphs that exhibit very strong forms of regularity, we extend their approach to graphs containing a hidden k partition and characterized by a milder form of volume-regularity. We show that the class of k-volume regular graphs is the largest class of undirected (possibly weighted) graphs whose transition matrix admits k “stepwise” eigenvectors (i.e., vectors that have constant entries over the components corresponding to the same set of the hidden partition). To obtain this result, we highlight a connection between volume regularity and lumpability of Markov chains. Moreover, we prove that if the stepwise eigenvectors are those associated to the first k largest eigenvalues of the transition matrix of a random walk on the graph and the gap between the k-th and the (k+1)-th eigenvalues is sufficiently large, the AVERAGING dynamics of Becchetti et al. recovers the underlying community structure of the graph in logarithmic time, with high probability.

Step-by-step community detection in volume-regular graphs / Becchetti, L.; Cruciani, E.; Pasquale, F.; Rizzo, S.. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 847:(2020), pp. 49-67. [10.1016/j.tcs.2020.09.036]

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

Becchetti L.
;
2020

Abstract

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 (usually the Laplacian matrix of the graph). Recent work (e.g., Becchetti et al., SODA 2017) suggests that observing the temporal evolution of the power method applied to an initial random vector may, at least in some cases, provide enough information on the space spanned by the first two eigenvectors, so as to allow recovery of a hidden partition without explicit eigenvector computations. While the results of Becchetti et al. apply to perfectly balanced partitions and/or graphs that exhibit very strong forms of regularity, we extend their approach to graphs containing a hidden k partition and characterized by a milder form of volume-regularity. We show that the class of k-volume regular graphs is the largest class of undirected (possibly weighted) graphs whose transition matrix admits k “stepwise” eigenvectors (i.e., vectors that have constant entries over the components corresponding to the same set of the hidden partition). To obtain this result, we highlight a connection between volume regularity and lumpability of Markov chains. Moreover, we prove that if the stepwise eigenvectors are those associated to the first k largest eigenvalues of the transition matrix of a random walk on the graph and the gap between the k-th and the (k+1)-th eigenvalues is sufficiently large, the AVERAGING dynamics of Becchetti et al. recovers the underlying community structure of the graph in logarithmic time, with high probability.
2020
Community detection; Distributed algorithms; Markov chains; Spectral analysis
01 Pubblicazione su rivista::01a Articolo in rivista
Step-by-step community detection in volume-regular graphs / Becchetti, L.; Cruciani, E.; Pasquale, F.; Rizzo, S.. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 847:(2020), pp. 49-67. [10.1016/j.tcs.2020.09.036]
File allegati a questo prodotto
File Dimensione Formato  
Becchetti_preprint_Step-by-step_2020.pdf

accesso aperto

Note: https://doi.org/10.1016/j.tcs.2020.09.036
Tipologia: Documento in Pre-print (manoscritto inviato all'editore, precedente alla peer review)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 340.96 kB
Formato Adobe PDF
340.96 kB Adobe PDF
Becchetti_Step-by-step_2020.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 560.88 kB
Formato Adobe PDF
560.88 kB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1463343
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 3
social impact