[發明專利]一種節點重要性排序的方法和系統

有效

• 申請號: 201410597128.0
• 申請日: 2014-10-29
• 公開（公告）號: CN105630800B
• 公開（公告）日: 2021-01-15
• 發明（設計）人: 呂琳媛;陳川;易玲玲;岳亞丁;賀鵬;王巨宏;管剛;任曉龍;佘莉;王澎;張婷
• 申請（專利權）人: 杭州師范大學;騰訊科技（深圳）有限公司
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/9536;G06Q50/00
• 代理公司: 深圳市深佳知識產權代理事務所(普通合伙) 44285
• 代理人: 王仲凱

1.一種應用于社交網絡中的節點重要性排序方法，其特征在于，所述方法包括：

獲取拓撲網絡中各個節點之間交互的節點日志信息；所述拓撲網絡中各個節點對應于社交網絡中的各個用戶，所述各個節點之間交互的節點日志信息用于記錄所述各個用戶之間的交互行為，所述交互行為包括：交互雙方的節點名稱、交互行為類型以及交互時間；所述交互雙方的節點名稱包括：交互的兩個用戶中交互發起方的標識號ID和交互接收方的ID；所述交互行為類型至少包括點贊與關注中的至少一種；

根據所述節點日志信息對所述拓撲網絡中的所有節點添加權值和方向，得到有向含權網絡，其中包括：根據交互雙方的兩個用戶之間交互行為的方向性，確定所述有向含權網絡中有向邊的方向，并根據所述兩個用戶之間交互行為的次數或頻率來設置所述有向邊的權值；

在所述有向含權網絡中加入背景節點，得到加入有所述背景節點的有向含權網絡，所述背景節點與所述有向含權網絡中原有的所有節點建立有雙向鏈接關系；

在加入有所述背景節點的有向含權網絡G′中原有的所有節點上各分配一單位的資源，則分配所述資源的時刻為在加入有所述背景節點的有向含權網絡G′上所述資源開始擴散的初始時刻；

通過如下方式計算節點x指向節點y之間的邊時產生的轉移概率矩陣P(x,y)：

其中，所述w^a(x,y)為所述節點x與所述節點y之間的邊的權重w(x,y)的a次方，所述a為可調節參數，其取值為0至1之間的數值，所述N為所述有向含權網絡中原有的所有節點的個數，所述節點x和所述節點y為所述G′中建立有邊的兩個節點；

從所述初始時刻開始，相隔預置的時間步，將所述有向含權網絡中的每個節點上分配的資源按照所述轉移概率矩陣向其指向的其它節點進行轉移，并計算資源轉移后的每個節點上的資源分布值；

隨著時間步的增加，根據所述轉移概率矩陣對每個節點上的資源分布值進行迭代，直至相鄰時間步中所述有向含權網絡中每個節點的資源數保持不變；

根據穩態時的有向含權網絡，計算所述各個節點的重要性分數，并根據所述各個節點的重要性分數對所述各個節點的重要性進行排序，以從所述社交網絡中確定出重要用戶。

2.根據權利要求1所述的方法，其特征在于，所述節點日志信息，還包括：所述交互發起方的屬性。

3.根據權利要求2所述的方法，其特征在于，所述獲取拓撲網絡中各個節點之間交互的節點日志信息之后，所述方法還包括：

對所述交互發起方的ID和所述交互接收方的ID進行匿名化處理；

對所述交互行為類型和所述交互發起方的屬性進行泛化處理。

4.根據權利要求1所述的方法，其特征在于，通過如下公式來表示所述有向含權網絡中的節點之間交互：

G＝(V,E,L,Lv,Le)；

其中，所述G為所述有向含權網絡，所述V是節點的集合，所述V＝{V₁,V₂,……,V_N}，所述N為所述有向含權網絡中所有節點的個數，所述E是邊的集合，所述E＝{(V_i,V_j,t)}，所述i＝1,2,……,N，所述j＝1,2,……,N，所述t為所述V_i和所述V_j之間存在關系的時刻，所述V_i和所述V_j為所述V中存在關系的兩個節點，所述L為標簽集，所述Lv為節點標簽函數，所述Le為邊標簽函數。

5.根據權利要求1所述的方法，其特征在于，所述隨著時間步的增加，根據所述轉移概率矩陣對每個節點上的資源分布值進行迭代，包括：

通過如下方式計算在所述時間步為t時所有節點上的資源分布向量

其中，所述為在所述時間步為(t-1)時有向含權網絡中所有節點上的資源分布向量，所述P^T為對方陣P的轉置，所述方陣P為所述有向含權網絡中所有節點之間資源的轉移概率矩陣。