中央研究院  |  資訊科學研究所  |  多媒體網路與系統實驗室
What Can the Temporal Social Behavior Tell Us? An Estimation of Vertex-Betweenness Using Dynamic Social Informations
(NOTE: Sheng-Wei Chen is also known as Kuan-Ta Chen.)

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


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

BibTex
@INPROCEEDINGS{lou10:betweenness,
  TITLE      = {What Can the Temporal Social Behavior Tell Us? An Estimation of Vertex-Betweenness Using Dynamic Social Informations},
  AUTHOR     = {Jing-Kai Lou and Shou-de Lin and Kuan-Ta Chen and Chin-Laung Lei},
  BOOKTITLE  = {Proceedings of ASONAM 2010},
  MONTH      = {August},
  YEAR       = {2010},
  X_TAG      = {sc}
}