数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究如何在图中测量两个顶点之间的相似度或距离？
有两种类型的度量，例如测地线距离和基于随机游走的距离。
测地线距离 - 图中两个顶点之间距离的一个简单度量是顶点之间的最短路径。通常，两个顶点之间的测地线距离是指顶点之间最短路径的多条边的长度。对于图中未连接的两个顶点，测地线距离表示为无穷大。
通过利用测地线距离，它可以表示图分析和聚类的一些有用度量。给定一个图 G = (V, E)，其中 V 是顶点集，E 是边集，它可以表示以下内容 -
对于一个顶点 v ∈ V，v 的偏心率，表示为 eccen(v)，是 v 与 V - {v} 中的其他顶点 u 之间的最大测地线距离。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 的促销数据的可能性来计算。这种类型的相似性取决于网络上的随机游走可达性，因此被定义为基于随机游走的相似性。
1K+ 浏览量
