[發明專利]基于傳播路徑分析的獨立級聯模型的影響力最大化方法

在審

• 申請號: 201710568222.7
• 申請日: 2017-07-11
• 公開（公告）號: CN107392365A
• 公開（公告）日: 2017-11-24
• 發明（設計）人: 劉維;陳昕;吳薔梅
• 申請（專利權）人: 揚州大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/00
• 代理公司: 南京中新達專利代理有限公司32226
• 代理人: 孫鷗,朱杰

技術領域

本發明屬于應用于復雜網絡中利用獨立級聯模型識別影響力最大化的節點的方法，特別涉及基于傳播路徑分析的獨立級聯模型的影響力最大化方法。

背景技術

復雜網絡的重要節點是指相比網絡其他節點而言，能夠在更大程度上影響網絡的結構與功能的一些特殊節點。近年來，識別有影響力節點受到越來越廣泛的關注，不僅因為其重大的理論研究意義，更因為其廣泛的實際應用價值。

隨著互聯網的發展，我們的日常生活中到處充斥著信息，搜索信息使我們每天必做的工作。如何有效的找到所需要的信息，或者看到目前的新聞熱點，除了通過搜索引擎搜索，也可以通過查看網絡中influential spreader發布的信息。很多社會網絡，如twitter、delicious允許用戶交流，發布信息。識別influential user可以有效的發布信息，使得信息的傳播廣度、深度都有所提高。不同的網絡發布的信息不同，運營方式也不同，如中國的新浪微博或騰訊微博，這樣的互動平臺，每個人都可以在上面發布信息，可以是自己的關注也可以是目前的社會熱點，用戶之間還存在著互動，每個用戶自己的影響力不同，其發布的信息傳播的廣度，是否會爆發(大范圍的傳播)，爆發的時間，持續的時間都有所不同。具有較強影響力的用戶，發布的信息很快會被人們轉發關注，傳播范圍廣，很快就會成為社會熱點。同理，如果想要控制輿論、控制疾病暴發，可以從節點角度出發，找出傳播最有效的節點，采取措施可以做到有效的控制。所以，復雜網絡中影響力節點的識別有著十分重要的理論意義和實際價值重要的研究課題。目前也有很多識別影響力節點的算法被設計出來。有度中心性(DC)、接近中心性(CC)以及介數中心性(BC)等。

在本發明之前，這些方法在識別有影響力方面存在缺陷和不足：度中心性(DC)的缺點是僅考慮了節點的最局部的信息，是對節點最直接影響力的描述，沒有對節點周圍的環境(例如節點所處的網絡位置、更高階鄰居等)進行更深入細致地探討，因而在很多情況下不夠精確；雖然接近中心性(CC)利用所有節點對之間的相對距離確定節點的中心性，在研究中應用非常廣泛，但時間復雜度比較高。在如今大規模的網絡環境中并不是很實用；介數中心性(BC)時間復雜度比較高，也并不是很適用于大規模的網絡。

發明內容

本發明的目的就是要克服上述缺陷，提供基于傳播路徑分析的獨立級聯模型的影響力最大化方法。

本發明的技術方案是：

基于傳播路徑分析的獨立級聯模型的影響力最大化方法，其主要技術特征在于包括如下步驟：

(1)輸入復雜網絡并確定初始傳播的種子節點；

(2)產生傳播路徑：種子節點激活網絡中任意頂點，若能激活成功便可以產生傳播路徑；

(3)構造激活概率最大前m條最短路徑集合：利用單源最短路徑方法得到概率最大的最短路徑。但是本方法是基于獨立級聯(IC)模型的，在獨立級聯模型中，我們不僅考慮概率最大的最短路徑，還要考慮概率最大的前m條路徑；

(4)計算路徑集合的最終激活概率：由步驟(3)得到概率最大前m條最短路徑集合，在根據我們所提出傳播路徑的計算公式計算得到最終激活概率；

(5)選擇節點集合：通過設置一定得閾值，利用步驟(4)得到的激活概率篩選產生新的節點集合；

(6)對節點集合求最大覆蓋：通過最大覆蓋的貪心算法最終的得到能夠最大覆蓋集合的種子集合S。

所述步驟(4)構造激活概率最大前m條最短路徑集合：首先本方法在考慮到最大概率的最短路徑的同時，考慮到種子節點u和頂點v之間概率最大的前m條最短路徑，不是只單一的利用一條最短路徑產生的概率進行研究計算，通過對概率最大的前m條最短路徑的研究和計算，能夠使得我們所提出的方法更具有準確性從而能夠有效率的識別出網絡中有影響力的節點。

所述步驟(6)對節點集合求最大覆蓋：通過步驟(3)、步驟(4)以及步驟(5)得到節點集合，最大覆蓋問題是指種子集合S中至少有一個元素出現在步驟(5)得到節點集合中，通過最大覆蓋算法得到的種子集合S能夠最大的影響或者激活復雜網絡中的頂點。