大规模图中核值维护对称性缺破算法研究
发布时间：2021-08-07 06:46
对称性缺破算法是分布式算法的一个重要研究方向。近些年来,将核值维护问题作为一类对称性缺破子问题在物理学等领域得到广泛的研究。以往的核值维护算法不能高效地处理顶点加入/删除这种情况下的核值维护问题。在一次算法迭代过程中,基于“匹配”的核值维护算法每个顶点最多只能关联到一条边,基于“优边集”的核值维护算法每个顶点最多只能关联到一条优势边。当一个顶点加入或删除时,与该顶点相关联的边必须通过多次迭代才能处理完,这会造成大量的冗余计算从而导致算法的低效性。为了解决以往算法的局限性,提出了一种称为“联合边集”的结构。该“联合边集”结构优先处理具有高优势度的顶点,使得与这些顶点相连的边能够在一次迭代中得到处理。通过理论证明表明,一个联合边集的加入或删除仍然能够使得图中每一个顶点的核值最多变化1。与基于“匹配”和基于“优边集”的结构相比,基于“联合边集”的结构需要更少的迭代次数便能维护图中每个顶点的核值,这将使得算法需要更少的重复访问和冗余计算。进一步将“联合边集”进行划分,可以将划分得到的不相交边集交给不同的线程进行处理,这样便可以利用多核处理器的优势得到并行的核值维护算法。除此以外,利用联合边集结...
【文章来源】：华中科技大学湖北省 211工程院校 985工程院校 教育部直属院校
【文章页数】：64 页
【学位级别】：硕士
【部分图文】：
顶点核值的计算过程
法对很多顶点进行不必要的访问从而降低算法的性能。最后，每个顶其 2 跳邻居内其它顶点的核值计算索引信息。当加入或删除边时，大要更新索引信息，这将花费高昂的时间成本。为了解决 这些缺陷， hang 等人50]提出了一种基于 的快速核值维护在所有顶点之间建立了一个全序关系，并指出某个顶点核值的增长只排在该顶点之后的邻居的个数。基于 的核值维护算法克算法中存在的缺陷，提高了核值维护的运行效率。特别是对于，能有效地减少算法运行所消耗的时间。文章中给出了如图 1-2 所示在顶点 0和顶点 4之间新加一条边时， 算法需要遍历点才能确认只有顶点 0的核值会增加 1,而基于 的算法只需一个顶点便能够找到所有核值会增加 1 的顶点集合。实验表明算法相比，基于 的核值维护算法在加边的情况下最多升 3 个数量级。
这个结构可以结合 算法或者基于 的找出核值真正发生变化的顶点集合。但是在一次迭代过程中，基于匹配能保证一个顶点最多加一条边。对于一条边 ，如果顶点 的核于顶点 的核值则称边 是顶点 的一条优势边。基于优边集的结构只能次迭代中每个顶点最多增加或者删除一条边。所以当在处理一个顶点并点增加或者删除了多条优势边时，文献 53]中提出的两种算法不能有效个高优势度顶点。虑图 1-3 中的示例，虚线是新加的边。顶点 4增加了 5 条优势边，分别, 4 5, 4 6, 4 1, 4 7。顶点 17增加了 3 条优势边，分 18, 17 14, 17 15。顶点 13增加了 2 条优势边，分别是 13 11。对于顶点 4，在一次迭代过程中，基于匹配或者优边集的结构最多新增的边，这是因为顶点 4新加的 5 条边都是顶点 4的优势边。所以至 次迭代才能处理完顶点 4新增的 5 条边。
【参考文献】：
期刊论文
[1]基于图着色的密集D2D网络资源分配算法[J]. 孙彦赞,范卫蓉,张舜卿,王涛,吴雅婷. 计算机工程. 2019(02)
[2]Learning dynamic dependency network structure with time lag[J]. Sizhen DU,Guojie SONG,Haikun HONG,Dong LIU. Science China（Information Sciences）. 2018(05)
[3]大数据背景下机器学习算法的综述[J]. 李成录. 信息记录材料. 2018(05)
[4]基于Pregel模型的分布式图着色算法[J]. 甘瀛,王鑫,冯志勇,杨雅君. 计算机科学与探索. 2018(06)
[5]关于图的极大独立集的理论及生成方法[J]. 李兢,刘长林,申石虎. 电子学报. 1995(08)
硕士论文
[1]动态图中核值维护算法研究[D]. 王娜.华中科技大学 2018
本文编号：3327293
【文章来源】：华中科技大学湖北省 211工程院校 985工程院校 教育部直属院校
【文章页数】：64 页
【学位级别】：硕士
【部分图文】：
顶点核值的计算过程
法对很多顶点进行不必要的访问从而降低算法的性能。最后，每个顶其 2 跳邻居内其它顶点的核值计算索引信息。当加入或删除边时，大要更新索引信息，这将花费高昂的时间成本。为了解决 这些缺陷， hang 等人50]提出了一种基于 的快速核值维护在所有顶点之间建立了一个全序关系，并指出某个顶点核值的增长只排在该顶点之后的邻居的个数。基于 的核值维护算法克算法中存在的缺陷，提高了核值维护的运行效率。特别是对于，能有效地减少算法运行所消耗的时间。文章中给出了如图 1-2 所示在顶点 0和顶点 4之间新加一条边时， 算法需要遍历点才能确认只有顶点 0的核值会增加 1,而基于 的算法只需一个顶点便能够找到所有核值会增加 1 的顶点集合。实验表明算法相比，基于 的核值维护算法在加边的情况下最多升 3 个数量级。
这个结构可以结合 算法或者基于 的找出核值真正发生变化的顶点集合。但是在一次迭代过程中，基于匹配能保证一个顶点最多加一条边。对于一条边 ，如果顶点 的核于顶点 的核值则称边 是顶点 的一条优势边。基于优边集的结构只能次迭代中每个顶点最多增加或者删除一条边。所以当在处理一个顶点并点增加或者删除了多条优势边时，文献 53]中提出的两种算法不能有效个高优势度顶点。虑图 1-3 中的示例，虚线是新加的边。顶点 4增加了 5 条优势边，分别, 4 5, 4 6, 4 1, 4 7。顶点 17增加了 3 条优势边，分 18, 17 14, 17 15。顶点 13增加了 2 条优势边，分别是 13 11。对于顶点 4，在一次迭代过程中，基于匹配或者优边集的结构最多新增的边，这是因为顶点 4新加的 5 条边都是顶点 4的优势边。所以至 次迭代才能处理完顶点 4新增的 5 条边。
【参考文献】：
期刊论文
[1]基于图着色的密集D2D网络资源分配算法[J]. 孙彦赞,范卫蓉,张舜卿,王涛,吴雅婷. 计算机工程. 2019(02)
[2]Learning dynamic dependency network structure with time lag[J]. Sizhen DU,Guojie SONG,Haikun HONG,Dong LIU. Science China（Information Sciences）. 2018(05)
[3]大数据背景下机器学习算法的综述[J]. 李成录. 信息记录材料. 2018(05)
[4]基于Pregel模型的分布式图着色算法[J]. 甘瀛,王鑫,冯志勇,杨雅君. 计算机科学与探索. 2018(06)
[5]关于图的极大独立集的理论及生成方法[J]. 李兢,刘长林,申石虎. 电子学报. 1995(08)
硕士论文
[1]动态图中核值维护算法研究[D]. 王娜.华中科技大学 2018
本文编号：3327293
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/3327293.html
