品牌传播与度社区网络社区检测的影响

文摘

社区检测是一个重要的任务挖掘复杂网络的结构和功能。在这篇文章中,一个新颖的标签传播方法度附近的影响提出了高效和有效地检测社区网络。首先,我们计算网络中每个节点的邻居影响范围内的度社区网络使用迭代方法。减轻问题的访问顺序相关性和收敛困难异步更新节点的标签时,我们的方法更新标签在一个升序排序α度附近的所有节点的影响。的度附近的影响也是作为更新权重值,参数的影响范围α可以设置为一个正整数。实验结果从几个真实和合成网络表明,我们的方法可以快速而准确地发现网络中的社区结构。我们的方法的性能比其他标签传播为基础的方法。

1。介绍

的出现,各种网络如互联网、社交网络和有机分子网络人类已进入网络时代。发现社区结构在实际网络具有重要的理论意义和较高的应用价值。例如,社交网络的社区结构(1)可以揭示组相同的利益,意见,或双分子的信仰和社区网络可以代表不同的功能模块2- - - - - -5]。

目前,多种算法提出了复杂网络社区探测,如分层聚类,模块化优化和谱聚类(6- - - - - -12]。然而,一些现有的方法受到之前的信息需求的问题,参数敏感性,可怜的时间效率,等等。2007年,一个标签传播算法由Raghavan et al。13),叫做LPA,它可以探测到内在社区网络中没有先验信息。因为其简单性、高速度、时间和效率,LPA最近备受关注。LPA和大多数改进算法的更新每个节点的标签以异步方式,直到达成共识。每个节点更新标签根据其相邻的邻居标签状态,和不同的节点有相同的影响在其附近(13- - - - - -16]。因此,标签可以敏感的更新顺序节点和难以收敛。梁等人提出了一种改进的标签传播方法命名LHLC通过引入分数代表品牌的传播强度与迭代过程。然而,最后的结果很容易衰减的参数16]。此外,为了提高社区检测的准确性,一些标签传播方法采取模块化的过程优化,得到更强大的结果,但是运行的时间和空间复杂性显著增加(14,15]。

改善标签传播的准确性和鲁棒性,我们提出一个方法使用度影响社区为社区检测,称为NILP。给定一个特定的价值,我们首先计算度附近的每个节点的影响。然后,我们安排节点更新过程在升序排序度附近的影响值。第三,我们异步更新每个节点的标签,新标签是最大的加权之和度社区的影响。我们的方法的主要贡献如下:我们提出一个方法来计算度的影响,这里可以量化节点的中心性在其本地链接结构。我们的方法考虑社区的影响在标签更新过程,这使得它比其他标签传播算法更健壮。我们的计算方法分离的过程度社区的影响和更新标签的节点,运行时间,提高了效率。标签按照一定的顺序给出更新可以加速收敛的过程。

剩下的纸是组织如下。部分2介绍了度的社区网络,以及度附近的影响公式。部分3描述了该算法的工作原理和步骤-NILP细节。部分4给出了实验结果和分析。最后,部分5总结了纸。

2。度附近的影响

给定一个网络,在那里组节点和吗边的集合,网络社区检测的任务是找到密集连通子图。标签传播方法应用来实现自动社区检测(13]。以节点为基本计算单元,我们初始化每个节点有一个独特的标签和标签通过网络传播在某种秩序。为了使紧密连接节点有相同的标签,我们考虑本地链接结构。在本节中,给出了一些相关的定义如下。

定义1 (度的邻居)。让是一个无向网络,是一组节点和是一组边缘。让。如果节点的最短路径的长度来是,那么节点被称为度的邻居节点,用。是集包含所有度的邻居。

很明显,的定义度的邻居是对称的,这意味着如果节点是度的邻居节点,那么节点到节点。特别是节点是0度的邻居本身。

定义2 (度社区网络)。让是一个无向网络节点和。生成的子图组成的和,被称为度附近的网络节点。

