中心性:度、介数与接近中心性
中心性回答「哪个顶点更重要」。三种口径成本与含义不同:度中心性数邻居,介数中心性统计经过该顶点的最短路径占比,接近中心性取到所有顶点距离之和的倒数。
三种口径的账本
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,印证度中心性的免索引邻接口径。
一手资料
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。