線上社交網路節點間相似性

線上社交網路中，節點與節點之間通常具有一定的相似性。根據不同的指標，可以度量節點不同方面的相似程度。

基本介紹

• 中文名：線上社交網路節點間相似性
• 外文名：node similarity in online social networks

一、定義

線上社交網路節點間相似性，描述了線上社交網路用戶之間的相似程度，根據不同的需求和定義，可以用相應的指標來進行度量，是線上社交網路分析研究的基礎。

二、基於網路半結構信息定義節點相似性

1. 基於共同鄰居數的CN指標

從網路拓撲結構角度出發，考慮兩個節點的共同鄰居數即common neighbors（CN），是基於網路半結構信息定義相似度的最簡單的方法。共同鄰居數越大，說明兩個節點越相似，越有可能在同一社團。

2. 其他6種規範化的指標

在 CN 指標的基礎上增加節點度的影響，便得到其他6 種規範的相似性指標。

（1）Salton 指標

又稱為餘弦相似性，其定義方式是兩個節點共同鄰居數比上他們各自節點度之積的平方根。

（2）Jaccard 指標

以Jaccard 的命名的相似度指標，其定義方式是兩個頂點共同鄰居數比上他們的所有鄰居數之和。

（3）Sørenson 指標

該指標用二倍兩節點的共同鄰居數比上他們的度之和得到。

（4）大度節點有利指標（hub promoted index,HPI）

兩個節點共同鄰居數比上他們中較小節點度，因此大度節點與其他節點之間更容易具有高的相似性。

（5）大度節點不利指標（hub depressed index,HDI）

與 HPI 相似，分母取兩端節點度的最大值得到。

（6）LHN-I 指標

兩個頂點共同鄰居數比上他們度之積。

三、基於網路結構信息定義節點相似性

基於網路結構信息定義的方法中常見的有Adamic-Adar Index（AA 指標）和Resource allocaion Index (RA 指標)。它們都考慮了共同鄰居的度信息，並且度小的共同鄰居節點的貢獻大於度大的共同鄰居節點的。而兩者只是在賦予節點權重上存在差異。對於兩個節點來說，他們的每一個共同鄰居對他們兩者關係的強弱的貢獻程度是不一樣的。

1. Adamic-Adar 指標

Adamic-Adar 簡稱AA，該指標根據共同鄰居的節點的度給每個節點賦予一個權重值，即為每個節點的度的對數分之一。然後把節點對的所有共同鄰居的權重值相加，其和作為該節點對的相似度值。

2. Resource Allocat

與 AA 指標定義很相似，Resource Allocation（RA）指標假設網路中每一個節點都有一定的資源，沒有直接相連的兩個節點之間通過共同鄰居作為媒介傳遞資源。每個節點都將自己的資源平均分配給它所有鄰居。把此時目標節點接受到的資源數定義為這兩個節點的相似度。

四、採用動力學方式定義節點相似性

典型採用動力學方式定義節點相似度的方法是基於隨機遊走過程而定義的相似度，它包括平均通勤時間、Cos+指標、有重啟的隨機遊走、SimRank 指標、局部隨機遊走指標等等。

1. 基於網路全局隨機遊走的相似性指標

基於網路全局隨機遊走的相似性指標有平均通勤時間、Cos+指標、有重啟的隨機遊走、SimRank 指標。比較簡單的幾種方法有：

（1）平均通勤時間（average commute time, ACT）

（2）基於隨機遊走的餘弦相似性（Cos+）

2. 基於網路局部隨機遊走的相似性指標

基於網路局部隨機遊走的相似性指標（local random，LRW），考慮了有限步數的隨機遊走過程（通常選擇的步數與網路的平均最短距離有關），其計算複雜度遠遠比全局隨機遊走的指標要低很多，運用於計算大規模網路的節點間相似性具有非常明顯的優勢。