文摘

发现社区结构和预测群落结构的变化是社会网络研究的一个重要研究课题。关注节点的重要性和他们的邻居和邻接信息的重要性,本文提出了一种新的节点重要性评估方法。提出的重叠社区检测算法(ILE)使用随机选择初始社区和采用自适应功能,扩大社区。最终优化社区获得重叠社区。重叠社区,本文分析了网络的进化在不同时期根据社交网络的稳定和差异。7个公共社区进化事件。实验结果表明,我们的算法是可行的,能够发现重叠社区有效地在复杂的社会网络。

1。介绍

随着信息技术的发展,微博和论坛等社交网络近年来发展迅速,逐渐成为人们交流感情的重要平台,分享经验,传递信息。目前,有许多社区检测算法基于节点集的分区,例如,Kernighan-Lin算法(1基于贪婪算法理论,光谱二分算法(2)基于光谱认为,GN算法(3基于分裂思想,纽曼快速算法(4)基于凝聚力思想。然而,这些社区检测算法的最终目标是将网络划分为几个独立的社区。上述算法严格把每个节点分成特定的社区和找不到重叠社区。在现实网络的深入研究,研究人员发现,不仅许多真实网络社区结构,也有重叠的特点和社区之间的相关性。网络是由许多重叠和相互联系的社区(5];例如,在人际网络中,每个人都属于几个不同的社区,如学校,家庭,和朋友们根据不同的分类方法。为研究网络结构的基础上,揭示了网络中的社区结构研究具有重要意义的功能网络和分析网络的组成结构。重叠社区检测已成为研究机会网络结构的关键问题。许多学者提出了大量的重叠社区发现算法,如线性调频(6,恶魔7],SLPA [8]。然而,当前重叠社区发现算法的准确性和复杂性需要改善。

在本文中,重叠社区发现算法分为四类。他们是集团渗透算法,标签传播算法,链接分区算法,算法和当地的扩张。我们主要关注重叠社区发现算法基于局部扩张。发现许多地方扩张算法以节点中心为评价指标。很大程度上决定初始节点重叠社区的划分结果。最初随机选择的节点会导致一定的偏差重叠节点在社区的成员。为兴趣社区,当用户属于网球和篮球社区,他们有不一致的偏好评估不同的社区,使偏离重叠节点成员的数量。如果网络中的所有节点作为初始节点的扩张,很容易形成一个独立的社区,这将使社区检测不准确。通过对复杂网络的多样性的研究,我们发现只有一个评价指标容易高重叠的当地社区。更多的因素需要考虑节点的选择。 We also find that it needs to have the following characteristics if the nodes can be located in the community center to stabilize the structure of the whole community. (a) The node must be a certain number of neighbor nodes. (b) Both the influence of neighbor nodes on the node itself and the high connectivity between neighbor nodes should be considered. (c) Whether the neighbor node is also of high importance.

社会网络分析(9)已成为一个重要的研究领域和数据挖掘中起着重要的作用,信息传播网络建模、行为分析、知识发现等。在现实世界中,大多数社交网络是动态的网络。他们的节点将会改变,节点之间的关系会随着时间的推移而演变。节点之间关系的密度是不同的。一些节点相对密集的连接,而其他人则相对稀疏的连接。一组节点相对密集的连接被认为是一个社区(10]。节点在社区通常有一些共同的属性。这反映了当地规则和全球秩序的社交网络在一定程度上。提取群落结构可以有效地揭示社交网络的特点和一般法律的组。它是社交网络的演化分析的基础。它还有助于推动相关应用程序的开发,例如,朋友推荐,隐私保护,网络营销,角色分析11]。因此,社区提取是一个重要的研究领域在社交网络领域的分析,分析和理解的具有重要意义的结构属性和群体社交网络的特征。

研究的动态网络改变随着时间的推移,有必要评估社区上下时间片之间的进化。建立准确、有效的评估标准是重要的判断是否存在一个进化社区之间的关系。常见的方法是计算相邻时间的相似性的社区。也有许多相似度计算的研究,例如,基于Jaccard系数评价方法和归一化互信息(敝中断)。选择合理、有效的评价标准和评价阈值设定一个具有挑战性的研究现状。我们认为这两个社区进化上的相似性和完整性和较低的时间片应考虑针对社区发展的评价在相邻的动态网络。基于宇宙中星系形成的想法(12),本文给出了大规模网络中的所有节点,并试图建立节点之间的重心的关系矩阵。最后,它选择全球节点具有地方特色,将他们划分为不同的节点链的初始结构。为静态网络,社区吸引周围的节点通过迭代在重力的作用下多点。它可以发现,相邻的时间片的群落结构,核心节点的改变重力链可以用来观察社区的演化过程的完整性。然后,结合当地不同进化行为,共同评估。

基于上述分析,我们提出一个重叠社区检测算法基于节点重要性和邻接信息。这项工作的主要贡献如下:(1)很多的节点重要性指标经常考虑单因素。我们的指标考虑节点重要性和邻接信息,即。,the importance of the node itself, the importance of node neighbors, and the connectivity between neighbors.(2)我们设计一个重叠社区检测算法基于节点重要性和邻接信息。它使用该中心节点相关性评估节点的重要性。(3)基于重叠社区发现算法的结果,我们进一步研究群落结构在不同的时刻。

本文的其余部分组织如下。节2,我们介绍我们的算法的相关工作(ILE)。该中心节点相关性及相关定义中定义的ILE算法将部分3。然后,在节4,我们现在ILE算法。此外,给出了实验结果和分析部分5。最后但并非最不重要,我们得出一个结论部分6。

2。相关工作

2.1。网络研究

自然世界可以抽象为一个复杂的网络,例如,生态网络与一个明确的劳动分工在蚁巢,学术论文的引文网络,神秘的神经网络在人类的大脑,和丰富多彩的公众舆论网络在互联网上。复杂网络是指网络结构有一定程度的复杂性或属性。网络自组织、自相似性、吸引子、小世界、无标度部分或完整的特征被称为复杂网络(9]。一般来说,大规模的复杂网络的特点,复杂的连接结构,复杂的节点,稀疏连接,复杂的时空演化过程,等等。对于许多复杂网络在现实世界中,我们只需要把实体在网络边缘节点和实体之间的关系。一个复杂的网络是一个工具用来探索复杂系统。这也是一个研究热点在图论的数学。通常是由整个网络图 ,在哪里代表了网络中节点图,代表的边缘,和两个节点集在集就对应于一个优势 。复杂网络的研究主要集中在结构分析的节点和边组成的图形。

2.2。重叠社区发现

由于社区检测算法用于复杂网络,提出了大量的算法。根据是否有重叠节点,他们可分为重叠社区发现算法和非重叠社区发现算法。一些代表不重叠的社区检测算法包括GN [1],CNM [5],LPA [13]。每个节点只能属于一个独立的社区,社区在网络未连接。随着社区检测的深入研究,人们还发现,这个社区结构显然不是常见的在现实世界中。这个艰难的部门不能真实反映实际的节点和社区之间的关系。

在现实世界中,许多社区在复杂网络不是孤立的,他们不断地沟通和重叠。就像自己的朋友、亲戚、和其他不同的关系,我们可以属于多个社交网络。一个人的标题可以教授,院长大学访问学者;即。,a person may have different attributes in different fields. When any node in the network belongs to two communities at the same time, it is shared by the two communities. These communities with shared nodes are called overlapping communities [14]。重叠社区发现更符合社区组织在现实世界的法则。近年来,它已成为一个新的社区检测研究的热点。出现了许多重叠社区发现算法。

提出的小团体渗透算法Palla et al。15)是第一个算法能够检测重叠社区。该算法认为社区是由一系列相互k-clique取得联系。它实现重叠社区发现通过合并相邻k-communities。节点的多个k-communities重叠的部分。Kumpula et al。16)进一步提出了一种快速小团体渗透算法(SCP),从而大大提高了集团的速度渗透算法。这些算法基于集团的理念渗透需要以小组为基本单位找到重叠部分。许多真实网络,特别是稀疏网络,可以找到一些重叠社区(17]。周et al。18)结合集团渗透检测算法和k - means算法,,然而,主要适用于稠密的网络。在标签传播算法,格里高利et al。19)提高了LPA算法并提出了干椰子肉算法。它允许每个节点存储多个标签通过标记列表;即。,each node can belong to a community at the same time. The SLPA algorithm proposed by Xie et al. [8)将标签满足阈值的频率划分为相应的社区通过多次迭代的节点标签。而基于分区的链接算法,埃文斯et al。20.)重叠社区部门变成分区使用边来表示节点的链接。它将基于节点社区检测算法来检测结构的链接。陈L-Attractor算法提出的et al。21)原始图变成一个链接图,引入了动态交互过程动态模拟距离。所有的距离通过动态交互过程收敛。不相交的社区结构出现在链接图转换为原始图像的重叠社区结构。

