Name
Abstract | ||
|---|---|---|
The computation of nodes centrality is of great importance for the analysis of graphs. The current flow betweenness is an interesting centrality index that is computed by considering how the information travels along all the possible paths of a graph. The current flow betweenness exploits basic results from electrical circuits, i.e. Kirchhoff's laws, to evaluate the centrality of vertices. The computation of the current flow betweenness may exceed the computational capability of a single machine for very large graphs composed by millions of nodes. In this paper we propose a solution that estimates the current flow betweenness in a distributed setting, by defining a vertex-centric, gossip-based algorithm. Each node, relying on its local information, in a self-adaptive way generates new flows to improve the betweenness of all the nodes of the graph. Our experimental evaluation shows that our proposal achieves high correlation with the exact current flow betweenness, and provides a good centrality measure for large graphs. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1109/SASO.2015.15 | SASO '15 Proceedings of the 2015 IEEE 9th International Conference on Self-Adaptive and Self-Organizing Systems |
Keywords | Field | DocType |
Internet,graph theory,Internet,Kirchhoff's laws,distributed current flow betweenness centrality,electrical circuits,graph analysis,node centrality,vertex-centric gossip-based algorithm | Network science,Approximation algorithm,Random walk closeness centrality,Computer science,Centrality,Network controllability,Theoretical computer science,Betweenness centrality,Network theory,Distributed computing,Computation | Conference |
ISSN | Citations | PageRank |
1949-3673 | 3 | 0.38 |
References | Authors | |
26 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alessandro Lulli | 1 | 82 | 10.35 |
| Laura Ricci | 2 | 151 | 14.12 |
| Emanuele Carlini | 3 | 166 | 20.15 |
| Patrizio Dazzi | 4 | 249 | 24.78 |