如图1、2 - 6节点的邻居节点1和被称为1度的邻居节点,节点1的1度社区网络与所有的事件边缘节点。节点7是一个二的邻居节点1和节点的生成子图由1 - 7是一个二社区网络的节点1。一般来说,我们可以把一个度网络作为一个完整的封闭系统由一个初始中心节点及其周边同行及其事件的边缘。在此系统中,从一个特定的节点,我们通过测量和分析其本地连接密度度的邻居和社区网络收益的平均程度对所有周边节点的影响。

在实际网络中,节点影响邻国通过其边缘。在一个未加权的网络,一个中心节点对每一个邻国拥有精确相同的影响。网络是一个加权时,周围的邻居的程度将影响他们体重的比例分配给中心节点事件边缘。而一个中心节点影响它的所有邻居,中心本身也吸收影响的邻居。由于网络固有的链接路径的特点,在其同样的邻居节点的影响是影响所有的1度的平均值的邻居。在下面,我们给出的计算公式度社区的影响。

定义3 (度附近)的影响。让是一个无向加权网络,在那里是一组节点,是一组边缘,然后呢边的权函数。节点之间的权重和节点是,1是默认值在一个未加权的网络。0度的公式邻居节点的影响 在哪里表示节点之间边的重量和节点。为节点对其度的邻居节点(),公式的影响

给定一个网络和参数通过递归计算,我们可以得到度社区影响标量每个节点。

权重的样本无向网络的边缘图1是1。如图2,度附近由公式计算每个节点的影响(1)和(2)在示例网络图所示1与参数= 1、2和3。7,例如,对于节点1度附近的影响是1/4,二是5/16,影响和3影响是271/960。我们把下面为例,说明3邻域的计算过程的影响。考虑

我们可以发现的价值增加,节点的邻居的扫描范围逐渐扩大。的计算度影响社区充分考虑每条路径的终点本身就是和长度。的影响度附近的节点(包括1度附近,二社区、…度附近)将在所有可能的路径传播,最终产生切实影响节点。最终,度的邻居节点的影响加权平均的吗度附近的邻居节点的影响。对于任何一个节点在一个网络中,其平均的事实度附近的影响相对小表明节点和边度附近的网络节点相对密度,节点具有较强的中心性。因此,节点是影响较小的社区,节点的标签吗更稳定。更大的平均度的邻居节点的影响是,稀疏的节点和边之间的联系和较弱的节点的中心性有。因此在这种情况下,节点的影响,它的邻居是啤酒和标签是容易改变。在我们的方法中,网络中的所有节点以升序排序的吗度附近的影响,我们选择这个订单更新标签的顺序,使得标签的更新顺序相对稳定。此外,影响越小,越早的节点更新。我们努力避免标签更新振荡促进融合。

定义4(比稳定的节点)。在标签更新过程中,一次迭代后,节点拥有完全相同的百分比标签之前被称为稳定节点的比例。我们可以计算稳定节点比率作为 在哪里是节点的标签的数量在这一轮迭代中没有变化。

稳定节点比率可以用来衡量算法的收敛程度的持续时间标签传播。

3所示。算法

就像原来的标签传播算法LPA,基于我们的算法度附近也影响迭代更新标签根据节点遍历顺序,最终将组具有相同标签的节点到相同的社区。不同之处在于,我们介绍每个节点的影响值,用它来确定节点的排名和更新节点标签。

3.1。标签的更新

更新标签算法的方法-NILP基于邻居节点的平均影响。当节点的标签需要更新,我们使用以下公式来确定它的新标签: 在哪里是一组1度节点的邻居和是克罗内克函数。如果,然后;否则。

因此,1度的标签的邻居产生最大的影响成为新的标签节点。如果存在多个标签的节点选择最附近的影响,我们随机选择一个标签作为节点的新标签。

3.2。算法描述

鉴于,我们可以描述算法-NILP以下步骤。

步骤1。对于任何一个节点在一个复杂的网络,计算平均度的邻居节点的影响。