在当地扩张算法,Lancichinetti et al。6)提出了中频采样算法。它扩展了社区通过随机选择初始节点。迭代后形成一个社区,满足要求的阈值函数。外面随机选择新种子节点的社区,将他们根据上述方法。Coscia et al。7)提出了恶魔的算法。它选择网络中的所有节点作为初始节点和不断扩大的邻居在会议的前提下阈值。然后,类似的扩展社区合并获得最终的重叠社区。曹et al。22)意识到当地社区扩张通过最小化的导电值集群。如果集群的传导价值减少集群在一个给定的删除节点时,外面被集群和重复迭代,直到传导集群会达到一个稳定状态的价值。周et al。23)提出了一个当地社区检测算法基于最小集群。该算法选择之一初始节点随机和发现它的邻居节点。如果发现节点的邻居给初始节点,这三个构成最小的社区。尽管有许多研究在重叠社区发现到目前为止,现有的重叠社区发现算法的复杂性和准确性仍需改善。因此,有必要研究发现重叠社区(24]。

然而,使用当地的一个非常重要的一步扩张算法来检测社区是选择初始节点。当地扩展社区检测算法的准确性很大程度上取决于初始节点的质量。不同的社区检测算法基于局部扩展选种方案不同。中频采样算法以随机方式选择初始节点。它是简单和快速的开始。如果初始节点是一个边缘节点,大量的高度重叠社区和重叠节点将形成。随机选择的节点通常有一些不确定因素,所以每次结果不一致。它需要多次运行以获得更好的分割结果。恶魔算法中的初始节点是网络中的所有节点。在满足阈值的前提下,恶魔算法不断扩大种子周围的邻居节点。 It merges the communities with high similarity to obtain the final overlapping community. When the network scale is large, it will be very time-consuming to detect the largest complete subgraph in the network. In addition, when there are multiple edge nodes, it is easy to have highly overlapping communities.

