基于WB-MMSB模型的微博网络社区发现

计算机科学 ›› 2015, Vol. 42 ›› Issue (3): 65-70.doi: 10.11896/j.issn.1002-137X.2015.03.014

基于WB-MMSB模型的微博网络社区发现

徐建民,武晓波,吴树芳,粟武林

河北大学数学与计算机学院保定071002,河北大学数学与计算机学院保定071002,河北大学管理学院保定071002,河北大学数学与计算机学院保定071002

出版日期:2018-11-14 发布日期:2018-11-14
基金资助:
本文受中国博士后科学基金项目(20070420700),河北省自然科学基金项目(F2011201146)资助

Community Detection for Micro-blog Network Based on WB-MMSB Model

XU Jian-min, WU Xiao-bo, WU Shu-fang and SU Wu-lin

Online:2018-11-14 Published:2018-11-14

摘要/Abstract

摘要： 提出了一个用于微博网络社区发现的模型WB-MMSB,该模型考虑了微博网络中节点存在的单向关系,节点的社区隶属度从链入主题隶属度和链出主题隶属度两个方面表示。用指数族分布和平均场变分推理方法推导了模型中各变量的表示,并用SVI算法计算模型涉及的参数。实验在新浪微博数据集上进行,采用归一化互信息和困惑度进行评估,结果表明,WB-MMSB模型的社区发现能力优于aMMSB模型,并且其收敛速度快于aMMSB模型。

关键词: 微博网络,社区发现,混合隶属度随机块模型,重叠社区

Abstract: Considering the nodes of Mico-blog network have single direction relations,a new model WB-MMSB was put forward for community detection,which uses directed edges to embody the direction relations of nodes,and two aspects link-in and link-out are used to quantify the community membership of nodes.Exponential family distribution and mean-field variational inference method were used to inference the representations of variables in this model,and SVI algorithm was used to compute relating parameters.Experiments adopted Sina-Weibo dataset and NMI to testify the performance of WB-MMSB.The results indicate that the community detection ability of WB-MMSB model is better than aMMSB model,and the convergence rate of WB-MMSB model is faster than aMMSB model.

Key words: Micro-blog network,Community detection,Mixed membership stochastic block model,Overlapping communities

徐建民,武晓波,吴树芳,粟武林. 基于WB-MMSB模型的微博网络社区发现[J]. 计算机科学, 2015, 42(3): 65-70. https://doi.org/10.11896/j.issn.1002-137X.2015.03.014

XU Jian-min, WU Xiao-bo, WU Shu-fang and SU Wu-lin. Community Detection for Micro-blog Network Based on WB-MMSB Model[J]. Computer Science, 2015, 42(3): 65-70. https://doi.org/10.11896/j.issn.1002-137X.2015.03.014

参考文献

[1] 丁连红,时鹏.网络社区发现[M].北京:化学工业出版社,2008:1-138
[2] Girvan M,Newman M E J.Community structure in social and biological network[J].Proceedings of National Academy of Sciences,2002,99(12):7812-7826
[3] 杨博,刘大,Liu Ji-ming,等.复杂网络聚类方法[J].软件学报,2009,20(1):54-66
[4] 程学旗,沈华伟.复杂网络的社区结构[J].复杂系统与复杂性科学,2011,8(1):57-70
[5] 樊鹏翼,王晖,姜志宏,等.微博网络测量研究[J].计算机研究与发展,2012,49(4):691-699
[6] 郭岩,白硕,杨志峰,等.网络日志规模分析和用户兴趣挖掘[J].计算机学报,2005,28(9):1483-1496
[7] Palla G,Derényi I,Farkas I,et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435(7043):814-818
[8] 陈克寒,韩盼盼,吴健.基于用户聚类的异构社交网络推荐算法[J].计算机学报,2013,6(2):349-358
[9] Gopalan P K,Blei D M.Efficient discovery of overlapping communities in massive network[J].Proceedings of the National Academy of Science of the United States of American,2013,110(36):14534-14539
[10] Wainwright M J,Jordan M I.Graphical Models,ExponentialFamilies,and Variational Inference[J].Foundations and Trends in Machine Learning,2008,1(1/2):1-305
[11] Airoldi E M,Blei D M,Fienberg S E,et al.Mixed membership stochastic block models[J].Journal of Machine Learning Research,2008,9:1981-2014
[12] Hoffman M,Blei D M,Wang Chong,et al.Stochastic variational infernce[J].Journal of Machine Learning Research,2013,14:1303-1347
[13] Hastings M B.Community detection as an inference problem[J].Physical Review E-PHYS REV E,2006,74(3)
[14] Gopalan P,Wang Chong,Blei D M.Modeling overlapping communities with node popularities[C]∥Advances in Neural Information Processing Systems.2013:2850-2858
[15] Danon L,Diaz-Guilera A,Duch J,et al.Comparing community structure identification[J].Journal of Statistical Mechanics:Theory and Experiment,2005(9):P09008
[16] Blei D M,Ng A Y,Jordan M I.Latent dirichlet allocation[J].Journal of Machine Learning Research,2003,3:993-1022
[17] 沈华伟,程学旗,陈海强,等.基于信息瓶颈的社区发现[J].计算机学报,2008,31(4):677-686
[18] Robbins H,Monro S.A stochastic approximation method[J].The Annals of Mathematica Statistics,1951,22(3):400-407
[19] 杨楠,弓丹志,李饮,等.Web社区发现技术综述[J].计算机研究与发展,2005,42(3):439-447
[20] 林友芳,王天宇,唐锐,等.一种有效的社会网络社区发现模型和算法[J].计算机研究与发展,2012,49(2):337-345
[21] Gregory S.Find overlapping communities in networks by label propagation[J].New Journal of Physics,2010,12(10):103018
[22] Yan B,Gregory S.Detecting community structure in networkusing edge prediction methods[J].Journal of Statistical Mecha-nics:Theory and Experiment,2012(9):P09008
[23] Blondel V D,Guillaume J L,Lambiotte R,et al.Fast unfolding of communities in large network[J].Journal of Statistical Mechanics:Theory and Experiment,2008(9):P10008
[24] He Dong-xiao,Liu Da-you,Zhang Wei-xiong,et al.Discovering link communities in complex networks by exploiting link dynamics[J].Journal of Statistical Mechanics:Theory and Experiment,2012(10):P10015

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed