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

在審

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

1.一種基于節點重要性估計的在線社交網絡拓撲推斷算法，具體步驟為：

步驟1：節點重要性估計

已知要推斷的網絡具有N個節點，代表網絡的節點集合；本發明所述節點重要性是指節點在傳播過程中的影響力，具體根據信息傳播過程獲得節點重要性；具體為：

步驟1-1：統計節點在t₀時刻獲得感染后t_max時間段內獲得消息的節點數目的增加量，記作為t₀時刻獲得感染的節點的重要性；

步驟1-2：已知節點u在一次傳播中的首達時間t_u和傳播時間t_max以及這段時間內影響力分布遵循等待時間分布ρ(τ)；計算節點u在這段t_u～t_u+t_max時間段內的影響力

步驟1-3：計算所有在t₀到t₀+t_max時間段內獲得信息的節點的影響力總和W；

步驟1-4：在一次傳播中，計算在t₀時刻獲得信息的所有節點的影響力

步驟1-5：估計出節點u在第c次傳播中的重要性為進而獲得網絡中每個節點的重要性；

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

步驟2-1：采用獨立級聯模型，獲得在一層級聯上推斷網絡拓撲的似然函數當考慮所有級聯后，得到似然函數目標為使似然函數最大化；

步驟2-2：記節點u的重要性為已知N個節點的重要性的均值和方差

通過探查b(u)和和的函數關系，得到能夠反映節點重要性的偏置b(u)；

步驟2-3：從一個空圖開始，每個節點對(u，v)遍歷，考察當節點對連邊狀態改變時，似然函數的增減變化用邊緣增益表示；獲得遍歷每一個節點對(u，v)時邊緣增益的變化趨勢和節點重要性之間的關系；

步驟2-4：根據是否具有網絡先驗知識更新邊緣增益；

步驟2-5：利用馬爾可夫鏈-蒙特卡洛采樣方法來解決似然函數最大化的問題；

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