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,我们首先建议一种能够高效和大量减少搜索空间的修剪技术。然后,我们讨论如何用精确和大致的算法来调整这一技术,以提高其效率。最后,通过在不同领域对多个网络进行广泛的实验,我们展示了我们拟议技术的高度实证效率。我们的算法不是现有方法的竞争对手,相反,在应用任何现有算法之前,它是一个可以用作快速预处理步骤的朋友。

0
下载
关闭预览

相关内容

【NeurIPS2020】点针图网络,Pointer Graph Networks
专知会员服务
39+阅读 · 2020年9月27日
专知会员服务
123+阅读 · 2020年9月8日
图卷积神经网络蒸馏知识,Distillating Knowledge from GCN
专知会员服务
94+阅读 · 2020年3月25日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【论文】图上的表示学习综述
机器学习研究会
14+阅读 · 2017年9月24日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Directional Graph Networks
Arxiv
27+阅读 · 2020年12月10日
Bridging Knowledge Graphs to Generate Scene Graphs
Arxiv
5+阅读 · 2020年1月7日
Learning to Importance Sample in Primary Sample Space
Learning to Focus when Ranking Answers
Arxiv
5+阅读 · 2018年8月8日
VIP会员
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【论文】图上的表示学习综述
机器学习研究会
14+阅读 · 2017年9月24日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员