一种基于代表参数的图聚类算法

图聚类是图数据管理领域中的一个重要问题。对于给定的图G,图聚类的目标是将图的顶点划分到不同的簇中。划分后,同一个簇中顶点间的连接较为紧密,而不同簇中顶点间连接较为松散。已有研究成果的共性问题是它们需要计算每两个顶点间的相似性,这需要浪费大量计算资源。基于上述问题,提出图聚类框架RPGC(Representative Parameter Graph Cluster)避免大量顶点间相似性的计算。RPGC使用历史聚类信息创建一组代表性强的参数集H。对于任意历史聚类参数h,RPGC可从代表参数集中找到与之相似程度较高的参数。当有新的聚类请求被提交时,RPGC可从H中找到与之相似程度高的代表参数,进而根据基于代表参数得到的聚类结果执行增量计算,实现图的高效聚类。利用大量真实数据集和合成数据集对RPGC的高效性进行了验证。