[發明專利]一種獨立級聯模型下基于極大似然的源定位方法

在審

• 申請號: 202110997385.3
• 申請日: 2021-08-27
• 公開（公告）號: CN113868546A
• 公開（公告）日: 2021-12-31
• 發明（設計）人: 劉維;沙圣凱
• 申請（專利權）人: 揚州大學
• 主分類號: G06F16/9536
• 分類號: G06F16/9536;G06F16/951;G06F17/11;G06F17/16;G06F17/18;G06Q50/00
• 代理公司: 北京風雅頌專利代理有限公司 11403
• 代理人: 李翔

本說明書一個或多個實施例提供一種獨立級聯模型下基于極大似然的源定位方法，通過根據種子節點集在IC模型上擴散，形成感染網絡，利用獨立路徑計算傳播概率，再計算影響范圍最小的似然函數利用貪心策略選取種子集合，最終得到輸出感染源，相比于傳統的源定位方法大部分都只能解決單影響源定位問題，并且利用簡單的IC模型來解決復雜的多源定位問題的工作甚少。本方法在只考慮概率因素的情況下，就能同時解決單源和多源的源定位問題，為以后似然概率運用于多源問題的研究提供了相應基礎。該技術可以提高識別社交網絡中影響力傳播的源節點方面的效率，擴展了該技術在源定位問題領域的應用范圍和實用性。

技術領域

本發明屬于應用于復雜網絡中運用獨立級聯模型和似然函數計算來進行源定位的方法，特別涉及一種基于獨立路徑技術以及影響力覆蓋的極大似然估計算法來進行傳播源定位的方法。

背景技術

互聯網技術的不斷發展正將世界變成地球村，人們的社交網絡不斷擴大這些都為信息的傳播提供了更加快捷、廣泛的傳播途徑，但這同時也為一些不良信息傳播提供了方便，如一些謠言、病毒等，通過這些移動客戶端被廣泛傳播，一些不明事理的人很容易受這些謠言影響，輕易相信這些傳聞，有些激進者可能會做出過激行為，造成自己和他人合法權利受到損害，這些給社會穩定帶來了不利影響。因此，如何準確、快速地進行傳播源定位是網絡科學研究中的一項重要的任務。越來越多的學者把目光投向了對社交網絡中的信息傳播的研究。

網絡拓撲結構是社交網絡的基礎，在研究過程中，社交網絡通常是以圖的形式抽象地展示網絡的拓撲結構和信息的傳播過程。目前對于社交網絡中的信息流傳播的研究，一些學者重點關注了信息源的定位問題，即通過研究如何構建有效的信息源定位的模型以期探測到的真正的信息源的可能性最大。因此，研究社交網絡中感染源(信息源)的定位問題有著十分重要的實際意義。從大的方面講，國家可以通過社交網絡對輿情及時分析，從而控制不良信息的傳播；從小的方面來說，謠言、惡意病的傳播這些不利因素的傳播和擴散對人們的生產和生活有著巨大的影響也可以最大化地減少。負面信息傳播的問題都是依托于具體的網絡而存在的，并且網絡的規模一般都十分巨大，節點相互之間的聯系同樣也非常復雜。在這樣的情況下，如果能夠快速地和準確地找到信息的來源，控制和縮小其傳播范圍，可以大大地減少對人們生活的影響。這個問題不僅僅是復雜網絡科學領域需要研究的重要課題，更是政府保證網絡安全，控制謠言傳播面臨的重大挑戰。在此背景下，對社交網絡中的感染源的定位問題進行深入地研究，并開發出相應的分析軟件供輿情監控部門和企業市場監控來使用是十分有意義的。

現有的源定位算法，處理單源問題的居多，而多源問題相對比較復雜，因此處理多源問題方法還比較少，并且現在源定位研究的方法大多都是基于SI、SIR模型等等的傳染病模型，依賴于時間因素作為考量，而對于IC這種概率模型研究的較少。識別社交網絡中影響力傳播的源節點方面的效率不足。

發明內容

有鑒于此，本說明書一個或多個實施例的目的在于提出一種獨立級聯模型下基于極大似然的源定位方法，以解決上述提出的其中一個或多個技術問題。

基于上述目的，本說明書一個或多個實施例提供了一種獨立級聯模型下基于極大似然的源定位方法(MLE-FIC)，包括：

在復雜網絡中確定初始傳播的種子節點集；

根據種子節點集在獨立級聯模型上擴散，直到網絡中不再產生感染節點為止，將感染的節點抽取形成感染網絡；

生成節點之間的獨立路徑，利用獨立路徑計算每一個節點對之間的傳播概率；

利用概率模擬選取的種子節點的影響范圍，使得選取種子節點的影響范圍與初始的影響范圍最大限度的重合，設計得到極大似然目標函數；

利用貪心算法選取影響力覆蓋最大的節點，得到影響源的種子集合，輸出感染源。

優選地，利用獨立路徑計算每一個節點對之間的傳播概率包括：