基于核心节点的局部社区发现算法.docxVIP

中文摘要随着mternet的不断发展和普及, 放网络环境下的各种电子应用平台不断涌现,为人和人之间的沟通提供了丰富多彩的电子技术手段和虚拟交互环境。在此应用背景下,社会网络分析逐步成为工业界和学术界普遍关心的热点问题,人们希望通过对虚拟社会网络进行定量的、有效的数据分析和挖掘,揭示隐含在虚拟数据背后的信息、规律和知识。社区是中观视角有效描述社会网络结构的重要指标,而社区发现也是社会网络分析中的基础性研究问题之一,在过去十多年内吸引了国内外众多研者的关注并形成了很多研究成果。但大多数研究都是以获取全局网络的所有信息为前提的,这在实践中难以满足。本文充分利用社会网络数据的局部性特征以及幂律分布、帕累托效应等特征,从微观(节点、边)和中观(中心子团)两个层面针对社区发现问题展开算法研宄。论文主要工作及创新点如下:1)充分利用社会网络中存在的普适幂律分布特性,提出了基于核心节点的局部社区发现算法LLCDA,从而回避传统算法对“必须获取全局网络信息”的条件限制。该算法使用改进的PageRank进行节点排序,然后利用网络中的局部结构信息来优化一个局部目标函数,由一个初始的种子节点,通过不断优化目标函数来获取其所在的局部社区,算法优势在于利用重要性高的节点进行社区发现,并且只需网络中的少量局部信息就可以完成社区的发现,算法效率比传统算法要高。2)针对大部分社区发现算法“社区规模不可控”及“分辨率极限限制”的问题,在上述LLCDA算法的基础上,提出了基于核心节点的多分辨率社区发现算法MRCDA,该算法通过修改的PageRank排序节点重要性并选择初始节点,同时使用基于Spin-glass模型的多分辨率模块度作为局部社区扩张的目标函数,从而扩张出规模可控的局部社区结构。算法优势在于通过参数的选择来控制不同网络应用下的不同规模的社区的发现,并且局部社区的发现效率较传统方法要更高。3)针对大部分社区发现研宄的对象都集中在节点,而忽视了边在社区发现中的重要性的问题,本文将上述算法LLCDA的思想移植到边社区的发现中,提出了基于核心边的边社区发现算法LLCM,该算法使用边聚类系数进行边排序,并利用选取的核心种子边作为边社区初始成员,再利用网络中的局部信息去挖掘边社区结构,并可转化为对应的节点型的重叠社区。算法优势在对高度重叠社区的发现有较好的效果,并且算法在边社区的挖掘效果和重叠社区的覆盖上都有较好的表现。4)针对传统社区发现研宄并不区分网络中节点的不同重要性及影响力,本文将网络中的节点的角色按照其重要性和影响力分为核心节点、中心成员节点和普通成员节点,基于此提出一种中心子团的定义,通过中心子团的发现找出网络中的核心区域;其次,提出一英文摘要With the rapid development and mature application of the Internet technique; a variety ofapplication platforms of the open network provide different electronic tools and virtualinteractive environments for communication and information exchange between people. In thecontext of those applications, social network analysis has gradually become a hot issue both inindustry and academic. People think the social network could be analyzed and minedquantitatively. And some hidden information and knowledge can be revealed from the analysisand mining. Community mining is one of the basic research problems in social network analysis.In the past decade, it has attracted more and more attention in the research community.Community detection technique has been developed rapidly and many research findings havebeen proposed. However, most studies are based on the global informa