[發明專利]基于多邊形系數的大型稀疏復雜網絡拓撲分析和簡化方法

有效

• 申請號: 202110303488.5
• 申請日: 2021-03-22
• 公開（公告）號: CN113190939B
• 公開（公告）日: 2022-09-06
• 發明（設計）人: 廖靈霞;李智;趙涵捷
• 申請（專利權）人: 桂林航天工業學院
• 主分類號: G06F30/18
• 分類號: G06F30/18;G06F17/16
• 代理公司: 桂林市華杰專利商標事務所有限責任公司 45112
• 代理人: 楊雪梅

1.一種基于多邊形系數的大型稀疏復雜網絡拓撲分析和簡化方法，其特征在于，包括如下步驟：

1)網絡多邊形系數的定義：給定一個網絡，將網絡拓撲抽象為一個無向圖G(V,E),其中，V表示該網絡的節點集，|V|表示網絡所包含的節點總數，E表示給定網絡的鏈路集，鏈路集中的鏈路是指連接相鄰兩節點的網絡通路，假設I表示給定網絡中包含的無嵌套多邊形集，Ci表示I中的一個無嵌套多邊形，那么給定網絡的多邊形系數為(∑_i∈ICi)/|V|；

2)網絡多邊形系數的計算：已知一個網絡的鄰接矩陣A，鄰接矩陣A是一個N×N的方陣，N為網絡的總節點數，該方陣的元素Aij值為1或0，取1表示節點i和j之間有鏈路直接相連，取0表示沒有鏈路相連，通過鄰接矩陣A計算出N，N即為多邊形系數的分母，而無嵌套多邊形集通過Matlab內置的polyshape類計算得到，然后計算出無嵌套多邊形集包含的所有節點數，即多邊形系數的分子，最后得到網絡的多邊形系數；

3)網絡同配系數的計算：同配系數計算不同節點的節點度間的Pearson相關系數，將步驟2)已知網絡的鄰接矩陣A輸入Matlab，通過Matlab的Brain Connectivity Toolbox內置的Assortativity函數直接計算出網絡的同配系數；

4)網絡拓撲分析：根據多邊形系數和同配系數，將網絡分為以下7種類型：(1)多邊形系數為0且有正同配系數、(2)多邊形系數為0且有負同配系數、(3)多邊形系數小于1且有正同配系數、(4)多邊形系數小于1且有負同配系數、(5)多邊形系數為1且有正同配系數、(6)多邊形系數為1且有負同配系數、(7)多邊形系數大于1，其中(1)類網絡對應線性拓撲、(2)類網絡對應星型架構、(3)類網絡對應的拓撲具有線性主干，部分分支有環狀結構、(4)類網絡對應的拓撲具有為星型主干，部分分支有環狀結構，此類網絡較少、(5)類網絡具有環形主干、(6)類網絡很少見、(7)類網絡具有網狀結構；

5)網絡拓撲簡化：根據網絡類型，采用的最長路徑分割和小面積非嵌套多邊形合并的綜合策略對網絡進行簡化，簡化要求是在不改變網絡主要拓撲特點的前提下減少網絡的節點，各類網絡類型的具體的簡化方法為：(1)類和(3)類網絡直接找到最長路徑，將最長路徑切斷得到多個子網絡實現網絡的分割；(2)和(4)類網絡只需考慮中心節點，即節點度高的節點和它們之間的鏈路組成了網絡的主干；(5)類網絡具有環形拓撲，這種拓撲環的階次高，數量少，不進行簡化；(6)類網絡很少見，難以確定拓撲結構和簡化方法；(7)類網絡具有數量眾多的低階環，且數量較多，簡化的方法是進行多邊形合并；

其中(7)類網絡采用多邊形合并進行簡化的過程如下：

(1)輸入網絡的鄰接矩陣A和多邊形面積閾值st；

(2)計算節點度矩陣D；

(3)簡化節點度矩陣D,將節點度小于2的節點從D中刪除；

(4)計算網絡的無嵌套多邊形集合；

(5)計算無嵌套多邊形集合中每個多邊形的面積；

(6)將面積小于閾值st的多邊形與其相鄰的多邊形合并；

(7)計算合并后的網絡的鄰接矩陣A；

(8)輸出A。

2.根據權利要求1所述的基于多邊形系數的大型稀疏復雜網絡拓撲分析和簡化方法，其特征在于，步驟2)中所述的網絡多邊形系數的計算過程如下；

(1)輸入網絡的鄰接矩陣A；

(2)計算節點度矩陣D,每個節點的節點度就是該節點與多少個節點直接相連；

(3)計算總節點數N；

(4)簡化節點度矩陣D,將節點度小于2的節點從D中刪除；

(5)計算網絡的無嵌套多邊形集合；

(6)計算無嵌套多邊形集合包含的所有節點數n；

(7)計算多邊形系數＝n/N；

(8)輸出多邊形系數。