[發明專利]一種用戶周邊最具影響力社區的搜索方法

有效

• 申請號: 201911296164.2
• 申請日: 2019-12-16
• 公開（公告）號: CN111177578B
• 公開（公告）日: 2022-04-15
• 發明（設計）人: 徐建
• 申請（專利權）人: 杭州電子科技大學
• 主分類號: G06F16/9536
• 分類號: G06F16/9536;G06Q50/00
• 代理公司: 杭州君度專利代理事務所(特殊普通合伙) 33240
• 代理人: 楊舟濤

1.一種用戶周邊最具影響力社區的搜索方法，其特征在于：

將一個社交網絡G(V,E)中的所有用戶節點抽象，用節點的集合V表示；用戶之間的聯系表示成兩個節點之間的邊，使用邊的集合E來表示；將兩個用戶之間的交互次數歸一化，表示成兩個節點之間的傳播概率；得到社交網絡G₁(V,E)；使用w(u,v)表示相鄰用戶u和v之間的傳播概率；如果不相鄰用戶v₀、v_k之間存在一條路徑那么v₀、v_k之間的傳播概率為由于v₀、v_k之間可能存在多條路徑，選取w(P)取值最大的那一條為最大影響路徑MIP；

對于一個用戶節點s，一個社區對這個用戶節點的影響力定義為：

Pr(s|V(C))＝1-Π_v∈V(c)(1-w_path(P_v→s)) (式1)

用戶周邊最具影響力社區搜索是指搜索用戶節點s周邊所有的社區C，比較周邊所有的社區對用戶節點s的影響力Pr，返回影響力最大的社區C_Max；

具體實現如下：

步驟(1)、確定搜索空間：

使用社交網絡G₁(V,E)作為輸入，通過迭代算法搜索用戶節點s周邊所有節點v，使得w(MIP_s→v)ε×p，其中ε是一個用戶指定的最小傳播概率值，只考慮對用戶節點s影響力大于等于ε的節點；對于εw(MIP_s→v)ε×p的節點，雖然在計算一個社區對用戶節點s的影響力時沒用，但是在確定一個社區時，對于一個社區的拓撲結構有影響，所以搜索空間需要包含這部分節點；從而確定社交網絡中，從用戶節點s出發，所有能夠以傳播概率ε×p到達的用戶節點集合V′；p是一個給定的閾值；

然后以同樣的方法確定用戶節點集合V′中任一節點到V′中其它節點的傳播概率，如果兩個節點之間的傳播概率大于p，而且這兩個節點之間沒有直接相連的邊，那么依據社區定義的條件Ⅱ，在這兩個節點之間增加一條邊，作為下個步驟中社區搜索的判斷依據；

步驟(1)結束后，得到一個子圖G′(V′,E′)，包含了用戶節點s以及與節點s的MIP傳播概率大于等于ε×p的所有用戶節點，并且根據社區的定義，對于子圖中所有MIP傳播概率大于等于ε×p的用戶節點對，如果沒有直接相連的邊，則增加這樣一條邊，傳播概率為這兩點間MIP的傳播概率。