步骤2。根据度附近的影响,安排网络中的节点在一个升序排序的影响值来确定节点的更新顺序标签。

步骤3。对于任何一个节点,为其分配一个独特的标签,并设置稳定的比例。

步骤4。根据上面的更新顺序确定,使用公式(5)更新标签的所有节点。

第5步。计算稳定的比率更新当前一轮的标签。

步骤6。比较的价值和;如果,然后,去一步4继续更新节点标签;否则,停止更新,执行回滚所有节点的标签来恢复他们以前的状态。

图3说明了社区检测的过程在上面的例子中使用算法NILP网络时。在图3(一个)样本的网络,每个节点使用一个独特的标签,标记和二社区影响值标签旁边的节点。根据按升序排列的影响值,节点更新订单的决定。节点5是第一个标签更新,使用公式(5)来决定新的标签,结果为相邻街区节点6有最大的影响,所以我们改变节点的标签5的节点数量的邻居,以防6。接下来,我们按顺序更新的所有节点。图3 (b)是划分社区的结果更新在第一轮标签传播。经过第一轮的标签更新过程完成后,与当前节点的稳定的比率,我们应该更新标签按照上述顺序下一轮的节点标签更新过程。算法不再继续运行,直到稳定的比率上升。图3 (c)显示了最终的结果,我们的算法在检测样本的网络社区。

算法基于NILP不同于其他标签传播算法。首先,NILP限制影响的范围,可以对他们的邻居节点变量,它不同于LHLC标签传播过程中的衰减程度设置,使其可行nonattenuation传播的地方在现实生活中。如一个网络朋友,只有数量有限的人范围内的朋友将在相同的朋友圈。当信息内部人士的兴趣已经发布,信息交流沿途的各种关系来达到信息共享的目的,虽然外人大多不可能传播这些信息,因为他们不感兴趣。其次,NILP为每个节点计算均值的影响的扫描范围度附近和完全的度社区网络结构考虑,使品牌传播的过程的效率。第三,节点之间的相互影响是一个客观存在,独立的品牌传播,所以节点邻居的影响和标签迭代更新过程是分开的。因为标签传播收益与节点相互影响,节点更新的过程必须基于平均社区影响的价值。最后,根据社区影响的大小,NILP更新所有节点以升序排序的过程,使更新标签更多明确的,而不是随机的。在一个未加权的网络,当,所有的邻居节点的影响往往是相同的。所以任何节点更新订单可以适用于标签传播过程。因此,对于未加权的网络,公式(5)可以简化为

在这一点上,LPA NILP算法变成原来的标签传播算法。因此,我们可以得出结论LPA仅仅是我们的一个简单示例度的邻居NILP标签传播算法。

3.3。复杂性分析

在本节中,我们分析和比较各种基于标签传播算法的时间和空间复杂性-NILP, LPA、LPAm LHLC。相关的数据表所示1。算法的时间复杂度,我们-NILP由三部分组成的计算度附近的影响,节点排序过程,和标签传播过程。值计算的影响,我们的算法需要遍历所有节点在网络和1度的所有节点的邻居,所以时间复杂度,在那里和分别是,边缘和网络中节点的数量。在排序过程中,我们采用快速排序算法的时间复杂度。标签传播过程的时间复杂度。因此,整体的时间复杂度当在一个稀疏的无标度网络。

然后,我们分析的空间复杂度-NILP算法。因为算法创建节点和最初的社区,我们使用邻接表来描述1度节点和节点之间的通信和社区之间的关系,它占据了和空间,分别相当于总空间的复杂性。

总之,在相同的时间复杂度,LPA, LHLC,-NILP有较低的空间复杂度。这是因为这些算法运行不使用邻接矩阵,从而导致的数据量的减少参与创建、阅读、和操作过程。运行时间消耗也减少由于减少空间的复杂性,这意味着上述三种算法也跑得更快。

4所示。实验结果和分析

