基於傳播路徑逆向追溯的信源和影響力節點定位方法與流程

2023-05-01 14:52:41

本發明涉及一種基於傳播路徑逆向追溯的信源和影響力節點定位方法，屬於計算機網絡技術領域。

背景技術：

1998年6月美國康奈爾大學的watts及其導師strogatz在《nature》上發表了題為「小世界網絡的集體動力學」的文章；1999年10月barabasi和albert在《science》發表了題為「隨機網絡中標度的湧現」的文章。這兩篇文章分別揭示了真實網絡的小世界特徵和無標度性質，為該領域研究奠定了堅實的理論基礎。無標度特性揭示了一個網絡中不同節點所扮演的角色可能大相逕庭，因此，識別最有影響力的節點近年來成為網絡科學領域的研究熱點，此項研究對控制疾病爆發、優化網絡資源、提升電子商務廣告效應、避免交通或internet網絡大面積癱瘓、促進媒體傳播效果、預測科學網絡中具有潛力的論文和作者均具有重要的實際意義。目前影響力度量方法主要基於網絡的靜態拓撲結構，但是真實網絡的拓撲結構則是動態變化的，因此傳統的度量方法並不適用於真實環境；隨著大數據技術發展(獲取數據的便捷性和處理數據能力的提高)，基於數據驅動背景下的影響力節點定位技術就顯得非常重要。類似於路由器轉發數據時可獲取分組的源地址和下一跳地址，採用傳播路徑也可有效刻畫信息在社交網絡的傳播過程，例如新浪微博中當節點i轉發所關注鄰居好友j發布的一條熱點新聞時，該信息的傳播跳數加1，通過分析節點i的轉發記錄就可獲知該節點的上遊節點(父節點)為j；以此類推，通過逆向追溯就可以定位該熱點新聞的發布源頭(信源)，同時在傳播過程中影響力節點發布的信息越容易受到「粉絲節點」關注和轉發，因此該類節點在逆向追溯過程中也更容易被發現。

專利申請號為cn201610255447.2的文獻中給出了「基於快速密度聚類的電力通信網節點重要性評估方法」，其通過計算節點度、緊密度、介數、將計算得到的數據歸一化輸入到快速密度聚類算法中，分析計算出電力通信網的節點的重要性結果。此方法使用節點的多維拓撲屬性綜合計算影響力，當網絡拓撲結構動態變化時就無法有效應用。

專利申請號為cn201210356136的文獻中給出了「一種基於多屬性決策的複雜網絡節點重要度綜合評價方法」，提出了一種基於多屬性決策的複雜網絡節點重要度綜合評價方法，利用網絡中單個節點的度中心性、介數中心性、接近中心性、結構洞等多個指標作為該節點重要性評價的多個屬性進行綜合計算，從而確定節點在網絡中的重要程度。此方法同樣只適用於靜態網拓撲結構。

專利申請號為cn201510614670.7的文獻中給出了「一種獲得社交網絡中影響力最大的前k個節點的方法」，根據信息的內容將信息分類到不同類別中，採用網絡流模擬的方法計算相應類別下不同節點之間的流量，通過加權平均方式計算實際的影響力得出最後節點集合。此方法從數據流驅動角度研究影響力節點定位方法，但是在計算時需要提前獲取網絡的整個拓撲結構進而生成鄰接矩陣，並且該方法採用模擬流量計算節點間的流量，無法刻畫實際網絡的真實環境。

技術實現要素：

本發明的目的是克服現有技術中存在的不足，提供一種網絡數據視角下基於傳播路徑逆向追溯的信源和影響力節點定位方法，解決了現實網絡中拓撲結構動態變化，傳統方法無法適應的問題，從而最終提升了網絡信源和影響力節點的定位效果。

按照本發明提供的技術方案，所述基於傳播路徑逆向追溯的信源和影響力節點定位方法包括以下步驟：

步驟1、利用社交網絡官方api抓取特定主題的數據，包括轉發該主題的節點id、轉發時間、上遊節點id、標題內容等；

步驟2、通過抓取的數據，針對信息進行逆向路徑追溯。給定離散任意時刻t，從抓包數據中時間戳為t時刻轉發該特定信息的節點開始追溯；若t時刻節點i轉發鄰居j發布的信息，則定義t-1時刻節點j已發布該信息並且j為節點i的上遊節點，同時節點i一旦轉發後未來將不再重複轉發該信息；以此類推，當t＝0時刻發布該信息的節點則為信源節點。為方便定位影響力節點，傳播路徑逆向追溯過程中每個中間節點均設置了計數器(counter)，一旦節點j被下遊節點i追溯到，則節點j計數器值加1；

步驟3、當追溯結束時，通過每個節點的累加計數器值定位影響力節點。影響力節點發布的信息容易受到「粉絲節點」關注和轉發，因此影響力節點在傳播路徑追溯過程中也會更多地被下遊節點所追溯，從而增加該節點的計數器值。需要說明的是網絡中可能具有多個影響力節點，所以可以通過設定門限值或按照計數值降序排列的前n位節點進行定位。

