时变社交网络中的社团结构：特征、挑战和最新方法综述【沙特国王大学】

制作和主办：Elsevier沙特国王大学学报时变社交网络中社团结构检测研究综述Norah Alotaibia，Mr.，Delel Rhoumab，caMajmaah大学计算机和信息科学学院信息技术系，Al-Majmaah 11952，沙特阿拉伯b沙特阿拉伯，Buraydah，Qassim大学计算机学院计算机科学系c突尼斯苏斯大学MARS研究实验室LR17ES05阿提奇莱因福奥文章历史记录：收到2021年2021年7月24日修订2021年8月16日接受2021年8月27日网上发售保留字：社区检测动态社交网络社交网络分析A B S T R A C T近年来，社交网络的使用广泛增加。在这些网络中，人们倾向于基于相似的兴趣形成群体。这些群体被称为社区或集群。检测这种结构使我们对社交网络的组织和功能有了非凡的理解这个问题被放大了，因为网络在发展，所以它们的结构也在变化。本调查突出了动态社交网络中社区检测问题的特征和挑战，由这种演变所驱动。我们的论文在技术上研究和比较了最先进的方法。由于网络模型的定义和问题的形成，这一调查将有助于研究人员找到最佳方法并选择相关的未来方向。版权所有©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。内容1.导言56472.社交网络56472.1.社交网络的定义2.2.社交网络的表示2.3.社交网络属性56482.3.1.“小世界”的影响...........................................................................................................................................................................................................................2.3.2.幂律分布度56482.3.3.社区结构56483.基本概念和基本知识56493.1.中心性措施56493.1.1.聚类系数56493.1.2.度中心56493.1.3.Betweenness中心性56493.1.4.接近中心56493.2.评价标准56493.2.1.模块化56493.2.2.标准化互信息（NMI）56494.静态网络中的社区检测4.1.分层方法56504.1.1.凝聚法5650*通讯作者。电子邮件地址：norah. mu.edu.sa（N。Alotaibi），d. qu.edu.sa（D. Rhouma）。沙特国王大学负责同行审查https://doi.org/10.1016/j.jksuci.2021.08.0161319-1578/©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comN. Alotaibi和D. 鲁马沙特国王大学学报56474.1.2.分裂的方法56505.动态网络中的社区检测5.1.动态网络56505.2.社区活动56506.动态社区检测主流方法的分类56506.1.网络快照56526.1.1.独立社区检测56526.1.2.依赖社区检测56536.2.时间网络56546.2.1.分离的社区56556.2.2.重叠社区56567.对比56578.挑战与未来发展方向5668.1.挑战56608.2.未来的方向56609.结论5660竞争利益声明确认5660参考文献56601. 介绍在过去的几年中，社交网络领域已经得到了研究界的极大关注。网络的一个例子是在线社交网络，如LinkedIn或Facebook。每个人都使用他/她的社交网络账户来维护、加强和建立与社会中其他人的关系。这种关系引起了科学家的注意和兴趣，他们开发了所谓的社会网络分析（SNA）。SNA被描述为研究和理解社交网络中两个或多个个体之间的关系/联系（Rhouma和Romdhane，2018）。SNA提供了一套工具和方法来直观地分析社会网络关系（Maivizhi等人，2016年; Rhouma和Romdhane，2018年）。这些关系是社会网络社区的构建结构。根据Santo Quinato（Quinato，2010），社区可以被描述为一组可能在网络中共享或执行类似责任的个人。通过使用各种为此目的而设计的检测方法来识别社区。社区检测有助于理解社会结构并暴露关于网络内用户的信息（Alvari等人，2014; Aston和Hu，2014）。检测社区可以用于各种领域，例如，生物学，社会学，甚至市场营销。当公司能够为客户提供适当和有效的推荐系统时，它有助于增强行业。有着相似兴趣的人组成了社区。在本文中，我们将使用系统性文献综述（SLR）方法学（Mengist等人，2020）研究社交网络中社区检测的基本概念。此外，我们还研究了几种用于识别和检测动态社交网络中社区的方法，以及该研究领域面临的挑战论文的其余部分组织如下：第二部分简要概述了社交网络。第三部分介绍了在社交网络中发现社区的关键概念和度量。第四部分介绍了静态社交网络中的传统社区检测方法。第五部分介绍了动态网络社区发现的基本概念。下一节研究了在动态社交网络中检测社区的各种方法。下一节将介绍不同模型的技术比较。第八节讨论了在动态社交网络中检测社区的挑战。第九节是论文的结论。2. 社交网络社交网络已经成为我们日常生活中非常重要和无处不在的一部分。“社交网络”这个词术语“在线服务”通常用于指与社交和工作交互情况的一般类别相关联的不同在线服务。什么是社交网络，它是如何表现的？它的特点和性质是什么？本节试图回答所有这些问题。2.1. 社交网络社交网络被定义为能够在用户之间进行通信和交互它们也可以被看作是一组相互作用的实体网络链接，代表允许多路通信的各种关系，社交网络帮助用户以文本、视频、图像等方式相互交流。2.2. 社交网络两种方法经常用于社交网络表示（Aston和Hu，2014）。第一种方法是图形表示法。图形成为科学家们用来分析社交网络的一种表示方法。个体由节点或顶点表示，而它们的关系称为边或链接。图1示出了图形表示方法。图1.一、一个简单网络的图形表示包含7个通过边相互连接的节点N. Alotaibi和D. 鲁马沙特国王大学学报5648ð Þ~第二种表示方法是邻接矩阵。在该方法中，连接和断开的节点分别由1和0表示，如表1所示。表1邻接矩阵节点123456710110001210100003110010140000100500110106000010171010010不同类型的图可以表示网络，我们将在下面更详细地解释：简单图：图1展示了一个简单的图，它有有限数量的节点和间接关系。有向图：网络中个体之间的交互和关系可以是有向的，也可以是无向的，如图2所示。例如，用户之间的关系在Twitter上被认为是一种直接的关系，而Facebook图二.直接和间接网络。是非定向的，因为Facebook的友谊是双向的。为了理解有向图中的整个系统，我们必须考虑它的方向。加权图：在相同的上下文中，关系可以是加权的，也可以是非加权的。如果与数值相关联，则图中的边可以被加权。非加权关系与值无关。加权关系和非加权关系需要不同的方法;然而，一些方法被开发来同时处理这两种关系。图3示出了加权图的思想。图三. 加权网络，其中每条边都关联一个数值.2.3. 社交网络属性对社交网络的研究表明，它们具有共同的性质，如2.3.1. “小世界”的影响1967年，（Milgram，1967）提出了一个假设，即每个人都通过一条短的社会关系链与任何个人联系在一起。作为对这一“六度分离”规则的检验，表明两个用户之间的路径的平均长度是6。这条规则证明了这样一个观点，即个人可以通过共享知识直接或间接地相互了解。这种现象看起来当然是正确的，因为对图上参数的统计表明，大多数社交网络的直径相对较小。直径被定义为所有可能的最短路径中的最长距离2.3.2. 幂律分布度在社交网络中，有许多低度节点和很少的高度节点。 实际上，节点的分布遵循幂律p k kexpc，其中k是度，c是幂律的指数。实际上，这个指数在2和3之间，代表度曲线的下降率。c越大，得到高度数顶点的概率越小.2.3.3. 群落结构在网络中，人们更容易根据共同的兴趣、背景、爱好等形成群体，这种群体被称为社区或集群，它被定义为一组内部链接多于外部链接的密集节点。人们认识的社区内的人比社区外的人多（图4）。同样，在他们的文章中，Djerbi等人。（2018）将社区定义为一个群体，其中个人围绕共同利益分组，群体内的关系比群体外的关系更重要。另一方面，Santo Paganato在他的文章（Paganato，2010）中表示，“社区”一词没有广泛认同的含义。此外，这些社区的检测和发现过程被称为社区检测。见图4。 社会网络上的社区结构。网络中的社区可以是分离的，也可以是重叠的：不相交社区：不相交社区中的节点然而，这种现象在真实的网络中是看不到的。●●●●N. Alotaibi和D. 鲁马沙特国王大学学报5649Xv.Σ我000rst在C. 哪里tot表示链接的权重之和在C中的节点的事件。重叠社区：在讨论真实网络时，我们注意到某些节点可能属于多个组或社区，如图所示。 五、在这种情况下，我们将有所谓的重叠社区（蓝色提到的节点是重叠节点）。节点计数（Perez和Germon，2016）。高度集中的节点在网络中的其他节点之间传输信息方面发挥着重要作用。介数中心性可以计算如下（Anthonisse，1971; Linton，1977）：BC省省州市Xrst省州市s;tvð2Þ图五. 重叠社区的网络结构。3. 基本概念和术语在本节中，我们将介绍结构中心性的一些测量方法。此外，我们将提出一些测量来评估所提出的社交网络中的社区检测方法的性能（Mrsato，2010）。其中rstv表示通过v的最短路径的数量，并且Rst表示s和t之间的最短路径的数目。3.1.4.接近中心性一个节点的接近中心性由它对网络中所有其他节点的接近度决定因为它可以访问整个网络，所以中心节点被认为是最重要的节点（Golbeck和Golbeck，2013）。它将通过取网络中每个节点之间的最短路径长度的平均值来确定接近中心度可以计算如下（Metcalf和Casey，2016）：3.1. 中心性措施C1wsGdv;wð3Þ每个节点都有自己的重要性和属性。为了确定节点的重要性，提出了结构中心性的各种度量方法中心性度量旨在评估社交网络实体通常抽象的3.1.1. 聚类系数聚类系数决定了一个节点的邻居之间的联系有多紧密。这取决于“我所有的朋友都互相认识”的性质。它被计算为（邻居之间的连接数）/（可能连接的总数）（Hansen等人， 2020年）。3.1.2. 程度中心性确定中心性的最基本的技术之一是程度。连接到一个节点的邻居的数量决定了它的程度。度越高，节点越重要一个具有高接近中心性的节点意味着它与许多节点有紧密的链接。3.2. 评价标准我们有一些测量在我们的处置，以评估方法的性能。最常见的方法是模块化和归一化互信息（NMI）。3.2.1. 模块化模块化度量了社区内的连接密度与社区之间根据网络的类型，它以正如Khan和Niazi（2017）所报告的那样，模块化被认为是最常用的方法之一。Newman（2004）首先定义如下：顶点i的中心度可以计算为：1倍。k i k j。ΣIJLows（Srinivasan等人， 2020年）：XAijQ¼2mAij-2mdci;cjð4ÞDði Þ¼Jn-1ð1Þ其中ki和kj表示顶点i和j的度哪里c i;c j表示顶点i和j所属的社区。的其中Aij表示邻接矩阵A的第ij个元素，并且n表示节点的数量。如图6所示，绿色节点被认为是重要节点，因为它具有最大程度的中心性。函数dc i;c j如果两个顶点ij属于同一个顶点，社区（i = j）。此外，Blondel等人（2008）对模块化的定义如下：2Xin 200万美元i;in.Xtot快！232Xin. Xtot！.2002年2月3日第四季度2m-2m5-42m-2m-2个月5ð5Þ其中，中的PP表示链接的权重之和见图6。 度中心性;绿色节点的节点度为5。3.1.3.中介中心性介数中心性决定了哪个节点在网络中充当桥梁。通过的最短路径的数量3.2.2. 归一化互信息（NMI）归一化互信息（NMI）被认为是最常用的度量方法之一. NMI用于测量两个分区C和C（真实社区结构和由社区检测算法检测到的社区结构）之间的差异。它的定义如下（Ratanato和Barthelemy，2007年）：●2N. Alotaibi和D. 鲁马沙特国王大学学报5650ja j jbj. jjjajlogXn-2 P Xja\bj log.ja\bj每次迭代，类似的社区被合并成更大的社区（Hartigan，2001）。NMIA类;B类a2AB2BanXb2Bjbjlog.jbjð6Þ4.1.2.分割方法其中A和B表示同一图的两个不同分区。4. 静态网络检测社交网络中的社区有助于发现网络的结构。此外，可视化为理解和分析数据提供了宝贵的帮助。在早期的研究中，大多数提出的社会网络方法都考虑了网络作为一个单一的聚合网络。在这里，在一段时间内观察到的实体之间的所有交互被组合起来，形成所谓的静态网络（图8）。已经提出了几种方法来检测静态社交网络中的社区。此外，还提出了对这些方法的若干修订。在2010年，当Raviato（2010）提出一项关于图中社区检测的调查时，他提到了50多种不同的方法。此外，Xie等人（2013）进行了其他调查，比较了10种方法。表2总结了一些最好的已知方法。在2021年的一项重大进展中，Agenda（2021）提出了一种基于用户交互来检测社区的新方法。在他们的方法中，他们遵循四个步骤来发现社区。首先，他们分析和评估网络，以收集有关节点和边缘的信息然后，他们审查并将数据集中的数值转换为分类值，并将网络交互转换为事务数据集。关联规则（ARL）是使用上一步中的事务数据集一旦这些规则被定义，他们就会过滤它们并删除任何冗余。然后，他们根据先前创建的规则提取社交网络的节点或用户，即，他们提取了所有可能的组合的所有可能的社区。与许多其他算法相比，该算法检测到网络中所有可能的社区。4.1. 分层方法分层方法使用树状结构对数据进行分组。有两种主要的方法：聚集和分裂的方法（图。 7）。见图7。用于聚类的齿廓图（Erman等人， 2015年）。4.1.1. 凝聚法凝聚方法考虑自下而上的方法。在这种方法中，每个节点最初形成自己的社区。与分裂方法考虑自上而下的方法。不像凝聚方法，该方法从包含大量节点的大社区开始，然后在每次迭代中分成更小的社区。当最终社区包括信号节点或满足用户的条件时，该过程停止5. 动态网络直到最近，社交网络的动态在社区的检测期间没有被考虑，这是由于难以研究其动态。已经开发了几种社区检测方法，主要用于没有变化的静态网络。近年来，人们对动态社区的检测越来越感兴趣在这一节中，我们介绍了动态社交网络的定义和不同的社区操作。5.1. 动态网络人们不断地加入和离开网络，因为个人的变化趋势。例如，每天都有新用户在Facebook上注册，许多其他用户同时删除或禁用他们的帐户。在LinkedIn中，用户可以与网络中的其他人连接或断开连接。这一事实创造了所谓的动态社会网络。因此，网络不断发展。如前所述，大多数提出的社会网络方法都将网络视为一个单一的聚合网络。然而，在这种类型的方法中，这种相互作用的时间性质将被忽略，因为这些相互作用将继续改变。在这种类型的动态网络中，相互作用将被视为一系列静态网络。图8示出了这两种类型的网络模型之间的区别5.2. 社区运营社区的演变是一系列事件（在连续的时间步骤中成功的变化）。9）。以下是研究中提到的一些最常见的事件：1. 出生/死亡：当一个新的社区从网络中出现或消失时。2. 增长/收缩：当一个现有的社区获得一些新的个体或失去一些个体时。3. 合并：当网络中的几个社区一起形成一个新的社区时4. 分裂：当一个社区分裂成更小的社区时。6. 动态社区检测由于人们对社区检测的兴趣越来越大，许多关于社区检测的研究已经发表。在他们的影响社区检测研究中，Khan和Niazi（2017）使用CiteSpace，这是一个Java应用程序，用于可视化研究文献趋势和模式，以跟踪网络社区检测领域的进展。在他们的研究中，他们专注于识别和研究具有高引用率的研究人员和期刊，以及在该领域出版物最多的国家。N. Alotaibi和D. 鲁马沙特国王大学学报5651见图8。 网络模型。表2静态网络中的社区发现方法。作者年方法时间复杂度代码可用性03 The Dog（2000）2000MCLo（nk2）http：www.micans.org/mcl/sourceGirvan和Newman2001GN算法o（n3）https://github.com/kjahan/community（2002年）03 The Dog（2004）凝聚法o（m：n）http://web.ist.utl.pt/aplf/code/gcf-003.htmlPalla等人（2005年），2005年团渗流法（CPM）o（exp（n））http://igraph.wikidot.com/community-detection-in-rBlondel et al. （2008年）Louvain方法o（m）https://perso.uclouvain.be/vincent.blondel/research/louvain.htmlXie等人（2011年）2012年说话人/听者标签传播算法（SLPA）o（Tm）https://sites.google.com/site/communitydetectionslpa/见图9。 动态网络中社区的演化。N. Alotaibi和D. 鲁马沙特国王大学学报5652jCjjC0jMohamed等人（2019）在他们对复杂网络中社区检测文献的调查中指出，大多数研究都集中在静态的非定向网络上，而忽略了动态定向网络，因为涉及到的困难和复杂性。实际上，复杂的现实世界网络是动态的，这有助于创建一种更有效的方法来解决动态社区检测问题。在2021年的一项重大进展中，Souravlas et al. （2021）将动态社会网络中社区检测的可用方法分为三种方法。第一种是自下而上的方法，每个节点最初被认为是一个单独的社区，然后这些社区合并成一个新的更大的社区。这种类型的方法可以用不同的策略来实现作者用三种策略区分它们，模块化优化，团渗透和标签传播。第二种方法是自上而下的方法，社区和子社区是通过划分整个网络来创建的。大多数文献使用这种技术的主要问题，如Souravlas等人。（2021）指出，算法的复杂性很高。最后一种方法是数据结构方法，其中方法使用基于数据结构的算法。以这样方法中，从网络中形成某种类型的数据结构，随后对其进行检查以检测社区。将它们与之前快照中发现的社区进行匹配（图 11）。Hopcroft等人（2004）介绍了使用静态网络快照跟踪社区变化的首批研究之一。首先，他们使用层次凝聚聚类来检测社区。CiteSeer数据集中的每篇论文将被视为一个单独的聚类。然后在每次迭代中将两个最近的聚类组合，直到所有的论文形成一个聚类。聚类算法将产生一组聚类树，例如T= {T1;T2，...，Tn}。选择第一棵树T1作为基树。其次，概念为了匹配群落，引入了自然群落的概念自然社区被描述为节点的集合，这些节点通常通过几次聚类算法运行聚集在网络中。他们比较数据集中的不同聚类，以确定自然群落的集合。他们在每次聚类运行之前随机删除5%的论文通过给出从不同聚类运行中获得的基树T1和树T2，他们比较T1和T2中的聚类之间的匹配。两个聚类C和C0匹配如下：Matc h.C;C0000米。. jC\C0jN;. jC\C0j7下一节介绍了动态社交网络中社区检测的主要方法的文献综述。我们将现有的方法分为两个基本类别的基础上的网络模态。第一类是网络快照，其中网络被视为一系列快照（第6.1节）。第二类是时间网络，其中网络被视为一系列变化（6.2节）。 图 10给出了我们对现有方法的分类的概述。见图10。社会动态网络中现有社区发现方法的分类。6.1. 网络快照在这种方法中，作者倾向于将网络分成一系列快照;每个快照都被认为是一个静态网络。因此，社区检测可以是独立的，也可以是依赖的。对于独立社区检测，这些方法倾向于在每个快照中单独检测社区，然后将它们匹配在一起（第6.1.1节）。然而，在依赖社区检测中，方法依赖于先前发现的社区来检测给定快照中的新社区（第6.1.2节）。一些研究没有独立或依赖地检测社区，而是同时检测。他们同时考虑所有快照以检测社区（Mitra等人，2012年）。然而，这些方法在处理诸如合并的一些操作时可能有困难。6.1.1. 独立社区检测此类别中的方法将网络划分为一系列快照。首先，这些方法使用静态网络算法在每个快照上分别检测社区接下来他们随着社区的历史和新的社区在这里是可能的。如Azaouzi et al. （2019），这种方法的主要缺点是，从层次树中提取重要社区不是一项简单的任务。Asur等人（2009）设计了一个基于事件的框架，用于表征事件社区的演变。在实验阶段，他们使用了两个不同的数据集，DBLP和临床试验数据集。首先，他们在不同的时间拍摄静态快照接下来，他们将马尔可夫聚类算法（MCL）应用于每个快照以检测社区，因为MCL是一种快速且可扩展的聚类算法。之后，他们在连续的快照中比较每对社区的大小，以确定涉及这些社区的事件。他们还将九个关键事件分为两类。其中五个是涉及社区的事件，四个是涉及个人的事件。然而，在社区的生命周期中，可能会发生本研究未涵盖的更多形式的事件。此外，正如Zhu et al.（2016）所指出的，这里的一些事件缺乏真正的意义。因此，Zhu et al.（2016）根据他们对社区属性的看法重建了框架。他们选择了两个数据集在实验程序阶段进行工作。首先，他们使用CNM算法在每个时间戳检测社区。通过观察它们的共同节点数，可以将其定义为它们的社区属性之一，以寻找两个社区之间的差异。然后，他们单独使用原始（Asur等人，2009）和重建的事件用于分析网络。结果表明，新框架具有较好的适应性。（Greene等人， 2010）提出了一个跟踪在一个动态网络中的社区增长。首先，将动态网络表示为一组时间集图{g1，. . ..因此，在一个或多个时间步长，作者旨在检测动态社区D={D1，. . . ，DK 0}。k0的集合指的是在时间t检测到的阶跃共同体为Ct= {Ct1，. . ，Ctkt}。他们的方法亲-塞兹作为如下所示：一静态社区检测算法最初应用于图g1以提取第一社区C1。此外，一个新的不同的动态社区生成的每一步社区。然后，生成图g2上的C2战线{F1，.. . ，Fk0}将与来自C1的步骤社区匹配。因此，采用Jaccard系数来比较所有对（C2a;Fi）. 动态通信的时间表和前沿-N. Alotaibi和D. 鲁马沙特国王大学学报5653IJ（c） þÞ¼见图11。 独立社区检测。根据关键事件：出生，死亡，合并，分裂，扩张和收缩，更新nity。重复该方法，直到处理完所有时间步。高复杂性被认为是本研究的一个缺点。Sun et al.（2015）专注于在线社交网络。在他们的实验中，他们使用了两个数据集，DBLP和Facebook数据集。首先，他们将数据集划分为一系列快照{G t，G t}。. }. 接下来，他们在每个快照中应用Louvain算法然后，他们计算了两个相关矩阵K1（t，ts）和K2（t，ts），以描述快照Gt和Gts中社区之间的关系。首先，对于快照Gt，局限性。独立检测社区的方法可能会经历传统社区检测方法的高复杂性和不稳定性。6.1.2. 依赖社区检测这类方法还将网络划分为快照序列然而，这里的方法依赖于先前发现的社区来检测新快照中的社区（图11）。12）。He and Chen（2015）提出了一种快速检测方法。首先，他们将网络划分为一系列连续的时间步长。接下来，使用Blondel算法，他们在时间步1初始化网络其次，对于网络K1t tsVCit·VCjts吉尔克什ð8ÞG t在时间步长，t = 2，3，.. . 根据Gt中的网络结构和Gt-1中的社区信息，接下来，对于快照Gt，小型网络Gt-新。接下来，他们再次使用Blondel算法检测Gt-new他们的方法提高了效率，并保持了社区的质量，K1t tsVCit·VCjts传统的方法。由于重新计算分区，9ij;þÞ ¼. K.VCjtsk与前一个时间步相比，他们的方法节省了时间。然而，它可能会面临一些困难，处理社区的巨大变化，这项研究的缺点是，它依赖于用于检测社区与每个快照的算法因此，效率和准确性从一种算法到另一种算法。结构（Guo等人，2014年）提出了另一种属于这类的方法。他们提出了一种新的进化社区结构N. Alotaibi和D. 鲁马沙特国王大学学报5654见图12。 依赖社区检测。动态加权网络的发现算法该算法遵循三个主要阶段。首先，通过计算输入矩阵和所有节点的强度来发现接下来，通过输入可以提高社区质量的节点来扩展社区。最后，合并之前发现的所有社区，以提高整体质量。为了评估他们的算法的效率，他们在每个时间步中计算了算法的三个质量指标：历史，总质量和快照质量。结果表明，该算法具有最大的总质量，可以有效地发现进化社区结构。Gao等人（2016），在他们的研究中引入了一种新的算法来发现社区进化。EvoLeaders算法主要关注引线节点。该算法在将网络划分为一系列时间戳之后遵循四个主要阶段。首先，应用Top Leaders算法（Khorasgani等人， 2010），以得到领导节点L1和对应的社区C1。然后，在彼此的时间戳上，他们引入了一种更新的方法来寻找初始的leader节点。 在最后一个时间戳，它们隔离不再属于每个初始社区c0t;i的节点。社区分 裂 后 ， 很少有社区可以合并以提高社区质量。最后，将更新每个社区中的leader节点。结果表明，该算法能够实现对社区结构的合理分析然而，该算法在处理动态变化的数据时可能会遇到一些困难。Folino和Pizzuti（2013）介绍了一种用于发现动态网络社区的多目标遗传算法（DYNMOGA）。他们的方法旨在优化快照质量和减少时间成本，而不固定的控制参数。在实验阶段，他们使用了两个合成数据集.必须回顾的是，遗传算法需要很长时间才能产生解决方案。Rozenshtein等人（2014）发现了动态交互网络社区，其中包含所有网络节点交互的时间戳信息。他们认为所有的节点交互事件都是可识别的和无向的。他们在实验阶段使用了三个真实的数据集。他们引入了有效的算法来寻找稠密子图。在图中，它们标识由所选快照中出现的边的并集组成的密集节点的子集。局限性。这些方法可能难以直接应用移动社区检测方法。6.2. 时间网络在这种方法中，方法直接作用于时间网络。首先，拍摄具有一系列修改的初始快照接下来，在第一个快照上检测社区。然后，t的社区根据的修改被更新，t +1。最后，t +1的社区根据t +2的 修 改进 行 更 新 ，依 此 类推（图10）。 13）。我们将这些方法N. Alotaibi和D. 鲁马沙特国王大学学报5655图十三. 时间网络方法。属于这一类别的方法分为检测脱节（第6.2.1节）和重叠社区（第6.2.2节）。6.2.1. 脱节的社区已经建立了几种技术来检测脱节的社区，其中每个节点属于一个单一的社区。Raghavan et al. （ 2007 ） 提 出 了 标 签 传 播 算 法 （ LabelPropagation Algo- rithm，简称BPR），这是一种发现网络中脱节社区的算法在该算法中，每个节点都有一个唯一的通信标签，允许这些标签通过网络广播。基于这种标签传播的过程，社区被塑造。 由于LPA中存在一些随机性传播问题，Xie et al. （2013）提出了LabelRank算法，其中提出了一组算子来控制和稳定传播动态。基于 LabelRank ， Xie et al. （ 2013 ） 设 计 了 LabelRankT 算 法 。LabelRankT以增量方式检测动态网络中的社区。该算法能够检测各种类型的网络中的社区，包括直接/无向和加权/未加权的边缘，一般的时间复杂度为O（m）。由于许多已开发的基于模块化的算法具有较高的计算复杂度，Shang等人（2014）介绍了一种基于Louvain算法的增量模块化算法，具有低计算复杂度O（1）。该算法有助于跟踪网络他们在实验阶段使用了不同类型的数据集他们模拟了网络-工作随着边的顺序增加而改变，而不考虑边的减少。与BGL和CNM（Palsetia等人，2012），他们的算法在计算时间方面优于其他算法。Qi等人（2013）介绍了一种称为无限社区动态随机场（IC-DRF）的新方法，用于确定社会意义背景下动态社区的结构。IC-DRF被认为是开发用于分析动态社区的在线和动态方法的第一个模型。 在实验阶段，他们在Geo-Life数据集上评估了该算法。所提出的模型与三种算法进行了比较，ObjectGrowth（Li等人，2010）、动态随机块模型（DSBM）（Yang等人，2011），和动态无限关系模型（dynamicinfinite Relational Model，diflex）（Ishiguro等人，2010年）。与其他三种算法相比，IC-DRF取得了良好的效果。作为缺点，所提出的方法仅适用于特定的网络数据。Xu et al.（2013）提出了一种跟踪移动社交网络中社区核心演变的算法。这种方法背后的主要思想是基于给定网络中的稳定链接找到一个分区。首先，他们提出了一种稳定链接提取方法，用于寻找累积稳定联系人（CSC）。然后，他们讨论了CSC的变化。最后，介绍了一种基于标签的社区核心跟踪算法，用于显示社区核心的演化.节点或链接的增加被定义为节点或链接插入的序列，而节点或链接的减少被认为是节点或链接移除的序列N. Alotaibi和D. 鲁马沙特国王大学学报5656[2]因此，定义了四个事件：添加/删除节点和添加/删除边。这种基于标签的社区核心跟踪算法在实验阶段显示出稳定的社区核心。Aston和Hu（2014）介绍了对SCAN（网络结构聚类算法）的改进（Xu等人， 2007），一种为静态网络开发的算法，能够检测动态网络中的社区。在动态扫描（DSCAN）中，SCAN算法将在第一个时间戳上执行。然后，将获得所有连续时间戳的两个时间戳之间的边缘差。网络将随着边的变化而更新。在升级边缘时，节点可能成为核心，或者不再是核心。一个当前的cluster-id或一个新的cluster-id被传播到所有在结构上加入的节点上以形成一个新的社区。一个节点可以通过传播成为一个中心点或一个离群点研究结果表明，DSCAN的功能更快，比SCAN更强大Nguyen et al.（2014）提出了一种称为快速社区适应（QCA）的新框架，用于检测和跟踪动态社交网络中的社区评估。所建议的框架首先是一个初始的社区结构，利用布隆德尔的方法。它考虑了结构历史，并专门与影响其社区结构的网络修改一起操作，其中网络变化被视为事件的集合。它可以是newNode、removeNode、new- Edge和removeEdge。并给出了QCA技术在城域网转发策略和OSN蠕虫控制Yu等人（2019）提出了一种基于贝叶斯概率模型的新模型，称为进化贝叶斯非负矩阵分解（EvoBNMF）。为了解释社区结构的演化特征，EvoBNMF提出了演化行为来量化社区在相邻快照之间的过渡关系。EvoBNMF通过减少每个快照网络对应的进化行为，自动捕捉最合适的社区数量。此外，他们开发了一种有效的算法来优化EvoBNMF基于均值漂移（MS）方法，Messaoudi和Kamel（2019）提出了一种新的社区检测方法，称为多目标蝙蝠算法。BA是一种基于群体智能的生物启发算法该算法模拟实际蝙蝠MS方法将用于产生高质量的个人。使用多目标BA，这些个体被优化。在有了最好的一个之后，他们解码它以得到相应的社区。他们通过使用两个目标函数得到一组最佳解，而不是一个此外，通过调整频率和速度，创建新的解决方案在真实复杂网络上的实验结果表明，该算法在模型度和密度方面的性能优于同类算法。Yu等人（2019）介绍了一种基于图正则化非负矩阵因子化（ECGNMF）的进化聚类新框架。ECGNMF能够同步检测动态群落结构和相关的进化模式。该模型可以准确地检测社区的组成，评估社区的时间演化，解决社区数量的变化，并预测时间网络的社区结构的变化。实验结果表明，该框架在社区发现方面具有较强的方法.FanzhenLiu等人（2020）引入了一种称为DECS的新型多目标进化聚类算法，以捕获动态社交网络中社区他们开发了一个迁移操作符，与高效的操作符一起工作，确保节点和大多数邻居的分组，并使用编码网络结构数据的基因组矩阵来扩展搜索区域。作为优化目标之一，DECS基于基因组矩阵度量模块化。此外，通过标签传播的种群生成（PGLP）策略来初始化种群，以提高DECS的搜索效率在模拟数据集和真实数据集上的实验结果表明了DECS在聚类精度和平滑性方面的优越性局限性。几种方法被开发来检测脱节的社区。在真实网络中，节点通常是多个联合社区。6.2.2. 重叠社区在一个真实的网络中，我们可以注意到重叠的社区，所以最近，研究人员已经开发了几种方法来检测重叠的社区。Cazabet et al.（2010）提出了一种用于检测重叠社区的算法，称为iLCD。iLCD（intrinsic，Longitudinal Community Detection）被认为是第一个在时间网络中检测动态社区的算法。iLCD通过插入边缘然后整合相同的边缘来检测重叠社区。在实验阶段，他们使用了JASSS数据集。他们在有重叠和没有重叠的图中测试了他们的算法。 结果表明，iLCD给出了比CPM更好的结果（Palla等人，2005年）。然而，iLCD无法处理社区Mahfoudh等人（2018）旨在识别动态和重叠的社区，并提出一种增量多代理方法来检测它们。他们讨论了所提出的方法的检测，其中他们使用了多代理系统（MAS）。MAS被描述为一个系统，其中多个独立的和智能的实体，称为代理，交互。它非常适合于对不同实体之间的相互作用非常复杂的现象进行建模。MAS非常适合于对动态环境中不同独立实体在相互作用中进化的现象进行建模他们用它来设计动态网络，他们从初始部分开始，其提议的功能定义如下：FPa·QP1-a·SP 10其中P是一组社区，Q是模块化函数，S是属性相似性函数，并且8 0; 1是用于平衡模块化和属性相似性之间的权衡的加权参数。这种方法允许检测动态社区和所有相关操作。一旦它们检测到初始分区，代理就与每个检测到的社区相关联。然后，在实验和评估中，他们通过将其应用于真实数据集DBLP，Yelp和TripAdvisor并将其结果与iLCD模型（Cazabet et et al.， 2010）和GM模型。最后，他们的方法使他们能够通过本地计算跟踪许多社区的演变他们的解决方案还具有以低计算成本响应网络修改的能力此外，考虑到社交网络的多智能体模拟的优点，Amblard和Cazabet（2011）还提出了一个允许发现动态社交网络的多智能体框架在他们的方法中，一组独立的因素共同努力，发现动态的社会。结果表明，该模型能有效地克服所有问题.综上所述，本文提出了一个动态社交网络中社区发现的渐进式多智能体平台一组代理人共同努力，在拟议的方法，以现代化目