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

Abstract (English) |
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 E.1 DATA STRUCTURES D.3.3 Language Constructs and Features |

1) Download Document PDF |

Open access Restricted Private