資料結構
網路
關係資料庫管理系統
作業系統
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+ 瀏覽量
