Graph Clustering using Effective Resistance

DOI10.4230/LIPICS.ITCS.2018.41MaRDI QIDQ4993308zbMATH OpenOpenAlexFDO

Authors Vedat Levi Alev, Nima Anari, Lap Chi Lau

Publication date 15 June 2021

Full work available at URL https://arxiv.org/abs/1711.06530

zbMATH Keywords

conductanceeffective resistanceelectrical flowsgraph partitioning

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Applications of graph theory to circuits and networks (94C15)

Abstract: $$We design a polynomial time algorithm that for any weighted undirected graph $G=(V,E,veccw)$ and sufficiently large $delta>1$, partitions $V$ into subsets $V_1,ldots,V_h$ for some $hgeq1$, such that $$ at most $delt{a}^{-1}$ fraction of the weights are between clusters, i.e. [ w(E - cup_{i = 1}^h E(V_i)) lesssim frac{w(E)}{delta};] $$ the effective resistance diameter of each of the induced subgraphs $G[V_i]$ is at most $delt{a}^3$ times the average weighted degree, i.e. [ max_{u, v in V_i} mathsf{Reff}_{G[V_i]}(u, v) lesssim delta^3 cdot frac{|V|}{w(E)} quad ext{ for all } i=1, ldots, 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.

Recommendations

• Graph clustering
• Community detection algorithm based on effective resistance of network
• Graph Clustering in All Parameter Regimes
• Graph sparsification by effective resistances
• Graph clustering with a constraint on cluster sizes
• Density-constrained graph clustering
• Algorithmic techniques for finding resistance distances on structured graphs
• Improved Graph Clustering
• Cluster Identification in Nearest-Neighbor Graphs

Cites work

• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• A generalization of permanent inequalities and applications in counting and optimization
• A Nearly-m log n Time Solver for SDD Linear Systems
• A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
• Approaching optimality for solving SDD linear systems
• Approximating unique games
• Approximating unique games using low diameter graph decomposition
• Approximation algorithms for the 0-extension problem
• Bounds on the cover time
• Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs
• Covering problems for Brownian motion on spheres
• Eigenvalue bounds, spectral partitioning, and metrical deformations via flows
• Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs
• Excluded minors, network decomposition, and multicommodity flow
• Fast generation of random spanning trees and the effective resistance metric
• Faster Generation of Random Spanning Trees
• Graph sparsification by effective resistances
• Higher Eigenvalues of Graphs
• scientific article; zbMATH DE number 1303557 (Why is no real title available?)
• scientific article; zbMATH DE number 2079348 (Why is no real title available?)
• scientific article; zbMATH DE number 6297701 (Why is no real title available?)
• scientific article; zbMATH DE number 3337135 (Why is no real title available?)
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
• Low diameter graph decompositions
• Metric clustering via consistent labeling
• Min-max Graph Partitioning and Small Set Expansion
• Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems
• On clusterings: good, bad and spectral
• Rounding Semidefinite Programming Hierarchies via Global Correlation
• Sampling random spanning trees faster than matrix multiplication
• Spectral algorithms for unique games
• Spectral sparsification of graphs
• The electrical resistance of a graph captures its commute and cover times
• The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees
• Unique games on expanding constraint graphs are easy (extended abstract)

Cited in

(10)

• Community detection by resistance distance: automation and benchmark testing
• Effective Resistance Preserving Directed Graph Symmetrization
• A Spectral Approach to Network Design
• Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis
• La métrica de resistencia efectiva
• Cover and hitting times of hyperbolic random graphs
• On the streaming complexity of expander decomposition
• Optimal sublinear sampling of spanning trees and determinantal point processes via average-case entropic independence
• Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions
• Worst-case to expander-case reductions: derandomized and generalized

This page was built for publication: Graph Clustering using Effective Resistance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993308)