论文部分内容阅读
社区结构作为社交网络的重要特征之一,在宏观上可以帮助我们深入理解网络的拓扑特性和本质的同时,在微观上对探索网络中用户的行为特点和用户之间的逻辑关系有着重要的作用。因此,社区发现作为社交网络的一项重要研究吸引众多领域的科研人员从不同的角度进行研究,但目前社区发现的研究仍然有许多未能解决的问题,如社交网络的重叠社区发现问题、异质网络的社区发现问题和社区发现的应用等等。在社区发现领域,早期的社区发现方法主要集中在对不含协变量或其他信息的社交网络做非重叠社区发现,而混合隶属度随机块模型(Mixed Membership Stochastic Block Model,MMSB)可以对有向网络作重叠社区划分,同时可以获得各节点在各社区的隶属度情况。但是现有的MMSB模型只考虑了社交网络本身的连接信息,并未考虑节点的协变量信息,这会令模型的社区划分精度和应用受到限制。Roy et al.(2018)考虑了用带有节点协变量的随机块模型(Stochastic Model,SBM)来研究Facebook数据,但SBM模型不能用于重叠社区。基于以上,本文通过研究现有的社交网络社区发现方法,分析各自的优缺点,提出了基于混合隶属度随机块模型的含有协变量信息的重叠社区划分方法,主要完成了以下几方面的研究内容:1)在MMSB模型的基础上,提出了一种针对含有节点协变量信息网络的重叠社区划分模型。首先,通过建立生成模型来模拟观测网络的生成过程,根据估计的参数,即节点的混合隶属度,对社交网络进行社区划分。由于本模型的似然函数复杂度比较高,且参数之间并不是互相独立的,直接利用极大似然估计方法不方便进行估参,因此,本文运用变分期望最大(Variational Bayes expectation maximization,VBEM)算法做参数估计。我们将从数学角度说明了模型构建的合理性,并详细地推导了利用VBEM算法求解模型参数的迭代公式。2)众所周知,社交网络中的节点会含有很多协变量信息,如Facebook用户的年龄、性别、院校、职业、喜好、家乡等,有些协变量对于社区发现并没有很重要的作用。尤其是在社交网络中节点足够多时,筛选协变量可以在保证社区发现效果的前提下,大大降低模型的运行时间。本文筛选协变量采用的办法是The Least Absolute Shrinkage and Selection Operator(Lasso)法,该方法能够对变量进行筛选降低模型的复杂程度,本文还介绍了确定社区数目的方法。3)运用含有协变量的MMSB模型做数值模拟以此来评估本模型的性能。主要评估本模型在单一社区和重叠社区以及低、中、高不同的进出比率和平均度下构造的生成网络下的表现情况。评估模型所用的主要指标是标准化互信息和模块度。结果表明,含有协变量的MMSB模型在高平均度下生成的网络社区发现效果比较好。4)运用含有协变量的MMSB模型对Facebook数据做社区发现,进行实证分析,并通过可视化的方法显示社区划分结果。该实证表明本模型的似然函数可以收敛,通过构建邻接阵的热力图、展示节点的混合隶属度等展示模型的划分效果。最后,利用模块度方法,我们对含有协变量的MMSB模型和基础的MMSB模型以及含有协变量的SBM模型的社区发现效果进行量化比较。最终,我们发现,含有协变量的MMSB模型的社区划分效果要优于其他两个模型。