论文部分内容阅读
随着信息技术的飞速发展,Twitter、Facebook、新浪微博、微信等各类在线社交平台逐渐改变人们的生活和工作方式。在这些平台上,每天产生大量、繁杂的网络数据,包括节点链接关系数据和内容属性数据。链接关系数据隐含网络统计特性、潜在结构和交互规律,内容属性数据包含丰富的数字图像、文本和音频等描述节点特征属性的内容信息。对这些复杂的网络数据进行挖掘和分析为机器学习、数据挖掘等领域提供了新的机遇和挑战。网络的社区发现是进行网络分析的一个基本问题,这对实现数据的自然划分、数据压缩、可视化分析、以及内容推荐等具有重要的科学意义和应用价值。该问题提出以来,各种社区发现方法和技术应运而生,其中,K-means聚类算法由于其思想简单、易于实现、对大规模数据的处理具有高效性和可伸缩性等,在网络数据的节点划分中得到广泛应用。但该算法也存在明显的缺陷:1)对初始点的选取十分敏感,其性能容易受初始种子节点的影响;2)要求预先指定聚类个数。因此,针对网络型数据的特性,如何提出K-means型划分聚类方法的初始化策略有待进一步研究。研究发现,实际网络通常稀疏而且存在噪声信息,对于社区结构不清晰的网络,如何利用网络中辅助信息挖掘有意义的社区结构为研究者提出新的要求。本文以网络数据为研究对象,对K-means型划分聚类方法中的聚类个数、初始点选取、如何有效处理社区结构不清晰网络以及将节点的属性特征进行有效结合展开研究,并对如何考虑边的不确定性进行探索。本文的主要研究成果包括:1)提出了一种基于节点中心度和离散度的社区发现方法。根据网络数据的特性,基于网络中节点的中心度和离散度两个量化指标,从决策图和综合得分两个角度给出确定聚类个数和初始中心选择的策略,为基于K-means型方法进行网络的社区发现提供一定的指导,人工网络和实际网络上的对比实验验证了提出方法的有效性。在该方法基础上,提出了一种通过节点属性的k近邻图(k Nearest Neighbor, kkNN)增强的社区发现方法,通过节点的属性相似性对原始链接关系网络进行增强,从而降低网络稀疏性和噪声对节点划分的影响。实验对比表明该方法不仅能够处理不同节点属性类型的网络,而且具有较高的划分准确率。2)提出了主动融合先验信息的社区发现方法。对于社区结构不清晰的网络,通常难以准确选取聚类个数和初始中心,而且节点容易划分错误。基于主动学习,提出一种主动选择节点和链接的策略。该方法是一种双向方法,通过增强节点到所属类的凝聚力并增大类间距离使边界清晰化,从而提高节点划分的准确率。而且,通过主动选择节点,能够自动估计社区个数并选择初始中心。该方法能够以少量的人工标注,显著提高节点划分的准确率。3)提出了一种自适应融合链接结构信息和节点内容属性信息的社区发现方法(Adapt fusion of structural and attribute information, Adapt-SA)。该方法是一种局部加权的K-means模型,通过交替迭代,能够自动学习每个节点在两种异构信息的融合权重以及节点划分的隶属度矩阵。该方法得到的节点划分结果,使得同类的节点不仅链接紧密,而且具有较高的属性相似性。理论和实验验证了算法的收敛性,实验分析了模型对信息融合权重学习的有效性。通过与其他融合节点属性的社区发现方法对比,表明了Adapt-SA方法的性能。4)提出了不确定属性网络中的社区发现方法。现实网络中节点之间的边通常具有不确定性,而且节点具有高维的属性信息。针对这类复杂的网络数据,本章提出不确定属性网络的社区发现方法,综合考虑边的不确定性以及节点的属性信息。通过边的不确定性提取出重要的节点属性,进一步利用重要属性减弱边的不确定性以挖掘有意义的社区结构。人工网络以及实际网络的实验对比证明了方法的有效性,参数的实验分析验证了对抽样数以及权重阈值的鲁棒性。