[發明專利]一種基于凝聚熵的動態影響力最大化方法

在審

• 申請號: 202011338087.5
• 申請日: 2020-11-25
• 公開（公告）號: CN112380456A
• 公開（公告）日: 2021-02-19
• 發明（設計）人: 李衛民;鐘克欣;王釗;劉艷霞
• 申請（專利權）人: 上海大學
• 主分類號: G06F16/9536
• 分類號: G06F16/9536;G06Q50/00
• 代理公司: 北京盛詢知識產權代理有限公司 11901
• 代理人: 方亞兵

本發明公開了一種基于凝聚熵的動態影響力最大化方法，具體包括：1)提出了CeCOPRA算法對社交網絡進行重疊社區發現；2)選出聚集區內有潛力的節點構建候選種子集；3)提出了可選擇動態影響力傳播算法，利用多種熵計算得到相鄰節點間的凝聚力并由此來決定節點是否有能力成為另一節點的可傳播先驅，使信息繼續有效擴散；4)最后，通過多個數據集上的多次實驗，驗證DEIM算法能否在不同場景中使理想數量的用戶被成功影響。此方法能過濾網絡中的邊緣節點，縮小種子節點選擇范圍，使得效率可以大幅度提高，而且個體自主性被保留，信息傳播過程更加真實。

技術領域

本發明涉及社交網絡技術領域，特別是涉及一種基于凝聚熵的動態影響力最大化方法。

背景技術

隨著網絡技術的發展，各種社交軟件成為了人們線上交流的主流形式，如Facebook，YouTube，Twitter等。由此觸發了海量的網絡數據，使得影響力最大化的研究前景更加廣闊并重要。影響最大化是指在社交網絡中選擇一組種子節點，根據特定的擴散模型使其對網絡中其他節點的整體影響達到最大化的問題。一個被廣泛應用的營銷策略中通過口碑效應產生連鎖反應讓自己的商品被更多人購買，但如何以最小開銷獲得最好的宣傳效果，即初始用戶集的選擇是影響力最大化問題面臨的挑戰。

影響力最大化的目標是確定K個有影響力的種子節點，復雜網絡的特性使得這項工作非常復雜。節點在網絡中的自身屬性和結構特征在種子選擇過程中起著關鍵性的作用，而社區結構正是因這些特征而存在，利用社區體現用戶的拓撲特點是一個合理選擇，同時社區中特殊用戶也可為信息的擴散提供良好開端，因此社區劃分的精確度直接影響著種子集的效果。目前有關社區劃分的工作中包括，通過節點對鄰居節點所屬社區的隸屬度大小判斷劃分社區結果，通過自組織節點間吸引力劃分社區結構，通過預算分配確定社區并通過預算轉移確定種子節點等。但這些算法缺乏對用戶間社交距離的量化從而影響社區劃分結果，而且得到的社區結構為非重疊社區，顯然這不太符合現實。如何得到一個精準的社區結構并將次融入影響力最大化過程中，使結果更加理想并提高算法效率是一個值得研究的方向。

影響力最大化領域中的經典傳播模型——獨立級聯模型和線性閾值模型，由此發展出了多個模型。但大多數算法存在一定的局限性，沒有考慮到真實社交網絡中擴散過程的不確定性，忽略了由個體的自主性導致的選擇分享對象的權利。在現實中，用戶可以主觀選擇分享信息的對象，對于摯友可能無話不談，但對于同事可能只有工作上的交流。用戶決定與何人進行資源共享是信息擴散的起點。從空間角度觀察社交網絡中每個用戶，以其為中心呈放射狀構成多條路徑，信息沿路徑流動至其他用戶。由于用戶自主選擇信息流動經過點，使得以該用戶為起點的傳播路徑的長度和方向具有不確定性。根據以上特點，如何將由個體自主性導致的傳播路徑動態性問題進行建模是一個挑戰。

發明內容

本發明的目的是提供一種基于凝聚熵的動態影響力最大化方法，以解決上述現有技術存在的問題，使網絡中的邊緣節點被過濾掉，種子節點選擇范圍縮小，個體自主性被保留，信息傳播過程更加真實。

為實現上述目的，本發明提供了如下方案：

本發明提供一種基于凝聚熵的動態影響力最大化方法，包括以下步驟：

S1.提構建CeCOPRA算法：利用節點的局部拓撲信息，用凝聚熵的概念定義了用戶間的親疏程度，并進行重疊社區劃分；

S2.為了減小種子節點的選擇范圍，利用社區結構篩選出候選種子集，所述候選種子集為有潛力成為種子的節點集，具體包括：

在大型網絡中選擇的聚集橋；在每個社區中選擇的聚集焦點；

S3.構建可選擇動態影響力傳播算法：加入了傳播控制因子α，用于表示傳播條件的下限，結合自信息熵和凝聚熵的凝聚力判斷用戶能否能成為可傳播先驅而去影響他人，當凝聚力達到閾值時傳播者才有機會去表達自己的觀點，否則影響擴散結束；