Emilio Cruciani
(Universitaet Salzburg)

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

Venerdi' 09 Aprile 2021 ORE 15:00

Dipartimento di Matematica e Fisica
Universita' degli Studi Roma Tre


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. Based on a joint work with Luca Becchetti, Francesco
Pasquale, and Sara Rizzo. Link to the paper:
https://arxiv.org/abs/1907.07149

Per partecipare al Seminario cliccare sul seguente Link:
https://teams.microsoft.com/dl/launcher/launcher.html?url=%2F_%23%2Fl%2Fmeetup-join%2F19%3A388bb369590943489346c5edc8bb7b83%40thread.tacv2%2F1616503317900%3Fcontext%3D%257b%2522Tid%2522%253a%2522ffb4df68-f464-458c-a546-00fb3af66f6a%2522%252c%2522Oid%2522%253a%25220403197b-0405-4fee-b33b-ddfb43c6b8a1%2522%257d%26anon%3Dtrue&type=meetup-join&deeplinkId=eae4ec5d-f8ce-46a9-a036-1e06c82809ae&directDl=true&msLaunch=true&enableMobilePage=true&suppressPrompt=true