在大多数地方扩张算法,初始节点的选择很大程度上决定了检测的重叠社区。有许多指标来评估节点的重要性。节点中心是代表早期指标之一。许多当地的扩张检测算法以节点中心为评价指标由于网络的中心节点可以稳定整个社区的结构;例如,王et al。25)提出了结构中心节点的概念,基于当地社区进行了扩张。高度精确但只能在较小的网络。学位中心节点中心的主要衡量标准。一般来说,网络中节点度越大,越高的中心节点。中间性中心措施的能力一个节点作为媒介。如果节点充当媒介更加频繁,其价值更大。亲密中心定义为节点的最短路径的长度到达网络中的其他节点。值越大,节点的重要性越高。此外,聚类系数是一种评估指标之间的连接节点和网络中相邻节点。是衡量计算三角形的数量的比例由实际网络中的节点三角形的数量预计将节点包围。 The larger the clustering coefficient, the closer the relationship between the node and its neighbors.

2.3。重叠社区进化

社交网络发展的主要目标是找到不同时间片的群落结构。我人们可以实时改变群落结构通过研究动态社会进化。根据分析现有社交网络的进化算法,它们可以分为相似性进化算法和基于节点核心的进化算法。

基于相似度算法的进化分析,相似性的社区相比,在相邻的时间片通常确定进化事件。杨et al。26]使用Jaccard系数计算的比值十字路口和社区联盟节点在两个相邻时间片,因为它可以更好地获得社区的相似性。Yu et al。27增加社区活动和影响Jaccard系数。基于三方决定,社区的法律进化是根据这三个参数。朱et al。28]提出了基于社区的概念属性Jaccard系数和重建每个事件根据社区属性。上面的进化分析算法是基于Jaccard系数或改进的相似性分析。他们未能考虑特定的拓扑网络,所以进化事件结果的准确性降低。

