复杂网络属性图聚类的新方法：结构凝聚性和质量问题解决

制作和主办：Elsevier沙特国王大学学报复杂网络中基于标签传播的属性图聚类Kamal Berahmanda，Sogol Haghanib，Mehrdad Rostamic，Yuefeng Liaa澳大利亚布里斯班昆士兰科技大学科学与工程系b伊朗德黑兰Vanak Alzahra大学计算机工程系和数据挖掘实验室c伊朗萨南达杰库尔德斯坦大学计算机工程系阿提奇莱因福奥文章历史记录：收到2020年2020年7月31日修订2020年8月18日接受2020年9月1日网上发售保留字：复杂网络属性图聚类标签传播节点相似度A B S T R A C T扩散法是复杂网络中社团发现的主要方法之一。在这种方法中，使用的概念，即扩散内的节点是一个社区的成员比扩散的节点，不在同一个社区。这样，稠密子图将检测中间层中的图。LPA算法是扩散方法中最有效的算法之一，它通过散布标签来模拟传染病的传播，近年来引起了人们的广泛关注。该算法具有线性时间顺序、利用局部信息、不依赖于任何参数等优点，是近年来最流行的社区检测算法之一，但由于LPA算法的随机性，存在因怪物社区规模较大而导致的不稳定、质量不高等问题。该算法适用于属性网络。本文提出了一种新的LPA算法，使得检测出的社区不仅具有结构凝聚性和属性同质性，而且解决了社区不稳定和质量低的问题为此，本文从具有边的结点的属性图出发，导出结点属性与拓扑结构相结合的加权图此外，每个节点的中心性将被计算为等于每个节点使用拉普拉斯中心性的影响，并且选择节点的步骤被增强用于更新以及基于节点的影响的更新机制。所提出的方法进行了比较，其他主要的和新的属性图聚类算法真实和人工数据集。实验结果表明，该算法在不调整参数的情况下，对不同密度和熵准则的网络进行聚类，归一化互信息表明该算法比现有的属性图聚类方法更有效、更精确©2022由Elsevier B.V.代表沙特国王大学出版。这是一篇开放获取的文章，CC BY-NC-ND许可证（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍复杂网络是研究当前发生的各种自然现象的重要工具，如生物网络、大脑网络以及技术时代人类创造的社会网络等。工作和网络流量可以由复杂的网络来描述。这个问题使网络科学成为一个热门的、广泛的、跨学科的领域在当今时代。在这些复杂网络的核心，存在许多问题，例如社区检测（Mohammadi等人，2019），识别扩散节点（Berahmand等人，2018年a，2019年），最大影响力（Berahmand*通讯作者。电子邮件地址：kamal. hdr.qut.edu.au（K. Berahmand），s. student.alzahra.ac.ir（S. Haghani），M. eng.uok.ac.ir（M. Rostami），y2.li @ qut.edu. au（Y. Li）。沙特国王大学负责同行审查https://doi.org/10.1016/j.jksuci.2020.08.0131319-1578/©2022由Elsevier B. V.出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.com1870K. Berahmand等人 /沙特国王大学学报-计算机与信息科学34（2022）1869- 1883例如，2018 c）和链接预测（Haghani和Keyvanpour，2019），这被认为是主要的挑战。社团结构是复杂网络中最普遍、最重要的拓扑性质之一。社区检测被划分为几个密集连接的子图，以便于理解和可视化大型图。近年来，随着可用于现实世界对象的丰富信息的增殖，图中的顶点通常与描述顶点的特征和属性的若干属性相关联（Gibson和Faith，2011，Berahmand等人，2018年b）。 在PPI网络中，属性值可以表示基 因 表 达 数 据 ， 其 在 暴 露 于 刺 激 时编 码 每 个 基 因 的 差 异 表 达 值（Rostami等人，2020年）。在社交网络中，属性可能对应于成员的个人概况，例如年龄、兴趣、地点等（Xu等人，2012，Greene和Cunningham，2013）。网络图由超链接交织的网页组成。 每个网页还具有一系列属性，包括URL、名称、关键字、内容、标签等六项。这个问题导致了一种新型的图，称为属性图，因此需要一种新的聚类任务，称为属性图聚类。拓扑网络结构反映了节点之间的相互作用，节点属性信息反映了节点之间的共同特征。它们都在网络社区结构的形成中发挥着重要作用。然而，目前大多数社区发现算法都是基于网络拓扑结构的.使用网络拓扑结构和节点属性信息的这种属性网络中的社区检测是至关重要的，但也是具有挑战性的，并且强烈依赖于适当的相似性学习（Huang等人，2015，Fang等人，2016年）。理想的属性图聚类应该通过平衡结构和属性相似性来生成具有密集子图的聚类，所述密集子图具有内聚的聚类内结构和同质顶点属性（Li等人， 2017年）。虽然图聚类已经被广泛研究，因此，具有丰富属性的大型图的聚类分析在实践中仍然是一个主要的挑战（Yang等人，2009年）。一个属性图聚类是由一组节点之间相似度最大的节点组成的。在这方面，节点的相似性可以基于两个度量来计算，包括结构相似性和属性相似性（Amiri等人，2018年）。基于网络拓扑结构提取结构相似度。属性相似度的计算使用的是完全独立于网络拓扑结构的各个节点的内部charac- teristics。拓扑网络结构反映了节点之间的相互作用，节点属性信息反映了节点之间的共同特征。它们都在网络社区结构的形成中发挥着重要作用（Karimi-Majd和Fathian，2017年，Alinezhad等人，2020年）。如前所述，结构相似性度量是使用网络拓扑来提取的，网络拓扑可以通过不同的方法来计算，例如k距离邻域和公共邻域。在k-距离邻域方法中，如果距离（即，Manhattan距离）小于k。在公共邻居方法中，如果两个节点有更多的公共邻居，即使它们不相邻，也是相似的。如前所述，属性相似性考虑了节点的内部特征，而不需要任何关于网络拓扑和图结构的知识。例如，社交网络中个人节点作者认为，一个具有丰富属性的大型图的有用的聚类分析，需要一个系统的图聚类分析框架，划分基于结构相似性和属性相似性的图。社区发现问题一般分为两类：仅利用结构信息和结构信息与属性相结合。在第一类中，传统上采用网络结构来识别稠密子图;一些流行的方法 包括 模块 化（ Clauset 等 人，2004 ） ，标 签传 播算 法（ LPA）（Raghavan等人，2007）和随机游走（Pons and Latterfly，2005，Rosvall and Bergstrom，2008）。然而，与这些方法相反，一些方法使用结构信息和网络属性，并且结构-属性组合图聚类方法旨在将具有丰富属性的图划分为具有内聚簇内结构和同质属性值的若干簇; SA-簇（Zhou等人，2009）、CODICIL（Ruan等人，2013）和PCL-DC（Yang等人，2009）方法是这一类别中流行的方法之一。LPA方法是一种近年来最流行的社区发现方法是基于结构网络的。 这种方法由于其低时间复杂度（线性顺序）和低空间复杂度（使用局部信息）而受到欢迎。该算法由于随机性的存在，存在着不稳定、检测质量不高等问题，人们提出了许多算法来增强其随机性。本文提出了结构-属性相似性标签传播算法（SAS-LP），它是LPA算法在属性网络中的适应版本。此外，该算法的这项工作的主要贡献总结如下-降低五倍：SAS-LP算法是一种适应于属性网络的算法，减少了迭代次数，保持了原有的时间效率。SAS-LP算法比LPA算法具有更好的稳定性。以这种方式，保证了算法的稳定性。同时，避免了影响力小的节点对影响力大的节点的反向干扰和不必要的迭代更新。在同时考虑图的结构和属性信息的属性网络中，提出了一种新的顶点相似性度量。提出了一种新的度量属性网络中节点影响力的方法，该方法可以在网络中起到簇中心的作用在综合基准测试和真实网络上的准确率和效率实验结果表明，该算法本文的其余部分组织如下。第二节总结了复杂网络中属性图聚类的相关工作. 第三节介绍了本文的一些基本内容，如属性相似度和结构相似度的定义、标签影响、标签接受度，以及本文提出的算法（SAS-LP）。第4对仿真和实验分析的结果进行了说明，第5给出了结论。2. 相关工作社区检测在文献中已经得到了广泛的研究在这一部分中，对现有的流行的社区发现算法进行了总结性的介绍。一个很好的表面-●●●●●K. Berahmand等人 /Journal of King Saud University- Computer and Information Sciences 34（2022）1869-18831871图1.一、结构聚类和属性聚类的范畴Vey可在（Bothorel等人，2015，Chunaev，2019）。作者将现有的社区发现算法分为两大类：1）非属性图主要集中在基于节点的连接结构上，忽略了节点的属性; 2）属性图同时处理结构和属性信息。非属性图分为四个主要组，包括，a）层次聚类，b）基于模块的方法，c）基于随机游走的方法，以及d）基于标签传播的算法，并且属性图被分成四个众所周知的组，包括a）边缘加权，b）增强图，c）质量函数优化，d）统一距离。这类社区检测包括两个主要分支，如图2所示。1.一、层次聚类是复杂网络分析中一种常用的、最古老的社区（簇）发现方法任何层次聚类方法的出发点都是相似性度量的定义层次聚类方法可以分为两大类，包括凝聚算法和分裂算法发现社区。在随机游走方法中，每个节点最初包含一个游走器然后，每个步行者将随机选择它当前所站节点的邻居进行定位。随机漫步背后的想法是，漫 步 往 往 被 困 在 社 区 网 络 的 密 集 部 分 （ Pons and Latterfly ，2005）。目前，已经提出了许多基于随机游走的社区检测方法，诸如MCL（vanDongen，2000）、Walktrap（Pons和Latterfly，2005）和Info- map（Rosvall和Bergstrom，2008）算法。基于模块性的方法尝试基于模块性度量来检测社区。这些方法假设一个分隔良好的社区具有很高的模块化价值.显然，将n个节点划分为k个非空群的方法的数量由第二类斯特林数（k）给出;因此，不同社区划分的数量是贝尔数。因此，它被证明是一个NP完全问题的模块化优化所有基于模块化的方法的目的是发现网络的分区，使得模块化值最大化。提出的模块化最大化的方法可以分为三个主要类别：基于贪婪，启发式方法，和频谱优化。 标签传播算法（LPA）是Raghavan等人提出的一种流行的快速社区发现方法。（2007年）。最初，为网络中的每个节点分配唯一的标签在下一步中，每个节点使用其邻居中出现频率最高的标签更新其当相邻标签的频率相等时，算法随机选择最频繁的标签。这个标签宣传-重复该过程，直到具有相同标签的节点被分组到一个社区中。LPA的主要优点包括拥有接近线性的时间复杂度、使用局部信息、与自由参数和目标函数无关以及实现简单（Sun等人， 2015年）。但由于该算法初始节点选择的随机性和平局状态下节点标签的随机更新，存在不稳定、质量不高、形成怪物社区等缺点 最近的研究表明，已经设计了许多修改版本的LPA以提高其稳定性和鲁棒性（Berahmand和Bouyer，2018年，Zhang等人，2018，Berahmand和Bouyer，2019，Garza和Schaeffer，2019）。上述的图聚类和图摘要方法只考虑了图的一个方面的属性，而忽略了其他方面。属性图聚类利用来自结构和属性的信息来发现图中的聚类这些集群是密集连接的节点组，并且它们的属性也高度相似。许多图聚类方法已经被提出来利用图的结构信息之外的内容信息。作者将这些方法分为四类：（1）将属性图转换为加权图的方法最后，将对每一组的选定办法作一概述。第一类包括基于原始属性图到加权图的转换的方法，诸如FocusCo（Perozzi等人，2014年）。通过将节点属性的信息存储在图的边缘内来从节点中移除节点属性，这是通过将节点边缘中的两个节点之间的相似性值作为属性的权重来执行的。第二类包括基于距离的方法，诸如SI聚类（Zhou和Liu，2013）、SA聚类（Zhou等人， 2009）和CODICIL（Ruan等人， 2013年）。 结构信息存储在节点之间的相似性（距离）函数中，并与属性相似性（距离）函数相结合。第三类涉及基于模型的方法，其包括但不限于PCL-DC （Yang 等人， 2009 ）、贝叶斯概率模型（ Xu 等人，2012）和CESNA（Yang等人， 2013年）。它们基于概率模型，避免了距离测量的人工设计第四类是子空间聚类方法。在这一类别中所提出的方法的选定集合包括CoPaM（Moser等人，2009）、GAMer（ Gunnemann 等 人 ， 2010 ） 、 DB-CSC （ Günnemann 等 人 ，2011）和SSCG（Günnemann等人，2013年）。它们只在;;21872K. Berahmand等人 /沙特国王大学学报-计算机与信息科学34（2022）1869- 1883将它们的相关特征的上下文作为所有节点的属性的子集2.1. 属性图到赋权图的转换方法图的节点之间的属性相似性可以示出关系的强度。因此，通过将节点属性的信息存储在图表。该算法将两个节点之间的属性相似度作为其权值，将图整形为加权图后，考虑到边的权值，可以对加权图应用不同的图聚类算法。如果在聚类过程中边保持高权重，则可以获得具有相似属性值的节点组。2.2. 基于距离的方法attr 3. attrk）与V中的节点相关联并描述它们的特征。K是A的属性向量的维数。在本文中，作者主要研究了节点上具有二进制（可互换，标号）属性的图.结构相似度是社区检测中最重要的相似性度量，基于网络拓扑结构提取结构相似度。定义1（属性相似性（ASIM））。 属性相似度的计算使用的是完全独立于网络拓扑结构的各个节点的内部特征。这里使用简单匹配系数标准（Faizal，2014）来计算属性的相似性。简单匹配系数（SMC）是一种用于关联二进制数据样本之间相似性的统计度量。匹配系数仅适用于具有分类节点属性的图。它被定义为匹配属性的总数与当前属性的总数的比率，由等式2计算。（1）如下：属性图聚类的最简单的想法是定义一些顶点距离度量，该度量考虑图中顶点的结构和属性信息你比如说SMC i j匹配属性的数量i;j属性的总数i;jð1Þ顶点属性值的差异可以量化为相邻顶点之间的距离（Steinhaeuser和Chawla，2010）。文本的网页内容和超链接也结合在一个相似性度量的网页聚类。不同的相似性（距离）的措施，提出了这个目的，和经典的基于距离的聚类方法可以应用到图形数据使用这些建议的措施。2.3. 基于模型的方法属性图聚类的另一个相关工作流主要建立在生成概率模型上，其中节点（i）和节点（j）使用n二进制描述，美德.先知-愿定义2（结构相似性（SSIM））。 结构相似度是社区检测中最重要的相似性度量，基于网络拓扑结构提取结构相似度。节点a和b的结构相似性采用Jaccard相似性。它是节点a和b的公共邻居与所有邻居节点的比率a和b的。结果，Jaccard索引的值防止更高程度的节点与其他节点具有高相似性索引。Jaccard相似性（a，b）由等式（1）计算（2）如下：真实和顶点属性信息与每个图内的聚类成员的一组共享和隐藏变量相关（Yang等人， 2013年）。这种方法避免了距离测量的人工Jaccardij½Ca\Cb]½Ca[Cb]Ca表示节点a2V的一阶邻域。ð2Þ2.4. 子空间聚类最近的方法使用无监督的特征选择作为子空间聚类，并在属性子集中提取具有同态性的凝聚子图。子空间聚类方法的提出是为了解决这个问题，通过识别簇的相关特征，特别是对于高维数据。然而，找到相关特征在计算上是困难的。需要一个优化步骤来组合不同的质量度量，例如密度、熵和维度。下面总结了这一类别中的一些选定方法，这些方法将子空间聚类与密集子图挖掘相结合。3. 该方法在处理算法之前，让我们回顾一些定义和概念，它们是所提出的算法的基础。3.1. 背景和注释一般来说，属性网络可以用三元组G =（V，E，A）表示，其中V是节点集，E是表示节点之间现有关系的边集，A表示属性向量集。n的值=|V|是顶点总数，m=| E|是边的总数，并且A（attr 1，attr 2，定义3（重量 Matrix）。 考虑的归因图G =（V，E，A），其使用结构相似性和彼此具有边的两个节点之间的属性被转换为加权图G=（V，E，W）。每个边的权重将通过等式获得。（3），它是由组合的属性相似性矩阵方程。（1）和来自Eq.（二）、两个节点（i，j）之间的边的权重是量化节点之间的接近度的度量。这两种类型的相似性的组合用于增加两个节点之间的链接的权重的准确性。边的权重越准确，通过采用拉普拉斯中心性，在结构和属性方面具有更大影响的节点的检测将更容易（Qi等人，2012年）。结构相似性和非结构相似性是两个完全独立的问题，每个问题在确定相似性方面都有不同的作用。在这些类型的算法中的主要挑战是这两种类型的结构和非结构相似性的有效组合，以增强结果，其中元素（i，j）将等于Eq.（三）、权值i;jfaωSSIMi;j1-aωASIMi;jgifAi;j1/410;否则为1/3其中a[0，1]是融合系数，一个影响结构和属性成分之间平衡的超参数。此外，SSIM（i，j）和ASIM（i，j）分别被称为结构相似度和属性相似度1/10@01CAP¼iIJ我ðÞ2S¼¼K. Berahmand等人 /Journal of King Saud University- Computer and Information Sciences 34（2022）1869-18831873定义4（标签影响（LI））。许多中心性度量可以识别节点的影响。然而，大多数这些中心度使用图的结构信息来确定具有高影响力的节点;但是，这些中心度都不是属性图的适当选项，因为它们忽略了属性的信息。由于所考虑的图矩阵是使用结构和属性信息加权的，因此作者使用拉普拉斯中心性准则，该准则近年来一直用于计算加权网络中节点的中心性。 拉普拉斯中心性，由于其线性复杂性和半局部信息的使用，在检测加权网络中的影响节点方面非常流行（Qi等人，2012年）。该测度不仅考虑了节点的直接相邻性，而且考虑了相邻节点的重要性和影响力为了检测节点，社区中的簇头相当精确。Laplacian中心性定义为网络的Laplacian能量随着目标节点从网络中消除而下降为了计算Laplace中心，作者首先利用公式3将图G=（V，E，A）转换为权图G=（N，E，W），然后计算每个节点到其邻居的链接的权和，得到对角矩阵Y（G）：3.2. SAS-LP算法通过假设一个属性图G=（V，E，A）和聚类数K，本文研究的聚类问题的基本思想是将 G的节点集 V 划分为 K 个不相交的子集 V1 ，V2，. . . ，Vn，其中V=对于任意i-j，nv i和Vi|Vj=e，紧密连接;以及（2）簇内的节点在它们的属性值中具有关于属性的低多样性，而不同簇中的节点可以具有不同的属性值。LPA算法只利用图的结构信息进行社区检测，首先为每个节点分配一个唯一的标签，然后在几个更新阶段中选择频率最高的节点如果算法达到每个节点的标签等于节点中相邻标签的最大数量的迭代并且不再发生变化，则稠密子图下已经达到相同标签的所有节点都被检测为社区图。然而，该算法面临着不稳定和低性能，由于怪物社区的发展所造成的节点的同等重要性和随机行为在更新阶段和平局打破模式。在每个集群中，是更重要的顶点，0x1公司简介·· ·0·· ·0·· ·0···Xnð4Þ（簇的中心），使得从其边界更接近社区的中心，出现更多重要的顶点（具有更显著的影响）;因此，图中的顶点与其相邻图相比的影响力越高，可以指示该顶点的更显著的作用中的节点其中xnj1wij是节点i之间的链路的权重之和社区具有不同影响力排名。 的节点与影响力较大的节点扮演支配者的角色以及网络中的其他节点网络的拉普拉斯能量也被计算为Eq。（五）n影响力较低的人扮演从属者的角色。一个节点可以影响其他节点（dominator），也可以被其他节点影响（sub-ordinator），集群中所有节点的重要性并不相同。ElGXXi2Xw2ð5Þ相似本研究的目的是检测这些节点，1/1Ij影响结构和属性维度，节点i的拉普拉斯中心性LAPCi可以表示为属性图中的聚类为此，两个新的概念-LAPCDEiELG-ELGiEL GE L Gð6Þ引入概念，并将其应用于高精度算法LPA中，以解决属性聚类问题在第一个概念中，将为两个节点定义新的相似性在该等式中，EL（Gi）是网络的拉普拉斯能量值。在移除节点i之后工作。在使用加权矩阵确定每个节点的拉普拉斯中心性之后，每个节点的标签影响力将等于该节点的中心值，其在等式中定义。(7)如下所示：LIi;lILI（i，l）表示标签l对节点i的影响，其中[LAPC]i是节点（i）的拉普拉斯中心性定义5（标签验收（LA））。在原始LPA中，所有邻居具有相同的传播标签的概率。 在SAS-LP方法中，使用邻居的标签影响（LI）来选择用于传播的最佳标签。标签验收通过等式计算。（8）如下：LAihargmax LIv2Cuv;li8Cu表示节点u V的一阶邻域。在标签更新阶段，每一个节点都会得到一个在其一级相邻节点中具有相当影响力的节点标签。根据结构和属性的组合，对数据进行分类。利用这一相似性得到加权图，并利用第二个概念计算了加权图中各节点基于拉普拉斯中心度的影响力。在下文中，图G=（V，E，A）将被转换为具有结构-属性融合的图G=（V，E，W），使用等式：（3），这是两个节点之间的边的权重。然后，利用加权图的拉普拉斯中心度，计算出每个节点的中心度，该中心度等于该节点对相邻节点的影响，节点对相邻节点的影响不仅体现在结构上，还体现在属性上。在等式（1）中给出的加权矩阵中具有较高拉普拉斯中心性的节点。（3）在结构和属性方面将对它们的相邻部分具有渗透性。在集群中具有中心地位并与群体中其他成员有相当数量联系的节点在控制、引导和建立社区的力量和稳定性方面做出了重大贡献，而处于社区边界的节点则可能在社区之间起到领导和引导的中介作用。属性图由邻接矩阵和属性矩阵组成。在此基础上，给出了结构相似度矩阵和属性相似度矩阵的计算公式。此外，作者将使用一些00X200X3001874K. Berahmand等人 /沙特国王大学学报-计算机与信息科学34（2022）1869- 1883图二. SAS-LP算法的步骤。图3.第三章。 混合参数（l）=0.1和属性噪声（v）=0.1的LFR-EA数据集的图形结构和基础事实：30个节点被划分为3个不同的社区。生成加权矩阵的公式。生成的加权矩阵将用于使用拉普拉斯中心性计算节点的影响。此外，节点的选择和更新将根据该算法和一些公式进行。作者将对节点标签和节点的影响力进行求和，并选择影响力较大的标签。在本文提出的算法中，平局模式很少发生，因此，将考虑链接权重，作者将对相似标签的权重链接求和，并选择其中最大的链接。该算法的步骤如图所示。 二、例1.考虑图3所示的混合参数= 0.1且属性噪声= 0.1的网络LFR-EA，其指示SAS-LP方法（算法1）的更新过程。表1中解释了该过程的所有步骤，作者在下文中更详细地考虑了这些步骤。一开始，所有节点都被唯一地标记为类似于LPA。然后，加权计算节点的相似性和标签影响（拉普拉斯中心性）。 最显著的标签影响被认为是更新其标签的第一个节点。 此节点使用从具有最高标签影响的相邻节点中选定的标签更新其标签。例如，通过采用SA-LPA，更新顺序为30？26岁？23岁？二十四岁？十七岁？21岁？15岁？六个？十八岁？20个？... 什么？十九岁？ 十七岁？ 13个序列。首先用节点23的标签更新节点30，因为节点30对节点23具有更大的标签影响30、邻居之间在节点30之后，更新节点26。它用节点20的标签更新其标签，因为节点在其邻居中的标签影响更显著。然后，节点23用标签23更新。所有其他节点都根据其标签影响值类似地更新其标签。在迭代1结束时，节点蓝色、绿色和被聚集在同一社区中，因为它们接收到相同的标签23、20、15节点7。 此外，节点9至18被收集在另一社区中，因为它们的标签被更新为节点16的标签≈K. Berahmand等人 /Journal of King Saud University- Computer and Information Sciences 34（2022）1869-18831875表1基于图1的SAS-LP算法的迭代。3.第三章。3.3. 伪代码算法1：提出的SAS-LP社区检测算法输入：网络G=（V，E）输出：社区结构C={C，C}通常运行在不同的时间复杂度上。在第一阶段，初始化所有具有唯一标签的节点的时间复杂度表示为O（n）。第二步，标签影响力的计算。为了计算标签影响，需要计算属性相似度和结构相似度，它们的时间复杂度都是O（nk），因为复杂网络通常1 k拥有一个具有少量邻居的大规模图，并且1. 将所述属性图转换为加权图2. 为网络3. 通过公式计算标签影响（七）4. 当节点的标签改变或t最大迭代时，5.按照节点强度的升序排列节点，并将结果放在向量v上。6.设t= 1。7.对于每个节点vie X向量，根据等式中的接受标签更新其标签。（八）8.如果正在发生抢七状态，则计算相邻节点的太阳标签9.t = t +1。10. End while11. 建立基于相似标签的社区12. 返回社区结构。3.4. 计算复杂度本节讨论了所提出的SAS-LP算法的时间复杂度。假设一个网络，n=| V|节点和m=| E|链路G=（V，E），设k为平均节点度。该算法由几个独立的步骤组成。每一步都是独立的-时间复杂度O（m）第三步是基于标签影响对节点进行排序，其时间复杂度为O（n）（由于在线性时间内使用基数和桶排序算法第四步是标签传播过程。由于只考虑了等于O（m）的邻居，所以根据接受标签，标签更新的时间复杂度也是O（nk）。最后，O（n）是将具有相同标签的节点分配到其社区的时间复杂度。算法的时间复杂度一般为O（3nk + m + 2n）O（m）。由于无标度网络具有稀疏性，因此边的数量近似等于节点的数量，因此O（m）<$O（n）。4. 实验评价在本节中，给出了SAS-LP的实验结果通过一系列实验对所提出的方法进行了综合性能评估。组织如下。第4.1节总结了以下实验中使用的所有数据集。在两组数据集上评估了该方法的有效性：1）合成数据集和2）真实世界数据集。第4.2节审查评价指标。第4.3节讨论了合成数据集的综合结果，包括参数分析实验和对迭代1迭代2迭代3节点标签影响订单更新当前标签新标签订单更新当前标签新标签订单更新当前标签新标签12830302330232330232323026262026202026202032423232323232323232342324242324232324232351817172317232317232363521211521151521151571115151515151515151582766156151561515916181815181515181515101020202020202020202011302525202520202520201231121220122020122020133221521515215151416292915291515291515153911112011202011202016141010231023231023231743112012020120201833272715271515271515191228282328232328232320338823823238232321423320320203202022234420420204202023582222232223232223232451552352323523232532991591515915152660141423142323142323272816161516151516151528281919201920201920202930771571515715153082131320132020132020KNMIA;Bk k k k1/1第1页P.Σð9Þ小行星1876 Berahmand等人 /沙特国王大学学报-计算机与信息科学34（2022）1869- 1883所提出的方法的能力。第4.4节给出了在真实世界数据集上与几种最先进的方法进行比较的性能评估结果，第4.5显示了社区中心与拉普拉斯中心之间的关系。所有的实验都是在配备四核Intel i7 2.20 GHz处理器和16 GB RAM的台式机上进行的。4.2.1. NMI网络的两个分区A和B的归一化互信息NMI（A，B）设C是混淆矩阵，其元素Cij是划分A的社区i中也在划分B的社区j中的节点的数量。-2PCA PCB Ci jlogn Ci j=CiCjCACBi<$1Ci：logCi=nj< $1Cj：log Cj=n4.1. 数据集为了验证和评估SAS-LP的性能，使用了两类数据集合成数据集是计算机生成的网络，允许创建对评估合成生成的社区和检测到的社区之间的相似性有用的地面实况从真实环境中提取的真实世界数据集更好地代表了实际的网络行为。这些网络的描述如下。4.1.1. 合成数据集LFR-EA是使用Elhadi和Agam提出的基准生成的合成网络（Liu和 Lü ， 2010 ） 。 它 是 Lancichinetti 等 人 的 LFR 基 准 的 扩 展（Lancichinetti等人，2008年）。网络生成器使用两个参数m和m，都在区间[0.1，0.9]中，分别控制结构和属性值混合参数m决定社区内和社区间连接的速率。少量的m给出了一个清晰的社区结构，其中集群内的链接比集群间的链接多得多类似M是噪声属性参数，其中低值产生属于同一社区的节点的相似特征M的组合 和m值产生的图形具有明显的模糊的结构和/或属性。其中CA（CB）是分区A（B）中的组的数量，Ci（Cj）是行i（列j）中的C的元素的总和，并且n是节点的数量如果A=B，则NMI（A，B）=1。如果A和B完全不同，则NMI（A，B）= 0。准确度是一种常见的统计测量，指的是测量值与特定值的接近程度。在社区检测中，准确性意味着提取的社区与真实网络中的群体之间有更好的对应关系。它表示正确聚类节点数与所有节点数的比率。4.2.2. F1得分F1-score捕获通过社区发现算法获得w.r.t.地面实况此外，它允许利用密度散点图对分区质量4.2.3. 密度利用密度函数分析了图中顶点之间的强连接，密度函数表示簇中出现的边数与整个图中边总数的比值。将所有聚类的比率累积起来，以评估总体影响。密度值位于[0，1]的区间内K.k1X4.1.2.真实世界的数据集dfCgi¼11/4kEk1/1kECik10Cora（Sen等人， 2008）包含一组表示科学出版物的节点，其中两个节点之间的边是从一个出版物到另一个出版物的引用。该网络的属性如果一个单词出现在这篇论文中，该单词的属性被设置为1，否则为0。每个节点被分为七类：1）基于案例的推理; 2）遗传算法;3）神经网络; 4）概率方法; 5）强化学习; 6）规则学习; 5）理论。Citeseer（Sen等人，2008）是另一个引文网络，其中每个节点属于以下六个类别之一：1）代理;2)人工智能; 3）数据库; 4）行动; 5）信息检索;和6）机器学习。哪里E和E C i分别表示图和每个簇中的边数。4.2.4. 熵衡量聚类结果质量的一个关键方面是根据顶点的属性来确定它们之间的相关性。对于每个属性，针对具有关联属性的每个聚类计算熵当同一个簇内的所有顶点都具有相似的属性或与它们相关联的上下文时，则总体熵获得最小值。熵（Entropy）=XkCik熵（Entropy）=xk CikWebKB数据集（Sen等人， 2008）由科学文献组成，其中包括四所大学的网页网络：1）1/1 kVk多姆拉特河康奈尔大学; 2）得克萨斯州; 3）华盛顿州和4）威斯康星州。每一页网-熵-Xpt logpt工作可以分为五类：1）课程; 2）教师; 3）学生; 4）项目; 5）员工。Political Blogs Dataset是一个关于美国政治的博客网络，这些博客之间有超链接。每个Weblog都与描述Weblog的政治倾向的属性相关联，标记为自由或保守。统计表2KS KSs1这些测试网络的特性总结在表2中。4.2. 评价方案两个主要的度量组用于评估社区检测方法的性能，称为外部和内部测量。而后者通常用于真实标签不可访问的情况。在下文中，将描述这些指数真实世界数据集的特征数据集节点边缘属性社区CiteSeer1787328537036科拉2708542914335康奈尔19530417035Texas18732817035华盛顿23044617035威斯康星26553017035政治博客149019,09072KSK. Berahmand等人 /Journal of King Saud University- Computer and Information Sciences 34（2022）1869-18831877表3LFR-EA-1000参数设置。参数值节点数（N）1000平均度数（k）25最大度数（maxk）40混合参数（m）[0. 1;0. 九、群落规模分布指数（t1）1社区规模的最小值（minc）60社区规模最大值（maxc）100重叠节点数（om）0属性数4属性属性范围（R）10属性噪音[0. 1;0. 九、图四、不同混合参数下LPA和SAS-LP的NMI值，通过设置m= 0.1。其中p t是聚类C k中取值为s的顶点的分数，其中s 2 dom（a t）。4.3. 对合成数据集作者生成了一个由1000个节点组成的网络基准，命名为LFREA-1000，以评估SAS-LP的各个方面。生成表3中报告的参数组合的不同实例由于生成网络是随机过程，不同的运行可能会导致不同的结果分区，因此我们将十次运行的结果1. 混合参数m：对于变化的m的情况，属性噪声是固定的m= 0.1。图4示出了SAS-LP在生成的属性图上的性能。在这次考试中，亲-通过与原LPA的比较，验证了该方法的有效性和稳定性与LPA相比，SAS-LP和LPA在结构良好的社区中表现更好随着混合参数的增大，LPA的性能下降，而SAS-LP在每一步都保持稳定。此外，当图具有模糊的社区结构时，该方法具有可比较的性能。当图的结构变得不那么清晰时，使用属性就起着至关重要的作用。因此，SAS-LP的能力是由于利用图结构和属性线性。2. 噪声参数m：固定m参数，SAS-LP比较不同的噪音设置。为此，作者修复了将混合参数设为m=0.5，以便具有结构足够模糊的属性拟定方法的性能比较总结见表4。这些结果证明了算法对噪声的鲁棒性从表4中可以看出，除熵之外的所有结果都保持稳定。如前所述，从属性的角度来看，低熵值表示同质社区密度测量顶点周围的连通性从表4中的数据，作者得出结论，在大多数情况下，添加顶点属性可以提高群落检测的性能3. nattr范围参数：为了评估SAS-LP获得的属性范围结果的质量，作者报告了不同噪声跨度的结果（图5）。特别地，随着属性值范围的增加，熵值通过增加噪声参数而上升。值得指出的是，熵不仅对噪声参数敏感，而且对属性值的范围也很敏感。同样的结论也适用于NMI，这是由于广泛的属性导致相似节点较少的事实。直观地说，在充分利用各种信息并进行有