[發明專利]社交活動網絡中種子節點篩選方法和裝置

有效

• 申請號: 201611069792.3
• 申請日: 2016-11-28
• 公開（公告）號: CN108122168B
• 公開（公告）日: 2020-11-13
• 發明（設計）人: 趙鵬鵬;吳志勇;李永坤;殷俊;鄧大付;孫龍君;王巨宏;陳偉
• 申請（專利權）人: 中國科學技術大學先進技術研究院;騰訊科技（深圳）有限公司
• 主分類號: G06Q50/00
• 分類號: G06Q50/00
• 代理公司: 廣州華進聯合專利商標代理有限公司 44224
• 代理人: 何平;鄧云鵬

1.一種社交活動網絡中種子節點篩選方法，包括：

獲取表示社交活動網絡的集合參數，所述集合參數包括用戶集合、活動集合、用戶間的關系集合和用戶與活動間的關系集合；

根據所述集合參數獲取活動類型超邊集合、超邊中除某用戶外的其余用戶組成的集合、某用戶參加的活動類型對應的超邊集合、用戶受活動的影響比例、用戶好友集合；

根據用戶受活動的影響比例得到用戶受好友的影響比例，以及根據所述用戶受好友的影響比例、用戶好友集合、用戶受活動的影響比例和超邊中除某用戶外的其余用戶組成的集合和某用戶參加的活動類型對應的超邊集合得到節點隨機游走時的轉移概率；

獲取候選節點集合及所述候選節點集合的影響力；

獲取用戶受到的總的影響變量，根據用戶受到的總的影響變量、用戶集合減去候選節點集合后剩余用戶集合中節點間的轉移概率、用戶集合減去候選節點集合后剩余用戶集合中節點到候選節點集合中的節點的轉移概率估算所述候選節點集合的影響力值；

通過貪心算法迭代估算得到影響力值最大的候選節點，在每一次迭代后，將候選節點集合中各候選節點相對于所述候選節點集合的影響力的增量進行更新；

記錄第一次迭代過程中的隨機游走的軌跡，采用第一次迭代的隨機游走的軌跡對剩余(k-1)次數迭代進行迭代重用，其中，k為種子節點的個數。

2.根據權利要求1所述的方法，其特征在于，所述獲取用戶受到的總的影響變量，根據所述用戶受到的總的影響變量、用戶集合減去候選節點集合后剩余用戶集合中節點間的轉移概率、用戶集合減去候選節點集合后剩余用戶集合中節點到候選節點集合中的節點的轉移概率估算所述候選節點集合的影響力值的步驟包括：

獲取用戶受到的總的影響變量、根據用戶受到的總的影響變量、用戶集合減去候選節點集合后剩余用戶集合中節點間的轉移概率、用戶集合減去候選節點集合后剩余用戶集合中節點到候選節點集合中的節點的轉移概率構建候選節點集合對所選節點影響力值的多項式；

獲取所述多項式的前L項，采用所述多項式前L項估算所述候選節點集合的影響力值；且滿足多項式與多項式的前L項之差在預設范圍內，L為自然數。

3.根據權利要求2所述的方法，其特征在于，所述采用所述多項式前L項估算所述候選節點集合的影響力值的步驟包括：

從選擇的第一節點出發開始隨機游走，并記錄第一變量；

判斷是否達到L步，若是，則判斷R次隨機游走是否結束，若R次隨機游走結束，則返回第一變量的值，若R次隨機游走未結束，則繼續執行從選擇的第一節點出發開始下一次隨機游走；

若未達到L步，則選擇一條超邊，再從所述超邊中選擇一個節點；

判斷所述節點是否屬于候選節點集合，若是，則停止隨機游走，將第一變量增加用戶受到的總的影響變量的步數次冪與R的比值，再執行判斷所述R次隨機游走是否結束的步驟；

若所述節點不屬于候選節點集合，則執行判斷是否達到L步的步驟，R為自然數。

4.根據權利要求1所述的方法，其特征在于，所述方法還包括：

獲取第一用戶向第二用戶施加影響時的權重、第一用戶通過活動對第二用戶施加影響的權重、活動對第二用戶施加影響的權重；

根據所述用戶受到的總的影響變量、用戶受好友的影響比例、第一用戶向第二用戶施加影響時的權重、第一用戶通過活動對第二用戶施加影響的權重、活動對第二用戶施加影響的權重得到第一用戶對第二用戶的影響力大小。