Bhat et al。29日)提出了density-based进化算法。该算法选择核心节点通过计算密度值。它观察相邻时间片的社区结构和基于日志的方式更新节点的属性。上述步骤进行迭代,直到形成一个完整的社区演化路径。Dhouiou et al。30.基于边缘节点)确定进化事件。他们发现的核心节点和边缘节点很少有在每一个社区。然后,他们把最边缘节点到现有核心社区。最后,他们观察到核心节点的变化来确定类别的进化事件。从最初的群落结构定义的组成员关系,卡兰等。31日]描述的时间演化过程从最初的群落结构与当前网络拓扑结构的强度和频率之间的互动社区成员和重叠的程度不同。Yu et al。32)提出了一个新的进化模型框架基于正交非负矩阵分解。框架的本质是假定遵循当地的社区结构进化模式(地蜡)在每一个快照。这些地方进化模式来自于共同的全球进化模式(GEP)。它可以同步检测颞群落结构,提取进化模式,并预测结构,包括未来的快照。王等人。33)提出了一种新的动态重叠社区演变跟踪方法。该方法检测峰谷结构的初始重叠社区结构的拓扑势场基于节点位置分析。它更新动态群落结构逐步和追踪社会进化事件基于核心节点的变化。通过分析现有进化算法的基于核心节点,它可以发现这些算法考虑全球网络的拓扑信息,有效改善当前社会进化结果的准确性。然而,这些算法的核心节点有不同的特征和类型的进化事件密切相关。挖掘不同核心节点的特点是必要的,以便更好地分析多个不同的进化事件的核心节点。

在分析动态网络的进化时,动态网络通常转化成静态网络。除了社区提取、社区发展评估标准的研究也是一个不可或缺的部分网络的动态演化分析,即。,研究社区之间的关系随着时间的特点,以确定是否有一个社区之间的进化。

最经典的评估标准Jaccard评估社区之间的相似性计算的比例共同节点和设置一个阈值。认为有一个进化关系社区相似度大于阈值时。相似的相似仍然基于Jaccard法官社区共享节点的比例,无论节点的重量。Gliwa et al。34]节点权值添加到第一次相似度公式。尽管节点的重要性考虑,可以选择任何节点的重要性来计算相似度。相似性将受到节点重要性的选择;例如,安娜et al。14)评估变化的群落相似性程度的节点重要性排名。一般来说,大多数研究没有考虑节点权重的相似度评价的影响。一些人认为节点重量和忽略节点权重计算方法。他们都有一个伟大的对社区发展的质量和准确性的影响评估结果。

3所示。预赛

3.1。中心节点相关性

大多数的指标来评估节点的中心节点为主要计量标准的程度。学位中心往往忽略了所选节点及其邻居之间的关系。亲密中心和中间性中心不能用于大规模网络因为全球网络拓扑结构的信息。虽然聚类系数考虑节点之间的连接关系,它只考虑直接连接。因此,在某些网络初始节点选择的影响不明显。

我们认为,一个节点中心的评价指标是容易高重叠的当地社区。为了确保网络的中心节点,我们考虑节点与邻接信息事业的重要性,即。节点本身的重要性,邻居节点的数量,和邻居之间的联系。提出的公式如下: 在哪里和节点的邻居节点吗 ; 代表了边缘连接的节点和节点 ;函数的 , 是你的邻居节点的 。它代表了最大数量的邻居节点的路径可以到达的节点 ,不包括你的邻居节点 。 节点的度 。 表示节点的重要性 。如果节点是更重要的是,更大的价值。重要性评分的节点相当于公式(1),定义如下: 和的邻居集吗和 ,分别。

该中心节点相关性避免上述评价指标的问题。我们的指标考虑网络拓扑的本地信息。计算大大减少在一个大型网络。特别是一些节点是许多邻居,但是邻居们没有其他连接,中心节点相关性值为0。

3.2。相似度评价

目前,相似性方法用于比较的相似社区之前和之后的时间片(35]。尽管社区的整体结构可以比较简单、快速,结果的准确性难以保证由于缺少考虑网络的拓扑结构。魏et al。36]介绍了顶点比较策略。这个方法只考虑社区的核心节点的变化。这并不能解释核心顶点的选择策略的考虑,缺乏整体的进化。Brodka et al。37]给出一个更合理的组织进化检测算法(GED)。公差变化指标提出了动态平衡和转换节点的数量和重要性。格定义社区发展全面的事件分类。然而,对社区的规模是敏感,尤其是对一些规模较小的网络。尽管Magnien et al。38)结合节点的相似性评价公式的重要性,仍然存在一些问题。

