一种基于社团结构寻找社交网络中任意两点最短路径的方法

摘要

一种基于社团结构寻找社交网络中任意两点最短路径的方法。社交网络往往可以用带权无向图模型来表示，其中图中每个点代表个人，每条边代表人与人之间的联系，联系越紧密，边上的权重越大，两点距离越短。本发明旨在提出一种能快速返回误差范围内任意两点间最短路径的两阶段方案，包括：预处理阶段，首先改进现有的结构化聚类算法，使其适用于带权图，并对图进行社团划分；然后根据社团划分结果构建超图，其中原图中每个社团对应超图中的超点，社团之间的联系对应超图中的超边，并根据选取的地标节点估算超边的长度；在线查询阶段，根据两点所在的社团相对位置不同，利用超图缩小搜索范围，返回两点间的估算最短路径。