[發明專利]基于時態圖代價最小生成樹的增量方法及系統

在審

• 申請號: 201911314540.6
• 申請日: 2019-12-19
• 公開（公告）號: CN111061964A
• 公開（公告）日: 2020-04-24
• 發明（設計）人: 李文浩;葛又銘;劉玉葆
• 申請（專利權）人: 中山大學
• 主分類號: G06F16/9536
• 分類號: G06F16/9536;G06Q50/00
• 代理公司: 北京中濟緯天專利代理有限公司 11429
• 代理人: 黃啟文

本發明涉及一種基于時態圖代價最小生成樹的增量方法，包括以下內容：將節點集V劃分為受ΔG影響的終端節點集Xa和未受ΔG影響的終端節點集Xu；對于終端節點集Xa，將G+ΔG轉換為靜態圖，在該靜態圖下，找尋從根節點r到Xa中所有節點的路徑，得到受影響子圖Gs；對受影響子圖Gs進行預處理，得到受影響子圖Gs的閉包；通過受影響子圖Gs的閉包計算覆蓋Xa的有向斯坦納樹Ta；對于終端節點集Xu，從初始的有向斯坦納樹T中提取從根節點到終端節點集Xu中各個節點的路徑，組成未受影響終端節點的有向斯坦納樹Tu；將Ta和Tu合并，得到覆蓋整個V集合的有向斯坦納樹new?T；對合并得到的有向斯坦納樹new?T進行后處理操作，將其轉化為對應的代價最小生成樹MSTw。

技術領域

本發明涉及時態圖技術領域，更具體地，涉及一種基于時態圖代價最小生成樹的增量方法及系統。

背景技術

近些年，社交網絡以及大型網絡越來越受到研究人員的重視。在以往，人們大多是關注靜態網絡。這些靜態網絡都包含時間信息，這些時間信息對網絡分析具有十分重要影響。這些帶有時間信息的網絡稱之為時態網絡。時態網絡中一個重要類型就是社交網絡，其中每條邊代表兩個團體或者個體之間的一次聯絡。另一個例子是交通網絡，每條邊上的時間標簽可以代表著某交通工具的離開和到達時間。還有很多其他時態網的例子，比如大腦神經網絡、經濟網絡等。

考慮公交網絡中行駛路線作為時態圖的一個例子。每條行駛路線包含起始站點、到達站點、起始時間、到達時間和費用信息。假設公交網絡是一個時態圖G＝(V，E)，其中E中每條邊e都是(u,v,t_u,t_v,w)，e鏈接起始節點u和到達節點v，開始時間是t_u，到達時間t_v，開銷為w。在時態圖G中一條路徑P是一條邊的序列e₁，e₂，…，e_k，k≤|V|，其中邊e_i的到達節點是邊e_i+1的起始節點，并且e_i+1的起始時間不小于e_i的到達時間，這樣的路徑滿足時間約束。在公交網絡中，當且僅當路徑P滿足時間約束時，交通工具才能沿著路徑P行駛。時態圖中路徑的時間約束為很多研究帶來了很大的挑戰。

最小生成樹問題是圖論中的一個經典問題，它在現實中的應用也十分廣泛。在社交網絡中，最小生成樹問題應用于信息傳播、病毒營銷、謠言傳播等方面的研究；在公交路網中，最小生成樹問題可以應用于路徑規劃、最優選址等問題的研究。在時態圖下，代價最小生成樹也是一個十分重要的問題。

Silu Huang、Ada Wai-Chee Fu、Ruifeng Liu等人在《minimum spanning treesin temporal graphs》中，給出了計算時態圖G中代價最小生樹的方法。在現實情況中，時態圖并不是一成不變的，比如公交網絡中經常會發生公交車改變線路，增加公交線路等情況，這相當于對時態圖進行改變。如果要在改變后的時態圖中重新找尋新的代價最小生成樹，根據目前的方法，需要重新運行原本的方法。然而，新的代價最小成樹和初始的代價最小生成樹只有一部分不同，只需要對可能會變化的部分進行計算就能夠快速更新最小生成樹。如果重新運行原來的方法，十分不明智。

發明內容

本發明為解決現有的代價最小生成樹更新方法存在的計算量大、效率低下的技術缺陷，提供了一種基于時態圖代價最小生成樹的增量方法。

為實現以上發明目的，采用的技術方案是：

基于時態圖代價最小生成樹的增量方法，包括以下內容：

設時態圖G＝(V，E)其受影響后的變化量為ΔG，其中V表示時態圖的節點集，E表示時態圖的邊集；

將節點集V劃分為受ΔG影響的終端節點集Xa和未受ΔG影響的終端節點集Xu；