Dirichlet Eigenvalues, Local Random Walks, and Analyzing Clusters in Graphs

Pavel Kolev, He Sun

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A cluster S in a massive graph G is characterised by the property that its corresponding vertices are better connected with each other, in comparison with the other vertices of the graph. Modeling, finding and analyzing clusters in massive graphs is an important topic in various disciplines. In this work we study local random walks that always stay in a cluster S . Moreover, we initiate the study of the local mixing time and the almost stable distribution, by analyzing Dirichlet eigenvalues in graphs. We prove that the Dirichlet eigenvalues of any connected subset S can be used to bound the ϵ-uniform mixing time, which improves the previous best-known result. We further present two applications of our results. The first is a polynomial-time algorithm for finding clusters with an improved approximation guarantee, while the second is the significance ordering of vertices in a cluster.
Original languageEnglish
Title of host publicationAlgorithms and Computation - 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings
PublisherSpringer, Cham
Pages621-632
Number of pages12
ISBN (Electronic)978-3-319-13075-0
ISBN (Print) 978-3-319-13074-3
DOIs
Publication statusE-pub ahead of print - 8 Nov 2014
EventThe 25th International Symposium on Algorithms and Computation (ISAAC 2014) - Jeonju Traditional Culture Center, Jeonju, Korea, Democratic People's Republic of
Duration: 15 Dec 201417 Dec 2014
http://tcs.postech.ac.kr/isaac2014/

Conference

ConferenceThe 25th International Symposium on Algorithms and Computation (ISAAC 2014)
Abbreviated titleISAAC 2014
CountryKorea, Democratic People's Republic of
CityJeonju
Period15/12/1417/12/14
Internet address

Fingerprint

Dive into the research topics of 'Dirichlet Eigenvalues, Local Random Walks, and Analyzing Clusters in Graphs'. Together they form a unique fingerprint.

Cite this