Totally asynchronous distributed estimation of eigenvector centrality in digraphs with application to the PageRank problem

Themistoklis Charalambous, Christoforos N. Hadjicostis, Michael G. Rabbat, Mikael Johansson

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

4 Citations (Scopus)

Abstract

We propose a distributed coordination mechanism which enables nodes in a directed graph to accurately estimate their eigenvector centrality (eigencentrality) even if they update their values at times determined by their own clocks. The clocks need neither be synchronized nor have the same speed. The main idea is to let nodes adjust the weights on outgoing links to compensate for their update speed: the higher the update frequency, the smaller the link weights. Our mechanism is used to develop a distributed algorithm for computing the PageRank vector, commonly used to assign importance to web pages and rank search results. Although several distributed approaches in the literature can deal with asynchronism, they cannot handle the different update speeds that occur when servers have heterogeneous computational capabilities. When existing algorithms are executed using heterogeneous update speeds, they compute incorrect PageRank values. The advantages of our algorithm over existing approaches are verified through illustrative examples.

Original languageEnglish
Title of host publication2016 IEEE 55th Conference on Decision and Control, CDC 2016
PublisherIEEE
Pages25-30
Number of pages6
ISBN (Electronic)9781509018376
DOIs
Publication statusPublished - 27 Dec 2016
MoE publication typeA4 Article in a conference publication
EventIEEE Conference on Decision and Control - ARIA Resort & Casino, Las Vegas, United States
Duration: 12 Dec 201614 Dec 2016
Conference number: 55

Conference

ConferenceIEEE Conference on Decision and Control
Abbreviated titleCDC
CountryUnited States
CityLas Vegas
Period12/12/201614/12/2016

Keywords

  • asynchronous operation
  • Distributed coordination
  • eigencentrality estimation
  • PageRank problem

Fingerprint Dive into the research topics of 'Totally asynchronous distributed estimation of eigenvector centrality in digraphs with application to the PageRank problem'. Together they form a unique fingerprint.

  • Cite this

    Charalambous, T., Hadjicostis, C. N., Rabbat, M. G., & Johansson, M. (2016). Totally asynchronous distributed estimation of eigenvector centrality in digraphs with application to the PageRank problem. In 2016 IEEE 55th Conference on Decision and Control, CDC 2016 (pp. 25-30). [7798241] IEEE. https://doi.org/10.1109/CDC.2016.7798241