社区检测自适应切换基于亲和力

文摘

在复杂网络中社区结构发挥重要作用在研究网络功能。尽管有各种各样的算法基于亲和力或相似,他们的缺点是显而易见的。他们表现良好在强大的社区,但执行贫困弱势社区。实验表明,有时,社区检测算法基于一个亲和效果不佳,尤其是对弱势社区。所以我们设计一个自适应切换(SAS)算法,在弱两个紧密联系的社区被组合。与一些先进的算法相比,该算法具有竞争力的准确性及其附近的时间复杂度是线性的。我们的算法框架还提供了一个新的社区检测算法组合。一些广泛的计算模拟人工和实际网络确认我们的算法的潜在能力。

1。介绍

网络科学的继续推进在深化的理解中起着重要的作用在现实世界中复杂系统(1- - - - - -3]。一般,一个突出的属性中观察到许多复杂网络的社区结构,即。,the organization of nodes in different groups, with many edges connecting nodes of the same group and comparatively fewer connections among nodes of different groups [4- - - - - -7]。例如,在一个科学引文网络,社区组科学论文在同一主题或在一个类似的研究领域8),而在蛋白质相互作用网络,蛋白质在相同的生物过程(或在同一细胞组件)相互作用。此外,群落结构已被证明有很强的对流行病动力学的影响(9,10)和链接预测。因此,真正的网络数据的采集,每个人都应该注意社区结构,这是价值的复杂网络的进一步调查。

为深入了解社区结构,有必要定义什么是一个社区。一般来说,有三种类型的定义:本地定义,全球定义,定义基于顶点相似(6),包括定义基于模块化和拓扑结构,如self-referring定义和比较定义(11]。然而,有一些定义定量描述群落结构。2003年,Radicchi等人提供的社区定义定量描述的强和弱的感觉(12):子图C是一个社区在强烈如果 在弱意义上

里面的量化定义意味着度以上,或最多,多节点度外,里面的程度是节点的邻居的数量在同一社区和外面的程度是在其他社区的邻居节点的数量。此后,另一个定量的定义是由胡锦涛et al。(11)如下:子网(或子图)据说米社区网络(或图表)G当且仅当他们满足 ,对于任何节点 ,一个人 在哪里一个图的邻接矩阵吗G。与考虑詹et al。13),我们认为这个定义是广义的定义,因为它允许每个节点度外可以超过度,和只需要节点邻居最多的有自己的社区。在本文中,我们使用这个定义为我们的社区标准检测和值得注意的是,重叠节点不被认为是和节点只属于一个社区基于检测结果。

为了准确地描述程度的内部和外部之间的定量关系的社区,Lancichinetti等人引入混合参数为每个节点我表示节点我一小部分股份与外部节点和一小部分的链接与内部节点,即 (14,15]。在本文中,我们考虑到每个节点的混合参数小于0.5强大的社区,相反,它是超过0.5弱社区,这两种社区所有满足的定义胡锦涛et al。

有各种各样的社区检测算法设计。例如,Kernighan-Lin算法、谱二分法的时候,k——聚类方法,谱聚类算法是传统算法源于图论或统计数据。随着计算机的发展,大规模计算越来越普及,所以它是可行的增加计算的复杂性和网络规模。这些进步让研究者们开发出许多优化算法,包括基于模块化的贪婪算法(16和中间状态4,17]。与此同时,有一些算法是基于动力学方法(18- - - - - -23)和相似性或亲和力(24,25]。然而,忽视的区别强大的和弱社区是一个主要的缺点基于节点关联或相似的一些算法,使得这些算法的检测精度低弱社区。因此,我们设计一个自适应切换(SAS)算法的基于单一的亲和力和组合两个紧密联系。

社区检测的性能的评价标准可以由两种方法。一个是计算架构指标,包括保险,电导,模块化指标。知识测量,另一种是计算精度等指标,Jaccard指数和归一化互信息(敝中断)26]。我们采用敝中断指数作为算法的性能评价标准在某些现实世界的网络,在Lancichinetti-Fortunato-Radicchi (LFR)基准网络(异构网络)14),Girvan-Newman (GN)基准网络(均匀网络)(4),和非均匀流行相似优化(nPSO)基准网络(异构网络)27]。根据结果,我们发现我们的算法有优势一些先进的算法更适合异构网络和较大的幂律指数。本文概述如下。节2,我们设计的原理算法并讨论其复杂性。测试和研究的结果发表在部分3。结论部分进行了总结4。

