Alpha current flow betweenness centrality

Konstantin Avrachenkov, Nelly Litvak, Vasily Medyanikov, Marina Sokol

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

6 Downloads (Pure)

Abstract

A class of centrality measures called betweenness centralities reflects degree of participation of edges or nodes in communication between different parts of the network. The original shortest-path betweenness centrality is based on counting shortest paths which go through a node or an edge. One of shortcomings of the shortest-path betweenness centrality is that it ignores the paths that might be one or two steps longer than the shortest paths, while the edges on such paths can be important for communication processes in the network. To rectify this shortcoming a current flow betweenness centrality has been proposed. Similarly to the shortest path betweenness, it has prohibitive complexity for large size networks. In the present work we propose two regularizations of the current flow betweenness centrality, $\alpha$-current flow betweenness and truncated $\alpha$-current flow betweenness, which can be computed fast and correlate well with the original current flow betweenness.
Original languageEnglish
Title of host publicationAlgorithms and Models for the Web Graph
Subtitle of host publication10th International Workshop, WAW 2013, Cambridge, MA, USA, December 14-15, 2013, Proceedings
EditorsAnthony Bonato, Michael Mitzenmacher, Paweł Prałat
Place of PublicationCham
PublisherSpringer
Pages106-117
Number of pages12
ISBN (Electronic)978-3-319-03536-9
ISBN (Print)978-3-319-03535-2
DOIs
Publication statusPublished - 2013
Event10th International Workshop on Algorithms and Models for the Web Graph, WAW 2013 - Cambridge, United States
Duration: 14 Dec 201315 Dec 2013
Conference number: 10

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume8305
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Workshop

Workshop10th International Workshop on Algorithms and Models for the Web Graph, WAW 2013
Abbreviated titleWAW
CountryUnited States
CityCambridge
Period14/12/1315/12/13

Keywords

  • Centrality measure
  • Betweenness centrality
  • Closeness centrality
  • Large connected component
  • Power iteration

Fingerprint

Dive into the research topics of 'Alpha current flow betweenness centrality'. Together they form a unique fingerprint.

Cite this