Effective Resistance Preserving Directed Graph Symmetrization

DOI10.1137/18M1172892MaRDI QIDQ4615300zbMATH OpenOpenAlexWikidataFDO

Authors Katherine Fitch

Publication date 4 February 2019

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

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

zbMATH Keywords

directed graph analysiseffective resistancegraph partitioninggraph symmetrizationkron reductionLyapunov equationspectral graph theory

Mathematics Subject Classification ID

Distance in graphs (05C12) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Lyapunov and other classical stabilities (Lagrange, Poisson, (L^p, l^p), etc.) in control theory (93D05)

Abstract: This work presents a new method for symmetrization of directed graphs that constructs an undirected graph with equivalent pairwise effective resistances as a given directed graph. Consequently a graph metric, square root of effective resistance, is preserved between the directed graph and its symmetrized version. It is shown that the preservation of this metric allows for interpretation of algebraic and spectral properties of the symmetrized graph in the context of the directed graph, due to the relationship between effective resistance and the Laplacian spectrum. Additionally, Lyapunov theory is used to demonstrate that the Laplacian matrix of a directed graph can be decomposed into the product of a projection matrix, a skew symmetric matrix, and the Laplacian matrix of the symmetrized graph. The application of effective resistance preserving graph symmetrization is discussed in the context of spectral graph partitioning and Kron reduction of directed graphs.

Recommendations

• A New Notion of Effective Resistance for Directed Graphs—Part II: Computing Resistances
• Graph sparsification by effective resistances
• Resistance matrices of balanced directed graphs
• A New Notion of Effective Resistance for Directed Graphs—Part I: Definition and Properties
• Dynamic effective resistances and approximate Schur complement on separable graphs
• Algorithmic techniques for finding resistance distances on structured graphs
• Effective graph resistance
• Kron Reduction and Effective Resistance of Directed Graphs
• Graph Clustering using Effective Resistance

Cites work

• A class of graph-geodetic distances generalizing the shortest-path and the resistance distances
• A Multiscale Pyramid Transform for Graph Signals
• A New Notion of Effective Resistance for Directed Graphs—Part I: Definition and Properties
• A New Notion of Effective Resistance for Directed Graphs—Part II: Computing Resistances
• Analysis and synthesis of stability matrices
• Clustering and community detection in directed networks: a survey
• Detection of structurally homogeneous subsets in graphs
• Expander flows, geometric embeddings and graph partitioning
• Graph clustering
• Graph sparsification by effective resistances
• scientific article; zbMATH DE number 3681933 (Why is no real title available?)
• scientific article; zbMATH DE number 1333614 (Why is no real title available?)
• scientific article; zbMATH DE number 1134987 (Why is no real title available?)
• scientific article; zbMATH DE number 1418964 (Why is no real title available?)
• scientific article; zbMATH DE number 3035866 (Why is no real title available?)
• Kron Reduction of Graphs With Applications to Electrical Networks
• Laplacians and the Cheeger inequality for directed graphs
• Machine Learning: ECML 2004
• Minimizing Effective Resistance of a Graph
• On the Quality of Spectral Separators
• On the spectra of nonsymmetric Laplacian matrices
• Random walks and the effective resistance of networks
• Spectral bisection of graphs and connectedness
• Structural, Syntactic, and Statistical Pattern Recognition
• The communicability distance in graphs
• The electrical resistance of a graph captures its commute and cover times

Cited in

(5)

• Hubs-biased resistance distances on graphs and networks
• A metric on directed graphs and Markov chains based on hitting probabilities
• Kron Reduction and Effective Resistance of Directed Graphs
• Pseudoinverses of Signed Laplacian Matrices
• Random walks, conductance, and resistance for the connection graph Laplacian

This page was built for publication: Effective Resistance Preserving Directed Graph Symmetrization

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