《大规模分布式计算深入解析》12.1 中心性:度、介数与接近中心性

度中心性数邻居、介数看必经最短路径、接近看距离倒数;5 顶点图最大度 3,探针出度 alpha=2/beta=1/gamma=0。

中心性:度、介数与接近中心性

中心性回答「哪个顶点更重要」。三种口径成本与含义不同:度中心性数邻居,介数中心性统计经过该顶点的最短路径占比,接近中心性取到所有顶点距离之和的倒数。

三种口径的账本

graph 用例 1、6:5 顶点 5 边图顶点 1 度数 3、最大度 3。原生探针沿关系指针计数出度:alpha=2、beta=1、gamma=0——度数只遍历邻接,O(度数)。介数要做全源最短路径:星形图中心顶点是全部最短路径必经点,介数最高。接近中心性要顶点间距离,BFS 层数(graph 用例 7:源点 0 层 0、顶点 1 层 1、顶点 4 层 2)是天然输入。

对齐卷十:打分聚合

卷十打分把文档特征聚合为可排序分数;中心性把图结构特征聚合为顶点分数。同样的取舍:度中心性便宜但有偏,介数全局但需枚举顶点对最短路径,分布式下通信量 ∝ 路径枚举;接近中心性在连通图上计算开销最大。

验证

从卷十一实验包 解包,graph 用例 1、6 验证度数计数与最大度 3;用例 7 验证 BFS 层数作为接近中心性的距离输入;原生探针 neo4j-probe.sh 沿关系指针计数出度 alpha=2、beta=1、gamma=0,印证度中心性的免索引邻接口径。

一手资料

卷十一目录 · 系列导读与实验

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图