Locally computable approximations for spectral clustering and absorption times of random walks

Abstract

We address the problem of determining a natural local neighbourhood or "cluster" associated to a given seed vertex in an undirected graph. We formulate the task in terms of absorption times of random walks from other vertices to the vertex of interest, and observe that these times are well approximated by the components of the principal eigenvector of the corresponding fundamental matrix of the graph's adjacency matrix. We further present a locally computable gradient-descent method to estimate this Dirichlet-Fiedler vector, based on minimising the respective Rayleigh quotient. Experimental evaluation shows that the approximations behave well and yield well-defined local clusters.

21 pages, 8 figures

References in corpus (6)

• Emergence of scaling in random networks
• The structure and function of complex networks
• Finding and evaluating community structure in networks
• Cooperative Game Theory Approaches for Network Partitioning
• Finding Communities in Linear Time: A Physics Approach
• On the NP-Completeness of Some Graph Cluster Measures

Cited by in corpus (2)

• On Proximity and Structural Role-based Embeddings in Networks: Misconceptions, Techniques, and Applications
• A Local Approach for Identifying Clusters in Networks