An important tool in analyzing complex social and information networks is s-t simple path counting, which is known to be #P-complete. In this paper, we study efficient s-t simple path counting in directed graphs. For a given pair of vertices s and t in a directed graph, first we propose a pruning technique that can efficiently and considerably reduce the search space. Then, we discuss how this technique can be adjusted with exact and approximate algorithms, to improve their efficiency. In the end, by performing extensive experiments over several networks from different domains, we show high empirical efficiency of our proposed technique. Our algorithm is not a competitor of existing methods, rather, it is a friend that can be used as a fast pre-processing step, before applying any existing algorithm.
翻译:分析复杂的社会和信息网络的一个重要工具是S-t简单路径计数,众所周知,路径计数是 #P-完成的。在本文中,我们研究了在定向图表中高效的S-t简单路径计数。对于一对给定的脊椎和在定向图表中 t,我们首先建议一种能够高效和大量减少搜索空间的修剪技术。然后,我们讨论如何用精确和大致的算法来调整这一技术,以提高其效率。最后,通过在不同领域对多个网络进行广泛的实验,我们展示了我们拟议技术的高度实证效率。我们的算法不是现有方法的竞争对手,相反,在应用任何现有算法之前,它是一个可以用作快速预处理步骤的朋友。