[發明專利]一種移動社交網絡中基于K階馬爾科夫鏈的節點中心性預測方法

有效

• 申請號: 201910020960.7
• 申請日: 2019-01-09
• 公開（公告）號: CN109617742B
• 公開（公告）日: 2020-04-24
• 發明（設計）人: 周歡;陳鑫;江愷;吳桐
• 申請（專利權）人: 三峽大學
• 主分類號: H04L12/24
• 分類號: H04L12/24;H04W4/21
• 代理公司: 宜昌市三峽專利事務所 42103
• 代理人: 吳思高

1.一種移動社交網絡中基于K階馬爾科夫鏈的節點中心性預測方法，其特征在于：針對具有N個移動節點的移動社交網絡，其中i∈{1,2,...,N}；在移動社交網絡中，節點間的接觸描述為網絡連通圖G(V,E)，其中節點對i,j∈V之間的隨機接觸過程建模成連通圖中的邊e_ij∈E；假設觀測的網絡開始時間為T_s＝0,結束時間為T_e＝T；將過去的觀測時間T按照窗口大小w劃分為n＝T/w個時間窗口，基于過去的n個時間窗口的數據來預測未來的第n+1個時間窗口的節點中心性值；

節點中心性預測方法包括以下步驟：

步驟1：每個節點都利用自己的緩存記錄和其它節點的歷史接觸，包括接觸次數和接觸時間間隔，每個節點和其他節點接觸時，不僅記錄彼此的接觸情況，而且交換彼此緩存中的歷史接觸記錄，這樣每個節點就能夠得到整個網絡中節點的歷史接觸情況；

步驟2：利用緩存中存儲的接觸歷史記錄，每個節點可以構建一個時間序列網絡拓撲圖；

根據構建的時間序列網絡拓撲圖，每個節點計算在每個時間窗口內的中心性值；

步驟3：構建K階狀態轉移矩陣；

步驟4：對步驟2中得到的節點i的中心性值序列進行離散化，得到一個有限的狀態空間，表示為S；K階狀態轉移概率的馬爾可夫鏈用來估計對于所有a∈S和b∈S，其中：b＝(b₁,b₂,...,b_k)，記n_ba為狀態b在序列中跟在值a后的次數，記n_b為狀態b在序列中出現的次數，p_b,a表示從狀態b到狀態(b₂,...,b_k,a)的狀態轉移概率的估計；基于構建的K階狀態轉移矩陣，K階馬爾科夫鏈的最大似然估計量的狀態轉移概率為：

具體地，記b_i表示節點i在K階馬爾科夫鏈中的當前狀態；節點i在下一時間窗口的中心性值計算為：

2.根據權利要求1所述一種移動社交網絡中基于K階馬爾科夫鏈的節點中心性預測方法，其特征在于：步驟3包括：

基于K階馬爾科夫鏈的預測方法中，對節點中心性的預測是通過當前已知的歷史狀態信息計算其所有可能出現的狀態的概率，其中概率最大的狀態就是所求的狀態，即為預測的中心性值；狀態轉移概率矩陣是由狀態的概率組成，基于K階馬爾科夫鏈的中心性預測方法主要是對狀態轉移概率矩陣的求解；

在求解K階狀態概率轉移矩陣M時，通過距離當前時間窗口的鄰近的K個時間窗口中的中心性來預測下一個時間窗口中節點的中心性；在狀態轉移概率矩陣M中，矩陣元素表示從一個狀態d，經過k個時間單位后到達狀態e的概率，成為k步狀態轉移概率：

m_d,e＝P(X_n+1＝e|X(n-k+1,n)＝d) (2)

其中，d表示(d₀,d₁,...,d_K-1)中任意連續的K個中心性值，e表示一個獨立的中心性值；

狀態轉移矩陣M的求解是由節點的大量中心性的歷史數據而得到的，可以用節點中心性值出現過的頻率來近似其概率：

式中：N(d)表示的是歷史數據序列中某一狀態d出現的次數，即K個中心性值連續出現的次數，N(e,d)表示的是歷史數據序列中經過狀態d以后，下一個狀態為e的次數。