当地社区检测算法基于最小集群

文摘

为了更有效地发现当地社区的结构,提出了一种新的基于最小集群当地社区检测算法。大多数的当地社区检测算法从一个节点开始。单个节点的集聚能力必须小于多个节点,所以一开始的社区的扩展算法在本文中不再是只从初始节点但从节点集群包含这个初始集群中的节点和节点相对密集的相互连接。该算法主要包括两个阶段。首先它检测到最小的集群,然后发现当地社区从最小的集群扩展。实验结果表明,当地社区的质量检测到我们的算法比其它算法无论在模拟真实的网络或网络。

1。介绍

复杂网络社区探测一直是一个热门研究领域。最近,大量的算法提出了研究全球结构的网络,如模块化优化算法(1,2),谱聚类算法(3- - - - - -6),层次聚类算法(7- - - - - -10),和标签传播算法(11- - - - - -14]。然而,随着复杂网络的不断扩张,很容易收集大型网络数据集与数以百万计的节点。如何如此大规模数据集存储在计算机内存分析学者是一个巨大的挑战。计算为研究这种大规模网络的总体结构是不可想象的。所以当地社区检测成为一个吸引人的问题,吸引了越来越多的关注15- - - - - -18]。当地社区检测的主要任务是要找到一个社区使用的本地信息网络。当地社区检测具有良好的可扩展性。如果当地社区检测算法是迭代执行,可以找到更多的当地社区和整个网络的社区结构。这种全球社区的时间复杂度检测算法依赖于当地社区检测算法的效率和精度,所以当地社区检测算法的研究仍有很长的路要走。有几个问题需要解决在当地社区检测的研究。首先,我们应该确定初始状态和为当地社区找到初始节点检测,以确定所需的本地信息;然后,我们需要选择一个目标函数,并通过不断迭代优化的目标函数,我们发现高质量的群落结构;之后,我们需要找到一个合适的节点展开方法,所以该算法可以提取当地社区从初始状态一步一步;最后,为了终止算法,需要一个合适的终止条件来确定社区的边界。

