基于k-核分解的改进Nyström谱图聚类算法在大型网络上的应用研究

沙特国王大学学报基于k-核分解的改进Nyström谱图聚类算法涂景智a，刚梅a，李刚，弗朗西斯科·皮恰利ba中国地质大学（北京）工程技术学院100083中国北京b数学与应用系R. Caccioppoli，那不勒斯费德里科二世大学，那不勒斯，意大利阿提奇莱因福奥文章历史记录：接收日期：2022年2022年3月23日修订2022年4月14日接受2022年4月22日在线提供保留字：大型网络Nyström谱图聚类k-核分解标签传播A B S T R A C T图（网络）上的聚类由于规模的增加而变得棘手。Nyström谱图聚类（NSC）是一种流行的方法来规避这个问题。然而，NSC目前面临两个问题：（1）如何有效地获得大型网络的代表性样本;（2）NSC是不合理的节点映射。针对这一问题，本文提出了一种基于k-核分解采样的改进Nyström谱图聚类算法。在该方法中，我们首先采用k-核分解作为抽样方法，然后使用样本进行NSC以获得样本节点和与样本连接的节点的簇，并且最后利用所提出的标签传播算法将剩余节点分组到先前找到的簇中。为了评估性能，我们使用谱聚类和NSC作为基线，并将我们的算法与9个小型网络上的基线进行比较。此外，所提出的方法适用于5个大型网络。对于一个约1.2亿条边的大型网络，该方法的模块度为0.355，计算时间为1234.95 s，表明该方法具有比NSC更高的精度和比谱聚类更高的效率。©2022作者（S）。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍图（网络）被应用于表示现实世界中的对象之间的关系，诸如社交网络（Du等人，2020; Sherchan等人，2013年; Jiang等人，2016）和生物网络（Hu et al.，2020; Liu等人，2020年; Li等人，2017年）。机器学习作为一种分析和理解数据的工具，由于其令人印象深刻的能力，已经广泛应用于各个领域（Karniadakis等人，2021; Ma和Mei，2021;Sabir等人，2022年）。 几十年来，已经开发了经典的机器学习、聚类算法来进行图聚类（Wu等人，2022; Zhang等人，2017; Scott，2015;Zfle等人，2014年）。图聚类是图挖掘的基本算法之一。它的目标是找到一组密集连接的节点在不同的节点之间，几乎没有连接*通讯作者。电子邮件地址：gang. cugb.edu.cn（G. Mei）。沙特国王大学负责同行审查ent集群。目前，图聚类的主要挑战是现实世界中的大多数网络都是大规模的，因此将它们整体聚类是棘手的。规避这个问题的一个可行策略是取图的一个小的有代表性的样本，然后用传统聚类分析得到的子图的固有聚类结构来近似整个原始图的固有聚类结构（Zhang et al.， 2020年）。近年来，为了避免直接对大型网络进行整体聚类，Nyström谱聚类算法，一种常见的谱聚类（SC）方法（Liu et al.，2018年;温例如，2020）在大型网络上使用Nyström扩展方法（Fowlkes等人，2004）用于近似相似性矩阵和通过代表性样本的特征分解，已经成功地在大规模图形结构数据和分散点数据中实现（Li等人，2015 年;Belabbas 和 Wolfe ， 2009 年 ） 。 在 Nyström 谱 聚 类 算 法 中 ， 采 用Nyström扩展方法，通过样本矩阵近似计算整个矩阵的特征向量，使得Nyström谱聚类的效率依赖于样本的数量，避免了大型网络中大相似矩阵的存储和运算所带来的内存瓶颈。因此，与其他聚类算法相比，https://doi.org/10.1016/j.jksuci.2022.04.0091319-1578/©2022作者。由爱思唯尔公司出版代表沙特国王大学这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comJ. Tu，G.Mei和F.皮恰利沙特国王大学学报3674X在网络中，Nyström谱聚类通常在计算上更便宜。然而，Nyström扩展方法的使用也导致了潜在的问题，即Nyström谱聚类方法对于未连接到样本的节点（方差为0的节点）的映射是不合理的（Zhanget al.， 2017年）。在Nyström谱聚类方法中，Nyström方法用于通过对部分数据点进行采样来近似计算特征向量，即，这种方法稍微牺牲了聚类的准确性，以换取算法效率的显著提高。因此，聚类方法的可靠性直接取决于抽样数据的代表性。在Nyström谱聚类算法中，如何采样是一个关键问题.有效的抽样策略（即，选择少量有意义的样本）可以显著提高Nyström谱聚类的效率，以满足大型网络的聚类要求。目前，国内外学者已经开展了大量的研究工作在Nyström方法的采样策略上，这些采样算法可以分为两类：增量采样方法和一次采样方法。一次性采样是最广泛使用的采样算法，例如随机采样，它首先由Fowlkes等人（2004）用于Nyström谱聚类算法。此外，为了解决大型数据集上的聚类问题，Belabbas和Wolfe（2009）使用Schur补进行采样，Zhang和Kwok（2010）使用中心点获得可靠的样本在k-均值中。然而，随机抽样和基于舒尔补的抽样是不稳定的。对于散乱点数据的结构，采用基于k均值中心点的采样方法.增量抽样方法主要包括基于方差的增量抽样算法和通过误差分析的增量抽样（Zhang et al.，2017年）。增量抽样的实质是它是一次性抽样方法的一种补充方法因此，该策略降低了基于一次采样方法的Nyström谱聚类算法的效率复杂网络的研究正受到越来越多的关注。为了分析网络拓扑结构，Seidman（1983）首先提出了一个被广泛接受的概念，称为k-核，其中创建了一个称为k-核剪枝的算法来获取输入网络的k-核。然后，Batagelj和Zaversnik（2003）提出了一种有效的k-核分解算法，该算法的复杂度仅为O（m），可以快速得到网络的k将整个图分解为若干k-核心子图的k -核心分解是一种有效的图划分方法，并且被称为可分解核心的图的k -核心是最大大小子图，其中每个节点在子图中至少具有k个邻居（Panet al.，2018;Al-garadi等人，2017年）。基于这一思想，图的密度核大致保持其聚类结构（Alvarez-Hamelin et al.， 2017年）。为了获得图结构数据的稳定和有意义的样本，我们使用k-核分解作为图结构数据的采样策略。此外，针对这些映射不正确的节点，提出了一种基于k-核分解的标签传播算法，该算法利用Nyström谱聚类方法得到的合理节点簇作为采样策略，预测与样本无关的节点本文提出了一种改进的基于k-核分解采样的Nyström谱图聚类算法（k-INSC）.在所提出的方法中，（1）我们首先执行输入大网络的k-核分解;（2）我们然后使用顶部k-核心子图的顶点作为样本进行利用Nyström谱图聚类，得到样本节点和与样本相连节点的聚类;（3）将方差为0的节点分组到先前找到的样本和与样本相连节点的聚类中，最终得到输入大网络的所有聚类为了评估所提出的聚类方法的性能，我们使用传统的谱聚类和Nyström谱图聚类作为基线，并将所提出的方法与9个真实世界的网络进行比较。最后，该方法被应用于5组大型网络。结果表明，该方法对大型网络具有较高的精度，计算效率也令人满意。在这项工作中，我们的贡献可以总结如下。(1)k-核分解作为一种抽样策略被应用于图结构数据，以获得稳定的和有意义的样本，从而提高聚类质量。(2)提出了一种基于k-核分解的标签传播算法方差为0的节点的聚类基于先前找到的聚类。(3)在k-核心分解采样中选择k值的建议（即， 采样率的选择的样本），从而使该方法可以方便地应用于大型网络。本文的其余部分组织如下。第二部分是研究的背景。第3节具体介绍了所提出的算法。在第4节中，为了展示所提出的聚类算法的能力，列出了实验设置和结果。在第5节中，讨论了所提出的方法。最后，在第6节中得出了几个结论。2. 背景：传统的Nyström谱聚类算法2.1. 传统谱聚类算法机器学习算法可以根据关于数据的可用信息分为监督学习、半监督学习和无监督学习（Brunton等人，2020;Sabir等人，2022年）。作为一种无监督学习算法，基于图论的谱聚类具有优异的聚类性能以及广泛的适用性（Von Luxburg，2007），其中拉普拉斯矩阵（Qiao et al.，2022; Priebe等人，2019）对输入数据进行降维，然后根据特征向量得到输入数据的聚类（见图1）。谱聚类不仅适用于离散数据，而且由于图论的特点，谱聚类也适用于图结构数据。当对图结构数据进行聚类时，首先需要对输入数据进行处理，以形成无向图G。G1/2V;E1/2V其中V是节点集，E是图G的边集;见图。 1（a）.然后，聚类的问题被转换成割图问题，这是将图划分成至少两个最优子图（见等式10）。（2）），即，不同子图之间的连接尽可能低，而同一子图中的节点之间的连接尽可能高，其中连接程度通过边权重之和来度量切割线A;BW u;v2u2A;v 2B其中图G被划分为A和B的两个不相交子集，并且Wu;v是图G的邻接矩阵。此外，还发展了割图法。划分图G的方法有很多，如J. Tu，G.Mei和F.皮恰利沙特国王大学学报3675图1.一、图结构数据的谱聚类算法（a）一个简单的7节点无向图;（b）通过邻接矩阵以及度矩阵计算相应的拉普拉斯矩阵;（c）通过拉普拉斯矩阵的特征分解得到每个节点对应的特征向量，最后通过k-均值聚类将节点分类到不同的聚类中。例如，2001）、最小切割（Sarkar和Soundararajan，2000）、归一化 切 割 （ Ncut ） （ Shi 和 Malik ， 2000 ） 、 比 率 切 割 （ Hagen 和Kahng，1992）和平均切割（Wu，1993），其中Ncut是最常用的。2.2. 矩阵逼近在谱聚类中，即使大型邻接矩阵和拉普拉斯矩阵以稀疏格式存储，大型矩阵的特征向量的计算也是相当昂贵的通过压缩。 Fowlkes等人（2004）利用Nyström方法获得了一个大矩阵的低秩矩阵近似解，从而能够保持整个大矩阵的相似值。虽然可能会有一些精度损失，但它可以明显降低计算复杂度。Nyström方法是一种用于找到近似特征分解的技术（Li等人，2015年）。它利用矩阵的列（或行）子集来近似大矩阵的谱分解J. Tu，G.Mei和F.皮恰利沙特国王大学学报36762n2i¼i;j1n×nð- Þe-1-1m×me e eee;k2bi;j¼1 qPmSij我D^i; j^l：1. qnS¼ Jð ÞK;千分之四我At一KbA;k¼RbA;k一一At一e本文分三步介绍了对称半正定矩阵L步骤1：构造低维子空间Nyström方法起源于积分方程领域选择（Wang等人， 2021年）。这里，存在SPSD矩阵LR n×n，一个低维子空间，使用一组m < 0.3时，现实世界的网络具有良好的社区结构在本节中，如图4所示，我们通过将其与RNSC和SC进行比较来评估所提出的k-INSC。SC在大多数情况下显示出最佳的准确性。一般来说，建议的k-INSC也显示出可靠的精度，这只是略低于SC，而RNSC的精度是最低的。具体的比较结果（图4和图5（a））表明如下：(1) 上述9个数据集的SC聚类结果的Q值均超过0.4，总体上SC可以达到最佳的精度。(2) 上述9个数据集的k-INSC聚类结果的Q而且，无论哪种情况，k-INSC的Q值都要比RNSC的Q值(3) 如图5（a）所示，当采样率较低（约为1%）时，k-INSC仍然可以获得准确的聚类结果（Q> 0.3），RNSC的准确性较差。当采样率低，方差为0）J. Tu，G.Mei和F.皮恰利沙特国王大学学报3682占大多数，导致RNSC的准确性较低。无论采样率如何，k-INSC的Q值都比RNSC的Q值好得多.当采样率较高，方差为0的节点数占少数，且非理性映射对Nyström谱图聚类算法的影响较差时，k-INSC的准确率高于RNSC，证明k-核分解采样比随机采样更具有代表性。当采样率较低时，方差为0的节点数占大多数，在Nyström谱图聚类算法中无理映射的影响显著的情况下，k-INSC的聚类精度仍然很高，并且远高于RNSC，证明了本文提出的标签传播算法有效地克服了Nyström谱图聚类算法的缺点。4.3.2. 建议方法在这一节中，建议的k-INSC的有效性进行了评估，通过比较它与RNSC。在图4中看到的上述比较结果表明：(1) 基于不同采样策略的两种算法的效率随着采样率的降低而提高。(2) RNSC的效率高于基于k-INSC的聚类算法，这是由于顶部k-核心子图的代表性;即，通过k-核心分解采样获得的样本与更多的节点相关联。一般来说，RNC是最快的。J. Tu，G.Mei和F.皮恰利沙特国王大学学报3683表3大型网络的聚类结果和运行时间运行时间（s）数据集群集号采样比k-INSCRNSCVNSC公司简介1520.06%448.17589.78569.2sx堆栈溢出60.10%25.1610.7121.27索克波凯茨1030.20%211.22146.90187.77维基顶级猫250.06%36.6317.0220.32康奥尔库特1000.51%1234.95133.46487.38图六、程序的工作量在本文提出的图聚类算法中适用于大数据集。（a）com-Orkut;（b）com-LiveJournal。(3) 通常，当采样率较低（约1%）时，k-INSC的效率与RNSC的效率相似。4.4. 该方法在大型网络中的应用根据上述实验结果和分析，我们发现k-INSC仍然可以实现类似于SC的优秀社区结构和类似于RNSC的 高 效 率 （图1）。（ 4）当采样率低（大约1%）。因此，我们通过选择高k值（低采样率，约为1%）来使用k-INSC来处理大型网络。为了进一步评估所提出的k-INSC在大型网络中的性能，将k-INSC与RNSC和使用基于方差的增量采样（VNSC）的Nyström谱图聚类进行了比较（Zhang et al.，2017年，在大型网络？如图 4）和图。 5（c），对于大型网络，当获得的样本较少时，与RNSC相比，由于采样方法的改进，VNSC的精度略有提高，VNSC的效率略有降低。与RNSC和VNSC相比，k-INSC在采样策略和映射过程上的改进使得k-INSC在效率略有下降的情况下，精度得到了显著提高而且，如表3所列，对于这些无法通过谱聚类进行聚类的大型网络，例如具有3，072，441个节点和117，185，083条边的com-Orkut数据集， k-INSC的运行时间仅为1234.95 s，这是令人满意的。因此，该算法在应用于大型网络时，在准确性和速度方面都具有良好的性能为了研究限制所提出的算法的效率的潜在瓶颈，专门针对数据集com-Orkut和com-LiveJournal（图6）。程序3，即，所提出的用于剩余未标记节点的标记传播需要超过50%的工作量，这表明计算上最昂贵的过程是标记传播，并且该过程dure有很大的改进潜力。综上所述，对于这些不能用经典谱聚类进行聚类的大型网络，与RNSC和VNSC相比，k-INSC的精度有明显的提高。另一方面，虽然所提出的标签传播方法降低了聚类效率，但所提出的聚类算法的总体效率仅略低于传统的Nyström谱图聚类算法（RNSC和VNSC）。因此，对于大型网络，该方法可以在较低的采样率（约1%）下获得准确、鲁棒的聚类结果和令人满意的效率。5. 讨论5.1. 建议方法与经典的谱聚类相比，该聚类方法由于采用了近似的思想，只需要少量的样本就可以得到整个图的聚类结果，从而可以对大型网络进行聚类该算法背后的想法是牺牲精度来提高效率，以满足大型网络的计算需求。这两种技术的使用，即，有效的抽样方法和建议的标签传播方法，结果在一个更高的准确性提出的聚类J. Tu，G.Mei和F.皮恰利沙特国王大学学报3684与传统的Nyström谱图聚类方法相比，与传统的Nyström谱图聚类算法相比，由于采用了k-核分解采样，得到了更具代表性的样本，因此该聚类算法在高采样率下具有更高的精度，而在低采样率下的精度并没有因为采用了所提出的标签传播方法而明显降低克服了传统Nyström谱图聚类算法对方差为0的节点映射的不足。5.2. 建议方法所提出的聚类方法的架构包括三个主要的程序，这导致了它的主要缺点，它是算法上比传统的Nyström谱聚类算法更复杂。提出的聚类方法的效率略低于传统的Nyström谱图聚类算法。 而且，由于k核采样方法的特点，所提出的算法只能将样本数控制在一个范围内，而不能控制到一个精确值。6. 结论在本文中，我们提出了k-INSC，一个高效和准确的图聚类算法的大型网络，通过使用k-核心分解的采样策略。为了对大型网络进行聚类，在Nyström谱聚类算法的基础上，首先对输入的大型网络进行k-核分解尤其是程序3。此外，对于大型网络的聚类，我们正在考虑将k核分解与人工神经网络相结合（Zhang et al.，2022; Sabir，2021; Wu等人，2021; Sabir等人， 2022年），以实现更好的聚类结果。竞争利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作。附录A.缩略语列表k- INSC基于改进的Nyström谱图聚类k-核分解采样NSC Nyström谱图聚类基于随机抽样的RNSC Nyström谱图聚类SC谱聚类对称半正定基于方差增量采样附录B.注释说明以获得稳定且有意义的样本。然后，一个标签传播-针对Nyström谱图聚类算法中顶点映射不合理的问题，提出了一种基于k-核分解的聚类方法为了评估k-核心抽样策略和所提出的标签传播算法对传统Nyström谱图聚类的改进效果，我们使用谱聚类算法和Nyström谱图聚类作为基线，并在9组真实数据集上将我们的算法与基线进行比较。此外，为了验证该算法在大型网络中的有效性，将该算法应用于5组大型真实网络，并使用从上述9组真实网络数据集的比较结果中获得的建议采样率（约1%）进行了验证。结果表明：（1）k-核分解采样比随机采样和基于方差的增量采样更具有代表性;（2）标签传播算法有效地解决了方差为0的节点的非理性映射问题;（3）聚类算法的准确率远高于Nyström谱图聚类算法（RNSC和VNSC），而在大型网络中，聚类算法的整体效率略低于RNSC和VNSC因此，该算法对大型网络具有较高的聚类精度和较好的聚类效率在所提出的算法中，由于标签传播方法的存在，使得改进的Nyström谱聚类算法的效率普遍低于Nyström谱图聚类算法。有一个提高效率的共同策略平行战略大型网络分簇算法的并行策略是在多核CPU、众核GPU甚至分布式计算等平台上设计基于并行架构的高效分簇算法在未来，并行策略可以用来提高所提出的图聚类算法的计算速度G图图的V图的边集图或矩阵图的W完全邻接矩阵S样本邻接矩阵L-拉普拉斯矩阵C重排拉普拉斯矩阵由特征向量组成的U特征