基于改进阈值与遗传算法的社区发现方法研究

发布时间：2020-07-07 03:17

【摘要】：复杂网络在对现实中诸多系统的描述方面有着突出贡献,诸如物流、互联网等等现实系统都可以使用复杂网络来进行描述。复杂网络中的一个重要的特征为社区结构特征,具体表现为:在同一社区内,结点间边较为稠密;在不同社区之间边则较为稀疏。社区发现方法可以有效探测网络内部结构,发现不同网络中潜在的规律,这对于我们理解网络功能,预测网络行为有着重要意义和价值。目前,社区发现算法大致可分为以下三种:基于优化的算法、启发式算法及其他算法。但是,这些算法或多或少的存在着运行速度不够快、精确度较低等问题。为了解决上述问题,本文针对社区发现方法,主要进行如下工作:1、针对传统的社区发现算法时间复杂度高的问题,本文将传统阈值与结构相似度的概念结合,提出一种新的社区发现算法STCA。该算法主要思想如下:(1)对于给定阈值k,计算网络两点间的结构相似度作为这两点间的边权值。(2)删除结构相似度小于k的边,并重复以上步骤(1)(2),直到没有边可以删除,计算此时社区对应的模块函数Q的值;(3)将阈值增加一定量,并重复上述过程;(4)取最大模块度对应社区为最终划分结果。通过大量的实验测试,结果表明:本文提出的STCA算法可以在确保划分精度的前提下,提升算法的运行速度。2、针对传统遗传算法在社区发现方面生成初始种群精确度较低的问题,本文提出一种新的基于改进遗传算法的社区发现方法SSGA。该方法主要思想为:将传统的遗传算法轮盘赌选择法与社区网路中结构相似度的概念结合,使染色体上的每一个基因都趋于选择结构相似度比较大的邻居结点,从而大大提升初始种群的划分精度。本算法在人工基准网络数据与真实世界网络数据下进行了实验。结果表明,本文提出的SSGA算法在提升初始种群划分精度的同时,整体划分精度也有所提升,具有更高的整体划分性能。
【学位授予单位】：云南大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP18;O157.5
【图文】：

社区结构,分布特性

社区结构在复杂网络中普遍存在，应用领域不同，相应的社区结构含义逡逑不同。如：科学家协作网络中的社区代表学术研宄相似的科学家群体；共享逡逑单车网络中社区代表具有相似功能的区域范围的集合，如同属学校范畴的区逡逑域。社区结构具有非重叠社区结构和重叠社区结构（Ｐａｌｌａｅ／ｆｌ／，邋２００５）之分。逡逑非重叠社区结构即网络的每个结点只属于一个社区，而重叠社区则表示网络逡逑中存在同时属于多个社区的结点，如在社会网络中每个结点（人）在家庭网络逡逑中扮演父母角色，而在单位又扮演职工角色；在蛋白质交互网络中，一个蛋逡逑白质分子可能因与其他多个蛋白质分子簇相互作用而具有不同功能＞８］。目逡逑前，人们对于社区结构的研究己经渗透到了计算机、物理、社会学、生物学、逡逑数学等多个领域，与社区发现相关的文献也层出不穷，《Ｎａｔｕｒｅ》、《Ｓｃｉｅｎｃｅ》逡逑等国际顶级期刊均有呈现；麻省理工、斯坦福大学等知名高校均设置了复杂逡逑网络课程［９￣。社区发现己经成为当前多领域研究的前沿热点之一。逡逑正因复杂网络中社区结构普遍存在，因此研究网络社区结构具有巨大的逡逑

基于改进阈值与遗传算法的社区发现方法研究

“七桥”向翻示宜民

邻接矩阵,网络图,构造矩阵,赋权图

逦社区发现概述逦逡逑作网络图。按照边是否有方向，可将网络图划分为有向图和无向图；逡逑按照边是否有权值，将网络划分为有权图和无权图。下面给出图的定义：逡逑定义２－１（图）令Ｇ＝（Ｋ￡）表示图，其中，吟｛Ｖｌ，ｖ２，…＿ｖｎ｝为网络结点集合，逡逑门为结点个数，佐｛０＾』）｜１，」６７｜＾尹＿／｝为网络边的集合，｜五｜邋＝邋？７为边数。逡逑定义２－２邋（图的矩阵表示）对于给定非赋权图Ｇ，采用ｎｘｎ的邻接矩阵Ａ表逡逑示，构造矩阵」＝邋（％）＿，贝Ｕ有：逡逑＿＼ｌ邋＾邋ｖＪ＾ｅＥ逦ｎ邋ｎ逡逑％邋＝叫0邋（ｖ，＋，ｖ＞￡逦（）逡逑为了直观描述上述定义，给定图４邋（ａ）所示网络Ｇ，其邻接矩阵Ａ如图４邋（ｂ）逡逑所示：逡逑

【参考文献】