Decentralized computation of effective resistances and acceleration of consensus algorithms

Necdet Serhat Aybat, Mert Gurbuzbalaban

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)

Abstract

The effective resistance between a pair of nodes in a weighted undirected graph is defined as the potential difference induced between them when a unit current is injected at the first node and extracted at the second node, treating edge weights as the conductance values of edges. The effective resistance is a key quantity of interest in many applications and fields including solving linear systems, Markov Chains and continuous-time averaging networks. We develop an efficient linearly convergent distributed algorithm for computing effective resistances and demonstrate its performance through numerical studies. We also apply our algorithm to the consensus problem where the aim is to compute the average of node values in a distributed manner. We show that the distributed algorithm we developed for effective resistances can be used to accelerate the convergence of the classical consensus iterations considerably by a factor depending on the network structure.

Original languageEnglish (US)
Title of host publication2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages538-542
Number of pages5
ISBN (Electronic)9781509059904
DOIs
StatePublished - Mar 7 2018
Event5th IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Montreal, Canada
Duration: Nov 14 2017Nov 16 2017

Publication series

Name2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings
Volume2018-January

Other

Other5th IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017
CountryCanada
CityMontreal
Period11/14/1711/16/17

Fingerprint

Parallel algorithms
Markov processes
Linear systems

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Signal Processing

Keywords

  • Effective resistance
  • Kaczmarz method
  • Laplacian matrix
  • consensus
  • distributed optimization
  • graph

Cite this

Aybat, N. S., & Gurbuzbalaban, M. (2018). Decentralized computation of effective resistances and acceleration of consensus algorithms. In 2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings (pp. 538-542). (2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings; Vol. 2018-January). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/GlobalSIP.2017.8308701
Aybat, Necdet Serhat ; Gurbuzbalaban, Mert. / Decentralized computation of effective resistances and acceleration of consensus algorithms. 2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2018. pp. 538-542 (2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings).
@inproceedings{e3973ccd49144094b66d7e39fb792177,
title = "Decentralized computation of effective resistances and acceleration of consensus algorithms",
abstract = "The effective resistance between a pair of nodes in a weighted undirected graph is defined as the potential difference induced between them when a unit current is injected at the first node and extracted at the second node, treating edge weights as the conductance values of edges. The effective resistance is a key quantity of interest in many applications and fields including solving linear systems, Markov Chains and continuous-time averaging networks. We develop an efficient linearly convergent distributed algorithm for computing effective resistances and demonstrate its performance through numerical studies. We also apply our algorithm to the consensus problem where the aim is to compute the average of node values in a distributed manner. We show that the distributed algorithm we developed for effective resistances can be used to accelerate the convergence of the classical consensus iterations considerably by a factor depending on the network structure.",
keywords = "Effective resistance, Kaczmarz method, Laplacian matrix, consensus, distributed optimization, graph",
author = "Aybat, {Necdet Serhat} and Mert Gurbuzbalaban",
year = "2018",
month = "3",
day = "7",
doi = "10.1109/GlobalSIP.2017.8308701",
language = "English (US)",
series = "2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "538--542",
booktitle = "2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings",
address = "United States",

}

Aybat, NS & Gurbuzbalaban, M 2018, Decentralized computation of effective resistances and acceleration of consensus algorithms. in 2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings. 2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings, vol. 2018-January, Institute of Electrical and Electronics Engineers Inc., pp. 538-542, 5th IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017, Montreal, Canada, 11/14/17. https://doi.org/10.1109/GlobalSIP.2017.8308701

Decentralized computation of effective resistances and acceleration of consensus algorithms. / Aybat, Necdet Serhat; Gurbuzbalaban, Mert.

2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2018. p. 538-542 (2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings; Vol. 2018-January).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Decentralized computation of effective resistances and acceleration of consensus algorithms

AU - Aybat, Necdet Serhat

AU - Gurbuzbalaban, Mert

PY - 2018/3/7

Y1 - 2018/3/7

N2 - The effective resistance between a pair of nodes in a weighted undirected graph is defined as the potential difference induced between them when a unit current is injected at the first node and extracted at the second node, treating edge weights as the conductance values of edges. The effective resistance is a key quantity of interest in many applications and fields including solving linear systems, Markov Chains and continuous-time averaging networks. We develop an efficient linearly convergent distributed algorithm for computing effective resistances and demonstrate its performance through numerical studies. We also apply our algorithm to the consensus problem where the aim is to compute the average of node values in a distributed manner. We show that the distributed algorithm we developed for effective resistances can be used to accelerate the convergence of the classical consensus iterations considerably by a factor depending on the network structure.

AB - The effective resistance between a pair of nodes in a weighted undirected graph is defined as the potential difference induced between them when a unit current is injected at the first node and extracted at the second node, treating edge weights as the conductance values of edges. The effective resistance is a key quantity of interest in many applications and fields including solving linear systems, Markov Chains and continuous-time averaging networks. We develop an efficient linearly convergent distributed algorithm for computing effective resistances and demonstrate its performance through numerical studies. We also apply our algorithm to the consensus problem where the aim is to compute the average of node values in a distributed manner. We show that the distributed algorithm we developed for effective resistances can be used to accelerate the convergence of the classical consensus iterations considerably by a factor depending on the network structure.

KW - Effective resistance

KW - Kaczmarz method

KW - Laplacian matrix

KW - consensus

KW - distributed optimization

KW - graph

UR - http://www.scopus.com/inward/record.url?scp=85048130703&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85048130703&partnerID=8YFLogxK

U2 - 10.1109/GlobalSIP.2017.8308701

DO - 10.1109/GlobalSIP.2017.8308701

M3 - Conference contribution

T3 - 2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings

SP - 538

EP - 542

BT - 2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

ER -

Aybat NS, Gurbuzbalaban M. Decentralized computation of effective resistances and acceleration of consensus algorithms. In 2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings. Institute of Electrical and Electronics Engineers Inc. 2018. p. 538-542. (2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings). https://doi.org/10.1109/GlobalSIP.2017.8308701