License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2018.41
URN: urn:nbn:de:0030-drops-83696
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8369/
Go to the corresponding LIPIcs Volume Portal

Alev, Vedat Levi ; Anari, Nima ; Lau, Lap Chi ; Oveis Gharan, Shayan

Graph Clustering using Effective Resistance

pdf-format:
LIPIcs-ITCS-2018-41.pdf (0.5 MB)

Abstract

We design a polynomial time algorithm that for any weighted undirected graph G = (V, E, w) and sufficiently large \delta > 1, partitions V into subsets V(1),..., V(h) for some h>= 1, such that at most \delta^{-1} fraction of the weights are between clusters, i.e.

sum(i < j) |E(V(i), V(j)| < w(E)/\delta

and the effective resistance diameter of each of the induced subgraphs
G[V(i)] is at most \delta^3 times the inverse of the average weighted degree, i.e.

max{ Reff(u, v) : u, v \in V(i)} < \delta^3 ยท |V|/w(E)

for all i = 1,..., h. In particular, it is possible to remove one
percent of weight of edges of any given graph such that each of the
resulting connected components has effective resistance diameter at
most the inverse of the average weighted degree. Our proof is based
on a new connection between effective resistance and low conductance
sets. We show that if the effective resistance between two vertices u and 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.

BibTeX - Entry

@InProceedings{alev_et_al:LIPIcs:2018:8369,
  author =	{Vedat Levi Alev and Nima Anari and Lap Chi Lau and Shayan Oveis Gharan},
  title =	{{Graph Clustering using Effective Resistance}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{41:1--41:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Anna R. Karlin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8369},
  URN =		{urn:nbn:de:0030-drops-83696},
  doi =		{10.4230/LIPIcs.ITCS.2018.41},
  annote =	{Keywords: Electrical Flows, Effective Resistance, Conductance, Graph Partitioning}
}

Keywords: Electrical Flows, Effective Resistance, Conductance, Graph Partitioning
Collection: 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Issue Date: 2018
Date of publication: 12.01.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI