[發明專利]一種基于并發進程與影響力期望的傳播種子節點選擇方法

有效

• 申請號: 201710217508.0
• 申請日: 2017-04-05
• 公開（公告）號: CN108710618B
• 公開（公告）日: 2022-02-22
• 發明（設計）人: 盛益強;郝怡然;王勁林
• 申請（專利權）人: 鄭州芯蘭德網絡科技有限公司
• 主分類號: G06F16/9536
• 分類號: G06F16/9536;G06Q50/00
• 代理公司: 北京方安思達知識產權代理有限公司 11472
• 代理人: 王宇楊;楊青

本發明涉及一種基于并發進程與影響力期望的傳播種子節點選擇方法，包括：對種子節點集合和其他節點集合進行初始化，并計算出其他節點集合中任一節點的影響力期望值，將最大值對應的節點放入種子節點集合中；其中，所述種子節點集合用于存放已被選中的種子節點，其初始集合為空集，所述其他節點集合用于存放未被選中的節點，其初始集合為所有待激活的節點；采用并發進程方法來計算種子節點集合中所有節點與其他節點集合中任一節點組合之后的影響力期望值，從其他節點集合中選擇組合影響力期望值最大的節點作為待激活節點，將該點從其他節點集合移動到種子節點集合中；重復之前的步驟，直至選夠所有待激活的種子節點為止。

技術領域

本發明涉及社會計算與媒體挖掘領域，尤其涉及一種基于并發進程與影響力期望的傳播種子節點選擇方法。

背景技術

隨著互聯網技術的快速發展，越來越多的在線社交網絡相繼出現。在這些社交網絡中，網絡中的個體之間以社會網絡為媒介相互影響，傳播信息、觀點與影響力。實際上，隨著大數據的研究日益廣泛，社交網絡影響力傳播已經成為數據挖掘和社交網絡分析中的關鍵問題之一。

在社會網絡領域中，影響力最大化問題是指給定一種傳播模型并選取一個種子節點的集合，信息從這個節點集合開始傳播，最終使網絡上激活節點的覆蓋率達到最大。影響力最大化的目標在于用最短的時間和最少的種子節點來獲得最大的傳播覆蓋率。當前的互聯網中，影響力傳播主要通過信息傳播來體現，因此分析信息傳播的影響因素對改進影響力傳播模型具有重要意義。信息傳播的影響因素可以看作影響力傳播模型中節點激活概率的影響因素。

當前應用較為廣泛的傳播模型包括獨立級聯模型和線性閾值模型。獨立級聯模型將活躍節點視為發布者，被激活節點視為接收者，發布者激活接收者。因此，獨立級聯模型是以發布者為中心的模型，一個節點只能影響與其直接相連的節點，一旦一個節點被激活，它將嘗試去激活所有鄰居節點。線性閾值模型中每個節點有一個被影響閾值，這個閾值在0到1的范圍內均勻、隨機地選取，一旦確定在傳播中就不再改變。與獨立級聯模型一樣，在t＝0時刻有且僅有種子集合S₀中的節點被激活。在之后每個時刻t≥1，每個不活躍節點都需要依據它所有已激活的鄰居到它的線性加權和是否已達到它的被影響值來判斷是否被激活，若是，則節點v在t時刻被激活，否則，節點v仍然保持不活躍狀態。當某一時刻不再有新的節點被激活時，傳播過程結束。

對于整個傳播過程而言，種子節點的選取是傳播的基礎，因為種子節點的選取結果直接影響傳播的最終效果，包括覆蓋率及傳播時間在內。目前常用的種子節點的選取方法有貪心算法，基于節點度的啟發式算法，基于距離的啟發式算法，以及隨機算法等。

假設初始化后的活躍節點為S，用f(S)表示使用S中的節點作為種子節點進行傳播得到最終活躍的節點數目。以覆蓋率較高的貪心算法為例，首先初始化一個空的集合S，然后每添加一個節點時需要遍歷所有節點，將使得f(S+v)-f(S)的值最大的那個節點加入節點集合S。使用貪心算法選擇種子節點時，由于每次添加一個節點時均需要遍歷所有節點，因此導致時間復雜度較高，且貪心算法沒有考慮圖的拓撲結構，這是貪心算法的局限所在。

對于基于節點度的啟發式算法，即選擇度數最高的k個節點作為初始的活躍節點，該算法相比貪心算法而言時間復雜度降低很多，但由于該算法每次只選擇度數較高的節點，忽略了部分節點的信息，而貪心算法每添加一個節點時均遍歷所有節點從而選出局部最優解，因此基于節點度的啟發式算法算法效果遠不及貪心算法。對于更簡單的隨機算法，即從原節點集合中隨機選取若干節點作為種子節點，由于不確定因素較多，隨機性大，一般不被選用。

使用貪心算法進行傳播，在選取種子節點集合S時，需要對每一個未激活節點進行驗證，當用戶節點數量增加時，算法的復雜度非常高，而且由于傳播算法的隨機性而導致不夠穩定。針對上述問題，有必要減少驗證的節點數，提高驗證的節點質量，以改善算法的復雜度，進而提高傳播效率，將信息在盡量短的時間內大范圍的傳播。

發明內容