[發明專利]一種在線社交網絡中有影響力傳播者識別與量化的方法

在審

• 申請號: 201711165911.X
• 申請日: 2017-11-21
• 公開（公告）號: CN107945036A
• 公開（公告）日: 2018-04-20
• 發明（設計）人: 胡延慶;賈寒;孫嘉辰;謝家榮;劉榮
• 申請（專利權）人: 中山大學
• 主分類號: G06Q50/00
• 分類號: G06Q50/00;G06F17/30
• 代理公司: 廣州市深研專利事務所44229
• 代理人: 劉玉穎

技術領域

本發明屬于信息領域，特別涉及一種在線社交網絡中有影響力傳播者識別與量化的方法。

背景技術

現代的在線社交網絡平臺正以其強大的傳播與交流功能逐步取代傳統媒體，成為現代人們日常生活中的重要組成部分。這些社交網絡的一個共有的特性就是它們巨大的規模。一些信息爆發式的傳播會在整個社交網絡上產生影響，這也是一些市場營銷手段的理論依據。

頂點傳播能力是指一個頂點如果傳播一個消息，最終能影響其它頂點數量的期望值。目前，該領域認為度量頂點傳播影響力需要獲取網絡的全局信息并且該領域最流行的度量算法如k-shell等都需要基于全局網絡結構來設計。但是，隨著網絡規模的增大，如現實生活中網絡可能有數以億計的節點，全局網絡結構會變得難以獲取。這就引出一個問題，通過局部網絡結構能否度量全局網絡傳播影響力。大型在線社交網絡的成員數目龐大,它們的出現對傳統社會網絡中的影響最大化算法,包括傳播模型均提出了巨大的挑戰。近年來,社會網絡中影響最大化算法再次成為研究熱點。目前研究的目標主要集中在如何擴大影響范圍同時降低算法的時間復雜度。

實證研究表明，社交網絡上的信息傳播可以用SIR家族傳播模型來進行表示。而早在2003年就被證明，SIR模型等價于網絡上的邊滲流模型。為清楚起見，下面介紹網絡上的邊滲流中最為簡單的模型。

一般將社交網絡抽象為一張有向(無向)圖G(V，E)，V代表節點的集合，每個點表示個人或組織；E代表邊的集合，每條邊表示個體之間的關系(合作、朋友、敵對等)。每個節點有兩種狀態,激活狀態(購買了某產品或接受了某觀念等)和未激活狀態(還未購買或未接受)。處于激活狀態的節點對處于未激活狀態的節點存在影響，如果這個影響導致了某個節點從未激活狀態變為激活狀態則這個過程稱為激活。某節點的鄰居節點被激活的越多，則該節點被激活的可能性就越大。新激活的節點又會影響其處于未激活狀態的鄰居節點。隨著時間的推移，越來越多的節點從未激活狀態轉變為激活狀態。整個傳播過程是不可逆的，即:一個節點可以從未激活狀態變為激活狀態，反之則不可。

對于給定的網絡，假設每條邊以概率p保留，或者說以1-p的概率去掉。顯然，p＝0意味著刪除所有邊，而p＝1就是原始的網絡。當p＜1時，原始網絡可能會分解成若干個聯通子圖(如圖1所示)。滲流理論主要集中在研究這些聯通子圖大小的分布、最大聯通子圖的大小等與p以及網絡結構的關系。滲流理論中最迷人的是相變理論：當p很小時，所有的聯通子圖都會比較小，且遠小于整個網絡的規模；當p大于某一個臨界值p_c時，會出現一個而且只有一個(不考慮鏈狀等人為構造的特殊網絡)最大的聯通子圖，這個特殊聯通子圖的規模與整個網絡的規模成正比。也就是，當網絡規模趨于無窮大時，該聯通子圖的規模與網絡規模的比值趨于一個大于0的常數，而其它子圖(包括規模第二大的)的規模與整個網絡規模的比值將趨于0。這時我們把這個最大的聯通子圖叫做巨聯通子圖(Giant Component)，p_c叫做相變點。

一個頂點的影響力或者說傳播能力天然定義為：其中，S_i表示頂點i的傳播能力，P_i(s)是從頂點i出發信息傳播范圍為s的概率。由于網絡結構的復雜性，在理論上我們非常難以計算P_i(s)，但是，雙峰分布告訴我們一個重要的事實：頂點傳播能力的天然定義公式只有最后一項(s為巨聯通子圖規模)起主導作用。從圖2可以看到，一個信息傳播開來的時候傳播范圍比沒有傳播開始的傳播范圍要大幾個數量級，這暗示：求一個頂點的期望傳播范圍時，只需考慮傳播那一項(巨聯通子圖項)，傳播不開的那些都可以忽略不計。從而我們可以得到頂點的傳播能力期望最簡單的，用一句話就能講完的物理定義：一個頂點的傳播能力，等于該頂點在最大連通子圖中的概率乘以最大連通子圖大小。其數學描述如下：

S_i＝s^∞P(i，s^∞)

由于傳播的結果只可能是兩個相態中的一個，因此只需知道一個相態的信息，就可以得知另一個相態信息。而這兩個相態中，第一個是個局域態，也即是說我們只需使用網絡局部的信息就可以獲得這個態的所有特征。同樣，一個頂點群V的傳播能力可以定義為p(V，s)為V中的結點一共可以傳播的范圍為s的概率。

在現有技術中，普通貪心算法(NGA算法)可以達到識別和量化社交網絡中有影響力傳播者的目的，但是時間復雜度非常高。