从属与领导度的复杂网络社团检测算法研究
发布时间：2020-12-21 03:53
通过社团检测和社团分析可以获取复杂网络中的重要信息,帮助控制网络、预测网络演化。最初的社团检测研究集中在无向网络和非重叠社团上,但由于现实世界存在大量有向网络,以及网络中普遍存在的重叠性,重叠社团检测和有向网络社团检测逐渐成为社团检测研究的重点和热点。重叠社团检测一直是复杂网络研究领域的重点和难点之一。由于真实网络普遍存在层次结构,结合层次性的重叠社团检测方法将更适用于现实世界复杂网络的研究分析。本文基于领导度和从属度概念,并对计算领导度的条件做了适合本文重叠社团检测模型的改动。在此基础上结合网络层次性建立了一种基于领导度和从属度的重叠社团检测算法模型——从属度树算法模型。模型根据从属度值将网络重新组织为树结构,通过划分树来发现重叠节点和重叠社团。实验表明从属度树算法模型可以结合层次性检测重叠社团,并且能找到其他算法不能找到的重叠节点。划分社团的扩展模块度值大于对比算法,社团划分结果更接近实际社团结构。相比于无向网络社团检测,有向网络社团检测要考虑网络的方向信息,社团检测更加复杂困难,要将无向网络社团检测算法改进以适用于有向网络,关键在于将网络的方向性融入算法模型中。本文利用包含网络方...
【文章来源】：西安科技大学陕西省
【文章页数】：70 页
【学位级别】：硕士
【部分图文】：
“歌尼斯堡七桥”简化网络图
1绪论11绪论1.1研究背景和意义1.1.1复杂网络复杂网络的引入是为了研究现实中的复杂系统，复杂网络的“复杂”之处在于结构复杂、节点复杂和影响因素复杂。对应到复杂系统就是系统成员之间的关系复杂、成员和关系的含义多样、这些含义可能还随着时间不断变化、复杂系统可能会受到许多内力外力因素的影响和作用。复杂网络一般都具有一些特殊的共有性质，比如自组织、自相似、吸引子、小世界、无标度等性质。对于复杂网络的研究经历了四个阶段。第一个阶段数学家欧拉提出图论(GraphTheory)作为复杂网络的研究工具。欧拉在对“歌尼斯堡七桥问题”进行研究时将普莱格尔河上的七座桥和河中间的两座岛和河岸抽象为了图形，如图1.1和图1.2所示。抽象后的图形很像我们现在常见的网络图，七桥问题也被简化为一笔画图形问题。图论现在是数学中一个独立的分支，对复杂网络的研究起着至关重要的作用。图1.1“歌尼斯堡七桥”示意图图1.2“歌尼斯堡七桥”简化网络图第二个阶段是20世纪60年代，匈牙利两位数学家提出了ER随机图理论[1]，该理论中描述了一种比较简单的随机图网络，图中包括n个节点，并且以概率p随机连接任意两个节点形成最终网络。学术界中公认ER随机图理论是开启复杂网络系统性研究的开创性理论。
1绪论3的事，但越大型的网络，社团检测越有意义。因为对大型网络直接进行结构分析和动态演化预测是相当复杂的，这时候就可以通过研究社团的结构来研究整个网络的拓扑结构，通过研究社团的功能揭示网络的功能，通过研究社团的规律和演化趋势来推断网络的规律、预测网络的演化趋势。社团结构之所以具有这样由部分推整体的特殊功能，是因为复杂网络普遍具有自相似特性。网络的自相似性是指网络和它的一部分子网络即社团在结构、性质、功能上几乎或者完全相同。图1.3具有社团结构的网络最初研究者们一直致力于非重叠社团检测研究，就是将网络划分成不相交的社团结构，一个节点只能被划分在一个社团中。这是因为最初的研究一般都在人工网络上做实验，人为设置了非重叠的网络，而且非重叠社团检测更加简单清晰地反映了社团检测的意义。但随着研究者们开始研究真实世界的复杂网络，发现了非重叠社团检测算法用于一些具有重叠特性的现实网络中时有较大的局限性。比如社交网络中的人们自然地拥有多个社团成员的身份特征；一个人通常与家人、朋友和同事等几个社交群体有联系；研究人员可能在几个研究领域都很活跃；比如生物网络中节点可能具有多个功能。因此重叠确实是许多现实世界网络尤其是社交网络的重要特征。出于这个原因，研究者们越来越关注重叠社团检测算法的研究。重叠社团结构是指网络中可能有多个节点属于多个群集。例如图1.4就是一个含有重叠社团结构的小网络。在图1.4中，节点7、8、9组成一个社团，这个社团与其他的社团不存在重叠。节点1、2、3、4组成一个社团，节点4、5、6组成一个社团，这两个社团之间有重叠，重叠节点为节点4。重叠社团检测的另一个重要意义是能同时找到重叠节点，这些重叠节点往往在现实中具有特殊地性质或者功能。比如
【参考文献】：
期刊论文
[1]节点不对称转移概率的网络社区发现算法[J]. 许平华,胡文斌,邱振宇,聂聪,唐传慧,高旷,刘中舟. 软件学报. 2019(12)
[2]从属度树算法检测复杂网络重叠社团[J]. 付立东,李丹,李占利. 计算机科学. 2019(12)
[3]结合概率矩阵的改进谱聚类社区发现算法[J]. 张书博,任淑霞,吴涛. 西安电子科技大学学报. 2019(03)
[4]基于多层复杂网络理论的海洋货运网络的抗毁性研究[J]. 刘泽羲,王文俊,潘林. 海洋通报. 2018(06)
[5]基于复杂网络的危险品道路运输网络优化策略研究[J]. 种鹏云,尹惠. 复杂系统与复杂性科学. 2018(03)
[6]新型社交网络谣言传播演化模型研究[J]. 吴晓,刘万平,杨武,卢玲,刘小洋,黄诗雯. 复杂系统与复杂性科学. 2018(02)
[7]基于进化谱分方法的动态社团检测[J]. 付立东,聂靖靖. 计算机科学. 2018(02)
[8]一种改进的网络鲁棒性与有效性增强方法[J]. 慕彩红,柴文壹,刘逸,刘敬. 西安电子科技大学学报. 2018(04)
[9]在线社会网络谣言检测综述[J]. 陈燕方,李志宇,梁循,齐金山. 计算机学报. 2018(07)
[10]基于矢量影响力聚类系数的高效有向网络社团划分算法[J]. 邓小龙,翟佳羽,尹栾玉. 电子与信息学报. 2017(09)
本文编号：2929137
【文章来源】：西安科技大学陕西省
【文章页数】：70 页
【学位级别】：硕士
【部分图文】：
“歌尼斯堡七桥”简化网络图
1绪论11绪论1.1研究背景和意义1.1.1复杂网络复杂网络的引入是为了研究现实中的复杂系统，复杂网络的“复杂”之处在于结构复杂、节点复杂和影响因素复杂。对应到复杂系统就是系统成员之间的关系复杂、成员和关系的含义多样、这些含义可能还随着时间不断变化、复杂系统可能会受到许多内力外力因素的影响和作用。复杂网络一般都具有一些特殊的共有性质，比如自组织、自相似、吸引子、小世界、无标度等性质。对于复杂网络的研究经历了四个阶段。第一个阶段数学家欧拉提出图论(GraphTheory)作为复杂网络的研究工具。欧拉在对“歌尼斯堡七桥问题”进行研究时将普莱格尔河上的七座桥和河中间的两座岛和河岸抽象为了图形，如图1.1和图1.2所示。抽象后的图形很像我们现在常见的网络图，七桥问题也被简化为一笔画图形问题。图论现在是数学中一个独立的分支，对复杂网络的研究起着至关重要的作用。图1.1“歌尼斯堡七桥”示意图图1.2“歌尼斯堡七桥”简化网络图第二个阶段是20世纪60年代，匈牙利两位数学家提出了ER随机图理论[1]，该理论中描述了一种比较简单的随机图网络，图中包括n个节点，并且以概率p随机连接任意两个节点形成最终网络。学术界中公认ER随机图理论是开启复杂网络系统性研究的开创性理论。
1绪论3的事，但越大型的网络，社团检测越有意义。因为对大型网络直接进行结构分析和动态演化预测是相当复杂的，这时候就可以通过研究社团的结构来研究整个网络的拓扑结构，通过研究社团的功能揭示网络的功能，通过研究社团的规律和演化趋势来推断网络的规律、预测网络的演化趋势。社团结构之所以具有这样由部分推整体的特殊功能，是因为复杂网络普遍具有自相似特性。网络的自相似性是指网络和它的一部分子网络即社团在结构、性质、功能上几乎或者完全相同。图1.3具有社团结构的网络最初研究者们一直致力于非重叠社团检测研究，就是将网络划分成不相交的社团结构，一个节点只能被划分在一个社团中。这是因为最初的研究一般都在人工网络上做实验，人为设置了非重叠的网络，而且非重叠社团检测更加简单清晰地反映了社团检测的意义。但随着研究者们开始研究真实世界的复杂网络，发现了非重叠社团检测算法用于一些具有重叠特性的现实网络中时有较大的局限性。比如社交网络中的人们自然地拥有多个社团成员的身份特征；一个人通常与家人、朋友和同事等几个社交群体有联系；研究人员可能在几个研究领域都很活跃；比如生物网络中节点可能具有多个功能。因此重叠确实是许多现实世界网络尤其是社交网络的重要特征。出于这个原因，研究者们越来越关注重叠社团检测算法的研究。重叠社团结构是指网络中可能有多个节点属于多个群集。例如图1.4就是一个含有重叠社团结构的小网络。在图1.4中，节点7、8、9组成一个社团，这个社团与其他的社团不存在重叠。节点1、2、3、4组成一个社团，节点4、5、6组成一个社团，这两个社团之间有重叠，重叠节点为节点4。重叠社团检测的另一个重要意义是能同时找到重叠节点，这些重叠节点往往在现实中具有特殊地性质或者功能。比如
【参考文献】：
期刊论文
[1]节点不对称转移概率的网络社区发现算法[J]. 许平华,胡文斌,邱振宇,聂聪,唐传慧,高旷,刘中舟. 软件学报. 2019(12)
[2]从属度树算法检测复杂网络重叠社团[J]. 付立东,李丹,李占利. 计算机科学. 2019(12)
[3]结合概率矩阵的改进谱聚类社区发现算法[J]. 张书博,任淑霞,吴涛. 西安电子科技大学学报. 2019(03)
[4]基于多层复杂网络理论的海洋货运网络的抗毁性研究[J]. 刘泽羲,王文俊,潘林. 海洋通报. 2018(06)
[5]基于复杂网络的危险品道路运输网络优化策略研究[J]. 种鹏云,尹惠. 复杂系统与复杂性科学. 2018(03)
[6]新型社交网络谣言传播演化模型研究[J]. 吴晓,刘万平,杨武,卢玲,刘小洋,黄诗雯. 复杂系统与复杂性科学. 2018(02)
[7]基于进化谱分方法的动态社团检测[J]. 付立东,聂靖靖. 计算机科学. 2018(02)
[8]一种改进的网络鲁棒性与有效性增强方法[J]. 慕彩红,柴文壹,刘逸,刘敬. 西安电子科技大学学报. 2018(04)
[9]在线社会网络谣言检测综述[J]. 陈燕方,李志宇,梁循,齐金山. 计算机学报. 2018(07)
[10]基于矢量影响力聚类系数的高效有向网络社团划分算法[J]. 邓小龙,翟佳羽,尹栾玉. 电子与信息学报. 2017(09)
本文编号：2929137
本文链接：https://www.wllwen.com/shoufeilunwen/benkebiyelunwen/2929137.html