给节点质量,万有引力的概念(12引入复杂网络。与更大的影响力通常可以影响他们的邻居节点链接。本文中定义的链接引力系数代表网络中链接的影响。链接的重力系数越大,越多的节点核心区域。它的影响力越大,越会吸引你的邻居节点的节点链接加入社区链接。鉴于网络的任何链接,链接重力系数如下: 在哪里的数量是 多边形与节点链接上 。分母是最低程度的节点在链接 。添加1分子是防止的数量 - - - - - -多边形上的链接从0。

核心节点的重力链公式如下: 在哪里是核心节点的程度。

考虑到全球网络社区,我们结合不同测量社会进化的上部和更低的时间片。不同的公式如下: 在哪里社区之间的节点重要性的区别是相邻的时间片。安娜et al。14)的平方 。结果可以达到的最低和最大可以达到 。数据分布不均,导致正常化后缺乏良好的社会分工。上述不同公式结合核心节点的节点变化范围重力链,共同评估社区的演化趋势。如果差异较大,社区在时间片更多的不同时间片吗 。 平均节点重要性。分母是常见的节点的数量。分母是工会的节点(14]。如果节点存在在最后时间和下次消失,不同的节点不能计算。函数用于规范化公式。它可以避免阈值选择的标准问题。通常,数据归一化的值范围 。

社区发展分析主要完成两个任务:第一,是否有社区之间的进化;第二,什么是进化的类型。我们提出一个社区进化算法基于上述相似性评价方法。提出的算法使用选择的核心节点节点相关中心构建核心节点重力链。根据重力链的变化,我们观察社会的进化的完整性。不同评估社区的进化节点核心节点重力外链。因此,我们分析社区的聚合行为,建立一个新的进化分析模型。算法弥补了这个缺陷,GED算法对社区规模十分敏感。它是更一般的数据选择和我可以不同时间片的类型的进化事件。基于事件的重叠社区进化模型如下:形成:一些无关的节点在网络中形成一个社区由于越来越多的接触。任何社区之间的相似性和社区满足以下几点: 持续:重力链的核心节点的社区不是断开的时间吗 ,在接下来的时间窗口和社区继续当且仅当社区存在并满足以下: 增长:重力链的核心节点的社区不是断开的时间吗 ,和社区的大小大于,在时间当且仅当社区存在并满足以下: 萎缩:重力链上的节点在社区的核心节点减少时间 ,但社区作为一个整体仍处于持续状态当且仅当社区存在并满足以下: 分裂:重力链的核心节点的社区坏了时 ;当且仅当有多个(大于或等于2)社区 在时间 , 满足以下几点: 合并:有多个重力链的核心节点在社区在时间 。当且仅当多个(大于或等于2)社区 存在的时间 , 满足以下几点: 溶解:社区消失的时间 只有在任何社区当时 不存在满足以下:

3.3。相关的概念

复杂网络的深入研究,发现社区发现的问题主要集中在有限的信息未经授权的和无向网络。我如何更有价值的信息吗?如何定义社会后更准确地获取丰富的信息和正确分配节点相应的社区?以下主要介绍了结构信息的概念,社区边界,和属性中提到的相关重叠社区发现算法。

定义1。(社区的邻居集)。社区的邻居集是一个组合节点直接连接的边与社区C。 在哪里代表一个社区和代表你的邻居节点集 。

定义2 (Jaccard系数(39])。Jaccard系数两个节点之间的定义如下: Jaccard系数可以用来测量节点之间的亲密关系。的啤酒 ,更类似的两个节点。

定义3。(节点和社区相似)。节点之间的相似性和社区定义如下: 在哪里是指直接连接的节点集边缘与社区 。 反映了节点之间的相似程度和社区 。值越大,越高的节点和社区之间的相似性。

定义4。(社区相似)。 社区之间的相似之处吗和社区 : 更大的价值 是,社区之间的相似性越大和社区将。这两个社区将合并是否满足一定的阈值范围。

定义5(聚类系数(40])。聚类系数在社区代表社区之间的关系。这是定义如下: 在哪里表示节点在社区的数量和是实际数量的边缘。社区之间的聚类系数是类似于复杂网络聚类特征。它等于边的实际数量比边缘社区的理论最大数量 。

定义6(自适应函数(41])。自适应适应度函数节点在社区的紧密性措施。具体的公式定义如下: 在哪里和代表节点度的总和在社区和社区外的节点度的总和,分别。的参数控件的大小社区,在那里 。的价值就越大 ,在社区密实度越高节点之间。

定义7。(转移概率矩阵)。网络的节点矩阵由节点的重要性加权,加权邻接矩阵规范化的行向量作为一步转移概率矩阵的随机游走策略。其表达式如下: 在哪里代表节点的重要性;代表了转移概率;和代表了全球网络。

定义8。(节点概率分布)。假设 - - - - - -一步到达概率分布 。 代表一个代理从节点的概率到节点后 - - - - - -步传输。它可以表达的迭代方程如下:

定义9。(平均概率)。的平均概率本文将采用所有节点的节点和大于成同一个社区。