在本节中,我们评估算法的性能-NILP通过实验。我们的算法是使用ANSI c++实现。电脑上的所有实验3.20 GHz处理器和4.0 GB的内存。

4.1。数据集

评估算法的性能,我们使用以下三个现实世界的网络。

扎卡里的空手道俱乐部网络。一个社会关系网络成员之间的美国大学空手道俱乐部(http://networkdata.ics.uci.edu/data.php?id=105)105年由顶点和882边,每个顶点代表俱乐部成员和一条边表示两个成员,以为美国朋友而不仅仅是熟人,经常联系对方。由于内部纠纷,俱乐部分成两组,这是其真正的网络社区结构。

NCAA大学橄榄球网络。美式足球游戏的网络部门之间IA学院在常规赛期间2000年秋季(http://networkdata.ics.uci.edu/data.php?id=5)115年由顶点和1232边,在每个顶点对应于一个美国大学足球队,每个边代表两个相应的球队在常规赛打了一场比赛2000年秋季。所有的团队分为11个会议和5个独立团队。

关于美国政治的书。关于最近的美国政治的书卖的网络在线书商由105点和882边缘,每个顶点对应于一个美国政治的书,每条边表示两个相应的频繁copurchasing书籍。

DBLP Coauthorship网络。加权网络作者(即四个研究领域。,DB, IR, DM, and ML) extracted from the DBLP computer science bibliographical dataset is composed of 28,702 vertexes and 66,832 edges, in which each vertex corresponds to a distinct author who has published more than twenty papers and each edge represents their coauthor relationship. The weight of an edge denotes the number of papers coauthored by these two authors.

与此同时,我们利用工具由Lancichinetti et al。17)生成几个合成网络和把他们分成两组基于网络的节点数量,一组的节点数量是1000,另一组10000。每组由15个网络,与他们的混合系数从0.1到0.8步长为0.05。进一步评估我们的方法的性能,我们也上运行算法的不同数量的网络节点,包括1000年、5000年,25000年,5000年,100000年,250000年和500000年,混合系数为0.3。

4.2。分析参数的影响

比较不同的价值观的影响在我们的算法的性能,我们进行我们的实验基准足球数据集和15 1000 -合成LFR网络节点与他们混合在一个增量系数从0.1到0.8不等间隔为0.05。设置的值从1到40,当检测社区在现实网络足球和合成网络,敝中断值算法的数据所示4(一)和4 (b)。

如图4(一),在真正的足球网络,敝中断获得价值最高,表明结果是最接近正确的。当11、13、20、敝中断价值大幅波动,这是因为,根据这些值,获得标签更新订单和节点的社区影响真正的网络划分为几个大型社区,因此敝中断是显著降低。这意味着一个真正的链接结构网络有一定的随机性;因此基于标签传播算法运行在这些网络社区检测节点的遍历顺序更敏感。图4 (b)显示1000 -合成网络节点上的实验结果,我们可以发现,与真正的网络相比,该算法更稳定的合成网络。当混合系数2、0.4或0.6,总能产生最大敝中断值。网络的混合系数为0.8,敝中断时不是最大的价值,但它是非常接近最大值。大量的实验表明,在大多数情况下,community-dividing算法结果NILP最佳或算法。因此,所有的后续部分进行了实验使用2-NILP实验分析。

4.3。评估在真实的网络

首先,我们分析的结果算法NILP和LPAm Zachary空手道的网络,如图5。在图5(一个),算法的检测结果LPAm,网络分为三个社区,虽然算法2-NILP将网络划分为两个社区,这正是真正的情况下,就像地面实况图所示5 (b)。比较这两个数据,我们可以知道,最显著的区别在于是否节点集被视为一个独立的社区。从图可以看出,节点组成的子图的结构是相对稳定的,密切与节点1,所以节点集吗应该属于社会属于哪个节点1。算法LPAm采用当地模块化优化原则但不找到最优的社区,而我们2-NILP算法发现网络结构通过计算局部地区的当地社区的影响和分析密度。虽然并不一定最优分区最大的网络模块的价值观,更有效地检测网络的固有的社会结构。敝中断值,我们从实验获得的四种不同的标签传播算法,即LPA,扎贾里LHLC和2-NILP网络LPAm表中列出的空手道和足球2。从表可以看出2,我们的算法2-NILP实现最好的结果的准确性,这也是几乎适用于LPAm像样的准确性。然而,早些时候提出的标签传播算法LPA和LHLC准确性较低由于他们更新过程不受控。

在下面,我们将分析的结果我们NILP算法在实际DBLP coauthorship网络。自从网络DBLP不提供一个标准的结果可以用来比较,我们评估的正确性得到社区网络的数据源。该方法检测不同大小的3466个社区网络。表3列出了五个真正的社区发现。由于空间的限制我们的纸,只有7个成员列出每个社区。从表可以看出3,社区和社区在数据挖掘领域的专家、学者Philip s . Yu和加威汉被视为他们的领军人物,分别。社区由专家、学者在数据库从InfoLab斯坦福大学实验室。社区由专家、学者从CMU在机器学习领域和社区是由专家和学者在信息检索领域。它可以观察到,科学家从一个社区,被我们的算法,往往在同一领域的研究,占他们频繁的学术合作。在相同的领域,通常有多个社区是由不同的团队工作。在一个团队中,通常有一个共同或相似的研究方向和长期合作,虽然不同的工作团队将很少有机会合作。因此,社区检测结果通过该算法从DBLP声音和准确。

4.4。评价合成网络

我们也评估算法的性能在合成网络。图6说明了社区检测精度的比较四个标签传播算法LPA, LPAm LHLC, 2-NILP。1000 -节点的混合系数合成网络图6(一)和10000 -节点网络图6 (b)两个从0.1到0.8不等。它可以观察到,LHLC的准确性相对较低较其他三种算法。算法LPA、LPAm敝中断和NILP有更高的价值。当节点的数目是1000,如图6(一)2-NILP显然比的准确性,LPA的算法。当混合系数小于0.55,2-NILP LPAm同等精度的算法,当混合系数大于0.55,2-NILP比LPAm更好。当节点的数目是10000,如图6 (b),我们的算法的精度2-NILP优于其他三种算法。

4.5。运行时间比较

为了比较上述四种算法的效率,我们继续合成网络进行实验,实验结果如图7。在这个实验中,我们选择网络的混合系数是0.3和节点的数目是1000,5000,10000,25000,50000,100000,250000,500000。从图可以看出7在相同的情况下,我们的算法的运行时间NILP应低于其他三种算法。这是因为NILP计算每个节点度附近的影响并更新标签根据影响程度,最后标签的影响密切相关;因此NILP算法可以使节点标签更容易实现他们的稳定性。因此,算法NILP需要更少的时间比其他三种算法。拥有巨大的空间成本发生在运行时,节点的数量超过10000时,算法LPAm未能继续其在合理的时间完成。

5。结论

本文基于新颖的标签传播算法,称为NILP,提出了在网络社区检测。基于网络的链接结构,我们的方法介绍了测量节点度附近的影响,充分考虑节点的影响对他们的邻居为了确定节点的更新顺序标签。该方法提高了社区检测的准确性和效率,减少了内存消耗。我们的方法的结果是著名的在不同类型的网络。适用于社区检测和演化分析的动态网络,尤其是大量的在线社交网络。

利益冲突

作者宣称没有利益冲突有关的出版。

确认

部分支持的工作是由美国国家科学基金会的拨款61173093,61202182,71373200,2012年中国博士后科学基金会m521776,陕西省自然科学基础研究计划的拨款2013 jm8019和2014 jq8359,中央大学的基础研究基金资助K5051323001 BDY10,陕西博士后科学基金会。任何意见,结果和结论表示这是作者的,不一定反映资助机构的意见。

引用

1. z赵,冯,问:Wang j . z黄g·j·威廉姆斯和j .粉丝,“面向主题的社区检测通过社交对象和链接分析社交网络,”以知识为基础的系统26卷,第173 - 164页,2012年。视图:出版商的网站|谷歌学术搜索
2. r·艾伯特和A.-L。巴斯”统计力学的复杂网络,“现代物理学的评论,卷74,不。1,47 - 97、2002页。视图:出版商的网站|谷歌学术搜索|MathSciNet
3. A.-L。巴巴斯和r·阿尔伯特”出现随机网络的扩展,“科学,卷286,不。5439年,第512 - 509页,1999年。视图:出版商的网站|谷歌学术搜索|MathSciNet
4. a . Lancichinetti j . Saramaki m . Kivela, s . Fortunato”描述复杂网络的社区结构,”《公共科学图书馆•综合》,5卷,不。8篇文章ID e11976 2010。视图:出版商的网站|谷歌学术搜索
5. m·e·纽曼,“复杂网络的结构和功能,暹罗审查,45卷,不。2、167 - 256年,2003页。视图:出版商的网站|谷歌学术搜索|MathSciNet
6. r·t·Ng和j·汉,“Clarans:空间数据挖掘对象的聚类方法,”IEEE工程知识和数据,14卷,不。5,1003 - 1016年,2002页。视图:出版商的网站|谷歌学术搜索
7. m . Girvan m·e·纽曼,“在社会和生物群落结构的网络,”美国国家科学院院刊》上的美利坚合众国,卷99,不。12日,第7826 - 7821页,2002年。视图:出版商的网站|谷歌学术搜索|MathSciNet
8. j·a·哈和m . a . Wong”算法136:k - means聚类算法”,英国皇家统计学会杂志》上。系列C(应用统计),28卷,不。1,第108 - 100页,1979。视图:谷歌学术搜索
9. m .酯H.-P。徐Kriegel, j·桑德,x,”density-based算法发现在大型空间数据库集群的噪音,”第二届国际会议上知识发现和数据挖掘(KDD ' 96),第231 - 226页,1996年。视图:谷歌学术搜索
10. p .脑桥和m .今年”计算使用随机漫步在大型网络社区,”计算机和信息Sciences-ISCIS 2005卷,3733在计算机科学的课堂讲稿,第293 - 284页,2005年。视图:出版商的网站|谷歌学术搜索
11. m·e·j·纽曼,“检测在网络社区结构,”欧洲物理期刊B:凝聚态和复杂的系统,38卷,不。2、321 - 330年,2004页。视图:出版商的网站|谷歌学术搜索
12. 刘黄j . h .太阳,y,问:歌曲,和t . Weninger”对在线多分辨率社区检测大规模网络,”《公共科学图书馆•综合》》第六卷,没有。8篇文章ID e23829 2011。视图:出版商的网站|谷歌学术搜索
13. 联合国Raghavan、r·艾伯特和s .库马拉”附近的线性时间算法检测大规模网络中的社区结构,”物理评论E,卷76,不。第三条ID 036106, 2007。视图:出版商的网站|谷歌学术搜索
14. m·j·巴伯和j·w·克拉克,“检测网络社区传播约束下标签,”物理评论E文章ID 026129卷,80年,2009年。视图:出版商的网站|谷歌学术搜索
15. x刘和t .日本村田公司“先进modularity-specialized标签传播算法检测社区网络,”自然史答:统计力学及其应用,卷389,不。7,1493 - 1500年,2010页。视图:出版商的网站|谷歌学术搜索
16. i . x y Leung) p .回族·利奥和j·Crowcroft说“在大型网络社区对实时检测物理评论E文章ID 066107卷,79年,2009年。视图:出版商的网站|谷歌学术搜索
17. a . Lancichinetti Fortunato s、f . Radicchi“基准图测试社区检测算法”,物理评论E,卷78,不。4、文章ID 046110, 2008。视图:出版商的网站|谷歌学术搜索

版权

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