[發明專利]基于隨機游走訪問頻數的入度信息估計方法及系統

有效

• 申請號: 201811632238.0
• 申請日: 2018-12-29
• 公開（公告）號: CN109657160B
• 公開（公告）日: 2023-01-06
• 發明（設計）人: 呂欣;陳灑然;劉忠;譚躍進;秦爍;蔡夢思;黃格;肖時耀
• 申請（專利權）人: 中國人民解放軍國防科技大學
• 主分類號: G06F16/9536
• 分類號: G06F16/9536;G06Q50/00
• 代理公司: 長沙國科天河知識產權代理有限公司 43225
• 代理人: 董惠文

1.一種基于隨機游走訪問頻數的復雜網絡入度信息估計方法，其特征在于：包括以下步驟：

步驟1：從待估計入度信息的有向網絡中隨機選擇隨機游走的種子節點，所述種子節點為網絡的任意節點，然后實施隨機游走，隨機游走的后續節點由當前節點的鄰居節點隨機選出；

步驟2：在隨機游走過程中，對于任意的一個入度為的節點i，近似地將該節點i被訪問的過程用n次伯努利實驗進行建模:

其中X_i代表節點i在隨機游走中被訪問次數的隨機變量，x_i為各個節點i被重復訪問的次數，p_i是節點i在隨機游走中可能被訪問的概率，X_i的期望表示為：

E[X_i]=np_i，

在有向網絡中，任意節點i的入樣概率p_i近似地與它的入度成正比，即

kⁱⁿ表示網絡的平均入度，N為網絡的節點數；

則X_i的期望表示為：

步驟3：當實施行走的步數n與網絡的節點數N相等時，則X_i的期望表示為：

表示在隨機游走過程中節點被訪問的次數近似地與它的入度成正比；

步驟4：統計每個節點i被訪問的次數x_i，根據所統計的每個節點i被訪問的次數估計入度信息p_d(x_i)并輸出；

其中m_i是隨機游走過程中被訪問了x_i次的節點的數量。

2.一種基于隨機游走訪問頻數的復雜網絡入度信息估計系統，其特征在于：包括處理器，以及與所述處理器連接的存儲器，所述存儲器存儲有基于隨機游走訪問頻數的入度信息估計方法的程序，所述基于隨機游走訪問頻數的入度信息估計方法的程序被所述處理器執行時實現權利要求1所述方法的步驟。