Istituto di Scienza e Tecnologie dell'Informazione     
Lulli A., Ricci L., Carlini E., Dazzi P. Distributed Current Flow Betweenness Centrality. In: SASO - 2015 IEEE 9th International Conference on Self-Adaptive and Self-Organizing Systems (Boston, USA, 21-25/09 2015). Proceedings, pp. 71 - 80. IEEE, 2015.
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.
DOI: 10.1109/SASO.2015.15
Subject Graph Processing
Distributed Algorithms
C.2.4 Distributed Systems
D.3.3 Language Constructs and Features

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional