论文部分内容阅读
社会信息网络是基于交互式社会媒体平台建立起来的一种新型网络,其以虚拟化互动的交流模式极大地推动了用户参与网络的广度与深度,是人类社会活动在网络空间的虚拟映射。研究和分析社会信息网络可以间接地认识和学习人们在现实社会中的情感倾向和行为特点,为社会学、经济学、网络应用、隐私保护与安全等相关学科领域的应用研究提供有价值理论依据和技术支撑。但随着用户数目的不断增长和网络结构的不断复杂化,单纯地从节点入手或者宏观整体分析社会信息网络,其难度均非常大。因此,研究者们选择从一种中观尺度“社区”来度量网络,降低社会信息网络分析的复杂性。 社区发现是非监督学习领域的一个热点问题。尽管社区发现算法在过去的十多年发展很快,但较高的计算复杂度使得已有算法难以扩展分析纷繁芜杂的社会信息网络,特别是随着社会媒体应用技术飞速发展而不断膨胀的大规模社会信息网络。如何快速且有效的挖掘大规模社会信息网络社区是一项极具挑战的任务。针对社会信息网络数据结构的不同特点,本文沿着算法适用性呈递进式逐渐增强的关系主线,依次研究和设计了三种不同的高效社区发现算法,其分别适用于富含三角形拓扑结构、包含一定三角形拓扑结构以及无三角形拓扑结构要求的不同社会信息网络分析。具体而言,本文的主要贡献和创新点如下: 1.提出了一种基于三角形拓扑结构的多层社区发现算法 大规模社会信息网络社区结构的分析研究中,多层社区发现是一类可扩展性极好的方法,其通过一种多层模式先将网络规模降阶,再进行社区挖掘并最终以间接地方式得到网络的社区发现结果。但已有的多层社区发现算法,或因社区发现精度较低,或因计算复杂度较高,均难以进一步扩展分析更大规模社会信息网络。针对上述问题,本文提出了一种基于三角形拓扑结构的多层社区发现算法(TMLCD)。通过将具有强社区效应的三角形进行聚合粗化,TMLCD不仅保持了粗化网络与原大规模社会信息网络的基本社区结构一致性,提高了社区发现精度,而且以较高的粗化缩减比率和相对于局部聚集子团计算简单的三角形遍历过程,加快了社区发现的速度。另外,流算法的引入,降低了多层社区发现对系统内存的占用。实验结果表明,TMLCD的性能明显优于目前较好水平的多层社区发现算法,解决了已有算法中存在的诸多问题,实现了预期高精度、低损耗的目标。但是,TMLCD仅适用于富含三角形拓扑结构的社会信息网络研究。 2.提出了一种基于预粗化抽样NystrOm方法的谱分析算法 为进一步挖掘社会信息网络社区,而不局限于富含三角形的拓扑结构,我们研究谱分析算法。谱分析算法是一种能够发现全局最优解、且不受线性可分条件限制的社区发现算法,但特征矩阵分解计算复杂度较高,限制了其可扩展分析能力。大量近似算法中,基于Nystr(O)m方法的谱分析精度最高,但已有的算法须基于节点多维属性先建立相似度矩阵再进行计算,因此难以直接从链接结构的角度分析大规模社会信息网络。针对上述问题,本文提出了一种基于预粗化抽样Nystrom方法的谱分析算法(NSCD)。通过预粗化处理,NSCD先将原大规模社会信息网络转化成一个加权网络,并直接构建权重矩阵用于NystrOm方法的抽样,提高了社区发现的精度,且省略了相似度矩阵计算与NystrOm方法一同加快了谱分析算法社区发现的速度。实验结果表明,NSCD完全适用于直接分析基于链接结构的大规模社会信息网络,且在计算精度和速度方面均优于其他近似谱分析算法。但是,NSCD研究的社会信息网络仍需包含一定的三角形拓扑结构。 3.提出了一种基于遗传算法的多路最大间隔社区发现算法 为设计一种无三角形拓扑结构要求、具有普遍适用性的社会信息网络分析算法,我们进一步研究最大间隔社区发现算法。最大间隔社区发现是由支持向量机的基本理论拓展应用于非监督学习领域而形成的一种具有高计算精度算法。但是,由社区属性标签未知而产生的非凸极值优化问题,使得最大间隔算法的时间复杂度过高且易于陷入局部极小值。针对上述问题,本文提出了一种基于遗传算法的多路最大间隔社区发现算法(GAM3CD)。GAM3CD首先推导出了一种对偶空间下的多路最大间隔社区发现算法,并针对定义式中Kernel矩阵采用NystrOm方法进行低秩近似,极大地加快了算法的计算速度,再运用遗传算法将其固有的非凸规划问题转化为可有效求得全局最优解的凸规划问题,提升了算法的整体性能。实验结果表明,GAM3CD性能均优于已有的最大间隔社区发现算法,特别是在保持其高计算精度的前提下提升了其计算速度,使之完全适合于分析具有各种数据结构的大规模社会信息网络。