基于高影响力边的复杂网络重叠社区发现算法研究
发布时间：2020-12-09 06:28
现实世界中的许多复杂系统都可以抽象地表现为网络形态,随着大型网络数据可用性的提高,以及学者们对复杂网络定量、定性特征研究的深入,大型复杂网络的研究已变成一门极具意义的课题,而找寻复杂网络数据中的社群结构正是其中被着重研究的难点之一。2017年,一种围绕找到社团中心点继而吸引拉拢周围其他点的类天体万有引力的基于种子点选取的重叠社区发现算法(CNS)被提出,随后,在2019年被提出的一种融入了其他天体磁力干扰的基于中心边选取的重叠社区发现算法(CES)是对传统的CNS做出了的进一步改进,但由于CES算法延续了CNS算法的种子节点的选取过程,导致其在对节点质量的评估过程中存在一定偏差,因而极易产生影响力函数在对网络社区描述过程中产生不准确结果的可能,最终导致划分结果与真实情况不符或精确度不高等情况。本文针对CES的种子节点的选取过程和聚类过程,提出了相应的基于高影响力边的重叠社区发现算法(HIE),HIE分别在以下三部分对之前的算法进行了相应改善:利用邻居节点联系度(neighbor node connection degree,NNCD)调整了节点的质量来获得更加合理的种子节点,NNCD是...
【文章来源】：吉林大学吉林省 211工程院校 985工程院校 教育部直属院校
【文章页数】：62 页
【学位级别】：硕士
【部分图文】：
重叠社区（左）和非重叠社区（右）
第2章社区发现算法综述6第2章社区发现算法综述本章我们将从传统的、重叠的和基于边这三个维度，对社区发现算法展开详细介绍，分这三个方向只是为了更清晰的论述，需要强调的是，这三个维度不是完全不相交叉的分类，同时也针对每类分别列举了一些具有代表性的和时下热门的算法，对算法流程、特点和适用范围进行了说明。2.1传统的社区发现算法2.1.1图分割算法此类算法中最基本的一种算法是由Yuri等提出的最小割算法（MinimumCut），该算法在GraphCut、GrabCut等算法中得到了充分的应用。割即是一个划分图中顶点的过程，把边放在一个集合里便是最小割，目的是让连接两个划分的边的数目达到最小值。在下图中，边(e,k)和边(d,h)是最小割。下面介绍最小割算法的原理，首先通过计算得到图中的最小割所在边，这个过程是按事前确定的分组数将网格进行划分，同时满足各组连接的边的数目最小的过程。在负载均衡中，最小割算法应用于分布式计算，利用该算法能够有效减少互不相关的节点间的联系，对于集群节点尤为有效。但该算法也有局限之处，例如事先限制了网格的理想切割数，从而不能根据发现节点间关系划分社区，因此该算法应用范围有限。理解最小割的思路对于社区发现有很大意义，因为社区发现的过程从某种方面看就是寻找最优最小割的过程。图2.1最小割示意图
第2章社区发现算法综述813交换A中的（12kaaa，，，）与B中的（12kbbb，，，）；14until（G≤0）；15returnA和B。在该算法中，V是一个包含2n个节点的集合，E是边集合，C是一个2n*2n的权重矩阵，ijC代表节点i和j的直接边权重，其中0iiC=。Kernighan-Lin算法分为以下几个步骤：第一步把待划分的图G中的节点随机划分到两个指定规模的A、B社区中；第二步从两个社区中分别选择节点i和j，交换两节点的位置并计算交换前后G值的变化情况；第三步重复上述步骤，其中已交换过的节点不再交换；第四步当所有节点交换完成后停止。2.1.2基于模块度的算法基于模块度的方法亦是一类比较有特色的传统算法[5]。社区挖掘之初，难以定量评估算法效果。直到2003年Newman基于将相同类型的节点的链接分数与从随机结构中出现的相同类型的节点的链接分数进行比较的思想提出了模块度的概念，即：=linkNQm···············································(2.1)其中，Q是模块度，分子部分表示的是同种节点之间的链路边数，分母则表示的是所有的链路数。比方说我们有这么一个网络，其中0、1号节点属性相同，2、3、4号节点属性相同，那么同种节点之间的边数为3，总边数为5。图2.2模块度示意图对于这种简单的图可以数得过来，可以依次去计算，但复杂的网络须依靠算法来完成。同种节点之间的链路边可以通过公式(2.2)得到。
【参考文献】：
期刊论文
[1]面向属性网络的重叠社区发现算法[J]. 杜航原,裴希亚,王文剑. 计算机应用. 2019(11)
[2]一种新型的基于Levenshtein距离层次聚类的时序操作优化方法[J]. 朱坚,杨博,王永健,唐晓婕,李宏光. 化工学报. 2019(02)
[3]基于深度游走模型的标签传播社区发现算法[J]. 冯曦,朱福喜,刘世超. 计算机工程. 2018(03)
[4]基于种子节点选择的重叠社区发现算法[J]. 齐金山,梁循,王怡. 计算机应用研究. 2017(12)
[5]引入极值非相邻连接的连接聚类方法[J]. 王贵参,黄岚,王岩,宋立明,欧歌. 吉林大学学报(工学版). 2016(05)
[6]基于复杂网络的社区发现算法[J]. 杨晓光,朱保平. 南京理工大学学报. 2016(03)
[7]基于加权边相似度的重叠社区发现算法[J]. 王元欣,刘培强. 山东师范大学学报(自然科学版). 2016(02)
[8]基于相关系数和最佳阈值的股票网络模型构建[J]. 吴翎燕,韩华,宋宁宁. 复杂系统与复杂性科学. 2013(04)
硕士论文
[1]基于中心边选择的重叠社区发现算法研究[D]. 张方.吉林大学 2019
[2]面向复杂交通网络的社区发现方法研究[D]. 吴永科.山西大学 2018
[3]局部拓展类重叠社区发现算法的研究[D]. 袁闯.重庆大学 2018
本文编号：2906443
【文章来源】：吉林大学吉林省 211工程院校 985工程院校 教育部直属院校
【文章页数】：62 页
【学位级别】：硕士
【部分图文】：
重叠社区（左）和非重叠社区（右）
第2章社区发现算法综述6第2章社区发现算法综述本章我们将从传统的、重叠的和基于边这三个维度，对社区发现算法展开详细介绍，分这三个方向只是为了更清晰的论述，需要强调的是，这三个维度不是完全不相交叉的分类，同时也针对每类分别列举了一些具有代表性的和时下热门的算法，对算法流程、特点和适用范围进行了说明。2.1传统的社区发现算法2.1.1图分割算法此类算法中最基本的一种算法是由Yuri等提出的最小割算法（MinimumCut），该算法在GraphCut、GrabCut等算法中得到了充分的应用。割即是一个划分图中顶点的过程，把边放在一个集合里便是最小割，目的是让连接两个划分的边的数目达到最小值。在下图中，边(e,k)和边(d,h)是最小割。下面介绍最小割算法的原理，首先通过计算得到图中的最小割所在边，这个过程是按事前确定的分组数将网格进行划分，同时满足各组连接的边的数目最小的过程。在负载均衡中，最小割算法应用于分布式计算，利用该算法能够有效减少互不相关的节点间的联系，对于集群节点尤为有效。但该算法也有局限之处，例如事先限制了网格的理想切割数，从而不能根据发现节点间关系划分社区，因此该算法应用范围有限。理解最小割的思路对于社区发现有很大意义，因为社区发现的过程从某种方面看就是寻找最优最小割的过程。图2.1最小割示意图
第2章社区发现算法综述813交换A中的（12kaaa，，，）与B中的（12kbbb，，，）；14until（G≤0）；15returnA和B。在该算法中，V是一个包含2n个节点的集合，E是边集合，C是一个2n*2n的权重矩阵，ijC代表节点i和j的直接边权重，其中0iiC=。Kernighan-Lin算法分为以下几个步骤：第一步把待划分的图G中的节点随机划分到两个指定规模的A、B社区中；第二步从两个社区中分别选择节点i和j，交换两节点的位置并计算交换前后G值的变化情况；第三步重复上述步骤，其中已交换过的节点不再交换；第四步当所有节点交换完成后停止。2.1.2基于模块度的算法基于模块度的方法亦是一类比较有特色的传统算法[5]。社区挖掘之初，难以定量评估算法效果。直到2003年Newman基于将相同类型的节点的链接分数与从随机结构中出现的相同类型的节点的链接分数进行比较的思想提出了模块度的概念，即：=linkNQm···············································(2.1)其中，Q是模块度，分子部分表示的是同种节点之间的链路边数，分母则表示的是所有的链路数。比方说我们有这么一个网络，其中0、1号节点属性相同，2、3、4号节点属性相同，那么同种节点之间的边数为3，总边数为5。图2.2模块度示意图对于这种简单的图可以数得过来，可以依次去计算，但复杂的网络须依靠算法来完成。同种节点之间的链路边可以通过公式(2.2)得到。
【参考文献】：
期刊论文
[1]面向属性网络的重叠社区发现算法[J]. 杜航原,裴希亚,王文剑. 计算机应用. 2019(11)
[2]一种新型的基于Levenshtein距离层次聚类的时序操作优化方法[J]. 朱坚,杨博,王永健,唐晓婕,李宏光. 化工学报. 2019(02)
[3]基于深度游走模型的标签传播社区发现算法[J]. 冯曦,朱福喜,刘世超. 计算机工程. 2018(03)
[4]基于种子节点选择的重叠社区发现算法[J]. 齐金山,梁循,王怡. 计算机应用研究. 2017(12)
[5]引入极值非相邻连接的连接聚类方法[J]. 王贵参,黄岚,王岩,宋立明,欧歌. 吉林大学学报(工学版). 2016(05)
[6]基于复杂网络的社区发现算法[J]. 杨晓光,朱保平. 南京理工大学学报. 2016(03)
[7]基于加权边相似度的重叠社区发现算法[J]. 王元欣,刘培强. 山东师范大学学报(自然科学版). 2016(02)
[8]基于相关系数和最佳阈值的股票网络模型构建[J]. 吴翎燕,韩华,宋宁宁. 复杂系统与复杂性科学. 2013(04)
硕士论文
[1]基于中心边选择的重叠社区发现算法研究[D]. 张方.吉林大学 2019
[2]面向复杂交通网络的社区发现方法研究[D]. 吴永科.山西大学 2018
[3]局部拓展类重叠社区发现算法的研究[D]. 袁闯.重庆大学 2018
本文编号：2906443
本文链接：https://www.wllwen.com/shoufeilunwen/benkebiyelunwen/2906443.html
