异构社交网络中社区发现算法研究

《异构社交网络中社区发现算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ChinaUniversityofMining&Technology,Beijing博士学位论文异构社交网络中社区发现算法研究学院：机电与信息工程学院学号：TBP120404018作者：王婷学科专业：计算机应用技术导师：钱旭教授2016年1月中图分类号：TP31密级：单位代码：11413博士学位论文中文题目：异构社交网络中社区发现算法研究英文题目：CommunityDetectioninHeterogeneousSocialNetworks作者：王婷学号：TBP120404018学科专业：计算机应用技术研究方向：数据挖掘导师：钱旭职称：教授论文提交日期：2015年10

2、月22日论文答辩日期：2015年12月11日学位授予日期：2015年12月30日中国矿业大学（北京）独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中国矿业大学（北京）或其他教学机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。关于论文使用授权的说明本人完全了解中国矿业大学（北京）有关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件，允许论文被查阅或借阅；学

3、校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。（保密的论文在解密后应遵守此规定）摘要社会网络中的社区发现作为数据挖掘研究领域的一个热点，近几年发展迅速，研究内容主要集中在通过对网络中存在的关系进行分析，得到社区划分的结果。随着Web2.0的兴起和社交网络的蓬勃发展，出现了多种新型的在线社交方式，单一的社会网络关系结构已经不足以应对解决现实世界的问题，所以学者们进一步提出了异构社交网络（HeterogeneousSocialNetworks）的概念。这是一个复杂的网络抽象结构，网络中通常包含多种关系和实体，这些不同的关系和实体组合形成了网络的

4、多样化复杂结构。如何处理这些复杂的结构和获取社区结构信息，是对传统的社会网络社区发现的一个新的挑战。本文将针对划分异构网络过程中，多维度、多维复杂关系、多类型节点等特性所带来的网络数据重构与降维问题；传统研究仅仅局限于图链接关系，并未考虑语义信息，也就是主题对划分社区的帮助作用；再者传统划分算法需要预先知识和预先设定社区个数来得到划分结果，但真实世界社交网络中的社区个数往往是不可知的，尤其在大规模的社交网络中预先知识不可知等问题展开研究。主要包括异构社交网络通用分析框架，基于标签传播近似线性的社区发现算法，基于主题感知的社区发现算法等，从而设计出高效快速的异构网络社区

5、发现算法。研究内容及创新点包括：1）提出了一种异构社交网络分析框架，针对异构网络进行数据重构，利用降维方法得到同构网络或者二分图，然后使用社区发现算法对同构网络或者二分图进行社区划分，从而将异构网络社区划分问题进行有效转化。2）将多维异构网络转化为同构网络后，提出了一种并行种子扩展算法PHSE，用来发现社交网络中的重叠社区结构。算法PHSE通过局部适应度函数优化和混合种子扩展策略来得到自然社区。相较于算法LFM，算法PHSE不仅在合成网络中有非常好的划分结果，同时在真实世界社交网络中也有非常好的划分结果。尤其，当合成网络的节点重叠度高达On=50%时，依旧可以准确的划

6、分出重叠社区。3）提出了一种基于标签传播的社区发现算法iSLPA，同时支持有向图、无向图和二分图的社区划分，算法在迭代过程中采用标签混合更新模式，并且在真实社交网络数据集上表现出准确的社区划分结果。4）提出了一种基于并行计算框架Dpark的标签传播算法HLPA，针对不同的网络使用了不同的节点标签初始化策略，包括有向图、无向图和二分图，同时还使用了混合标签更新策略使得算法更加稳定，标签衰减策略使得算法可以避免划分出“monster”社区，也可以使得较小的社区得到充分成长。相较于之前的基于标签传播的算法，算法HLPA在划分benchmark基准真实社交网络时表现出了非常高

7、的准确性，而且在划分大规模真实社交网络时表现得非常有竞争力，大大提高I算法效率，针对300万节点、1.7亿条边的二分图划分社区只需要37.12分钟，而且通过分析验证了划分出的社区是有真实含义的社区结构。5）根据1）中提出的异构社交网络分析框架，提出了一种基于主题感知的异构网络社区发现算法，该算法通过对数据重构将多模网络转化为二模网络（用户-文档），采用算法LDA-light从异构网络转化得到的二模网络映射为带权重的二分图网络（用户-主题），采用新提出的带权重的二分图社区发现算法WLPA对二分图进行社区划分，最终将用户和主题两种不同的实体划分在同一社区