如何测量图中两个顶点之间的相似性或距离?
有两种类型的测量方法，例如测地距离和基于随机游走的距离。
测地距离 − 图中两个顶点之间距离的一个简单度量是顶点之间的最短路径。通常，两个顶点之间的测地距离是顶点之间最短路径的多个边的长度。对于图中未链接的两个顶点，测地距离表示为无穷大。
利用测地距离，它可以表示各种有用的测量方法，用于图分析和聚类。给定一个图 G = (V, E)，其中 V 是顶点集，E 是边集，它可以表示如下 −
对于顶点 v ∈ V，v 的偏心率用 eccen(v) 表示，是 v 与多个顶点 u ∈ V − {v} 之间的最大测地线距离。v 的偏心率表示 v 与图中其最末端顶点的距离。
图 G 的半径是所有顶点中最小的偏心率。
即，r = min eccen(v)
v ∈ V
半径表示"最中心点"之间的距离以及图的"最远边界"。
图 G 的直径是所有顶点的最大偏心率。
即，d = max eccen(v)
v ∈ V
直径定义了一对顶点之间的最大距离。
外围顶点是产生直径的顶点。
SimRank − 基于随机游走和结构上下文的相似性 − 在各种应用中，测地距离可能不适用于计算图中顶点之间的相似性。在 SimRank 中，相似性度量取决于随机游走和图的基本框架。在数学中，随机游走是一种包含连续随机过程的轨迹。
相似度的表示方法有两种:−
如果两个用户在社交网络中拥有相同的邻居，则他们会被视为相同。这种启发式方法具有可感知性，因为两个从大量共同好友那里获得推荐的人会做出相同的决策。这种相似度取决于顶点的局部结构(即邻域)，被称为基于结构上下文的相似度。
假设 AllElectronics 在社交网络中向 Ada 和 Bob 发送促销数据。Ada 和 Bob 可以随机地将这些数据转发给他们在网络中的好友(或邻居)。Ada 和 Bob 之间的亲密度可以通过不同用户同时收到最初发送给 Ada 和 Bob 的促销数据的可能性来计算。这种相似性取决于网络上随机游走的可达性，因此被定义为基于随机游走的相似性。
