[發明專利]一種廣義最大度隨機游走圖抽樣方法

有效

• 申請號: 201410749244.X
• 申請日: 2014-12-09
• 公開（公告）號: CN104462374B
• 公開（公告）日: 2018-06-05
• 發明（設計）人: 李榮華;邱宇軒;毛睿;秦璐;金檀;蔡濤濤
• 申請（專利權）人: 深圳大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06Q50/00
• 代理公司: 深圳市興科達知識產權代理有限公司 44260
• 代理人: 王翀

本發明公開一種廣義最大度隨機游走圖抽樣算法，在圖上隨機游走采集樣本；根據采集得到的樣本構造無偏估計；能夠有效地平衡RW算法的“大偏差問題”以及MD算法的“重復樣本問題”，從而提升了從網絡中采集樣本點的整體效率。

技術領域

本發明屬于大圖數據挖掘技術領域，尤其涉及一種廣義最大度隨 機游走圖抽樣方法。

背景技術

近年來，在線社交網絡分析在學術界和工業界都引起了廣泛關 注。在所有在線社交網絡分析的相關研究中，一個最為基本的研究問 題是估計社交網絡中的節點性質以及整個社交網絡的拓撲特性。然 而，由于很多在線的社交網絡公司，例如騰訊、新浪微博、Facebook 以及Twitter等，都沒有向第三方發布其社交網絡的圖譜數據，并且 整個社交圖譜數據的大小對于第三方來說往往都是未知的。因此，廣 大從事社交網絡分析的研究者和開發者都面臨一個非常困難的數據 采集問題。這里的主要難點在于，如何設計和開發出一種簡便的方法 來從一個“對于研究者不可見”的社交網絡中提取出均勻的圖節點樣 本。

為了解決這一問題，目前在學術界有很多基于爬蟲技術的網絡抽 樣方法被提出并廣泛使用。可以把這些方法分為兩大類：一類是基于 圖遍歷的方法,另一類則是基于隨機游走的方法。基于圖遍歷的方法 主要是應用廣度優先搜索(BFS，breadth-firstsearch)或者深度優 先搜索(DFS，depth-first search)采集節點。然而，這一類方法 的主要缺點是在采集節點的過程中，算法會偏向于度比較高的節點， 這顯然與需要均勻的節點樣本的目標不相符。并且，這一類算法對度 比較高的節點偏向多少無法從理論上刻畫，因此很難糾正這一偏向， 進而無法得到均勻的節點樣本。目前，這一類算法逐漸被學術界和工 業界棄用。基于隨機游走的算法很好地解決了基于圖遍歷的算法的缺 陷，它們可以直接生成無偏的節點樣本，或者生成有偏但是偏向性已 知的節點樣本，故而這類算法在圖采樣中廣受歡迎。目前有兩種非常 流行的基于隨機游走的圖抽樣算法。第一種算法是重新加權的隨機游 走算法，稱之為RW(re-weighted random walk)算法；第二種算法 是最大度隨機游走算法，稱之為MD(maximum-degree random walk) 算法。下面簡要介紹這兩種算法。

將網絡抽象成一個圖G＝(V,E)，其中n＝|V|代表節點的個數，m＝|E| 代表邊的條數。令N(u)為節點u∈V的所有鄰接節點的集合，d_u＝|N(u)| 表示節點u的度。令f:V→R是一個定義在節點集V上的實值函數，表 示節點u的某種特性的值，例如節點的度，或者節點的某個屬性值。 在估計網絡特性的問題中，目標是估計整個網絡中所有節點的f(u) 值的平均值，記為這里的π^u＝[1/n,...,1/n]表示均勻分 布。例如，如果定義f(u)＝d_u,那么代表的是圖G中節點度的平均 值。如果定義則表示的是圖G中節點 的度分布，這里是一個指示函數，如果d_u＝d，則否則