复杂网络中的社团检测方法研究

发布时间：2017-08-29 23:06

  本文关键词：复杂网络中的社团检测方法研究

  更多相关文章： 复杂网络 社团结构 社团检测 网络稀疏化 主动学习

【摘要】：现实世界中众多的复杂系统都可抽象地表示为复杂网络,而社团结构是很多复杂网络最为显著的结构特征,其中的社团往往对应于网络的功能单元,从某种程度而言,整个网络的功能往往取决于社团之间的相互作用。通过检测网络的社团结构,可以在中观(mesoscale)结构层面探索网络的性质,研究网络的结构与功能之间的关系。此外,社团结构也能对网络的动力学特性产生重要的影响。因此,社团检测的研究不仅具有重要的理论意义,而且具有重要的实际应用价值,近年来吸引了计算机、物理、生物等多个学科研究人员的广泛关注,已成为复杂网络学科的一个研究热点。本文对已有的社团检测方法进行了深入的分析,针对这些方法中存在的问题与不足,提出了两类共5种社团检测方法。第一类方法关注的是如何从网络中检测得到尽可能精确的、高质量的社团结构,其中包括三种社团检测方法:(1)DBSCD:该方法首先利用一个稀疏化处理过程,从网络中移除可能位于不同社团之间的一些边,使得社团之间的边界变得清晰;接着使用谱二分法,基于网络转移矩阵第二特征向量中元素的符号,将网络分裂为两个子网络;然后在模块度的约束、指导下,以迭代方式使用同样的谱二分法对选中的子网络进行分裂,每一次迭代选中的都是其分裂能使得模块度增量最大的一个子网络。通过这样的持续分裂,得到最终的社团结构。(2)HBSCD:该方法同样先对网络进行稀疏化处理,使社团结构更加突出。接着基于网络转移矩阵第二特征向量中元素的符号,持续将网络分裂为一系列不可再分的子网络,并将每一个子网络当做一个社团,形成初始的社团结构。然后借鉴Fast算法的思想,通过合并其中一些社团得到最终的社团结构。(3)ASSCD:该方法将主动学习技术引入到社团检测的研究中,并与半监督社团检测算法结合,从网络中提取其社团结构。主动学习策略从网络中主动选取对半监督社团检测算法效用最大的顶点,生成高质量的Must-Link和Cannot-Link成对约束的半监督成分;半监督社团检测算法首先利用这些半监督成分构建初始的社团结构框架,然后充分利用它们以贪心方式对每一社团进行扩张,得到最终的社团结构。为了测试、验证这三种方法的性能,本文分别在一些实际网络数据集上进行了实验。实验结果证实,这三种方法均具有较强的社团检测能力,得到的社团结构质量明显优于对比方法。第二类方法的目标是从网络中高效地获取基本合理的、确定的社团结构,以克服一些运行效率较高的社团检测方法得到的结果具有不确定性的缺陷,并增强社团检测方法的泛化能力,方便对未知的新网络快速地进行探索性挖掘。主要包括两种社团检测方法:(1)VSAHCD:该方法受人类社交活动中选举投票行为的启发,首先通过模拟投票过程,让每个顶点按照一定的规则进行投票,得到一系列的小团体,然后分别使用两种策略,将其中一些小团体合并为较大的社团。一种策略借鉴了Fast算法的思想,每次合并能使得模块度增量最大并且相似性不为0的两个社团;另一种策略则合并相似性最大的两个社团,但确保合并操作能带来正的模块度增量。通过分别以这两种方式对小团体进行合并,得到最终的社团结构。(2)LPAd:该算法是对LPA算法的一个改进和增强,首先确定了一个合理的顶点序列,按照该序列的顺序,将其中每一顶点的标签更新为其邻居中最频繁出现的一个标签,同时也提出了存在标签竞争时的解决方案。通过这两方面的改进,使LPAd成为一个确定性的算法。然后在其运行得到的社团结构基础上,借鉴Fast算法的思想并结合相似性对其中一些社团进行合并,得到最终的社团结构。理论分析表明这两种方法均具有较高的运行效率。此外,本文也通过在5个实际网络数据集和2个LFR人工合成网络数据集上的实验,分别对这两种方法的性能进行了测试和评估。评估结果表明,这两种方法均能快速地从网络中检测得到比较合理的、确定的社团结构。
【关键词】：复杂网络 社团结构 社团检测 网络稀疏化 主动学习
【学位授予单位】：兰州大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O157.5;TP181
【目录】：