步驟4、定位信源節點。傳播路徑逆向追溯過程中，若t＝1時刻節點i轉發鄰居j發布的信息，說明t＝0時刻j已經發布該信息，則j為信源節點。在社交網絡中存在多個信源同時發布同一條熱點信息的情況，因此追溯過程最終可能會定位到多個信源，並且一個信源節點也可能被下遊節點多次追溯。為找到具有影響力的信源，可根據信源被追溯的權重次數進行定位，一個信源被追溯的次數越多，說明該信源發布的信息對網絡產生了越大的影響力。

本發明的有益效果如下：

若由於採集數據不完整導致無法定位初始信源，則利用節點計數器值和發布信息的時間戳找到距離信源最近的影響力節點，通過該影響力節點查找距離2跳範圍內的鄰居。因為信源並不一定就是影響力節點，信源發布的信息往往需要通過影響力節點才能有效擴散，若有鄰居比該影響力節點更早發布信息，則定位該鄰居節點為疑似信源。數據驅動的逆向追溯信源和影響力節點定位方法，不需要預先知道社交網絡的拓撲結構，可以非常靈活地適應現實網絡中拓撲結構動態變化的實際情形，克服了傳統方法無法適應的問題，能夠緊密結合大數據發展的時代背景，對網絡中海量數據進行分析處理，挖掘出這些海量數據蘊含的價值，從而最終提升網絡信源和影響力節點的定位效果。

附圖說明

圖1是本發明的流程圖。

圖2是實施例中按照本發明進行信源和影響力節點定位的示意圖。圖中a和o為信源節點，c、d、j、i為影響力節點。

圖3是社交網絡中信息的分享轉發率曲線示意圖。

具體實施方式

下面結合附圖和實施例對本發明作進一步說明。

如圖1所示，本發明所述的基於傳播路徑逆向追溯的信源和影響力節點定位方法，其包括以下步驟：

步驟1、利用社交網絡官方api抓取特定主題的數據，包括轉發該主題的節點id、轉發時間、上遊節點id、標題內容等；例如使用r、python編寫爬蟲程序訪問http://open.weibo.com/抓取新浪微博數據，回調地址改為127.0.0.1方便本地採集數據；

步驟2、通過抓取的數據，針對信息進行逆向路徑追溯。給定離散任意時刻t，從抓包數據中時間戳為t時刻轉發該特定信息的節點開始追溯；若t時刻節點i轉發鄰居j發布的信息，則定義t-1時刻節點j已發布該信息並且j為節點i的上遊節點，同時節點i一旦轉發後未來將不再重複轉發該信息；以此類推，當t＝0時刻發布該信息的節點則為信源節點。為方便定位影響力節點，傳播路徑逆向追溯過程中每個中間節點均設置了計數器(counter)，一旦節點j被下遊節點i追溯到，則節點j計數器值加1；

步驟3、當追溯結束時，通過每個節點的累加計數器值定位影響力節點。影響力節點發布的信息容易受到「粉絲節點」關注和轉發，因此影響力節點在傳播路徑追溯過程中也會更多地被下遊節點所追溯，從而增加該節點的計數器值。需要說明的是網絡中可能具有多個影響力節點，所以可以通過設定門限值或按照計數值降序排列的前n位節點進行定位。

步驟4、定位信源節點。傳播路徑逆向追溯過程中，若t＝1時刻節點i轉發鄰居j發布的信息，說明t＝0時刻j已經發布該信息，則j為信源節點。在社交網絡中存在多個信源同時發布同一條熱點信息的情況，因此追溯過程最終可能會定位到多個信源，並且一個信源節點也可能被下遊節點多次追溯。為找到具有影響力的信源，可根據信源被追溯的權重次數進行定位，一個信源被追溯的次數越多，說明該信源發布的信息對網絡產生了越大的影響力。若無法定位初始信源，則利用節點計數器值和發布信息的時間戳找到距離信源最近的影響力節點，通過該影響力節點查找距離2跳範圍內的鄰居。因為信源並不一定就是影響力節點，信源發布的信息往往需要通過影響力節點才能有效擴散，若有鄰居比該影響力節點更早發布信息，則定位該鄰居節點為疑似信源。

下面結合圖2和圖3來闡述本發明一個具體實施例。

(1)首先定義無向無權圖g＝{v,e},v表示圖中節點，e表示邊。令vi(t)＝1表示節點i在t時刻轉發或接收信息，vi(t)＝0表示節點i在t時刻沒有轉發或接收信息；設節點的狀態可以從狀態「0」變為「1」，但是不能從狀態「1」變為「0」；且一旦轉發或接收後將不再重複轉發或接收該信息。令a和o為信源節點,即va(0)＝vo(0)＝1，實施例中使用ic獨立級聯模型進行信息傳播，網絡節點被分成兩類：激活節點和未激活節點。激活節點(vi(t)＝1)表示已經接收或轉發信息的節點，未激活節點表示尚未接收或轉發信息的節點。假設t時刻已有一些處於激活狀態的節點u，此時u將去嘗試激活處於未激活狀態的鄰居節點v；但是u只有一次機會去激活v，若成功則在t+1時刻v變為激活節點，v重複上述過程激活鄰居；一旦失敗則u永遠不再激活v，該過程持續到沒有可以激活的節點則停止傳播。獨立級聯模型符合實際網絡中信息的傳播機制，例如新浪微博中一旦節點u激活鄰居節點v失敗，則說明節點v對u發布的信息不感興趣，未來v也不會再轉發節點u的該條信息。