大多数当地社区检测算法是基于上述过程。当地社区检测的定义是找到当地社区结构从一个或多个节点,但大多数现有的当地社区检测算法,包括Clauset [15],LWP [16],LS (17),仅从一个初始节点。他们贪婪地从候选节点选择最优节点,并将它们添加到当地社区。LMD [18从初始节点算法扩展不但是从最亲密的和下一个最近的地方度中央节点。它发现一个当地社区从每一个节点,分别。还是从单个节点开始,发现许多当地社区为初始节点。在一般情况下,单个节点的聚合能力低于多个节点。所以我们不能仅仅依靠当地社区的初始节点开始扩张。我们的主要目标是找到一个最小的集群紧密相连初始节点,然后检测当地社区集群基于最小。这可以避免不稳定由于过度依赖初始节点。在本文中,我们引入一个基于最小cluster-NewLCD当地社区检测算法。在这个新算法,社区的开始扩张不再只从初始节点,但集群的节点相对初始节点紧密相连。该算法主要包括两个部分:一个是最小的检测集群,另一个是当地社区的检测集群基于最小。 At the same time, the algorithm can be applied to the global community detection. After finding one local community using this algorithm, we can repeat the process to obtain the global community structure of the whole network.

2。相关的当地社区检测

2.1。当地社区的定义

当地社区检测的问题,提出了通过Clauset [15]。通常我们定义以下的当地社区问题:有一个非引导图,代表节点的集合,代表图中的边。图中的部分节点的连接信息已知或可以获得。当地社区的定义是。连接的节点的集合被定义为节点的集合与节点被定义为节点集的边界。也就是说,任何节点连接到一个节点和其他的核心节点集吗,如图1。

当地社区检测问题是开始从预选的源节点。它增加了节点满足条件成并删除不满足条件的节点D逐渐。

2.2。相关的算法

目前,许多当地社区检测算法。我们介绍两个代表当地社区检测算法。

(1)Clauset算法。为了解决当地社区检测的问题,Clauset [15)提出了当地社区模块化R并给出一个快速收敛贪婪算法找到当地社区最大的模块化。

当地社区模块化的定义如下: 在哪里和代表图中两个节点。如果节点和连接的价值是1;否则,它是0;如果节点和都是在的价值,是1;否则,它是0。

当地社区检测Clauset算法的过程类似于网络爬虫算法。首先,Clauset算法从一个初始节点。节点添加到子图吗,和它的所有邻居节点被添加到。算法中添加节点能带来的最大增量到当地社区迭代,直到当地社区的规模达到预设的大小。也就是说,该算法需要设置一个参数的大小来决定社区,结果深受初始节点。

(2)LWP算法。LWP [16)算法是一种改进的算法,它有一个明确的结束条件与Clauset算法。该算法定义了另一个地方社区模块化,表示为 在哪里和代表图中两个节点。如果节点和相互连接的价值是1;否则,它是0;如果节点和都是在的价值,是1;否则,它是0;如果只有一个节点和是在的价值,是1;否则,它是0。

给定一个无向和未加权的图LWP算法从一个初始节点找到最大值的子图。如果子图是一个社区(即),那么它将返回子图作为一个社区。否则,它认为没有社区,可以发现从这个初始节点。对于初始节点,LWP算法发现当地模块化的最大值的子图通过两个步骤。首先,初始化算法通过构造子图只有一个初始节点和所有的邻居节点的节点被添加到组吗。然后执行增量步和修剪算法步骤。

在增量的步骤中,所选择的节点使当地的模块化的增加添加到最高的价值迭代。贪婪算法将迭代添加节点来,直到没有节点可以添加。在修剪步骤中,如果当地的模块化当把一个节点从变大真的,然后删除它。在修剪过程中,算法必须确保连接的不是毁灭,直到没有节点可以被删除。然后更新设置重复这两个步骤,直到没有变化。该算法具有很高的回忆,但其精度较低。

这两种算法的复杂性,在那里节点的数目是在当地社区和探索节点的平均度是探索在当地社区。

3所示。该算法的描述

3.1。发现的最小的集群

一般来说,网络可以被描述为一个图,在那里组节点和吗边的集合。它包含节点和边缘。代表一个节点集的网络和当地社区节点的数量在吗。我们引入两个定义提出了相关算法。

定义1(邻居节点集)。它是一组节点直接连接到单个节点或一个社区。
为节点,它的邻居节点集可以表示为。
为社区包含节点,它的邻居节点集可以表示如下:

定义2(共享邻居的数量)。共享邻居节点的数量和可以计算为

最小集群算法的检测是关键。最小集群的节点连接到初始节点最密切。我们介绍一个方法(22]找到节点与初始节点紧密相连。它使用密度函数(23)是广泛使用的,可以计算的 在哪里代表社区边的数量和代表在社区的节点数量。更大的,越密集的节点是相关的。有必要设置一个阈值为决定选择哪些节点集群形成最初的最小。文献[22]给出的定义这个阈值函数所示

和阈值选择的节点构成最小集群。如果或,这些节点被认为是形成一个最小的集群。与其他方法相比,阈值不依赖于人工设置,但它是完全依赖于节点,所以算法的不确定性降低。在这个过程中,网络中所有节点可以分配给多个紧密连接集群。在这个过程中,约束条件的最小集群相对严格。那么全球网络的社区结构发现通过结合这些最小的集群。这是一个过程从地方到全球通过寻找所有最小集群获得全球的网络结构。我们当地的社区检测算法只需要找到一个社区在全球网络。灵感来自这个想法,我们改善这个算法如算法所示1。

在网络,我们想找到最小包含节点集群。首先我们需要遍历所有的邻居节点和找到的节点股票最和节点邻居吗(步骤3)。然后将节点,和他们共同的邻居节点作为初始最小集群(步骤4)。一般来说,节点和它的邻居节点是最有可能属于同一个社区。我们发现的节点最密切联系v根据共享邻居的数量。他们共享邻居的数量越多,两个节点连接的更紧密。也就是说,连接两个节点的节点和更有可能属于同一个社区。我们把它们放在一起作为初始最小集群当地社区的扩张,这是有效和可靠的经验验证了。

找到最小的集群的过程是一个例子如图所示2。假设我们想要找到最小集群包含节点1。我们需要遍历它的邻居节点2,3,4,6,,。我们可以看到节点3是最密切相关的一个节点1,最小的集群。是当地社区的起始节点集的扩展。

3.2。检测当地社区

首先,我们使用的算法1找到最接近的节点连接到初始节点。我们把节点和节点以及他们共同的邻居节点作为初始最小的集群。第二部分的算法是基于节点的最小的集群进行扩张,最后找到当地社区。中所示的特定过程的算法2。

在该算法中,我们仍然使用函数用于LWP算法作为当地社区发展的标准。算法1能找到最初的最小集群。在那之后,算法2发现你的邻居节点集NLC (LC)和计算的初始值(步骤2)。然后遍历所有的节点N(LC)(步骤03-04)找到一个节点最大,并将它添加到当地社区LC(步骤05-08);更新N(LC)和(09)步,直到没有新节点添加到LC(步骤10)。

的复杂性NewLCD算法Clauset算法几乎是一样的。NewLCD算法利用额外的时间找到最小的集群的初始节点的线性程度。

4所示。实验结果和分析

在本节中,NewLCD算法比较与几个代表当地社区检测算法,即LWP, LS和Clauset,来验证其性能。实验环境如下:英特尔(R)的核心(TM) i5 - 2400 @ 3.10 GHz CPU;内存2 G;操作系统:Windows 7;编程语言:c# . net。

4.1。实验数据

LFR基准网络的数据集和三个真实网络数据集用于实验。

(1)LFR基准网络(24)是目前最常用的合成网络社区检测。它包括以下参数:N的节点数量;是节点的数量最低社区包含;节点的数量是最大的社区包含;网络中节点的平均度;最大程度的节点;μ是一个混合参数,外部社区的节点与节点的概率。μ越大,就越难发现社区结构。我们生成四组LFR基准网络。两组网络、B1和B2、分享的共同参数,,。网络的其他两组,B3和B4,分享共同的参数,,。社区的大小B1和B3和社区的大小B2和B4,这意味着小型社区网络和大型社区网络,分别;每组包含9个网络μ从0.1到0.9代表从低到高混合网络。细节如表所示1。

(2)我们选择三个真正的网络包括扎贾里的空手道俱乐部网络(空手道),美国大学足球网络(足球),网络(Polbooks)和美国的政治书。的详细信息如表所示2。

4.2。人工网络实验

因为大尺寸的综合网络,节点随机选择50代表从每组作为初始节点和所有的实验结果都平均作为最终结果。数据3- - - - - -6是每个算法的实验结果比较图的四组LFR基准网络(B1-B4)。纵坐标代表三个评估标准为当地社区检测,分别,横坐标的值是μ(0.1 - -0.9)。以下的结论可以通过观察。

(1)LS和LWP算法相比Clauset算法有更高的精度。但是他们回忆价值低于Clauset算法。LS和LWP算法不能有精度高和回忆。他们的综合效应可能Clauset不高于基准算法。

(2)NewLCD算法的这三个指标都明显高于Clauset算法,显示初始状态确实影响当地社区检测算法的结果,并从最小的集群比单个节点。

(3)总体上,NewLCD算法是最好的。四组的网络,当参数μ小于0.5,NewLCD算法可以找到几乎所有的当地社区每个节点位置。在高混合网络中,当μ的值大于0.8,当地社区NewLCD算法的检测效果不好,就像其他算法。主要原因是网络的社区结构是不明显的。

总之,NewLCD算法可以检测当地社区在人工网络比其他三个地方社区检测算法。

4.3。真正的网络实验

为了进一步验证NewLCD算法的有效性,我们比较它与其他三个算法在三个真实网络(空手道,足球,和Polbooks)。这三种网络通常是用于验证算法在复杂网络的有效性。实验结果如表所示3和每个指标的最大值用粗体显示。精密的最大值空手道是0.989通过LS算法。但召回值是0.329这四种算法之间的最小值。所以LS算法是最糟糕的结果。空手道网络,Clauset LS算法和LWP算法有相同的问题,这意味着他们的回忆价值很低。而回忆和FNewLCD算法的分数值是最大的,NewLCD算法是最优的。在足球网络,NewLCD算法的综合效果也是最好的。Polbooks网络,NewLCD算法的优势更加明显,这三个指标的结果都是最好的。总之,NewLCD算法不仅可以有效地应用于人工网络,但它也可以是非常有效的网络状况。

空手道社会学的网络是一个典型的人际关系网络。它反映了在俱乐部经理和学员之间的关系。从一个空手道俱乐部网络是在美国的一所大学。俱乐部的管理员和老师有不同的意见是否提高俱乐部的费用。因此,俱乐部分裂成两个独立的小俱乐部。自空手道网络的结构很简单,它反映了现实世界中,许多社区检测算法使用它作为标准的实验数据来验证社区的质量。为了进一步验证算法的有效性,我们在空手道做进一步的实验。图7是真正的社区结构的空手道。如果我们选择8节点作为初始节点,数据8和9分别是,当地社区结构发现NewLCD和Clauset。是真正的当地社区包含节点8和是Clauset的结果。我们可以看到节点2是分配给当地社区,而节点23日,24日,25日和31日离开。包含节点8 NewLCD探测到的社区。只有节点2是错误地分配给社区,没有遗漏任何节点。当地社区被NewLCD更类似于真正的一个。当一个节点不能代表所有的情况,我们做更多实验扩大从每个节点的空手道和相应的精度进行比较,回忆,和F分数,如图10。横坐标代表34个节点,从0到33,纵坐标F分别得分、召回和精度。虽然Clauset的精度值略高于NewLCD扩大的结果从节点,记得Clauset值远低于NewLCD的结果。所以NewLCD算法比Clauset算法。

5。结论

本文提出了一种新的基于最小cluster-NewLCD当地社区检测算法。该算法主要包括两个部分。第一部分是为当地社区找到最初的最小集群扩张。第二部分是添加节点的邻居节点集满足当地社区的条件在当地社区。我们比较其他三个地方社区检测算法的改进算法和人工网络状况。实验结果表明,该算法可以找到当地社区结构比其他算法更有效。

相互竞争的利益

作者宣称没有利益冲突有关的出版。他们宣布他们没有任何商业或关联利益代表利益冲突与提交的工作。

确认

这项工作是由中国国家自然科学基金(没有。61572505,没有。51404258,没有。61402482),中国国家高技术研究发展计划(2012 aa011004),中国博士后科学基金会(没有。2015 t80555),江苏省博士后研究基金(没有计划项目。1501012 a)。

引用

1. m·e·j·纽曼和m . Girvan“发现和评估网络社区结构,”物理评论E-Statistical、非线性和软物质物理学,卷69,不。2、292 - 313年,2004页。视图:出版商的网站|谷歌学术搜索
2. j·李,s . p .总值和j·李,“模块化优化构象空间退火,”物理评论E,卷85,不。5篇文章ID 056702年,第508 - 499页,2012年。视图:出版商的网站|谷歌学术搜索
3. H.-W。沈和X.-Q。程,“光谱方法检测网络社区结构:比较分析,“杂志的统计力学:理论和实验,卷2010,不。10篇文章ID P10020 2010。视图:出版商的网站|谷歌学术搜索
4. j .吴Z.-M。崔,Y.-J。施,S.-L。盛,S.-R。锣,“当地density-based谱聚类相似矩阵结构,”杂志在通信,34卷,不。3,14-22,2013页。视图:出版商的网站|谷歌学术搜索
5. s . Mehrkanoon c . Alzate r .购物中心,r·兰贡和j·a·k·Suykens“多级semisupervised学习基于内核谱聚类,“IEEE神经网络和学习系统,26卷,不。4、720 - 733年,2015页。视图:出版商的网站|谷歌学术搜索
6. k . Taşdemir b Yalcin,即Yildirim”近似与利用谱聚类相似度信息使用基于测地线的混合距离的措施,”模式识别,48卷,不。4、1461 - 1473年,2015页。视图:出版商的网站|谷歌学术搜索
7. 诉他们,j . Guillaume r . Lambiotte et al .,“快速展开的大型网络社区,”杂志的统计力学:理论和实验,30卷,不。2、155 - 168年,2008页。视图:谷歌学术搜索
8. d . k . m . Tan威滕,a . Shojaie”集群图形套索改进高斯图形模型的估计,”计算统计和数据分析卷。85年,23-36,2015页。视图:出版商的网站|谷歌学术搜索
9. f . De Morsier d . Tuia m . Borgeaud诉盖斯和j。Thiran”集群层次聚类有效性测量和合并系统考虑异常值时,“模式识别,48卷,不。4、1478 - 1489年,2015页。视图:出版商的网站|谷歌学术搜索
10. a . Bouguettaya Yu, x, x,和a的歌,“高效会凝聚的层次聚类,专家系统与应用程序,42卷,不。5,2785 - 2797年,2015页。视图:出版商的网站|谷歌学术搜索
11. l . Subelj和m . Bajec”展开大型复杂网络中社区:结合防御和进攻核心提取标签传播,”物理评论大肠统计、非线性和软物质物理学,卷83,不。3、885 - 896年,2011页。视图:出版商的网站|谷歌学术搜索|MathSciNet
12. 李,h·卢、w .江和j .唐“通过同步检测群落结构标签传播,”Neurocomputing,卷151,不。3、1063 - 1075年,2015页。视图:出版商的网站|谷歌学术搜索
13. y, y, h·张,j . Wang和j .香港”标签传播semi-supervised非负矩阵分解的特征提取为基础,“Neurocomputing卷,149年,第1037 - 1021页,2015年。视图:出版商的网站|谷歌学术搜索
14. d . Zikic b·格洛克,a . Criminisi“随机森林分类编码地图册的高效multi-atlas标签传播,”医学图像分析,18卷,不。8,1262 - 1273年,2014页。视图:出版商的网站|谷歌学术搜索
15. a . Clauset”找到当地社区结构的网络,”物理评论E-Statistical、非线性和软物质物理学,卷72,不。2、254 - 271年,2005页。视图:出版商的网站|谷歌学术搜索
16. f·罗,j . z . Wang和e . Promislow“探索当地社区结构在大型网络中,”网络情报和代理系统》第六卷,没有。4、387 - 400年,2008页。视图:出版商的网站|谷歌学术搜索
17. z h . y . j . Wu黄,f, f·陈,“当地社区使用链接相似度检测,”计算机科学与技术杂志》上,27卷,不。6,1261 - 1268年,2012页。视图:出版商的网站|谷歌学术搜索
18. 问:陈,T.-T。吴,m .方”检测当地社区结构在复杂网络中基于地方度中央节点,“自然史答:统计力学及其应用,卷392,不。3、529 - 537年,2013页。视图:出版商的网站|谷歌学术搜索
19. http://www-personal.umich.edu/ mejn / netdata /
20. w·w·扎卡里,”一个信息流模型在小群体冲突和分裂,”《人类学研究,33卷,不。4、452 - 473年,1977页。视图:出版商的网站|谷歌学术搜索
21. m . Girvan m·e·j·纽曼,“在社会和生物群落结构的网络,”美国国家科学院院刊》上的美利坚合众国,卷99,不。12日,第7826 - 7821页,2002年。视图:出版商的网站|谷歌学术搜索|MathSciNet
22. n . p .阮t . n . Dinh s Tokala和m . t .泰国“重叠社区动态网络:检测和移动应用程序,”学报17年移动计算和网络国际会议(MobiCom 11),页85 - 95,拉斯维加斯,内华达州,美国,2011年9月。视图:出版商的网站|谷歌学术搜索
23. Fortunato s和c可以见到效果,“社区结构的图表,”计算复杂度施普林格,页490 - 512年,2012年。视图:谷歌学术搜索
24. a . Lancichinetti Fortunato s、f . Radicchi“基准图测试社区检测算法”,物理评论E,卷78,不。4篇文章ID 046110年,第570 - 561页,2008年。视图:出版商的网站|谷歌学术搜索

版权

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