基于生成模型的大规模网络广义社区发现方法研究
开题报告
目 录
一、选题背景
二、研究目的和意义
三、本文研究涉及的主要理论
四、本文研究的主要内容及研究框架
（一）本文研究的主要内容
（二）本文研究框架
五、写作提纲
六、本文研究进展
七、目前已经阅读的文献
一、选题背景
互联网时代催生了社会媒体和在线社交平台的蓬勃发展，这些网络具有用户自由表达意愿及产生信息的功能，成为人们信息生成、传播及交流的主要模式。流行的在线社交平台有Wikipedia、My Space、Facebook、YouTtibe、Twitter、微信、腾讯、淘宝、亚马逊、人人网、新浪微博、博客等。根据IntemetLiveStats报道，截至2014年11月，数字世界再次到达另一个重要的里程碑，全球互联网用户数量超过了30亿人大关；Facebook用户达到13.5亿，活跃用户基数显示增长了2.3%; Twitter有6亿用户；人人网有2.8亿用户；新浪微博有5.6亿用户；亚马逊每个月用户达7900万；淘宝有5亿用户，双十一时淘宝用户增至350亿。用户、消费者等实体对这些在线社交平台的应用兴趣愈加浓厚。普通用户通过在线社会网络进行各类交互，如用户通过微信、微博、Twitter进行关注、转帖等操作，基于这些操作信息可构建各类网络。消费者通过在线社交平台了解商家，如淘宝、当当、京东、亚马逊等商业营销网络平台，对各个商家进行关注、购买、评价等行为，基于这些行为形成多种交互网络。这些在线网络平台用户每天产生庞大的关系数据和内容数据，用户的增加也使网络由原来的以数据为中心变为以用户为中心，网络信息获取由原来的网页搜索方式变为网络群体智能挖掘方式。商家将在线社交平台作为信息获取源头，挖掘大规模网络数据获取信息，为进行各类市场营销产生盈利提供依据，在线社交平台成为下一代商务智能平台的重要部分。政府部门挖掘在线社交平台产生数据结构规律，进行突发事件监测、舆情监控、恐怖活动预防等。网络产生大量的数据可建模为关系网络，节点表示实体，包括用户、网页、组织等，节点边表示实体交互关系。如TNvitter用户关注网络节点表示用户，边表示用户间的关系；博客网页链接网络，节点表示网页，边表示网页间的引用关系；淘宝商家和用户构成的混合网络，节点表示用户或商家，边表示用户间关系、商家间关系及用户和商家间的关系。构建的网络系统除了包含大量链接之外，节点还包括丰富的内容属性。如用户发布的信息、博客网页的文本信息。在线社交平台产生越来越多的网络数据，其具有结构复杂、规模庞大、内容丰富等特点。对网络数据进行挖掘和分析有助于我们了解和管理各类系统，进而为决策者提供决策依据。己有成果表明对网络数据的研宄主要从3个层面进行：复杂网络理论和算法理论；社会网络分析，包括网络的微观(Micro)、中观(Meso)和宏观(Macro)研宄；网络的应用研宄，如搜索、预测、信息传播、推荐、广告。社会网络分析研宄随着社会媒体的发展近来成为学术界和工业界的重要研宄方向。其中微观研究包括用户建模、行为分析、影响度分析。宏观研宄包括网络的结构本质、规律研究，如小世界现象(Small World Phenomenon)、优先链接(Preferential Attachment)模型，大量网络数据的可获取性使这些结构属性的统计特性验证更加鲁棒。中观研究包括社区结构发现、结构洞分析、网络模体(network motif)等.网络中观结构的研宄对社会网络分析及其应用起着关键作用。将网络进行聚类，获取简化的网络关系结构具有重要的意义。如可将网络聚类为较小规模的结构，便于使用己有方法处理大规模网络分析；可利用聚类结构实现各种应用活动。其中，传统社区结构发现用来识别网络中的紧密链接节点簇，是社会网络分析的基础研宄。目前研究者提出了许多传统社区发现方法，如层次聚类方法、模块度方法、图分割算法、基于统计推理的方法等⑴。大多传统社区发现方法针对静态网络，解决紧密子图发现问题。最近，也有少量针对动态网络演化社区发现的方法[7-9]。已有的传统社区发现方法主要用来发现类内紧密、类间稀疏的网络结构。
二、研究目的和意义
随着社会媒体和在线社交平台的发展，互联网产生大量可建模为网络系统的数据，商家、政府、网站管理者等实体需要了解真正的网络结构。流行的结构发现方法传统社区发现方法要求我们预先假设网络具有某种结构，但网络中可能没有这种结构，也可能还有许多其它的结构。基于随机块模型的广义社区发现方法对网络结构假设较少，可以更好地发现网络中的多类型结构。广义社区发现模型不仅可以根据网络节点的随机对等性将节点聚类，还可发现类间链接规律。广义社区发现的研宄为网络建模提供了有效的理论模型，便于研宄者分析研究网络的属性；同时广义社区发现理论模型及算法实现也丰富了概率图模型在大规模复杂网络分析领域的理论框架。广义社区发现具有重要的实用价值：1)根据网络节点聚类结构可发现网络中哪些实体具有相同的性质，基于节点的相似性可实现各类应用，如对相似的实体实现相同推荐，基于节点相似性及类间链接规律实现链接预测；2)将大规模网络进行聚类实现网络压缩，降低网络问题求解规模；3)将大规模网络进行不同粒度的聚类，可在不同分辨率下可视化网络，为网络分析与导航提供直观解决方法。因此，本论文针对在线社会网络结构复杂、规模庞大、节点内容丰富等特点，关注网络数据的广义社区发现概率生成模型及求解。
三、本文研究涉及的主要理论
本论文相关的及设计的广义社区发现模型属于概率生成模型。机器学习领域，概率生成模型描述观测变量如何由给定参数集合生成。生成模型与判别模型相对应，生成模型是所有变量的模型，判别模型仅提供观测变量条件下给定隐含变量的模型。因此，生成模型可用来模拟模型中任何变量的值。如果节点间存在某种层次，则该生成模型称作层次生成模型。这种模型中通常有依赖于潜在变量的观测变量，潜在变量分布由参数特征化。如果参数有先验，则由其它超参数生成。只要建模需要这种结构可以有很多层。然而，随着模型复杂度的增加，计算量大幅度增长。许多情况下需要在模型丰富性和计算效率间进行折中。数据分析的生成模型方法包含两个阶段：第一阶段定义生成模型，先验分布在该阶段指派；第二阶段贝叶斯估计用来根据观测数据和先验分布推导后验分布。第一步方向为参数生成数据，对广义社区发现建模来说就是构建网络生成过程的链接模型。第二步方向为从数据估计参数，即根据观测数据和模型估计模型参数。本部分首先介绍典型的网络广义社区发现链接模型；然后给出概率模型的相关求解方法，包括EM算法、在线EM算法、变分贝叶斯推理及随机变分推理算法。
简单随机块模型SBM可实现广义社区发现，一些研宄者对该模型进行约束简化设计了一些传统社区发现链接模型，与本论文研宄相关的模型有基于PLSA模型的社区发现模型SPAEM、生成度-流行度链接模型PPL和链接社区模型LCM. —些研究者扩展SBM关于网络链接的生成过程，典型的模型有考虑节点重叠性质的混合隶属度随机块模型MMSB、考虑节点度分布的度更正随机块模型DCSBM、考虑链接方向的随机块模型GSB。与SBM相似，混合模型NMM及其扩展模型也具有网络多类型结构发现能力。
四、本文研究的主要内容及研究框架
（一）本文研究的主要内容
在线社会媒体产生的网络结构复杂、规模庞大，广义社区发现概率模型可以更好地处理在线网络潜在结构发现问题.但当前的广义社区发现模型及算法求解的速度和准确性还远远不能应对实际网络应用的需求，因此，有必要研究更符合实际的广义社区发现模型和算法，以提高网络结构发现算法的准确性和高效性。本文在GSB模型和NMM模型基础上展开研宄，首先设计一个启发式的广义社区发现快速算法估计GSB模型的参数；然后扩展GSB模型设计更实际的网络生成模型PPSB模型，并进一步融合网络节点内容；为降低PPSB模型的过拟合现象及对训练数据之外数据的可适性，对模型参数引入先验分布，并设计随机变分推理算法求解模型参数。最后，针对Newman的NMM模型可更快地实现类个数较大的广义社区发现优点，设计在线EM算法求解模型参数。本论文研究内容详细介绍如下：1)设计基于扩展随机块模型的快速广义社区发现算法随机块模型可生成多种类型结构的网络，该模型基于节点的概率对等性识别网络的广义社区。但简单随机块模型的网络生成假设不符合实际网络特性，模型参数估计算法不能有效处理大规模网络。扩展随机块模型GSB可更好的对网络节点的不同角色建模，但该模型的参数估计算法效率较低。为提高GSB模型参数估计算法的运行效率，基于GSB模型设计一种快速参数估计算法，使其在保证与GSB参数估计EM算法具有相似准确率的条件下，更有效地识别网络广义社区。2)设计网络广义社区发现链接模型和内容网络广义社区发现模型及求解算法扩展随机块模型对网络生成过程建模时，没有同时考虑节点的产生链接能力、接收链接能力、节点混合隶属度对生成网络链接的影响。不能很好地对实际幂率度分布的网络建模，且没有考虑节点内容属性。设计新的广义社区发现链接模型，使该模型具有己有随机块模型框架下所有模型广义社区发现的优点，还可以生成节点度服从幂率度分布的网络。基于设计的链接模型，进一步对网络节点内容属性和拓扑结构同时建模实现内容网络广义社区发现。3)设计三层广义社区发现贝叶斯模型及基于随机变分推理的推理算法上述链接模型可同时对多类型网络结构和节点混合隶属度建模，但是该模型没有对节点混合隶属度和网络链接概率生成过程建模。致使模型易随训练集合大小线性增长，出现过拟合现象。也不易为训练集合之外的网络实体实现链接预测。另外，己有的EM参数估计算法在千数个节点上运行时间都需要几个小时，使模型不适用处理大规模网络。针对己有广义社区发现算法存在的这些问题，设计一个三层贝叶斯网络广义社区发现模型，在上述设计的链接模型基础上增加节点隶属度和网络块链接模式的生成过程。并基于随机变分推理(Stochastic VariationalInference)设计参数估计算法。最后，与同类流行概率方法比较验证该模型和算法的有效性。4)设计基于混合模型的在线EM(ExpectationMaxiinization)广义社区发现算法随机块模型可对更多类型的网络结构聚类问题建模，其在线参数估计算法关于类个数的复杂度是C?(i^2)。Newman的混合模型也可以发现网络中潜在的广义社区，其关于类个数的复杂度为C>(in,可处理类个数较大的网络广义社区发现。但是基于混合模型的广义社区发现算法每次迭代需要在所有网络链接上操作，致使该算法不能处理百万级或更大规模的网络，从而不能应用到实际网络结构发现中。为了使该混合模型求解算法可应用到实际大规模网络上，设计一个基于混合模型的在线变分EM广义社区发现算法。最后与混合模型的传统EM算法和简单随机块模型的在线EM算法进行性能比较.
（二）本文研究框架
本文研究框架可简单表示为：
五、写作提纲
致谢 5-6
中文摘要 6-8
ABSTRACT 8-10
1 绪论 14-33
1.1 研究背景和意义 15-19
1.2 研究现状 19-27
1.2.1 社会网络建模 19-20
1.2.2 网络广义社区发现概率模型 20-22
1.2.3 大规模网络社区发现概率模型 22-23
1.2.4 基于内容的主题发现模型 23
1.2.5 融合内容和链接的社区(主题)发现模型 23-27
1.3 问题分析 27-29
1.4 主要研究内容 29-31
1.5 文章组织结构 31-32
1.6 小结 32-33
2 相关理论和技术 33-54
2.1 网络链接模型 33-49
2.1.1 简单随机块模型SBM 33-37
2.1.2 传统社区发现链接模型 37-41
2.1.3 广义社区发现链接模型 41-48
2.1.4 大规模网络社区发现链接模型 48-49
2.2 相关算法 49-53
2.2.1 参数估计准则 49-50
2.2.2 参数近似推理方法 50-53
2.3 小结 53-54
3 基于扩展随机块模型的快速广义社区发现算法 54-64
3.1 一种快速广义社区发现算法FGSB 54-58
3.1.1 存储空间改进策略 55-56
3.1.2 运行时间改进策略 56-57
3.1.3 FGSB 57-58
3.2 实验 58-63
3.2.1 FGSB在不同结构网络上的性能比较 59-60
3.2.2 不同清晰度的传统社区网络上算法性能比较 60-62
3.2.3 大规模网络上FGSB算法性能测试 62-63
3.3 小结 63-64
4 融合节点流行度、生成度及内容的广义社区发现方法 64-80
4.1 生成度-流行度随机块模型PPSB 64-68
4.2 融合内容和链接的内容模型PPSB-DC 68
4.3 实验 68-78
4.3.1 数据描述 69-71
4.3.2 非重叠社区度量 71-72
4.3.3 收敛性分析和重叠社区发现 72-73
4.3.4 非重叠社区发现性能比较 73-76
4.3.5 PPSB模型和PPSB-DC模型选择类个数 76-78
4.4 小结 78-80
5 基于随机变分推理的大规模网络广义社区发现方法 80-94
5.1 相关模型分析 80-81
5.2 三层贝叶斯网络链接模型和随机变分推理算法 81-88
5.2.1 三层贝叶斯网络链接模型 81-83
5.2.2 基于随机变分推理的广义社区发现算法GPPSB-SVI 83-88
5.3 实验 88-92
5.3.1 GPPSB-SVI算法的准确度计算测试 90
5.3.2 GPPSB-SVI算法效率测试 90-92
5.4 小结 92-94
6 基于混合模型的在线大规模网络广义社区发现方法 94-111
6.1 基于混合模型的在线变分EM算法Online-VEM 94-100
6.1.1 观测网络对数似然下界的可加性 96-98
6.1.2 在线变分EM算法 98-100
6.2 Online-VEM算法选择类个数 100-101
6.3 实验 101-109
6.3.1 数据描述 101-102
6.3.2 社区发现结果度量标准 102-103
6.3.3 Online-VEM算法的鲁棒性测试 103-104
6.3.4 算法性能比较 104-108
6.3.5 Online-VEM算法类个数选择 108-109
6.4 小结 109-111
7 总结与展望 111-115
7.1 全文工作总结 111-113
7.2 下一步研究展望 113-115
参考文献 115-121
六、本文研究进展(略)
七、目前已经阅读的主要文献
[1] Fortunate S. Community detection in graphs. Physics Reports, 2010, 486(3):75-174.
[2] Newman M E，Leicht E A. Mixture models and exploratory analysis in networks. Proceedingsof the National Academy of Sciences, 2007, 104(23):9564-9569.
[3] 杨博，刘杰，刘大有.基于随机网络集成模型的广义网络社区挖掘算法.自动化学报，2010，38(5):812-822.
[4] 王飞跃，李晓晨，毛文吉,etal.社会计算的基本方法与应用.杭州：浙江大学出版社，2013.
[5] Newman M. Finding community structure in networks using the eigenvectors of matrices.Physical Review E, 2002,
[6] Kempe D, Kleinberg J, Tardos E. Maximizing the spread of influence through a social network.Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery anddata mining. ACM, 2003. 137-146.
[7] Chi Y, Song X，Zhou D, et al. Evolutionary spectral clustering by incorporating temporalsmoothness. Proceedings of the 13th ACM SIGKDD international conference on Knowledgediscovery and data mining. ACM, 2007. 153-162.
[8] Lin Y R, Chi Y, Zhu S，et al. Facctnet: a framework for analyzing communities and theirevolutions in dynamic networks. Proceedings of the 17th international conference on WorldWide Web. ACM, 2008. 685-694.
[9] Yang T, Chi Y, Zhu S, et al. Detecting communities and their evolutions in dynamic socialnetworks—a Bayesian approach. Machine learning, 2011, 82(2):157-189.
[10] Yang B, Liu J, Liu D. Characterizing and extracting multiplex patterns in complex networks.Systems, Man, and Cybernetics, Part B: Cybernetics, EEEE Transactions on, 2012, 42(2):469-481.
[11] Newman M. Communities, modules and large-scale structure in networks. Nature Physics,2012’ 8(1):25-31.
[12]张宏毅,王立威,陈瑜希.概率图模型研宄进展综述.软件学报，2013，24(11):2476-2497.
[13] Koller D, Friedman N. Probabilistic graphical models: principles and techniques. MIT press,2009.
[14] Snijders T A, Nowicki K. Estimation and prediction for stochastic blockmodels for graphswith latent block structure. Journal of classification, 1997, 14(1):75-100.
[15] Nowicki K, Snijders TAB. Estimation and prediction for stochastic blockstructures. Journalof the American Statistical Association, 2001, 96(455): 1077-1087,
[16] Airoldi E M, Blei D M, Fienbcrg S E, et al. Mixed membership stochastic blockmodels. J.Mach. Learn. Res., 2008,9:1981-2014.
[17] Shen H W, Cheng X Q，Guo J F. Exploring the structural regularities in networks. PhysicalReview E, 2011, 84(5):056111
[18] Karrcr B, Newman M E. Stochastic blockmodels and community structure in networks. Phys?ical Review E, 2011, 83(1):016107.
[19] Fienberg S E, Wasserman S S. Categorical data analysis of single sociometric relations. Soci.ological methodology, 1981.156-192.
[20] Holland P W，Laskey K B，Lcinhardt S. Stochastic blockmodels: First steps. Social networks,1983,5(2):109-137.
[21] Wasserman S, Anderson C. Stochastic a posteriori blockmodels: Construction and assessment.Social Networks, 1987，9(1):1 一36.
[22] Guimer^ R, Sales-Pardo M. Missing and spurious interactions and the reconstruction of com?plex networks. Proceedings of the National Academy of Sciences, 2009, 106(52):22073-22078.
[23] Hastings M B. Community detection as an inference problem. Physical Review E, 2006,74(3):035102.
[24] Hofman J M, Wiggins C H. Bayesian approach to network modularity. Physical review letters,2008，100(25):258701.
[25] Moreno J L, Jennings H H. Who shall survive? 1934..
[26] Erd6s P, Rinyi A. On the evolution of random graphs. Publication of the Mathematical Instituteof the Hungarian Academy Sciences, 1960, 5:17-61.
[27] Goldenberg A, Zheng A X，Fienberg S E, et al. A survey of statistical network models. Foun?dations and Trends? in Machine Learning, 2010，2(2):129-233.
[28] Travers J, Milgram S. An experimental study of the small world problem. Sociometry, 1969.425-443.
[29] Holland P W, Leinhardt S. An exponential family of probability distributions for directedgraphs. Journal of the american Statistical association, 1981，76(373):33-50.
[30] Watts D J, Strogatz S H. Collective dynamics of 'small-world' networks, nature, 1998，393(6684):440-442.