论文部分内容阅读
随着Internet的不断发展和普及,开放网络环境下的各种电子应用平台不断涌现,为人和人之间的沟通提供了丰富多彩的电子技术手段和虚拟交互环境。在此应用背景下,社会网络分析逐步成为工业界和学术界普遍关心的热点问题,人们希望通过对虚拟社会网络进行定量的、有效的数据分析和挖掘,揭示隐含在虚拟数据背后的信息、规律和知识。社区是中观视角有效描述社会网络结构的重要指标,而社区发现也是社会网络分析中的基础性研究问题之一,在过去十多年内吸引了国内外众多研究者的关注并形成了很多研究成果。但大多数研究都是以获取全局网络的所有信息为前提的,这在实践中难以满足。本文充分利用社会网络数据的局部性特征以及幂律分布、帕累托效应等特征,从微观(节点、边)和中观(中心子团)两个层面针对社区发现问题展开算法研究。论文主要工作及创新点如下:1)充分利用社会网络中存在的普适幂律分布特性,提出了基于核心节点的局部社区发现算法LLCDA,从而回避传统算法对“必须获取全局网络信息”的条件限制。该算法使用改进的PageRank进行节点排序,然后利用网络中的局部结构信息来优化一个局部目标函数,由一个初始的种子节点,通过不断优化目标函数来获取其所在的局部社区,算法优势在于利用重要性高的节点进行社区发现,并且只需网络中的少量局部信息就可以完成社区的发现,算法效率比传统算法要高。2)针对大部分社区发现算法“社区规模不可控”及“分辨率极限限制”的问题,在上述LLCDA算法的基础上,提出了基于核心节点的多分辨率社区发现算法MRCDA,该算法通过修改的PageRank排序节点重要性并选择初始节点,同时使用基于Spin-glass模型的多分辨率模块度作为局部社区扩张的目标函数,从而扩张出规模可控的局部社区结构。算法优势在于通过参数的选择来控制不同网络应用下的不同规模的社区的发现,并且局部社区的发现效率较传统方法要更高。3)针对大部分社区发现研究的对象都集中在节点,而忽视了边在社区发现中的重要性的问题,本文将上述算法LLCDA的思想移植到边社区的发现中,提出了基于核心边的边社区发现算法LLCM,该算法使用边聚类系数进行边排序,并利用选取的核心种子边作为边社区初始成员,再利用网络中的局部信息去挖掘边社区结构,并可转化为对应的节点型的重叠社区。算法优势在对高度重叠社区的发现有较好的效果,并且算法在边社区的挖掘效果和重叠社区的覆盖上都有较好的表现。4)针对传统社区发现研究并不区分网络中节点的不同重要性及影响力,本文将网络中的节点的角色按照其重要性和影响力分为核心节点、中心成员节点和普通成员节点,基于此提出一种中心子团的定义,通过中心子团的发现找出网络中的核心区域;其次,提出一种“连接强度”的度量,用以计算网络中任意节点对直接的相似度;最后,本文借鉴了传统聚类算法的思想,提出了一种基于中心子团的社区发现算法,利用中心子团和连接强度对节点的社区归属进行分配。算法优势是在加权网络和大规模网络上的社区发现效果较好,算法时间复杂度较低,运行效率高。5)针对传统基于聚类的社区发现方法只能发现规模同等的社区,且对社区内部稠密程度不可控,本文在上述算法CCDM的基础上进行了改进,提出了两个基于密度社区发现算法DCCS和ONDCS,其中DCCS算法简单高效、易于实现,而ONDCS具有较高的稳定性和高效性,算法对于发现高密度差异性的社区具有良好的效果。