[發明專利]基于節點重要性估計的在線社交網絡拓撲推斷算法

在審

• 申請號: 202210693996.3
• 申請日: 2022-06-19
• 公開（公告）號: CN115001982A
• 公開（公告）日: 2022-09-02
• 發明（設計）人: 李聰;季宏宇;郝旭;李翔
• 申請（專利權）人: 復旦大學
• 主分類號: H04L41/12
• 分類號: H04L41/12;H04L41/14;H04L51/52
• 代理公司: 上海正旦專利代理有限公司 31200
• 代理人: 陸飛;陸尤

本發明屬于大規模網絡數據分析技術領域，具體為基于節點重要性估計的在線社交網絡拓撲推斷算法。本發明包括：依托獨立級聯模型，利用每個節點在每次傳播中獲得信息的時刻作為推斷的依據，從一個空圖開始，對每個節點對遍歷，利用蒙特卡洛采樣方法解決似然函數最大化問題；由于網絡的異質性，引入能夠反映節點重要性的偏置項，估計節點重要性，實現考慮節點重要性的網絡拓撲推斷；在已知網絡先驗知識時，提取表征節點重要性指標，根據帶有節點重要性的網絡拓撲推斷算法重構網絡；在未知網絡先驗知識時，估計節點重要性，使用帶有節點重要性的網絡拓撲推斷算法重構網絡。本發明在有無網絡先驗知識下都可以重構社交網絡，并提高了推斷的準確性。

技術領域

本發明屬于大規模網絡數據分析技術領域，具體涉及一種在線社交網絡拓撲推斷算法。

背景技術

近年來，復雜網絡在各個領域，都受到了廣泛的研究和關注，并取得了豐富的成果。不管是復雜多變的社會系統，還是生物系統，信息系統，都可以將其抽象成網絡模型，進而進行更深入的分析和研究。在以復雜網絡為背景的研究工作中，由網絡節點和連邊組成的網絡基本拓撲結構無疑是我們進行分析和探索的前提，然而在實際生活中，我們經常無法直接獲得網絡的拓撲結構，在這樣的背景下，研究網絡的拓撲推斷問題具有重要的現實意義。

然而，隨著大家隱私保護意識的增強，越來越多的平臺選擇不公開用戶之間直接的關注關系，想要直接獲取用戶之間的關系數據變得越來越困難，這極大地限制了我們對在線社交網絡的研究與分析。在實際生活中，人與人之間的交互是無處不在的，雖然節點之間直接的關系不易獲取，但是疾病或信息傳播之后的結果往往是很容易觀察到的，因為通常我們很容易通過觀察個體的行為表現看出它什么時候被感染或者接收到消息，但是很難觀察到誰與他們有著直接關系并把疾病或者消息傳遞給他們。與此同時，由于疾病傳播和信息傳播的方向性和時效性，這些傳播的結果中往往隱藏了大量的包含連邊關系的信息。所以，研究如何通過容易觀察到的動力學傳播結果，來逆向地推斷出無法觀察到的網絡拓撲結構這一問題在目前的社交網絡研究領域有較大的需求，且可行性高。

學術界已經有許多關于網絡拓撲推斷算法的研究，針對社交網絡，雖然節點之間直接的關系不易獲取，但是疾病或信息傳播之后的結果往往是很容易觀察到的，所以，大多數的網絡結構拓撲推斷問題是認為節點之間的關系是完全未知的，依據節點在傳播過程中或者傳播結束之后的狀態信息進行推斷的。

發明人在進行基于信息傳播的在線社交網絡拓撲推斷研究時發現，現有的工作往往忽略了真實在線社交網絡的異質性，往往認為節點是等價的，這樣統一的等價處理會使得丟失一部分重要的信息，導致拓撲推斷算法的準確性有待提高。

發明內容

鑒于以上情況，本發明的目的在于立足于在線社交網絡，充分把握在線社交網絡規模大，連邊稀疏，異質性強的特點，提出基于節點重要性估計的在線社交網絡拓撲推斷算法，以提高推斷準確性。

本發明提出的基于節點重要性估計的在線社交網絡拓撲推斷算法，具體步驟為：

步驟1：節點重要性估計。所述節點重要性是指節點在傳播過程中的影響力，具體根據信息傳播過程獲得節點重要性；

步驟2：在不帶有節點重要性的網絡拓撲推斷算法的基礎上，設計節點重要性偏置，更新遍歷過程中的邊緣增益，使用馬爾可夫鏈-蒙特卡洛采樣方法來解決似然函數最大化的問題；

步驟3：在沒有任何網絡先驗知識的情形下，應用步驟1提出的節點重要性估計方法，代入步驟2的帶有節點重要性的網絡拓撲推斷算法中，推斷網絡拓撲；在已經獲取網絡先驗知識的情形下，提取節點重要性指標(例如出度等)，代入步驟2的基于節點重要性估計的在線社交網絡拓撲推斷算法中，推斷網絡拓撲。

本發明中，步驟1的具體流程為：