Paper Info
Title
Graph Clustering using Effective Resistance.
Abstract
We design a polynomial time algorithm that for any weighted undirected graph G = (V, E, w) sufficiently large delta u003e 1, partitions V into subsets V(1),..., V(h) for some hu003e= 1, such that at most delta^{-1} fraction of the weights are between clusters, i.e.sum(i u003c j) |E(V(i), V(j)| u003c w(E)/delta and the effective resistance diameter of each of the induced subgraphsG[V(i)] is at most delta^3 times the inverse of the average weighted degree, i.e.max{ Reff(u, v) : u, v V(i)} u003c delta^3 · |V|/w(E)for all i = 1,..., h. In particular, it is possible to remove onepercent of weight of edges of any given graph such that each of theresulting connected components has effective resistance diameter atmost the inverse of the average weighted degree. Our proof is basedon a new connection between effective resistance low conductancesets. We show that if the effective resistance between two vertices u v is large, then there must be a low conductance cut separating u from v. This implies that very mildly expanding graphs have constant effective resistance diameter. We believe that this connection could be of independent interest in algorithm design.
Year
DOI
Venue
2018
10.4230/LIPIcs.ITCS.2018.41
conference on innovations in theoretical computer science
DocType
Volume
Citations 
Conference
abs/1711.06530
0
PageRank 
References 
Authors
0.34
7
4
Name
Order
Citations
PageRank
Vedat Levi Alev101.35
Nima Anari27914.83
Lap Chi Lau355435.27
Shayan Oveis Gharan432326.63