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

有效

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

1.一種廣義最大度隨機游走圖抽樣方法，包括以下步驟：

S1，在圖上隨機游走采集樣本；采集到社交網絡中的數據樣本點集S ；在圖中隨機選擇節點u設為初始節點，并且將計數器i置為1；使用作為參數生成一個幾何隨機變量并加入集合；將節點u作為，并加入樣本點集S；從節點u的鄰接節點中等概率隨機選取一個節點v；將節點v作為下一步的節點u，計數器i加1，返回采集到的樣本點集S和相應的幾何隨機變量集；循環執行直至不滿足條件；

S2，根據采集得到的樣本構造無偏估計；構造無偏估計的公式為：

其中，表示算法收集到的第i個節點，指用來表示樣本的重復次數，是一個非負整數, 其中表示節點u的度,E為期望，π^gmd指隨機游走的穩定概率分布， f指用戶感興趣的量。

2.根據權利要求1所述的廣義最大度隨機游走圖抽樣方法，其特征在于：在圖上隨機游走采集樣本的概率轉移方程如下：

P_uv代表的是從u點跳轉到v的概率,其含義是當前采集的樣本是u，那么P_uv代表下一步采集樣本v的概率，是一個非負整數。