2。结构分析和算法

在本节中,我们将分析群落结构和设计affinity-based SAS社区检测的算法,然后讨论了其复杂性。

2.1。群落结构的分析

一些研究表明,一般节点度服从幂律分布(28,29日]或[30.)对数正态分布分布在实际网络中,在很大程度上被称为节点中心节点和有强烈程度中心,如网络图1。尽管的数量中心节点在实际网络相对较少,他们的重要角色在社区和网络已经多次提到在某些文学研究[13,31日,32]。的识别中心节点通常被认为是启发式算法的切入点。在这些算法中,一个单一的亲和力往往缺乏社区检测,特别是对弱社区。因此,我们设计一个新算法,该算法结合了两种检测的亲和力弱社区。

众所周知,社会的终极目标检测算法基于亲和力或模块化是找到这样的全球最大指数和保证最小数量的不同社区之间的连接。他们都是不确定性多项式难题。撇开这些问题,我们的启发式算法及其检测过程是基于节点之间的关联被发现和被检测到,而不是两个单节点之间。出于不同的亲和力,即。共同的邻居(CN),中心郁闷(HD),中心提升(HP)指数由周总结et al。33),我们提供两个定义的关联节点j和节点集P如下所示,一些重要的符号如表所示1。

第一个亲和力任何节点之间j和节点集P如下:

第二个亲和力任何节点之间j和节点集P是由 在哪里节点的程度吗j。

这两个相似有不同的重点:第一个关注的绝对数量共同邻居和第二个是相对亲和力。我们的启发式算法的实现中心节点,然后检测属于同一个社区的其他节点根据这些传承。

一般来说,一个社区的节点之间的亲和力大于这些节点之间在不同的社区,虽然这有时很难被满足,特别是对于弱社区。为了说明这一点,我们计算第一和第二之间的亲和力中心LFR基准图的节点及其邻居。首先,第二间的亲和力中心节点的邻居在同一个社区和其他社区如图2(一个)。我们发现第二的节点上的相似之处强大的社区有明显差异,但它们混合在一起弱社区当 。我们进行一个类似的实验弱社区第一亲和力观察其区别的能力。自第一个亲和力是共同邻居的绝对数量,我们正常,只关注其规范化的形式在图2 (b)的符号中心节点我邻国的符号集 ,和节点j是一个邻居中心节点:

从统计结果,我们发现,强大的社区,第二个亲和力有效的区分能力。然而,这并不足以探测到弱社区和需要使用第一个亲和力。此外,检测的方法强大的社区是不合适的弱社区,可以发现许多社区由几个甚至一个节点,节点可以触发开关原理条件在我们的SAS算法。所以我们的算法分为两个部分,我们的名字在短SAS-1 SAS-2,分别。接下来,我们将详细描述算法及其原理。

2.2。该算法

在这里,我们将介绍我们的算法的两个部分,包括其核心原则和伪代码,然后分析其复杂性。一些重要的符号也表所示1。

2.2.1。的强大的社区方法SAS-1

在这种方法中,每个社区,其节点,这些节点的边缘,将逐渐从网络中删除后的检测。所以我们表示网络 后( )社区发现的地方和分别是节点和边的集合。为了描述该算法一般来说,我们将使用检测的例子社区。第一步:在步骤 ,选择一个节点的方法随着中心节点的度最大 。在这一步中,中心节点我和它的邻居,令人满意 ,检测到的节点属于吗 ,的节点集P由节点的我及其邻居节点 。第二步:在步骤 ,该方法搜索的节点 ,然后这些节点的邻居j被替换成这个社区当且仅当它满足条件 0.5价值在哪里确认的定义强大的社区,然后社区来是更新。的一步:同样的,当 ,为了减少复杂性,搜索的节点的方法,只有检测到这些节点的未被发现的邻居。然后,邻居j被替换成当且仅当它满足条件 和社区是更新。

