一种基于亲和聚类的分布式大图划分方法

摘要

本发明涉及一种基于亲和聚类的分布式大图划分方法，主要针对无权无向图划分处理，基于Boruvka算法层次亲和平衡图聚类将图初始划分为指定的k个子图，以顶点相似度作为距离度量，迭代合并距离较近的两类顶点，并移去子图中邻点相似度和值最小的顶点以约束规模过大的子图，在没有后续优化的情况下，划分质量也接近于现有的大图划分方法；并且针对大规模子图之间的割边率优化问题，本发明设计了降维的操作，通过将初始划分的结果映射为顶点序列并切分为一定数量的子片，随机选择相邻子图中的两个子片，根据互交换正收益及单点正收益迁移顶点，以此达到优化割边率的目的。