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

有效

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

本發(fā)明公開了一種用戶周邊最具影響力社區(qū)的搜索方法，適用于大規(guī)模社交網絡中的中用戶的個性化影響力社區(qū)搜索。本發(fā)明通過僅搜索用戶周邊一定范圍內網絡，同時結合特有的搜索剪枝技術，提高了社區(qū)搜索過程的效率，對大規(guī)模社交網絡中的社區(qū)搜索技術發(fā)展具有積極意義。本發(fā)明方法輸入一個使用圖表示的社交網絡、一個查詢節(jié)點以及確定搜索范圍的影響力值。首先確定需要搜索的節(jié)點集合，然后在這個集合內展開搜索。在搜索過程中，如果當前被搜索節(jié)點構成的集合對查詢節(jié)點的影響力小于已知的最大影響力社區(qū)，則停止當前被搜索節(jié)點集合的搜索。這個過程中使用的分枝界限方法顯著提高了整個搜索過程的效率，加快了最具影響力社區(qū)的查找。

技術領域

本發(fā)明屬于計算機應用技術領域，涉及社交網絡應用中一種用戶周邊最具影響力社區(qū)的搜索方法，特別適用于大規(guī)模社交網絡中的社區(qū)搜索，例如大規(guī)模社交網絡中用戶的個性化影響力社區(qū)搜索等。

背景技術

隨著計算機網絡的普及，社交網絡應用已經進入人們的日常生活。在眾多的社交網絡應用服務中，社區(qū)(Communities)是理解社交網絡構成的基石，網絡中的社區(qū)搜索是其中一種關鍵的服務，它是許多其它服務的基礎。這些應用例如社交圈的發(fā)掘，最具影響力社區(qū)的搜索等。但由于構成社交網絡的用戶規(guī)模數以萬計，進行大規(guī)模的有效社區(qū)搜索是十分困難的。

給定一個社交網絡G(V,E)，V是這個社交網絡中所有用戶的集合，E是網絡中用戶之間的聯系(邊)。使用w(u,v)表示相鄰用戶u和v之間的傳播概率。如果不相鄰用戶v₀、v_k之間存在一條路徑那么v₀、v_k之間的傳播概率為由于v₀、v_k之間可能存在多條路徑，選取w(P)取值最大的那一條為最大影響路徑MIP(Maximum InfluencePath)。

定義社交網絡G(V,E)中的一個社區(qū)C為G的一個子圖，滿足以下三個條件：

條件Ⅰ.社區(qū)C中至少有k個用戶節(jié)點；

條件Ⅱ.社區(qū)C中的任意兩個用戶節(jié)點之間都存在一條路徑MIP，其傳播概率大于p(p是一個給定的閾值)；

條件Ⅲ.社區(qū)C是相對最大的社區(qū)，即它不被包含在其它任意社區(qū)中。

對于一個用戶節(jié)點s，一個社區(qū)對這個用戶節(jié)點的影響力定義為：

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

本發(fā)明涉及的用戶周邊最具影響力社區(qū)搜索，是指搜索用戶節(jié)點s周邊所有的社區(qū)C，比較它們對用戶節(jié)點s的影響力Pr，返回影響力最大的社區(qū)C_Max。

在一個用戶周邊最具影響力社區(qū)的搜索過程中，需要遍歷用戶周邊所有的社區(qū)，計算并比較它們的影響力，在大規(guī)模社交網絡中，搜索過程計算復雜。因此降低此類計算的復雜度具有很大的迫切性。

發(fā)明內容

本發(fā)明的目的是在于克服現有技術中的不足，針對社交網絡中用戶周邊最具影響力社區(qū)的搜索特點，提供一種用戶周邊最具影響力社區(qū)的搜索方法。本發(fā)明不需要遍歷用戶周邊的所有社區(qū)，即可返回搜索結果。

本發(fā)明解決其技術問題所采用的技術方案具體步驟如下：

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