A Clustered Approach for Fast Computation of Betweenness Centrality in Social Networks

摘要

In the last few years, the data generated by social networking systems have become interesting to analyze local and global social phenomena. A useful metric to identify influential people or opinion leaders is the between ness centrality index. The computation of this index is a very demanding task since its exact calculation exhibits O(nm) time complexity for unweighted graphs. This complexity has a high impact on computation time if we consider that social networks data are continuously growing and today the number of nodes of the related graphs is in the order of billions. To address the problem, we propose a variant of the Brandes' algorithm for a very fast evaluation of approximated between ness indexes in large networks. In a preliminary phase, our method exploits a scalable and efficient clustering technique, based on Louvain method, to identify communities and border nodes that guide the selection of a limited number of pivot nodes. The experimental analysis shows that for sparse graphs (which represent a widespread class of social networks graphs) our method drastically reduces the computation time if compared with the most efficient solution for exact evaluation, whereas the degree of approximation is good especially if we are interested to identify the top k between ness values. The scalability analysis conducted on synthetic scale-free graphs also shows that our method behaves well when the network is very large (even though in these cases additional machines could be useful to handle memory consumption).