复杂网络社区发现算法研究

发布时间：2017-04-04 23:11

  本文关键词：复杂网络社区发现算法研究，由笔耕文化传播整理发布。

【摘要】：将实体视为节点,实体之间的关系视为边,现实世界中的很多系统就可通过网络的形式来呈现,如学术论文及它们的引用关系可构成引文网络,网页及连接网页的超链接可形成万维网等。在这些系统(或网络)中,实体之间的关系通常较为复杂,表现出如小世界、无标度、自组织以及社区结构特性等简单网络所不具备的诸多性质,因此它们也被称为复杂网络。在复杂网络中,具有“与内部节点连接较为紧密,与外部节点连接较为稀疏”特征的节点的集合被称为社区。社区发现是复杂网络领域的一个研究热点,具有广泛的应用价值。例如,社区发现可对“引文网络中关联较紧密论文构成的社区”进行挖掘从而实现同领域论文的推荐,对万维网中的网页进行社区挖掘则可对相似主题的网页进行聚类进而实现热点事件的跟踪等。目前,国内外针对社区发现已经做了一些研究,提出了很多算法,如基于介数分割的算法、基于模块度优化的算法、基于谱分析的算法等。这些算法对社区发现研究的发展具有十分重要的意义,但它们仍存在诸如时间复杂度高或分辨率限制等问题。考虑到社区发现在实际应用中的重要性以及已有算法的不足,本文对其进行了深入研究。主要研究内容包括：一、对社区结构的增强机制进行了研究,提出了基于信息传播相似性的增强方法。社区结构增强的目的是将社区的轮廓进行一个初步呈现,为后续社区发现提供良好的数据基础,进而提升其准确性。文献中已有算法大多通过计算连边两端节点的相似性,并将该相似性值作为连边权值来实现社区结构的增强。但是传统的节点相似性计算方法仅考虑了共同邻居的个数,而未考虑邻居之间的连接关系。为了充分考虑连接关系对节点相似性的影响,本文引入了信息传播机制的思想,设计了一种基于分层结构的传播扩散模型对传播影响力进行了评估,并将信息传播的相似性测量值作为连边权值对社区结构进行了增强。实验表明,与传统方法相比,本文给出的社区结构增强方法能够更为有效地对社区轮廓进行呈现。二、在全局社区发现方面,针对模块度优化类社区发现算法中固有的分辨率限制问题,提出了一种通过调节增强程度来实现分辨率控制的方法。该方法首先对连边增强程度的差异性分量进行抽取,然后通过设定的增强因子将该分量与连边的原始权值进行混合,实现了可调节的社区结构增强。在利用加权模块度方法进行优化求解中,不同的增强因子对应着社区轮廓的不同凸显程度,因而社区的识别粒度也相应不同,从而实现了分辨率的可控性。实验表明,该方法可在一定程度上对分辨率限制问题进行缓解。此外,还提出了社区核心与连边增强权值相对应的假设,基于该假设,对社区中具有较高内聚性的凝聚子群进行了提取,并通过对凝聚子群进行基于模块度的局部优化和合并操作实现了社区结构的挖掘。实验表明基于凝聚子群扩展的社区发现算法具有较高的准确性。三、在局部社区发现方面,提出了基于弱化干扰节点的社区发现算法和基于凝聚核心扩展的社区发现算法。在基于弱化干扰节点的方法中,利用CnllLocal算法可能遗漏源节点的特点,将不包含源节点的邻居社区在社区发现过程中所起的干扰作用进行了弱化,提高了找到源节点实际隶属社区的可能性。在基于凝聚核心扩展的方法中,利用社区核心与连边增强权值相对应的假设,首先找到凝聚子群的核心,然后利用该核心取代源节点进行局部社区的扩展。实验表明,无论源节点处于社区核心还是边缘,该算法的效果都优于Bagraw、Clauset、CnllLocal等经典算法。本文的创新点主要在于：一、提出了基于信息传播相似性的社区结构增强方法,该方法充分考虑了节点之间的连接关系对节点相似性的影响,使社区结构增强的结果更具合理性。二、提出了通过调节社区结构增强程度来实现分辨率控制的方法,该方法能有效缓解分辨率限制问题。三、提出了连边增强权值(经过社区结构增强后的连边权值)与连边的社区核心性相对应的思想,基于该思想能实现对凝聚子群以及社区核心的抽取,从而提高全局以及局部社区发现的准确性。本文以复杂网络社区发现高效算法为主要目标,开展了社区结构增强、全局社区发现以及局部社区发现的相关算法研究,进一步发展了社区发现算法。计算实验表明,本文提出的社区发现算法具有准确性较高、时间复杂度较低的优势,为包括在线教育在内的众多领域中涉及到关系聚类的社区发现应用提供了理论基础。
【关键词】：社区发现 传播相似性 核心逼近 凝聚子群
【学位授予单位】：华中师范大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要5-7
• ABSTRACT7-13
• 第一章 绪论13-21
• 1.1 研究背景与意义13-15
• 1.2 国内外研究现状15-19
• 1.2.1 学习社区研究现状15-16
• 1.2.2 复杂网络社区发现研究现状16-19
• 1.3 主要研究内容19
• 1.4 论文的组织结构19-21
• 第二章 复杂网络社区发现相关内容21-32
• 2.1 复杂网络社区结构21-25
• 2.1.1 复杂网络及社区结构21-23
• 2.1.2 教育领域的网络模型建立23-25
• 2.2 评估标准25-26
• 2.2.1 模块度标准25-26
• 2.2.2 NMI标准26
• 2.3 社区发现相关概念26-29
• 2.3.1 模块度优化26-27
• 2.3.2 标签传播思想27-28
• 2.3.3 社区结构增强28-29
• 2.4 实验环境及数据29-30
• 2.4.1 实验环境29-30
• 2.4.2 真实数据集30
• 2.4.3 仿真数据集30
• 2.5 本章小结30-32
• 第三章 基于信息传播相似性的社区结构增强方法32-57
• 3.1 引言32-33
• 3.2 社区结构增强与社区发现的关系33
• 3.3 节点传播影响力覆盖范围的计算33-42
• 3.3.1 传播影响力范围分析34
• 3.3.2 SIR传播仿真模型分析34-35
• 3.3.3 传播概率扩散原理分析35-39
• 3.3.4 分层信息传播估计法39-42
• 3.4 传播相似性计算42-47
• 3.5 社区结构的增强47-50
• 3.6 实验与分析50-56
• 3.6.1 信息传播率对社区结构增强程度的影响50-52
• 3.6.2 增强效果及社区划分结果与增强因子的关系52-56
• 3.7 本章小结56-57
• 第四章 基于凝聚子群扩展的社区发现算法57-89
• 4.1 引言57-58
• 4.2 基于社区结构增强的分辨率调节58-64
• 4.2.1 分辨率限制问题58-60
• 4.2.2 利用社区结构的增强对分辨率问题进行缓解60-64
• 4.3 基于山体结构抽取原理的凝聚子群发现64-76
• 4.3.1 凝聚子群特性分析64-68
• 4.3.2 凝聚子群的抽取68-75
• 4.3.3 凝聚子群中重叠元素的划分75-76
• 4.4 基于局部优化的社区发现76-85
• 4.4.1 基于模块度的局部优化76-82
• 4.4.2 子社区合并策略82-85
• 4.5 实验与分析85-87
• 4.6 本章小结87-89
• 第五章 局部社区社区发现算法89-105
• 5.1 引言89
• 5.2 基于弱化干扰节点的局部社区发现算法89-96
• 5.2.1 已有算法的不足及弱化干扰节点算法的可行性分析90-92
• 5.2.2 算法描述92-93
• 5.2.3 实验与分析93-96
• 5.3 基于凝聚核心扩展的局部社区发现算法96-104
• 5.3.1 算法描述97-98
• 5.3.2 实验与分析98-104
• 5.4 本章小结104-105
• 第六章 总结及展望105-108
• 6.1 本文工作总结105-106
• 6.2 下一步工作展望106-108
• 参考文献108-115
• 在校期间发表的论文、科研成果等115-116
• 致谢116

【参考文献】

中国期刊全文数据库 前5条

1 陈向东;方群;唐辉云;;Blog虚拟学习社区的社会网络研究——以“东行记”为例[J];电化教育研究;2008年01期

2 王洋;狄增如;樊瑛;;二分网络社团结构的比较性定义[J];复杂系统与复杂性科学;2009年04期

3 王永固;张庆;;MOOC:特征与学习机制[J];教育研究;2014年09期

4 王陆;;虚拟学习社区社会网络中的凝聚子群[J];中国电化教育;2009年08期

5 王陆;;虚拟学习社区社会网络位置分析与助学者群体的发现[J];中国电化教育;2010年03期

中国博士学位论文全文数据库 前1条

1 王陆;虚拟学习社区的社会网络结构研究[D];西北师范大学;2009年

  本文关键词：复杂网络社区发现算法研究，由笔耕文化传播整理发布。

，

本文编号：286060