的检测过程社区完成直到没有节点满足条件(8)。

2.2.2。的弱社区方法SAS-2

从图中的结果2,我们可以推断方法SAS-1可以发现许多社区,是由几个节点,甚至单个节点弱社区。因此,该算法需要一个自适应切换条件,以反映这一现象,使其从SAS-1 SAS-2。我们的方法是计算的平均规模的社区发现和交换条件之间的两个方法是由 在哪里 ,在这和平均度,是当前许多社区被检测到。实际上,几个邻居中心节点弱社区可以满足条件(7),所以社区SAS-1探测到的平均规模相同的顺序 ,和参数p来自假设检验是一个小的发生率。

一旦SAS-1触发切换条件,它将切换到SAS-2和重新检测网络。不同于第一种方法SAS-1,这个方法不会删除任何节点或边缘的网络,因为识别弱社区依赖于整个网络的建设。在下面,我们还将介绍这种新方法的检测进展社区作为一个例子。第一步:在步骤 ,方法选择节点我以最大程度为起始节点,不属于其他社区 。显然,我们有确认后开始节点。第二步:在步骤 ,方法选择中心节点的邻居j不属于其他社区 ,的成员社区当且仅当它满足以下条件: 在哪里γ是一个基于阈值的平均值在图2,然后是更新。的一步:当 ,SAS-1相似的方法,这种方法搜索的节点,只有检测到这些节点的未被发现的邻居。然后邻居j被替换成当且仅当它满足条件

的终止条件社区是单独的未被发现的节点的亲和力较低的节点被检测到,彼此具有较高的亲和力。我们假设的检测社区停止当没有节点j满足以下条件的步骤 : 在节点j是一种未被发现的邻居节点,属于哪一种 ,和节点属于 ,和参数用于减少网络中的社区。

算法的算法伪代码所示1和它的流程结构如图3。最后,我们分析了算法的复杂性。SAS-1方法,检测过程在每一个社区进行,所以我们考虑到每个社区的平均步数 。每个节点的复杂性在搜索和筛选条件(8)规模 。检测的社区,降低节点的数目,所以极端复杂性 ,在哪里是社区的数量被发现和平均程度。SAS-2方法,检测过程只有在检测到不同条件(11),所以复杂性也有关 。总之,SAS算法的复杂性 。显然,是社区的平均大小的顺序相同吗 ,也就是说, 。自 ,因此,复杂性可以派生 ,在哪里米是网络边缘的数量。

3所示。结果

在本节中,一些实验都进行真实网络(空手道俱乐部网络,海豚网络,足球队网络,和政治书籍网络)和合成网络(LFR GN, nPSO基准图)。首先,我们使用GN基准评估合适的参数范围和分析参数的灵敏度。SAS算法依赖于三个参数β,γ,ρ,参数的选择β与平均学历 。的参数ρ和γ可以自由选择的范围 。GN的基准,其规模是128和度分布相对集中,所以它适用于参数敏感性分析。因为它的平均程度是16,所以我们默认吗和主要研究参数的敏感性ρ和γ。基于图的结果4结果,我们发现是参数不敏感β和γ。然而,参数的变化ρ对结果有明显影响什么时候 。幸运的是,当参数 ,所有检测结果稳定,没有宽量程的波动。

在实践中,参数γ应该接近于1,确保初始节点检测的准确性。的参数应该适当的增加可以提高聚类系数。然后,我们评估我们的算法的优点和缺点与其他先进的算法相比:Infomap, LPA,鲁汶,Walktrap,快速贪婪,他们,他们批判。在实际网络性能比较证实了其潜在的能力见表2和图5。值得一提的是,一些社区划分略有不同的真理。可能的原因是,社区的具体部门导致社区的数量的增加,但其结果至少满足定量的定义我们的文章和有一个好的准确率。

为了准确性深入讨论我们的算法,我们使用三个基准网络:LFR, GN, nPSO研究算法的性能如何,敝中断(26),削弱的群落结构变化。

3.1。LFR基准

