基于局部扩展的重叠社区发现算法研究

论文摘要

具有社区结构是复杂网络最重要的特点之一,发现复杂网络中的社区结构在社会学、生物学尤其在计算机科学等领域有着重要的应用,在这些领域中各种系统通常被表示为复杂网络。一个社区是复杂网络中关联紧密的一个节点集合,社区内部节点间边的数量相对较多,社区内部节点与社区外部节点间边的数量相对较少。同一个社区内部的节点往往具有共同的特性或在网络中扮演着相似的角色。当网络中一个节点同时属于多个社区时,社区间就发生了重叠。在文献中有大量的重叠社区发现算法被提出,然而这些算法在处理大规模真实网络或动态网络时大多具有过大的时间消耗或难以得到准确的社区发现结果。由于缺乏扩展性较好的重叠社区发现算法和真实网络的动态性,大规模真实网络和大规模动态网络的重叠社区发现仍然是一个热点问题。基于局部扩展的社区发现算法是对大规模网络适应性最好的重叠社区发现算法之一。然而由于缺乏快速有效的种子选择方法和社区优化方法,这类算法往往得到准确性较低的社区结果或者在社区发现的过程中用到大量真实社区结构的先验信息。因此,本文基于局部扩展方法展开研究,主要内容包括种子选择方法、社区优化方法和动态网络的重叠社区发现。第一,在基于局部扩展的重叠社区发现算法中,种子的选择往往决定了局部扩展方法的社区发现准确性,然而目前缺乏有效的种子选择方法。一些现有方法忽略了种子间发生重叠的情况,出现扩展成几乎完全相同或高度相似社区的问题;一些方法将一个中心节点和它所有邻节点组成的集合作为一个种子,但是在选择种子过程中仅限定了中心节点的特征而没有考虑作为社区扩展起点的整个集合的特征。为了解决这些问题,本文提出一种基于网络子图总度和密度的无参数种子选择算法,该方法主要使用网络局部结构信息,首次将网络子图的总度和密度应用到种子选择算法中,并且不允许种子之间重叠。基于该种子选择算法,本文提出了一个适应大规模网络的快速准确的重叠社区发现算法DSCM（Density-based Seeding and Conductance Minimizing）。在人工网络上的实验结果表明该种子选择算法优于同类方法。在大规模真实网络上的实验结果表明DSCM算法的表现超过其它重叠社区发现算法,特别地,相对于基于网络全局结构信息的重叠社区发现算法,该算法在运行效率上提高了大约两个数量级,同时可以得到更加优质的社区结构;相对于当前基于网络局部信息的重叠社区发现算法,该算法在没有任何真实社区结构先验信息的前提下大幅度的提高了社区发现的准确度。第二,为了解决同一个种子内的节点可能不在同一个社区内的问题,本文将网络中节点的影响力融入到节点间相似度的计算中,并将一个社区的种子定义为由三个节点组成的线或三角形,每个种子包含一个影响力相对较大的核心节点,另外两个成员通过节点影响力和与核心节点间的相似度在核心节点的邻节点中选择,既保证了种子具有较大的总节点影响力,又减少了同一个种子内的节点不在同一个社区内的可能性。在此基础上,本文提出了一种基于节点影响力和节点间相似度的重叠社区发现算法VISM（Vertex Influence and Similarity Method）。在人工网络上的实验结果表明该种子选择方法相对于同类方法可以得到相对准确的社区结构。在大规模真实网络上的实验结果表明VISM算法的表现超过其它算法,特别地,相对于面向大规模网络的基于网络全局结构信息的重叠社区发现算法,该算法在运行效率上提高了多个数量级,同时可以得到更加优质的社区结构;相对于当前基于网络局部信息的重叠社区发现算法,该算法在没有任何先验信息的前提下大幅度的提高了社区发现的准确度。第三,为了提高基于局部扩展重叠社区发现算法的准确性,本文提出了三个社区优化过程对社区的导率进行优化:（1）通过节点的移动来修正节点与社区之间不准确的隶属关系;（2）提出一个社区合并函数,该函数包含社区间的相似度和社区合并带来的社区导率变化两部分,并用该函数对高度重叠的社区进行合并;（3）将社区导率作为目标函数来为网络中的孤立节点选择社区。在此基础上,本文提出了一个精确的基于网络局部结构信息的重叠社区发现算法LECM（Local Expansion and Conductance Minimizing）。在人工网络上的实验结果表明本文提出的三个社区优化过程可以有效的对社区导率进行优化并大幅度的提高发现社区的质量。在大规模真实网络上的实验结果表明LECM算法具有相对优秀的表现。最后,本文提出一个面向动态网络的基于局部扩展的自适应社区更新算法ADIS（Adaptive Community Update based on DIS）。在该算法中,动态网络的结构变化被分成了四个基本事件:节点和边插入、节点和边的移除。ADIS算法首先应用静态网络社区发现算法DIS对动态网络的初始网络结构进行社区划分得到一个基础社区结构,然后针对动态网络在每个时间点不同类型的结构变化分别对社区进行基于导率优化和局部扩展方法的更新。ADIS算法可以发现动态网络中发生的主要事件,包括社区诞生、社区消亡、社区扩张和社区收缩。在人工动态网络上的实验结果表明ADIS算法可以相对准确的发现动态网络的社区结构。

