知识卡片
最短路径不同于最小生成树
最短路径关注某起终点之间的最小距离;最小生成树关注连接全体节点时树的总边权最小,二者不是同一个目标。中介与接近中心度使用最短路径,不是靠Kruskal求一棵最小生成树;不能从MST的O(E log E)直接推出这些中心度的复杂度。原书计算考虑段把它们混在一起,需要明确纠正。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
最小生成树(minimum spanning tree)(http://bit.ly/1a1omgr)。NetworkX最小生成树算法(http://1.usa.gov/1a1omx6)实现了Kruskal的算法(http://bit.ly/1a1on3X),是计算机科学教育中很基本的一个算法。关于运行时复杂性,需要的时间为O(E logE),E代表图中边的
参考来源
- 位置:《社交网站的数据挖掘与分析(原书第2版)》第7章《7.4.3 为用户添加“关注”边来扩展兴趣图谱》(spine113;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part0102.html;u117-ch07-022)。
- 结论依据:原文在“最小生成树”附近的定义、例子或代码支撑本卡核心说明:最短路径关注某起终点之间的最小距离;最小生成树关注连接全体节点时树的总边权最小,二者不是同一个目标。边界按已读前提解释;示例未执行。
- 原始内容:最小生成树(minimum spanning tree)(http://bit.ly/1a1omgr)。NetworkX最小生成树算法(http://1.usa.gov/1a1omx6)实现了Kruskal的算法(http://bit.ly/1a1on3X),是计算机科学教育中很基本的一个算法。关于运行时复杂性,需要的时间为O(E logE),E代表图中边的