一种复杂网络中基于聚类系数的并行图摘要算法

摘要

本发明公开了一种复杂网络中基于聚类系数的并行图摘要算法，包括：将图的原始顶点集合划分为不同的分区；将分区子图的原始顶点集和边集作为图摘要的初始顶点集合和边集合，对各分区顶点，根据顶点选择策略确定初始点，计算该点聚类系数，并合并该顶点与所有一跳邻居顶点生成新摘要顶点；更新图摘要的顶点集，同时根据聚类系数生成修正边集合，并更新图摘要的边集合；继续选择下一个待合并顶点，重复执行上述合并过程，直至各分区摘要图中顶点总数小于阈值时停止，最终合并输出总的摘要图和修正边集合。本发明能够根据复杂网络中顶点的聚类系数进行并行摘要，避免了传统图摘要算法计算效率慢、压缩率低等缺陷，在图压缩、复杂网络顶点重要性排序等领域有较好的应用价值。