大规模社交网络上基于规则的最短传播路径计算方法

摘要

本发明公开了一种大规模社交网络上基于规则的最短传播路径计算方法，包括如下步骤：利用加权有向图构建社交网络图谱G(V，E，w)，V表示社交网络图谱G中全部顶点也即社交主体的集合，E表示全部边也即社交关系的集合，w表示边的权重；根据社交网络的社交主体之间的关系构建路径规则I表示顶点子集，R表示偏序关系集；根据路径规则中的偏序关系构建广义规则树利用分层收缩技术对社交网络图谱进行预处理，并将其划分为前向图Gu和后向图Gd；利用前向扩展算法求解前向图Gu和后向图Gd中基于路径规则的最短路径。本发明可以快速求解出基于规则的最短传播路径，同时可对查询算法的查询效率进行大幅度提升。