Detecting communities and their evolutions in dynamic social networks-a Bayesian approach

被引:292
作者
Yang, Tianbao [1 ]
Chi, Yun [2 ]
Zhu, Shenghuo [2 ]
Gong, Yihong [2 ]
Jin, Rong [1 ]
机构
[1] Michigan State Univ, Dept Comp Sci & Engn, E Lansing, MI 48824 USA
[2] NEC Labs Amer, Cupertino, CA 95014 USA
关键词
Social network; Community; Community evolution; Dynamic stochastic block model; Bayesian inference; Gibbs sampling;
D O I
10.1007/s10994-010-5214-7
中图分类号
TP18 [人工智能理论];
学科分类号
140502 [人工智能];
摘要
Although a large body of work is devoted to finding communities in static social networks, only a few studies examined the dynamics of communities in evolving social networks. In this paper, we propose a dynamic stochastic block model for finding communities and their evolution in a dynamic social network. The proposed model captures the evolution of communities by explicitly modeling the transition of community memberships for individual nodes in the network. Unlike many existing approaches for modeling social networks that estimate parameters by their most likely values (i.e., point estimation), in this study, we employ a Bayesian treatment for parameter estimation that computes the posterior distributions for all the unknown parameters. This Bayesian treatment allows us to capture the uncertainty in parameter values and therefore is more robust to data noise than point estimation. In addition, an efficient algorithm is developed for Bayesian inference to handle large sparse social networks. Extensive experimental studies based on both synthetic data and real-life data demonstrate that our model achieves higher accuracy and reveals more insights in the data than several state-of-the-art algorithms.
引用
收藏
页码:157 / 189
页数:33
相关论文
共 45 条
[1]
Ahmed A., 2008, PROC 8 SIAM INT C DA, P219
[2]
Airoldi EdoardoM., 2006, Proceedings of the International Biometrics Society Annual Meeting, P1
[3]
[Anonymous], 2006, P 12 ACM SIGKDD INT, DOI [10.1145/1150402.1150467, DOI 10.1145/1150402.1150467]
[4]
[Anonymous], 2005, Ph.D. thesis,
[5]
[Anonymous], ADV NEUR IN
[6]
[Anonymous], 2009, SIAM International Conference on Data Mining (SDM)
[7]
[Anonymous], 2002, Journal of Social Structure
[8]
Asur S, 2007, KDD-2007 PROCEEDINGS OF THE THIRTEENTH ACM SIGKDD INTERNATIONAL CONFERENCE ON KNOWLEDGE DISCOVERY AND DATA MINING, P913
[9]
Bishop C., 2006, PATTERN RECOGN, DOI DOI 10.1117/1.2819119
[10]
On modularity clustering [J].
Brandes, Ulrik ;
Delling, Daniel ;
Gaertler, Marco ;
Goerke, Robert ;
Hoefer, Martin ;
Nikoloski, Zoran ;
Wagner, Dorothea .
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2008, 20 (02) :172-188