知识卡片
广度优先枚举全部最短路径
要算中介中心性,先得知道每对节点之间有哪些最短路径,而不只是最短距离。做法是以 from_user 为根做广度优先搜索:用双端队列 frontier 存放 (prev_user, user) 对,队列先进先出,保证先发现的那一层先被处理,因此第一次到达某节点的路径长度就是最短长度。关键在于并列与去重:新路径比已知最短更短就替换,等长就作为“另一条同样短的路”追加,更长则丢弃。因为每个节点只从上一层扩展,多条等长路径会被完整收集,又不会膨胀成所有可能路径。边界是它只覆盖起点可达的部分,不连通图需要另行说明;而且每个节点都要单独跑一次 BFS,n 个节点共 n 次,时间与内存随规模迅速上升,这正是中介中心性停留于小图的原因。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第22章 网络分析 · 查看原书依据
在探索该图时,每当我们发现尚不知道相关最短路径的新邻居节点时,便将它们添加到队列的末尾以供以后探索,并用当前用户作为 prev_user。
参考来源
- 位置:《数据科学入门(第2版)》第22章 网络分析(源文件:extracted/数据科学入门(第2版)/_epub-src/OEBPS/Text/0026.xhtml)
- 结论依据:原文这一段直接给出本卡的核心判断:「在探索该图时,每当我们发现尚不知道相关最短路径的新邻居节点时,便将它们添加到队列……」
- 原始内容:在探索该图时,每当我们发现尚不知道相关最短路径的新邻居节点时,便将它们添加到队列的末尾以供以后探索,并用当前用户作为 prev_user。