论文目录

摘要

ABSTRACT

第1章绪论

1.1 课题背景及研究的目的和意义

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

1.2.1 非重叠社区发现算法

1.2.2 重叠社区发现算法

1.2.3 动态社区发现算法

1.3 本文的研究内容与创新点

1.3.1 本文的主要研究内容

1.3.2 本文的主要创新点

1.4 本文的组织结构

第2章基于高密度子图扩展的重叠社区发现算法

2.1 引言

2.2 相关概念

2.3 基于局部扩展的重叠社区发现

2.3.1 种子选择过程

2.3.2 种子扩展过程

2.4 由高密度、高总度子图扩展的社区发现算法

2.4.1 种子选择策略

2.4.2 种子扩展

2.4.3 社区优化

2.4.4 时间复杂度分析

2.5 实验结果与分析

2.5.1 人工合成网络上的实验结果与分析

2.5.2 真实网络上的实验结果与分析

2.6 本章小结

第3章基于节点影响力和相似度的重叠社区发现算法

3.1 引言

3.2 由高总节点影响力子图扩展的社区发现算法

3.2.1 基于节点影响力和节点间相似度的种子选择方法

3.2.2 社区扩展

3.3 实验结果与分析

3.3.1 在人工合成网络上的实验结果与分析

3.3.2 在大规模真实网络上的实验结果与分析

3.4 本章小结

第4章基于导率优化的重叠社区发现算法

4.1 引言

4.2 基于导率优化的局部扩展算法

4.2.1 种子选择

4.2.2 社区扩展

4.2.3 节点移动

4.2.4 社区合并

4.2.5 为孤立节点选择社区

4.2.6 时间复杂度分析

4.3 实验结果与分析

4.3.1 与NLEA算法的比较

4.3.2 与主流重叠社区发现算法的比较

4.4 本章小结

第5章基于局部扩展的动态网络重叠社区发现算法

5.1 引言

5.2 符号和定义

5.3 DIS算法简介

5.3.1 种子选择

5.3.2 社区扩展

5.4 基于DIS算法的动态社区发现

5.4.1 问题描述

5.4.2 动态网络重叠社区发现算法

5.5 实验结果与分析

5.5.1 静态网络上的实验结果与分析

5.5.2 动态网络上的实验结果与分析

5.6 本章小结

结论

参考文献

攻读博士学位期间发表的论文及其它成果

致谢

个人简历

文章来源

类型: 博士论文

作者: 高阳

导师: 张宏莉

关键词: 重叠社区发现,局部扩展,种子选择方法,社区优化,动态网络

来源: 哈尔滨工业大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 哈尔滨工业大学

分类号: O157.5

DOI: 10.27061/d.cnki.ghgdu.2019.000040

总页数: 121

文件大小: 5080K

下载量: 211

基于局部扩展的重叠社区发现算法研究

论文摘要

论文目录

文章来源

相关论文文献

猜你喜欢