[發(fā)明專利]基于傳播路徑逆向追溯的信源和影響力節(jié)點定位方法

在審

• 申請?zhí)枺?/td>: 201710291104.6
• 申請日: 2017-04-28
• 公開（公告）號: CN107135153A
• 公開（公告）日: 2017-09-05
• 發(fā)明（設(shè)計）人: 楊雄;奚吉;李曙英
• 申請（專利權(quán)）人: 常州工學(xué)院
• 主分類號: H04L12/721
• 分類號: H04L12/721;H04L12/733;G06F17/30
• 代理公司: 南京知識律師事務(wù)所32207
• 代理人: 高桂珍

技術(shù)領(lǐng)域

本發(fā)明涉及一種基于傳播路徑逆向追溯的信源和影響力節(jié)點定位方法，屬于計算機網(wǎng)絡(luò)技術(shù)領(lǐng)域。

背景技術(shù)

1998年6月美國康奈爾大學(xué)的Watts及其導(dǎo)師Strogatz在《Nature》上發(fā)表了題為“小世界網(wǎng)絡(luò)的集體動力學(xué)”的文章；1999年10月Barabasi和Albert在《Science》發(fā)表了題為“隨機網(wǎng)絡(luò)中標度的涌現(xiàn)”的文章。這兩篇文章分別揭示了真實網(wǎng)絡(luò)的小世界特征和無標度性質(zhì)，為該領(lǐng)域研究奠定了堅實的理論基礎(chǔ)。無標度特性揭示了一個網(wǎng)絡(luò)中不同節(jié)點所扮演的角色可能大相徑庭，因此，識別最有影響力的節(jié)點近年來成為網(wǎng)絡(luò)科學(xué)領(lǐng)域的研究熱點，此項研究對控制疾病爆發(fā)、優(yōu)化網(wǎng)絡(luò)資源、提升電子商務(wù)廣告效應(yīng)、避免交通或Internet網(wǎng)絡(luò)大面積癱瘓、促進媒體傳播效果、預(yù)測科學(xué)網(wǎng)絡(luò)中具有潛力的論文和作者均具有重要的實際意義。目前影響力度量方法主要基于網(wǎng)絡(luò)的靜態(tài)拓撲結(jié)構(gòu)，但是真實網(wǎng)絡(luò)的拓撲結(jié)構(gòu)則是動態(tài)變化的，因此傳統(tǒng)的度量方法并不適用于真實環(huán)境；隨著大數(shù)據(jù)技術(shù)發(fā)展(獲取數(shù)據(jù)的便捷性和處理數(shù)據(jù)能力的提高)，基于數(shù)據(jù)驅(qū)動背景下的影響力節(jié)點定位技術(shù)就顯得非常重要。類似于路由器轉(zhuǎn)發(fā)數(shù)據(jù)時可獲取分組的源地址和下一跳地址，采用傳播路徑也可有效刻畫信息在社交網(wǎng)絡(luò)的傳播過程，例如新浪微博中當節(jié)點i轉(zhuǎn)發(fā)所關(guān)注鄰居好友j發(fā)布的一條熱點新聞時，該信息的傳播跳數(shù)加1，通過分析節(jié)點i的轉(zhuǎn)發(fā)記錄就可獲知該節(jié)點的上游節(jié)點(父節(jié)點)為j；以此類推，通過逆向追溯就可以定位該熱點新聞的發(fā)布源頭(信源)，同時在傳播過程中影響力節(jié)點發(fā)布的信息越容易受到“粉絲節(jié)點”關(guān)注和轉(zhuǎn)發(fā)，因此該類節(jié)點在逆向追溯過程中也更容易被發(fā)現(xiàn)。

專利申請?zhí)枮镃N201610255447.2的文獻中給出了“基于快速密度聚類的電力通信網(wǎng)節(jié)點重要性評估方法”，其通過計算節(jié)點度、緊密度、介數(shù)、將計算得到的數(shù)據(jù)歸一化輸入到快速密度聚類算法中，分析計算出電力通信網(wǎng)的節(jié)點的重要性結(jié)果。此方法使用節(jié)點的多維拓撲屬性綜合計算影響力，當網(wǎng)絡(luò)拓撲結(jié)構(gòu)動態(tài)變化時就無法有效應(yīng)用。

專利申請?zhí)枮镃N201210356136的文獻中給出了“一種基于多屬性決策的復(fù)雜網(wǎng)絡(luò)節(jié)點重要度綜合評價方法”，提出了一種基于多屬性決策的復(fù)雜網(wǎng)絡(luò)節(jié)點重要度綜合評價方法，利用網(wǎng)絡(luò)中單個節(jié)點的度中心性、介數(shù)中心性、接近中心性、結(jié)構(gòu)洞等多個指標作為該節(jié)點重要性評價的多個屬性進行綜合計算，從而確定節(jié)點在網(wǎng)絡(luò)中的重要程度。此方法同樣只適用于靜態(tài)網(wǎng)拓撲結(jié)構(gòu)。

專利申請?zhí)枮镃N201510614670.7的文獻中給出了“一種獲得社交網(wǎng)絡(luò)中影響力最大的前k個節(jié)點的方法”，根據(jù)信息的內(nèi)容將信息分類到不同類別中，采用網(wǎng)絡(luò)流模擬的方法計算相應(yīng)類別下不同節(jié)點之間的流量，通過加權(quán)平均方式計算實際的影響力得出最后節(jié)點集合。此方法從數(shù)據(jù)流驅(qū)動角度研究影響力節(jié)點定位方法，但是在計算時需要提前獲取網(wǎng)絡(luò)的整個拓撲結(jié)構(gòu)進而生成鄰接矩陣，并且該方法采用模擬流量計算節(jié)點間的流量，無法刻畫實際網(wǎng)絡(luò)的真實環(huán)境。

發(fā)明內(nèi)容

本發(fā)明的目的是克服現(xiàn)有技術(shù)中存在的不足，提供一種網(wǎng)絡(luò)數(shù)據(jù)視角下基于傳播路徑逆向追溯的信源和影響力節(jié)點定位方法，解決了現(xiàn)實網(wǎng)絡(luò)中拓撲結(jié)構(gòu)動態(tài)變化，傳統(tǒng)方法無法適應(yīng)的問題，從而最終提升了網(wǎng)絡(luò)信源和影響力節(jié)點的定位效果。

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

步驟1、利用社交網(wǎng)絡(luò)官方API抓取特定主題的數(shù)據(jù)，包括轉(zhuǎn)發(fā)該主題的節(jié)點ID、轉(zhuǎn)發(fā)時間、上游節(jié)點ID、標題內(nèi)容等；

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

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