(2)如圖2所示，a和o為信源節點。設β為相鄰節點之間的傳播概率，β∈[0,1]，為了闡述方便，我們假設β＝1。從圖2可知當t＝4時，網絡中的所有節點都能接收到信源a和o發布的信息。定義從t＝4時進行逆向路徑追溯，vp(4)＝vq(4)＝vr(4)＝1,通過追溯節點p,q,r的轉發記錄，可以發現它們轉發的信息來自上遊節點i,即prev(vp)＝prev(vq)＝prev(vr)＝vi,並且vi(3)＝1。由於節點i被下遊節點p,q,r追溯了3次，因此節點i的計數器為3，即vi$counter＝3。

需要說明的是，雖然節點j可通過路徑a→c→d→e→k→j接收到信源a的信息，但是由於o也是信源並且傳播的路徑更短，因此節點j在t＝1時就可收到並轉發該信息(vj(1)＝1)，從而忽略了後續來自信源a的消息。

(3)按照上述步驟追溯結束時，通過每個節點的累加計數器值定位影響力節點。設定門限值θ＝3，vj$counter＝4、vi$counter＝vd$counter＝vc$counter＝3、va$counter＝2、vo$counter＝1；因此定位影響力節點為c,d,i,j。從圖3可知c,d,i,j四個節點對信息的接收轉發將導致分享轉發率曲線的上升，說明這四個節點擁有大量的粉絲節點，有助於信息在網絡中的傳播擴散。在t＝1時節點c和j就可收到並轉發信息，t＝3時節點i收到並轉發信息，從圖3可以看到雖然隨著時間推移導致熱點消息的整體分享轉發趨勢逐漸下降，但是節點i由於具有較多的鄰居仍然會導致局部分享轉發率曲線的上升。

(4)社交網絡中存在多個信源同時發布同一條熱點信息的情況，因此追溯過程最終可能會定位到多個信源。如圖2所示，當追溯結束時va(0)＝vo(0)＝1且va$counter＝2、vo$counter＝1。為找到具有影響力的信源，可根據信源被追溯的權重次數進行定位，顯然在圖2中節點a相對於節點o更具影響力。

但是在一些特殊情況如節點故意隱瞞信息來源或聲稱自己就是該信息的發布者時，則無法通過逆向追溯直接定位初始信源。這時可以利用節點計數器值和發布信息的時間戳找到距離信源最近的影響力節點，通過查找該影響力節點距離2跳範圍內的鄰居來定位疑似的信源節點。設從節點u去往節點v的有向路徑為p,傳播距離為t步(跳)，則有向路徑p可用從u去往v的中間節點按序表示，即u＝q0→q1→…→qt＝v。節點v能夠被u激活的概率為由於級聯模型傳播概率通常設置為區間[0.01,0.1]，因此節點v能夠被u經過t步激活的最大概率為10-t，例如當t＝3時v可以被u激活的最大概率只有0.001，所以可將節點u在t≥3時激活的節點數忽略不計，只考慮2跳範圍內的鄰居來定位信源。如圖2和圖3所示，節點c和j是影響力節點中最早轉發信息的兩個節點(vc(1)＝vj(1)＝1)，以節點c為例查找距離2跳範圍內的鄰居，可以發現ve(3)＝vi(3)＝vh(3)＝1,vd(2)＝vg(2)＝vf(2)＝1,vb(1)＝1,va(0)＝1；由於節點a發布信息的時間早於影響力節點c，因此可以認為a為信源節點。

上述過程也可以迭代使用，例如節點i故意隱瞞信息來源時，查找該節點距離2跳範圍內的鄰居可以發現節點c更早於i轉發信息，並且也可發現節點c是影響力節點，重複上面步驟直到定位信源a。

本發明首先採集網絡數據；然後針對特定的一條信息進行逆向路徑追溯，更新傳播路徑節點的計數器值，並最終通過節點計數器定位影響力節點；最後當逆向追溯不可實現時，利用節點計數器值和發布信息的時間戳找到距離信源最近的影響力節點，通過查找該影響力節點距離2跳範圍內的鄰居來定位信源，最終實現數據驅動下的信源和影響力節點定位。本發明解決了現實網絡中拓撲結構動態變化，傳統影響力節點定位方法無法適應的問題，最終提升了網絡信源和影響力節點的定位效果。

以上是本發明的較佳實施例而已，並非對本發明作任何形式上的限制，凡是依據本發明的技術實質對以上實施例所做的任何簡單修改、等同變化與修飾，均屬於發明技術方案的範圍內。