Alpha current flow betweenness centrality

Konstantin Avrachenkov; Nelly Litvak; Vasily Medyanikov; Marina Sokol

doi:10.1007/978-3-319-03536-9_9

Alpha current flow betweenness centrality

Konstantin Avrachenkov, Nelly Litvak, Vasily Medyanikov, Marina Sokol

Stochastic Operations Research

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-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 language	English
Title of host publication	Algorithms and Models for the Web Graph
Subtitle of host publication	10th International Workshop, WAW 2013, Cambridge, MA, USA, December 14-15, 2013, Proceedings
Editors	Anthony Bonato, Michael Mitzenmacher, Paweł Prałat
Place of Publication	Cham
Publisher	Springer
Pages	106-117
Number of pages	12
ISBN (Electronic)	978-3-319-03536-9
ISBN (Print)	978-3-319-03535-2
DOIs	https://doi.org/10.1007/978-3-319-03536-9_9
Publication status	Published - 2013
Event	10th International Workshop on Algorithms and Models for the Web Graph, WAW 2013 - Cambridge, United States Duration: 14 Dec 2013 → 15 Dec 2013 Conference number: 10

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	8305
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Workshop

Workshop	10th International Workshop on Algorithms and Models for the Web Graph, WAW 2013
Abbreviated title	WAW
Country	United States
City	Cambridge
Period	14/12/13 → 15/12/13

Keywords

Centrality measure
Betweenness centrality
Closeness centrality
Large connected component
Power iteration

Access to Document

10.1007/978-3-319-03536-9_9

Cite this

Avrachenkov, K., Litvak, N., Medyanikov, V., & Sokol, M. (2013). Alpha current flow betweenness centrality. In A. Bonato, M. Mitzenmacher, & P. Prałat (Eds.), Algorithms and Models for the Web Graph: 10th International Workshop, WAW 2013, Cambridge, MA, USA, December 14-15, 2013, Proceedings (pp. 106-117). (Lecture Notes in Computer Science; Vol. 8305). Springer. https://doi.org/10.1007/978-3-319-03536-9_9

Avrachenkov, Konstantin ; Litvak, Nelly ; Medyanikov, Vasily ; Sokol, Marina. / Alpha current flow betweenness centrality. Algorithms and Models for the Web Graph: 10th International Workshop, WAW 2013, Cambridge, MA, USA, December 14-15, 2013, Proceedings. editor / Anthony Bonato ; Michael Mitzenmacher ; Paweł Prałat. Cham : Springer, 2013. pp. 106-117 (Lecture Notes in Computer Science).

@inproceedings{074e73382e3c410fb1ce31bede4b2e58,

title = "Alpha current flow betweenness centrality",

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.",

keywords = "Centrality measure, Betweenness centrality, Closeness centrality, Large connected component, Power iteration",

author = "Konstantin Avrachenkov and Nelly Litvak and Vasily Medyanikov and Marina Sokol",

year = "2013",

doi = "10.1007/978-3-319-03536-9_9",

language = "English",

isbn = "978-3-319-03535-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "106--117",

editor = "Anthony Bonato and Michael Mitzenmacher and Pawe{\l} Pra{\l}at",

booktitle = "Algorithms and Models for the Web Graph",

address = "Netherlands",

note = "10th International Workshop on Algorithms and Models for the Web Graph, WAW 2013, WAW ; Conference date: 14-12-2013 Through 15-12-2013",

}

Avrachenkov, K, Litvak, N, Medyanikov, V & Sokol, M 2013, Alpha current flow betweenness centrality. in A Bonato, M Mitzenmacher & P Prałat (eds), Algorithms and Models for the Web Graph: 10th International Workshop, WAW 2013, Cambridge, MA, USA, December 14-15, 2013, Proceedings. Lecture Notes in Computer Science, vol. 8305, Springer, Cham, pp. 106-117, 10th International Workshop on Algorithms and Models for the Web Graph, WAW 2013, Cambridge, United States, 14/12/13. https://doi.org/10.1007/978-3-319-03536-9_9

Alpha current flow betweenness centrality. / Avrachenkov, Konstantin; Litvak, Nelly; Medyanikov, Vasily; Sokol, Marina.

Algorithms and Models for the Web Graph: 10th International Workshop, WAW 2013, Cambridge, MA, USA, December 14-15, 2013, Proceedings. ed. / Anthony Bonato; Michael Mitzenmacher; Paweł Prałat. Cham : Springer, 2013. p. 106-117 (Lecture Notes in Computer Science; Vol. 8305).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Alpha current flow betweenness centrality

AU - Avrachenkov, Konstantin

AU - Litvak, Nelly

AU - Medyanikov, Vasily

AU - Sokol, Marina

N1 - Conference code: 10

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - Centrality measure

KW - Betweenness centrality

KW - Closeness centrality

KW - Large connected component

KW - Power iteration

U2 - 10.1007/978-3-319-03536-9_9

DO - 10.1007/978-3-319-03536-9_9

M3 - Conference contribution

SN - 978-3-319-03535-2

T3 - Lecture Notes in Computer Science

SP - 106

EP - 117

BT - Algorithms and Models for the Web Graph

A2 - Bonato, Anthony

A2 - Mitzenmacher, Michael

A2 - Prałat, Paweł

PB - Springer

CY - Cham

T2 - 10th International Workshop on Algorithms and Models for the Web Graph, WAW 2013

Y2 - 14 December 2013 through 15 December 2013

ER -

Avrachenkov K, Litvak N, Medyanikov V, Sokol M. Alpha current flow betweenness centrality. In Bonato A, Mitzenmacher M, Prałat P, editors, Algorithms and Models for the Web Graph: 10th International Workshop, WAW 2013, Cambridge, MA, USA, December 14-15, 2013, Proceedings. Cham: Springer. 2013. p. 106-117. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-03536-9_9

Alpha current flow betweenness centrality

Abstract

Publication series

Workshop

Keywords

Access to Document

Fingerprint

Cite this