The betweenness centrality (BC) is an important quantity for understanding the structure of complex large networks. However, its calculation is in general difficult and known in simple cases only. In particular, the BC has been exactly computed for graphs constructed over a set of $N$ points in the infinite density limit, displaying a universal behavior. We reconsider this calculation and propose an expansion for large and finite densities. We compute the lowest non-trivial order and show that it encodes how straight are shortest paths and is therefore non-universal and depends on the graph considered. We compare our analytical result to numerical simulations obtained for various graphs such as the minimum spanning tree, the nearest neighbor graph, the relative neighborhood graph, the random geometric graph, the Gabriel graph, or the Delaunay triangulation. We show that in most cases the agreement with our analytical result is excellent even for densities of points that are relatively low. This method and our results provide a framework for understanding and computing this important quantity in large spatial networks.


翻译:中间中心点( BC) 是理解复杂大型网络结构的重要数量。 但是, 它的计算一般是困难的, 只有简单的例子才知道。 特别是, BC 精确地计算了在无限密度限制下以一组美元点构造的图表, 显示了一种普遍的行为。 我们重新考虑了这个计算, 并提议扩大大和有限密度。 我们计算了最低的非三角顺序, 并显示它编码了直径如何是最短的路径, 因此不普遍, 并且取决于所考虑的图表。 我们比较了我们的分析结果, 将其与各种图表( 如最小横幅树、 最近的相邻图、 相邻图、 随机几何图形、 加百列图 或 Delaunay 三角图 ) 的数值模拟相进行比较。 我们显示, 在大多数情况下, 与我们的分析结果的一致是极好的, 甚至对于相对较低的点的密度来说。 这种方法和我们的结果为大型空间网络理解和计算这一重要数量提供了一个框架 。

0
下载
关闭预览

相关内容

【干货书】开放数据结构,Open Data Structures,337页pdf
专知会员服务
16+阅读 · 2021年9月17日
专知会员服务
60+阅读 · 2020年3月19日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
“CVPR 2020 接受论文列表 1470篇论文都在这了
已删除
将门创投
5+阅读 · 2019年8月19日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
《pyramid Attention Network for Semantic Segmentation》
统计学习与视觉计算组
44+阅读 · 2018年8月30日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
暗通沟渠:Multi-lingual Attention
我爱读PAMI
7+阅读 · 2018年2月24日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2021年11月9日
Arxiv
0+阅读 · 2021年11月9日
Arxiv
0+阅读 · 2021年11月8日
Arxiv
0+阅读 · 2021年11月5日
Arxiv
38+阅读 · 2020年12月2日
VIP会员
相关资讯
“CVPR 2020 接受论文列表 1470篇论文都在这了
已删除
将门创投
5+阅读 · 2019年8月19日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
《pyramid Attention Network for Semantic Segmentation》
统计学习与视觉计算组
44+阅读 · 2018年8月30日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
暗通沟渠:Multi-lingual Attention
我爱读PAMI
7+阅读 · 2018年2月24日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员