[發明專利]一種基于鄰接矩陣構造的跳數矩陣恢復方法

有效

• 申請號: 202110255147.5
• 申請日: 2021-03-09
• 公開（公告）號: CN112995942B
• 公開（公告）日: 2022-07-15
• 發明（設計）人: 劉星成;趙瑩瑩
• 申請（專利權）人: 中山大學
• 主分類號: H04W4/38
• 分類號: H04W4/38;H04W40/04;H04W40/24;H04W40/34
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 劉俊

1.一種基于鄰接矩陣構造的跳數矩陣恢復方法，其特征在于：所述的方法包括步驟如下：

S1：由于不完整的泛洪過程或者惡意節點的攻擊，獲取的跳數矩陣中含有缺失項；

S2：如果跳數矩陣中，缺失的跳數的對稱位置被觀測到，使用對稱位置跳數將其補全；

S3：通過缺失的跳數矩陣推斷出不同節點對之間的連通性，從而得到鄰接矩陣A＝[a_ij]_n×n,i＝1,...,n；j＝1,...,n；

S4：采用最短路徑算法對步驟S3得到的鄰接矩陣進行處理，得到初步的跳數矩陣；

S5：對初步得到的跳數矩陣進行遍歷，對于沒有跳數值的位置，使用鄰居補全的跳數值代替，從而恢復得到完整的跳數矩陣；

步驟S3，具體的，

S301：對于被觀測到的跳數位置，若節點i到節點j的跳數值為1，則這兩個節點可以直接通信，鄰接矩陣對應的位置為1；反之，兩個節點在鄰接矩陣中對應的位置為0；

S302：對于跳數缺失的位置，若節點i和節點j相對于網絡中其它任意節點k，存在節點i到節點k的跳數值與節點k到節點j的跳數值之差大于1，則鄰接矩陣對應的位置為0；否則進入下一步；

S303：采用初步補全方法補全跳數矩陣若節點i和節點j相對于網絡中其它任意節點k，若存在節點i到節點k的跳數值和節點k到節點j的跳數值之差大于3，且對應的兩個跳數值都為補全的跳數，則鄰接矩陣對應的位置為0；否則進入下一步；

S304：判斷網絡中是否存在任意節點k，使得節點i到節點k的跳數值和節點k到節點j的跳數值之差大于2，且對應的兩個跳數值中有一個為補全的跳數，則鄰接矩陣對應的位置為0；否則鄰接矩陣對應的位置為1；

S305：若鄰接矩陣補充完整，則進行下一步，否則回到步驟S302。

2.根據權利要求1所述的基于鄰接矩陣構造的跳數矩陣恢復方法，其特征在于：步驟S1，構造的缺失跳數矩陣表示如下：

其中，⊙表示Hadamard乘積；Ω＝[ω_ij]_n*n表示一個隨機觀測矩陣，ω_ij表示跳數矩陣對應位置是否缺失，表示為：

其中，i＝1,....,n；j＝1,....,n。

3.根據權利要求2所述的基于鄰接矩陣構造的跳數矩陣恢復方法，其特征在于：所述的初步補全的方法：如果節點i和節點j之間的跳數值h_ij缺失，則使用節點i的鄰居到節點j的跳數和節點j的鄰居到節點i的跳數的平均值，來補全缺失的跳數值h_ij。

4.根據權利要求3所述的基于鄰接矩陣構造的跳數矩陣恢復方法，其特征在于：所述的初步補全方法，具體如下：對于一個跳數缺失的值初始化兩個鄰居列表L_i和L_j，根據跳數向量選擇節點i的鄰居，根據跳數向量選擇節點j的鄰居；節點i的鄰居節點的索引存儲在鄰居列表L_i中，節點j的鄰居節點的索引存儲在鄰居列表L_i中；變量n_i表示節點i的可用鄰居節點，變量n_j表示節點j的可用鄰居節點數；如果觀察到鄰居節點L_i(k)與節點j之間的跳數則可用鄰居節點n_i加1。

5.根據權利要求4所述的基于鄰接矩陣構造的跳數矩陣恢復方法，其特征在于：初步補全的跳數值由下式得到：

其中，表示矩陣初始補全后，節點i到節點j之間的跳數值。

6.根據權利要求5所述的基于鄰接矩陣構造的跳數矩陣恢復方法，其特征在于：所述的最短路徑算法為Floyd算法。