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

有效

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

本發明公開了一種基于隨機游走訪問頻數的入度信息估計方法，包括步驟1：從待估計入度信息的有向網絡中隨機選擇隨機游走的種子節點，所述種子節點為網絡的任意節點，然后實施隨機游走，隨機游走的后續節點由當前節點的鄰居節點隨機選出；步驟2：在隨機游走過程中，記錄各個節點i被重復訪問的次數x_i；步驟3：當實施行走的步數n與網絡的節點數N相等時，統計每個節點i被訪問的次數x_i；步驟4：根據所統計的每個節點i被訪問的次數估計入度信息并輸出；本發明針對有向網絡中的無向性不強的問題時，通過統計隨機游走過程中每個節點被訪問的次數進行入度信息的估計，其估計出的入度信息的誤差較小，且估計的效率更高。

技術領域

本發明屬于社會網絡拓撲信息估計領域，尤其涉及一種基于隨機游走訪問頻數的入度信息估計方法及系統。

背景技術

當前在線社交網絡規模巨大，為研究者們提供了研究復雜網絡、真實群體特征、行為的平臺。而又由于其規模巨大，研究者們無法進行全網絡信息收集或獲取用于分析。一般地，只能通過隨機游走的方式，獲取網絡的部分信息。利用獲取的網絡部分信息去恢復網絡的拓撲結構是后續進行復雜網絡分析、群體特征分析等的基礎。但是怎樣通過獲取的網絡部分信息去恢復網絡拓撲結構中重要的一個環節是對網絡入度分布的估計，因為在隨機游走過程中，入度信息是潛在的、隱藏了。有了入度信息的估計，即網絡入度分布的估計，才能進行網絡拓撲結構的恢復，從而進一步得出全網絡的特征。

傳統的入度信息估計方法，利用隨機游走過程中能夠收集到的出度信息，假設當網絡中節點的入度邊和出度邊高度對稱時，即網絡無向性程度較高時(無向性即無向邊的比例)，可以得到基于出度信息的估計方法EST_out：

其中，表示網絡的入度分布估計，表示網絡的出度分布的估計，q_d(k^out)是隨機游走抽樣獲取樣本的出度分布。

然而對于在線社交網絡來說，用戶之間的關系或行為是有方向的，例如，“關注行為”可以是“關注”或“被關注”兩種關系；“選舉行為”可以是“選舉”或“被選舉”關系等等。由此，網絡的邊可以分為“入度邊”和“出度邊”，用于分別描述“指向”該節點的關系(邊)和該節點指向其他節點的關系(邊)。并且在大多數情況下，有向網絡中的無向性不強。由此，利用式(1)得到的入度信息估計會引起很大的偏差，因此需要去解決有向網絡中的入度信息估計問題。

發明內容

本發明要解決的技術問題是：由于現有技術中對于網絡入度信息的估計方法是在網絡無向性程度較高時通過出度信息進行的估計方法，該方法在應用到有向性較高的社交網絡中時，所估計出來的入度信息誤差較大，從而不能很好地通過入度信息來了解網絡中用戶行為、恢復網絡拓撲結構，提出了一種對于有向網絡來說入度信息估計誤差較小的基于隨機游走訪問頻數的入度信息估計方法。

為解決該問題，本發明采用的技術方案是：

一種基于隨機游走訪問頻數的入度信息估計方法，包括以下步驟：

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

步驟2：在隨機游走過程中，記錄各個節點i被重復訪問的次數x_i；

步驟3：當實施行走的步數n與網絡的節點數N相等時，統計每個節點i被訪問的次數x_i；

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

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