Affiliations: [a] Faculty of Mathematics and Computer Sciences, Amirkabir University of Technology, Tehran, Iran | [b] Faculty of Electrical and Computer Engineering, University of Kurdistan, Sanandaj, Iran
Correspondence:
[*]
Corresponding author: Adel Mohammadpour, Faculty of Mathematics and Computer Sciences, Amirkabir University of Technology, Tehran, Iran. Tel.: +98 216 454 2533; Fax: +98 216 649 7930; E-mail: [email protected].
Abstract: There are several potent measures for mining the relationships among actors in social network analysis. Betweenness centrality measure is extensively utilized in network analysis. However, it is quite time-consuming to compute exactly the betweenness centrality in high dimensional social networks. Applying random projection approach, an approximation algorithm for computing betweenness centrality of a given node, is proposed in this paper, for both weighted and unweighted graphs. It is proved that the proposed method works better than the existing methods to approximate the betweenness centrality measure. The proposed algorithm significantly reduces the number of single-source shortest path computations. We test the method on real-world networks and a synthetic benchmark and observe that the proposed algorithm shows very promising results based on statistical evaluation measure.
Keywords: Betweenness centrality measure, random projection, social network mining, concentration inequalities, centrality indices, randomized algorithms, ranking