• 中文摘要3-5
• Abstract5-16
• 第一章 绪论16-27
• 1.1 引言16-17
• 1.2 复杂网络与链接挖掘17-23
• 1.2.1 复杂网络研究的起源及发展17-19
• 1.2.2 常见的复杂网络19-20
• 1.2.3 复杂网络的特性20-22
• 1.2.4 链接挖掘的内容、任务22-23
• 1.3 本论文的主要工作及贡献23-25
• 1.4 本论文的组织结构25-27
• 第二章 理论基础与相关工作27-43
• 2.1 相关概念、术语、符号及定义27-29
• 2.2 社团检测的意义29-30
• 2.3 社团检测研究的相关工作30-39
• 2.4 本论文实验使用的网络数据集39-40
• 2.5 社团结构的评价指标40-43
• 第三章 DBSCD：分裂的谱二分层次社团检测方法43-65
• 3.1 引言43-44
• 3.2 动因44-46
• 3.3 DBSCD方法46-54
• 3.3.1 网络稀疏化算法46-47
• 3.3.2 迭代的谱二分社团检测算法47-51
• 3.3.3 实现策略51-54
• 3.4 实验及结果分析54-63
• 3.4.1 对比方法及参数设置54-55
• 3.4.2 实验结果55-63
• 3.5 小结63-65
• 第四章 HBSCD：混合的谱二分层次社团检测方法65-78
• 4.1 引言65-66
• 4.2 HBSCD方法66-69
• 4.3 实验及结果分析69-75
• 4.3.1 对比算法及参数设置69
• 4.3.2 实验结果69-75
• 4.4 小结75-78
• 第五章 ASSCD：基于主动学习的半监督社团检测方法78-101
• 5.1 引言78-80
• 5.2 ASSCD方法80-90
• 5.2.1 概念和定义80-81
• 5.2.2 半监督社团检测算法81-83
• 5.2.3 基于主动学习的半监督成分获取算法83-88
• 5.2.4 基于随机游走的顶点相似性计算88-89
• 5.2.5 时间复杂度分析89-90
• 5.3 实验及结果分析90-100
• 5.3.1 参数设置90-91
• 5.3.2 实验方法及结果91-100
• 5.4 小结100-101
• 第六章 VSAHCD：模拟投票行为的凝聚层次社团检测方法101-122
• 6.1 引言101-102
• 6.2 思想启发102-103
• 6.3 VSAHCD方法103-110
• 6.3.1 VSAHCD方法的总体框架103
• 6.3.2 投票过程103-106
• 6.3.3 社团合并过程106-108
• 6.3.4 时间复杂度分析108-110
• 6.4 实验及结果分析110-121
• 6.4.1 评价标准的变更110-111
• 6.4.2 对比算法及设置111
• 6.4.3 实验结果及分析111-121
• 6.5 小结121-122
• 第七章 LPAd：一个确定性的LPA算法122-137
• 7.1 引言122-123
• 7.2 LPAd算法123-128
• 7.3 实验及结果分析128-136
• 7.3.1 对比算法及设置128
• 7.3.2 实验结果及分析128-136
• 7.4 小结136-137
• 第八章 总结与展望137-140
• 8.1 本文工作总结137-138
• 8.2 下一步需要开展的工作138-140
• 参考文献140-152
• 在学期间的研究成果152-154
• 致谢154

，

本文编号：755915