社会网络中的社区发现作为数据挖掘研究领域的一个热点,近几年发展迅速,研究内容主要集中在通过对网络中存在的关系进行分析,得到社区划分的结果。随着Web2.0的兴起和社交网络的蓬勃发展,出现了多种新型的在线社交方式,单一的社会网络关系结构已经不足以应对解决现实世界的问题,所以学者们进一步提出了异构社交网络(Heterogeneous Social Networks)的概念。这是一个复杂的网络抽象结构,网络中通常包含多种关系和实体,这些不同的关系和实体组合形成了网络的多样化复杂结构。如何处理这些复杂的结构和获取社区结构信息,是对传统的社会网络社区发现的一个新的挑战。本文将针对划分异构网络过程中,多维度、多维复杂关系、多类型节点等特性所带来的网络数据重构与降维问题;传统研究仅仅局限于图链接关系,并未考虑语义信息,也就是主题对划分社区的帮助作用;再者传统划分算法需要预先知识和预先设定社区个数来得到划分结果,但真实世界社交网络中的社区个数往往是不可知的,尤其在大规模的社交网络中预先知识不可知等问题展开研究。主要包括异构社交网络通用分析框架,基于标签传播近似线性的社区发现算法,基于主题感知的社区发现算法等,从而设计出高效快速的异构网络社区发现算法。研究内容及创新点包括:1)提出了一种异构社交网络分析框架,针对异构网络进行数据重构,利用降维方法得到同构网络或者二分图,然后使用社区发现算法对同构网络或者二分图进行社区划分,从而将异构网络社区划分问题进行有效转化。2)将多维异构网络转化为同构网络后,提出了一种并行种子扩展算法PHSE,用来发现社交网络中的重叠社区结构。算法PHSE通过局部适应度函数优化和混合种子扩展策略来得到自然社区。相较于算法LFM,算法PHSE不仅在合成网络中有非常好的划分结果,同时在真实世界社交网络中也有非常好的划分结果。尤其,当合成网络的节点重叠度高达On=50%时,依旧可以准确的划分出重叠社区。3)提出了一种基于标签传播的社区发现算法iSLPA,同时支持有向图、无向图和二分图的社区划分,算法在迭代过程中采用标签混合更新模式,并且在真实社交网络数据集上表现出准确的社区划分结果。4)提出了一种基于并行计算框架Dpark的标签传播算法HLPA,针对不同的网络使用了不同的节点标签初始化策略,包括有向图、无向图和二分图,同时还使用了混合标签更新策略使得算法更加稳定,标签衰减策略使得算法可以避免划分出“monster”社区,也可以使得较小的社区得到充分成长。相较于之前的基于标签传播的算法,算法HLPA在划分benchmark基准真实社交网络时表现出了非常高的准确性,而且在划分大规模真实社交网络时表现得非常有竞争力,大大提高算法效率,针对300万节点、1.7亿条边的二分图划分社区只需要37.12分钟,而且通过分析验证了划分出的社区是有真实含义的社区结构。5)根据1)中提出的异构社交网络分析框架,提出了一种基于主题感知的异构网络社区发现算法,该算法通过对数据重构将多模网络转化为二模网络(用户-文档),采用算法LDA-light从异构网络转化得到的二模网络映射为带权重的二分图网络(用户-主题),采用新提出的带权重的二分图社区发现算法WLPA对二分图进行社区划分,最终将用户和主题两种不同的实体划分在同一社区内,即划分出的社区带有语义信息,从而可以更好地进行社区结构分析。本文提出的社区发现算法具有一般性,可以推广到许多同构或者异构社交网络和数据集,并且可以应用到更广泛的实际问题中。
