[發明專利]一種疊加網絡的提取方法

在審

• 申請號: 201710022383.6
• 申請日: 2017-01-12
• 公開（公告）號: CN106909614A
• 公開（公告）日: 2017-06-30
• 發明（設計）人: 曹冠杰;徐建
• 申請（專利權）人: 杭州電子科技大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 杭州君度專利代理事務所(特殊普通合伙)33240
• 代理人: 杜軍

技術領域

本發明屬于計算機應用技術領域，涉及一種疊加網絡的提取方法，特別適用于大規模網絡的分層數據處理，例如道路網絡中的公交站點網絡、在線社交網絡中某一特定屬性網絡的提取等。

背景技術

在地理信息系統、社交網絡等應用中，道路網絡或者社交關系網絡是重要的基礎信息結構。隨著技術的發展，人們經常面臨海量網絡節點、邊數據的處理問題。而在一個實際應用中，經常需要針對某種特定問題求解，搜索一個網絡中所有的節點、邊的策略會帶來效率的問題。因此針對特定問題，提取特定的網絡，以加快問題求解的速度，對于提高算法的效率具有重要意義。

給定一個網絡G＝(V,E)，其中V表示網絡中的節點集合，E表示網絡中邊的集合。V中有兩種類型的節點，Vw白色節點集合和Vb黑色節點集合。例如在道路網絡中，可以用Vw表示道路網路的節點，Vb表示公交站點節點。在社交網絡中，可以用Vw表示不具有某種屬性的節點，Vb具有某種屬性的節點。顯然，Vw和Vb共同構成了整個網絡。

在求解一個特定問題的過程中，例如查找某兩個公交站v_bi，v_bj點的最近距離，一般的做法是搜索整個網絡，從而獲得這兩點之間的最短距離。顯然這種搜索算法需要訪問v_bi，v_bj之間的所有節點和可能路徑，效率較低。

本發明要解決的就是如何在一般網絡中提取某個特定屬性節點構成的網絡，從而縮小以后類似查詢的搜索空間。例如提取前面所述Vb節點的網絡，在后續搜索Vb所屬節點之間的最短路徑時，就只需搜索Vb節點的網絡，從而加快搜索速度。

發明內容

本發明的目的是在于克服現有技術中的不足，針對道路網絡或者社交網絡的特點，提供一種適用于疊加網絡的提取方法。

本發明的方法具體步驟如下：

步驟(1)、網絡節點的表示和索引；

所述網絡節點是指網絡中兩條邊的交叉點，或者邊上具有特定屬性的一個位置點。

對于一個網絡G＝(V,E)使用鄰接表來表示，鄰接表表示一個包含|V|個列表的數組Adj組成，其中每個列表對應于V中一個節點。對于每一個節點u∈V，鄰接表Adj[u]包含所有滿足條件(u,v)∈E的節點v，也就是Adj[u]包含所有和節點u相鄰的節點。鄰接表中的節點可以以任意順序存儲。

使用Vb表示某種具有特殊性質的網絡節點集合，如果一個節點u∈Vb，那么u就具有該集合的特殊性質。如Vb是網絡中公交站點集合，那么u∈Vb就說明u是一個公交站點。顯然，

對于一條邊(u,v)∈E，使用w(u,v)表示該邊的權重，在道路網絡中就表示該路段的長度。

如果存在一條路徑p＝<v₀,v₀,…,v₀>，那么它的長度w(p)是指其組成邊的所有長度之和。即w(p)＝∑w(v_i-1，v_i)，其中i＝1,2…,k。

節點u,v之間的最短路徑是u,v之間所有路徑中長度最短的那一條。

步驟(2)、對一個具有特殊性質的網絡節點s,查找其相鄰的具有相同特殊性質的所有節點；

如果一個具有特殊性質的網絡節點s,到其他具有相同特殊性質的另外一個節點a的最短路徑上不存在第三個具有相同特殊性質的節點，那這兩個節點具有近鄰關系。例如兩個公交站點的最短路徑上不存在另外一個公交站點，那么這兩個公交站點具有近鄰關系。本步驟對節點s周邊所有的鄰接節點展開搜索，如果在一條路徑上遇到相同特殊性質的節點，那么結束在該路徑方向上的搜索，具體實現如下：

2-1.初始化；

對于網絡中除節點s以外的所有節點v都進行以下操作：

設置v.via為假，表示從節點s出發的當前已知最短路徑沒有經過本節點v。

如果節點v跟節點s直接相連，那么

設置v.d為w(s,v)，表示從節點s出發到達節點v的當前已知最短路徑長度；

設置v.π為s，表示從節點s出發到達節點v的當前已知最短路徑中節點v的前繼節點；

如果節點v跟節點s沒有直接相連，那么

設置v.d為無窮，表示當前不存在從節點s到節點v的最短路徑；

設置v.π為空，表示當前節點v的前繼節點為空。

2-2.在鄰接節點中查找與節點s具有相同特殊性質的所有節點；

設置集合S等于{s},S表示已經找到的從節點s出發的最短路徑的節點集合。