在这一部分,LFR网络有两个不同尺度:1000年和5000年,呈现在图6。对于各种网络,我们考虑两个不同社区的规模,由字母S和B表示,S代表“小”社区有10到50个节点和B代表“大”社区,有大约20到100个节点15]。在图6四种类型的网络的,我们的算法测试敝中断 。为强大的和弱社区,我们的算法的性能比表中的一些算法2。

3.2。GN基准

除此之外,我们在GN基准测试SAS算法网络结果如图7,每个点也是100个相同网络上测试过。SAS算法的性能是其他算法在表2。众所周知,LFR基准是一种异构网络的度分布符合幂律分布。然而,GN基准,其度分布遵循正态分布的作用中心节点是削弱。网络结构的异质性可能会影响我们的算法的准确性。接下来,我们将使用nPSO基准进行进一步分析算法的性能。

3.3。nPSO基准

最近,有一个名为非均匀受欢迎程度相似的新网络生成模型优化(nPSO)社区检测和评价链接预测,可以创建合成网络和控制参数:网络规模、平均程度、社区数量、幂律指数,和温度。它允许一个温度来优化网络的混合性质。特别是,这个模型模拟随机几何图形如何生长在双曲空间中,生成现实的网络与集群,small-worldness scale-freeness, rich-clubness。

在这一部分,我们生成nPSO双曲网络与社区与这些参数:(网络大小),(平均程度的一半), (温度、逆相关聚类系数),(社区),(幂律度分布指数)。我们还比较了SAS算法与最先进的社区发现算法。结果的数据8- - - - - -10,我们发现SAS算法的性能对参数的变化不敏感N, ,和 。然而,它表现在异构网络和一般 。这表明我们的算法可能更适合于异构网络和较大的幂律指数。结合所有的检测结果,我们可以看到,SAS算法优于其他一些先进的算法,这些算法中精度等级高一些基准。附近的线性时间复杂度也是一个算法的优势。

4所示。结论

摘要SAS算法的性能评估与一些先进的算法在实际网络以及三个基准图,传统上用于现有的文献。首先,实验结果表明,使用不同的亲和力是可行的强大的和弱社区。我们的算法提高了精度弱社区,与一些算法相比,基于单一的亲和力,和一些先进的算法一样的可靠性。其次,一些基于启发式算法中心节点可能需要提前分析网络度分布或聚类系数来提高算法的精度。的作用的削弱中心节点可能是算法执行不好的原因与幂律指数2 nPSO基准,但表现良好在LFR基准和幂律指数3 nPSO基准。这也是未来算法改进的一个重要方向。最后,我们的亲和力的定义是基于共同邻居的概念。最近,有一个新的范式定义亲和力,不仅使用信息的数量与常见的邻居但还考虑(和集成)发生的相关信息链接之间的共同的邻居。欧盟共同的邻居和他们的交叉连接命名为当地社区,和亲和力的重新定义基于共同邻居在当地社区的功能演示显著提高链接预测monopartite和由两部分构成的网络。如果SAS算法采用基于当地社区模式紧密联系,而不是简单的共同邻居的范例,我们猜想这可能的创新可能使算法更适合于异构网络与小幂律指数。

数据可用性

