2026-08-01T14:35:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8369 2024-03-06T10:42:07Z ddc:004 open_access

Graph Clustering using Effective Resistance Alev, Vedat Levi Anari, Nima Lau, Lap Chi Oveis Gharan, Shayan Electrical Flows Effective Resistance Conductance Graph Partitioning 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vedat Levi Alev and Nima Anari and Lap Chi Lau and Shayan Oveis Gharan 2018 Is Part Of LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2018.41 urn:nbn:de:0030-drops-83696 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.41 eng https://creativecommons.org/licenses/by/3.0/legalcode