定义10。(稳定42])。稳定公式基于Jaccard主要计算并比较常见的节点及其相邻的两个社区的时间窗。的定义如下: 在哪里和在不同的时间对应于社区的数量。重叠节点也由这个公式表示。

11(模块化定义43])。重叠社区模块化函数是一个扩展功能的模块化功能。计算公式如下: 社区哪个节点的数量在哪里和节点是由和 。 和代表节点的度和节点 。 是网络的邻接矩阵。代表社区检测的结果的质量。更大的价值,更好的社区检测的结果。

12(归一化互信息定义44])。归一化互信息计算真正的网络和社会结构之间的相似性检测到的重叠社区发现算法。假设社区和社区在网络检测的结果,混合矩阵存储节点的数目分为社区在和社区在同时: 在哪里表示网络中节点的数量;代表所有节点元素的和连续的矩阵,即。节点的数量分为社区在 ; 代表社区的数量网络;和节点数量由社区吗和联合。的值范围 是在0和1之间。值越大,相似性越高发现真正的网络和社会结构。

4所示。算法

当地的重叠社区检测算法基于节点重要性和邻接信息主要包括四个阶段:(1)种子社区检测;(2)合并相似的种子社区;(3)社区扩张;(4)社区优化。种子社区的检测主要是通过计算每个节点的影响力分数据该中心节点相关性和选择核心种子节点根据邻接信息。然后,它形成一个社区种子与邻居节点结构。社区的扩张阶段,它选择的节点相似度高的社区,可以优化自适应函数加入社区。上述四个阶段后,可以实现整个网络的检测。因为每个种子社区扩展了其独立的邻居集,重叠结构网络中可以找到。

4.1。种子社区检测

第一步是计算所有节点和存储节点重要性的重要性计算公式(1)的设置 。然后,它计算的数字每个节点的得分大于其邻居节点和数量的邻居。节点被添加到集合如果的比率来大于阈值 。这类节点的重要性按照降序排列并选择第一个节点作为初始核心节点。在本地核心节点扩展的随机漫步。初始的建设核心社区完成(算法1)。

4.2。类似的种子社区合并

通过检测种子,种子社区可能会非常相似。他们需要合并种子扩张阶段,以避免不必要的计算。相似之处 社区之间根据定义计算4。种子社区将合并获得更加稳定和紧凑的种子社区如果 大于阈值(算法2)。

4.3。社区发展

在得到一个稳定的种子社区,一步是扩大获得邻居集种子社区首先。它计算相似度每个邻居节点之间 和社区在定义中使用的公式1。然后,它选择的节点相似度大于阈值作为候选节点。计算这些候选节点的适应度函数在加入当地社区。候选节点可以增加适应度函数的值被添加到社区;否则,他们将被视为自由网络中的节点。社区中的节点的适应度函数增量是-删除。最后,它更新继续重复以上步骤,直到是(算法3)。

4.4。社区优化

社区需要优化;即。,the free nodes are allocated to the community or allowed to form a community independently and communities with higher similarity are merged. The optimization is mainly divided into two steps: the first step is to calculate the similarity节点的每个社区。如果该节点被添加到社区大于阈值 ;否则,它形成一个独立的社区。第二步是计算相似度在社区之间。合并的社区大于阈值 。

4.5。社会进化

自部门时间窗的质量直接影响社区提取,分割的结果为后续的分析尤为重要。时间通常是一年或几个月。没有指标评估什么样的选择是最优的。我们选择部分重叠相邻时间窗的社会网络数据,通常重叠50% (45]。它确保相邻时间窗的网络拓扑相似性是大大增加和提取的进化事件也增加。进化评价方法提高了本文用于判断进化结果(算法4)。

5。实验结果和分析

在本节中,几个实验被用来分析和验证了该算法的有效性。合成网络和真实网络数据集的数据集。ILE算法的有效性,分析了模块化( )和标准互信息( )。在合成网络数据集,本文设置网络参数,比较了线性调频,SLPA,恶魔和L-Attractor重叠社区发现算法。我们分析ILE算法的性能和效率。在现实网络中,我们选择不同的阈值参数来观察社会的变化检测结果。我们比较上述四个算法来分析该ILE算法。为了验证提出的进化算法的有效性,本文使用DBLP和安然的数据集,选择当前代表社区进化算法进行比较分析。实验表明,ILE算法及其进化算法具有良好的性能,可以得到良好的社区检测的结果和演化的结果。