之前报道的数据被用来支持这项研究,在马克纽曼的网络数据(见http://www-personal.umich.edu/∼mejn / netdata /LFR)和算法程序是可用的https://github.com/eXascaleInfolab/LFR-Benchmark_UndirWeightOvp的更新日志。最初的作者已经免费提供的数据。这些先前的研究(和数据)是在相关地方引用文本中引用(4,15]。

的利益冲突

作者宣称没有利益冲突存在于本文的发表。

确认

这项工作是由中国国家自然科学基金支持下批准号。61873154,11331009,11601294和北师大跨学科研究基础(没有一年级博士候选人。BNUXKJC1806)。

引用

1. j .高,b .巴赛尔,A.-L。巴斯“万能弹性模式在复杂网络,”自然,卷530,不。7590年,第312 - 307页,2016年。视图:出版商的网站|谷歌学术搜索
2. a·r·本森d . f . Gleich, j . Leskovec“高阶复杂网络组织,”科学,卷353,不。6295年,第166 - 163页,2016年。视图:出版商的网站|谷歌学术搜索
3. g . y . Yu, j .周et al。“系统崩溃作为复杂网络的动力学,美国国家科学院院刊》上卷,113年,第11731 - 11726页,2016年。视图:出版商的网站|谷歌学术搜索
4. m . Girvan m·e·j·纽曼,“在社会和生物群落结构的网络,”美国国家科学院院刊》上,卷99,不。12日,第7826 - 7821页,2002年。视图:出版商的网站|谷歌学术搜索
5. m·a·波特j.p. Onnela, p . j .穆夏,“社区网络,”美国数学协会的通知卷,56号9日,第1097 - 1082页,2009年。视图:谷歌学术搜索
6. 走,“社区检测图”,物理的报告,卷486,不。3 - 5,75 - 174年,2010页。视图:出版商的网站|谷歌学术搜索
7. p . j .穆夏,t·理查森,k .梅肯·m·a·波特和j。Onnela”,社区结构时变、多尺度和多路传输网络,”科学,卷328,不。5980年,第878 - 876页,2010年。视图:出版商的网站|谷歌学术搜索
8. a .曾z s .沈j·l·周et al。”增加趋势,科学家之间切换话题,“自然通讯,10卷,不。1,p。3439年,2019。视图:出版商的网站|谷歌学术搜索
9. j.p.张和z金”,流行病蔓延在复杂网络的社区结构,”应用数学和计算,卷219,不。6,2829 - 2839年,2012页。视图:出版商的网站|谷歌学术搜索
10. X.-L。彭,m .小,X.-J。徐,x赋”,流行时间预测预报模式在社区网络,”新物理学杂志,15卷,不。11日,ID 113033条,2013年。视图:出版商的网站|谷歌学术搜索
11. p . y .问:胡,h . b . Chen, m·h·李,z . r . Di和y粉丝,“比较社区的定义和相应的识别算法,”物理评论E,卷78,不。2、文章ID 026121, 2008。视图:出版商的网站|谷歌学术搜索
12. f . Radicchi c可以见到效果,f . Cecconi住诉洛雷托,和d·帕里,“定义和识别社区网络,”美国国家科学院院刊》上,卷101,不。9日,第2663 - 2658页,2004年。视图:出版商的网站|谷歌学术搜索
13. d·詹f . Xi, y詹,f .堂,和k .大臣”模糊分析复杂网络社区探测的”自然史答:统计力学及其应用,卷389,不。22日,第5327 - 5319页,2010年。视图:出版商的网站|谷歌学术搜索
14. a . Lancichinetti Fortunato s、f . Radicchi“基准图测试社区检测算法”,物理评论E,卷78,不。4、文章ID 046110, 2008。视图:出版商的网站|谷歌学术搜索
15. Fortunato和a . Lancichinetti”社区检测算法:比较分析”,物理评论E,卷80,不。5、文章ID 056117, 2009。视图:出版商的网站|谷歌学术搜索
16. a . Clauset m·e·j·纽曼和c·摩尔,“发现社区结构在非常大的网络,”物理评论E,卷70,不。6、文章ID 066111, 2004。视图:出版商的网站|谷歌学术搜索
17. m·e·j·纽曼和m . Girvan“发现和评估网络社区结构,”物理评论E,卷69,不。2、文章ID 026113, 2004。视图:出版商的网站|谷歌学术搜索
18. a .阿里纳斯和a . Diaz-Guilera“在复杂网络同步和模块化,”欧洲物理专题》杂志上,卷143,不。1,19-25,2007页。视图:出版商的网站|谷歌学术搜索
19. s . Boccaletti m . Ivanchenko诉Latora, a . Pluchino和a . Rapisarda“检测复杂网络模块化动态聚类,物理评论E,卷75,不。4、文章ID 045102, 2007。视图:出版商的网站|谷歌学术搜索
20. l . j . s . Wu c .焦c·金et al .,“重叠社区通过网络动态检测,”物理评论E,卷85,不。1,文章ID 016115, 2012。视图:出版商的网站|谷歌学术搜索
21. m . Rosvall和c t Bergstrom,”一位信息理论解决复杂网络社区结构,框架”美国国家科学院院刊》上,卷104,不。18日,第7331 - 7327页,2007年。视图:出版商的网站|谷歌学术搜索
22. e·马萨罗主任f . Bagnoli, a . Guazzini·利奥”信息动态检测算法社区网络”,非线性科学与数值模拟通信,17卷,不。11日,第4303 - 4294页,2012年。视图:出版商的网站|谷歌学术搜索
23. d . m . n .玛雅j·e·m·德·奥利维拉·m·g . Quiles和e·e . n .澳门”通过改编Kuramoto动态复杂网络社区探测,”非线性科学与数值模拟通信,53卷,不。11日,第141 - 130页,2017年。视图:出版商的网站|谷歌学术搜索
24. l . t . Wang阴,x,“社区检测方法基于局部相似度聚类信息,“自然史答:统计力学及其应用卷,490年,第1354 - 1344页,2018年。视图:出版商的网站|谷歌学术搜索
25. f . d . Zarandi和m·k·拉夫桑贾尼在复杂网络社区探测使用结构相似,”自然史答:统计力学及其应用卷,503年,第891 - 882页,2018年。视图:出版商的网站|谷歌学术搜索
26. l . Danon a . Diaz-Guilera j .杜赫,竞技场,群落结构识别相比,“杂志的统计力学:理论和实验,卷2005,不。9篇文章ID P, 2005。视图:出版商的网站|谷歌学术搜索
27. A . Muscoloni和c v Cannistraci”,非均匀popularity-similarity优化(nPSO)模型有效地生成与社区实际的复杂网络,”新物理学杂志,20卷,不。5、文章ID 052002, 2018。视图:出版商的网站|谷歌学术搜索
28. r·阿尔伯特·h·宋,a·l·巴斯”互联网:全球网络的直径,自然,卷401,不。6479年,第131 - 130页,1999年。视图:出版商的网站|谷歌学术搜索
29. m·e·j·纽曼,网络:介绍,牛津大学出版社,纽约,纽约,美国,2010年。
30. 公元Broido和a . Clauset”无标度网络是罕见的。”自然通讯,10卷,不。1,p。1017年,2019。视图:出版商的网站|谷歌学术搜索
31. x张、t·马丁和m·e·j·纽曼,“识别网络的中心-外围结构”物理评论E,卷91,不。第三条ID 032803, 2015。视图:出版商的网站|谷歌学术搜索
32. p . y . Chen赵,k, p . Li和j·张,发现社区的中心,“科学报告》第六卷,没有。1,p。24017年,2016。视图:出版商的网站|谷歌学术搜索
33. 周t、l . Lu和研究。张“预测失踪链接通过当地信息,”欧洲物理期刊B,卷71,不。4、623 - 630年,2009页。视图:出版商的网站|谷歌学术搜索
34. m . Rosvall和c t . Bergstrom“随机漫步的地图揭示复杂网络社区结构,”美国国家科学院院刊》上,卷105,不。4、1118 - 1123年,2008页。视图:出版商的网站|谷歌学术搜索
35. 联合国Raghavan、r·艾伯特和s .库马拉”附近的线性时间算法检测大规模网络中的社区结构,”物理评论E,卷76,不。第三条ID 036106, 2007。视图:出版商的网站|谷歌学术搜索
36. 诉他们,j·l·纪尧姆r . Lambiotte和e . Lefebvre“快速展开的大型网络社区,”杂志的统计力学:理论和实验,卷2018,不。10篇文章ID P10008 2018。视图:出版商的网站|谷歌学术搜索
37. p .脑桥和m .今年”计算使用随机漫步在大型网络社区,”美国计算机和信息科学国际研讨会施普林格,页285 - 293年,伊斯坦布尔,土耳其,2005年10月。视图:出版商的网站|谷歌学术搜索
38. m·e·j·纽曼,“发现社区结构在网络中使用的特征向量矩阵,”Phyical审查E,卷74,不。第三条ID 036104, 2006。视图:出版商的网站|谷歌学术搜索
39. 诉他们,j·l·纪尧姆r . Lambiotte和e . Lefebvre”快速展开社区层次结构在大型网络中,”2008年,https://arxiv-web.arxiv.org/abs/0803.0476v1。视图:谷歌学术搜索

版权

版权©2019王Ning-Ning et al。这是一个开放分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。