The vertex-betweenness centrality index is an essential measurement for analyzing social networks, but the computation time is excessive. At present, the fastest algorithm, proposed by Brandes in 2001, requires O(VxE) time, which is computationally intractable for real-world social networks that usually contain millions of nodes and edges.

In this paper, we propose a fast and accurate algorithm for estimating vertex-betweenness centrality values for social networks. It only requires O(b^2xV) time, where b is the average degree in the network. Significantly, we demonstrate that the local dynamic information about the vertices is highly relevant to the global betweenness values. The experiment results show that the vertex-betweenness values estimated by the proposed model are close to the real values and their rank is fairly accurate. Furthermore, using data from online role-playing games, we present a new type of dynamic social network constructed from in-game chatting activity. Besides using such online game networks to evaluate our betweenness estimation model, we report several interesting findings derived from conducting static and dynamic social network analysis on game networks.

Jing-Kai Lou, Shou-de Lin, Kuan-Ta Chen, and Chin-Laung Lei, "What Can the Temporal Social Behavior Tell Us? An Estimation of Vertex-Betweenness Using Dynamic Social Informations," In Proceedings of ASONAM 2010, August 2010.

Full Text (PDF Format, 749 KB)

Slides (PDF Format, 1198 KB)