5.1。检测网络上合成

大多数网络都没有自然社区检测规模实际的场景。很多学者使用合成人工网络的数据来验证算法。在本文中,我们使用LFR [6网络因为其参数设置条件更符合真实的网络应用场景和更适合该算法的实验分析。探测器参数的含义如表所示1。

代表网络中混合参数。它的比例可以调整边缘团体内部的节点和节点之间的连接以外的社区。范围一般是在0和1之间。网络社区结构越明显,越小。

考虑到中频采样算法随机选择初始节点,本文得到三个不同的合成数据集根据人工网络的参数设置,如表所示2。

对于不同的混合参数D1数据集,观察社区各种算法的检测结果,重叠的模块化每个算法如图1。

从图可以看出1,SLPA L-Attractor混合参数时取得了不错的效果很小。SLPA大幅减少的总体性能 。ILE算法是最好的时候 。ILE算法的稳定性的增加变得越来越突出 。这表明我们的算法具有良好的适应性更复杂的网络。中频采样算法初始节点随机选择时是最严重的。恶魔算法扩展所有网络节点作为初始节点,很容易形成多个独立社区,导致低精度。

只有当社区不同的重叠节点所属变化对D2数据集,一个复合网络生成与七重叠社区结构。重叠模块化每个算法如图2。

作为增加,模块化ILE和线性调频稳步下降。SLPA最好当社区的数量等于2。稳定时的ILE算法的优点 。它更适合复杂的拓扑网络。这是因为ILE算法使用随机游走模型初始化核心社区,不会陷入局部优化。线性调频和L-Attractor显示稳定在某种程度上。他们不是那么有效ILE算法。恶魔算法的表现不佳的原因是,它检测到许多独立社区。

通过改变网络节点的数量在D3数据集,算法的运行速度ILE不同规模数据集验证。在这篇文章中,实验分析是根据每50000个节点的时间间隔进行。各种算法的运行时间比较图所示3。

我们发现基于标签传播SLPA算法时间效率最高。提出ILE算法增加了节点重要性的判断和社区在社区种子相似性阈值选择和扩张。时间效率也显著提高。恶魔是敏感数据集的大小。尺寸越大,影响越严重。恶魔的时间效率是最低的。中频采样算法随机选择初始节点和整个网络扩大。这是相当耗时。L-Attractor算法进行了链接图的转换计算两次,所以时间开销很大。

除了上述之外,我们比较不同的阈值参数 。的ILE算法不同参数获得在D1人工合成网络。结果如图所示4。

阈值参数确定初始节点的选择;即。,it adjusts the ratio of the number节点的重要性大于邻居节点总数的重要性的邻居节点。的值范围在哪里是(0,1),参数的变化范围是(0,1)。观察的价值 ,它可以发现,尽管参数是不同的,性能是大致相同的。它表明,参数的选择几乎没有影响的结果ILE算法。结果是非常贫穷的价值= 1。我们可以发现它是不容易找到合适的初始节点的选择很大。这导致质量下降的种子节点,进一步降低算法的准确性。

5.2。检测网络上真正的

在现实网络中,空手道公共数据集被选中来验证ILE算法的有效性。空手道空手道跆拳道俱乐部的网络数据集。78数据包括34个节点和边。节点代表俱乐部的成员,边代表了每个成员之间的朋友关系。空手道的数据集,我们选择不同的阈值并观察数据的变化检测结果。ILE算法的结果如图所示5。

在图5,颜色除了绿色代表重叠节点。和图5(模拟)表示下的检测结果 分别为0.2、0.5、0.9和0.7。通过比较不同的参数 ,可以看出ILE算法的结果非常类似于空手道时的实际结果 。ILE检测三个重叠社区节点、节点1和节点节点9日31日。当= 0.2,0.5,和0.9,分别发现不同的阈值对空手道社区的整体结构几乎没有影响检测,但也有伟大的重叠节点的选择上的差异。它还表明,拟议的ILE算法网络结构本身具有一定的稳定性。由于不同的阈值 ,初始节点的质量是不同的,最后,重叠节点后社区检测是不同的。

模块化ILE算法,从算法,SLPA算法,恶魔算法,L-Attractor算法运行在一个真正的网络如表所示3。

从模块化的角度 ,恶魔和线性调频表现不佳。在一些网络、SLPA和L-Attractor取得了良好的效果。在大多数情况下,ILE本文算法取得了良好的效果。这表明ILE算法可以正确的节点划分为相应的社区。中频采样的性能不是很好。它随机选择的节点作为种子节点,结果每次都是不同的,导致找不到足够的完整的子图覆盖整个网络。

的不同的算法在不同的数据集如图6。

我们可以看到ILE算法略低于SLPA算法在足球的数据集,但其他真实网络数据集上的性能稳定。这表明ILE算法对整个社区有良好的检测效果,可以有效地发现真实网络的社区结构,将选择的高质量的初始节点节点相关性中心。

5.3。进化的结果

本文分析了复杂网络的社区结构和特点,并进行预处理DBLP和安然的数据集来验证提出的进化算法。DBLP数据集的数据包括497014件,代表不同的文章的作者之间的引用关系。实验数据从2001年到2010年,分为十个时间片快照。每一次快照是设置为1年。安然数据集描述了安然公司员工信息交换的数据。2001年全年的数据选择,其中包括2359员工节点和136876电子邮件。此外,它分为12个月的时间片。

ILE算法检测在不同的网络社区结构。DBLP数据集,快照的时间间隔设置为1年10快照。不同时间的检测结果快照如图7。为安然公司数据集,快照的时间间隔设置为1月12快照。不同时间的检测结果快照如图8。

图7记录DBLP网络社区发现的数量从2001年到2010年。它可以发现社区的数量会随着时间而改变。社区的数量显示在2010年之前上升趋势。

对于安然的数据集,我们选择相邻的时间片的重叠数据和设置数据重叠社区考虑到相对较小的数据量的50%。我们可以看到在图8,社区的数量显示不确定随时间动态变化。

在本文的进化算法,最优参数 , ,和多次获得通过选择不同的参数,分析实验结果。

它可以看到从图9,等事件的数量持续增加,减少,合并,溶解时小条件严格,即。,当是小,比较大。这是因为和成反比,当设置条件的演化模型。减少事件不能检测,检测到的数量增长,合并,分裂,和其他活动减少线性超过0.2。在这个实验中,和将0.2和设置为0.3,增加了0.1吗 。设置最优。进化事件的类型和数量检测到该算法是最好的。像安然公司网络,最优参数DBLP网络0.3,0.2,和0.4,分别。图10显示了社区的趋势演化时间随着时间的推移DBLP网络。

可以看出,越来越多的事件逐渐减少,溶解事件随时间逐渐增加。经过多年的收集DBLP数据,分离和新成员已经达到一个相对稳定的状态。各种进化事件的频率呈现出稳定的趋势。也可以发现事件的萎缩和不断增长的算法检测到的高频,哪个更符合实际的现象。

提出的进化算法相比,GED (37],MODEC [46],Tajeuna [47]。安然公司的数据集上的实验结果如表所示4。

通过比较结果,发现格算法不能检测到事件和溶解形成事件。原因是安然数据集相对较小,所以得不能提取每个进化事件。Tajeuna算法可以检测各种进化事件作为一个整体,但很少分裂事件被检测到。此外,MODEC算法检测太少持续事件。与上面的算法相比,我们的算法检测到更少的持续活动。这是因为我们设置阈值条件的事件要大于90%的速度增长,所以持续的检测条件,成长和萎缩的事件完全不相交。这是一个严酷的条件,但这阈值设定与实际数据匹配。一般来说,进化检测模型本文提出可以提取各种进化事件,它有一个更好的社会进化的检测能力。

6。结论

在这篇文章中,一个重叠社区发现算法(ILE)及其进化算法提出了在移动网络的机会。基于节点关联中心和地方扩张,它可以检测到网络的社区结构。首先,计算每个节点的影响力得分,发现网络中最具影响力的节点为核心的种子。然后,它形成一个社区种子及其邻国紧密相连。其次,它合并类似种子社区减少计数和计算节点之间的相似性在邻居的种子集社区和社区。第三,它使用适应度函数来扩展社区。最后,优化社区通过添加节点不属于任何社区网络中的社区相似度最高的和合并社区提高社区的质量检测。与其他算法相比,在真正的和人工数据集,该算法可以准确地检测重叠节点同时具有近似线性时间复杂度,可以发现重叠社区有效和稳定。

数据可用性

支持本研究使用的数据集是获得http://snap.stanford.edu/data/。

的利益冲突

作者宣称没有利益冲突有关这篇文章的出版。

确认

这项工作是支持部分由中国国家自然科学基金(号,61 772 096 61 876 201,61 876 027)和重庆部分由国家自然科学基金(没有。cstc2019jcyj-cxttX0002)。