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

有效

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

本發明公開了一種基于多邊形系數的大型稀疏復雜網絡拓撲分析和簡化方法，包括如下步驟：1）網絡多邊形系數的定義；2）網絡多邊形系數的計算；3）網絡同配系數的計算；4）網絡拓撲分析；5）網絡拓撲簡化。這種方法，用以分析并簡化大規模稀疏廣域網的拓撲結構，降低大量基于網絡拓撲的遍歷算法、啟發算法、和近似算法的時間消耗，能在不改變原拓撲基本架構的基礎上減少了網絡所包含的節點數和鏈路數。

技術領域

本發明涉及網絡拓撲的分析和簡化技術，具體是一種基于多邊形系數的大型稀疏復雜網絡拓撲分析和簡化方法。

背景技術

隨著5G和物聯網技術的發展，通信與計算機網絡正在將越來越多的、具有不同智能水平的終端接入到網絡，并為它們提供不同服務質量的業務和服務。為了能夠滿足不同類型業務和服務的服務質量要求，當前的通信與計算機網絡需要對網絡資源進行靈活、智能的管理和優化。

該類靈活、智能的網絡管理和優化通常通過基于網絡拓撲的各種遍歷、啟發式、學習型、近似算法而實現。基本思路是通過遍歷網絡的所有節點和鏈路，或有選擇地遍歷某些節點和鏈路，找到符合要求的特定節點和鏈路，通過對這些節點和鏈路進行特別的處理達到資源管理和優化的目標。網絡拓撲抽象了網絡中節點和鏈路的物理和邏輯關系。網絡拓撲的規模，即網絡中節點和鏈路數，以及它們如何互聯，影響了該類算法的計算精度和時間消耗，直接影響了基于該類算法的應用的可行性和可實施性。

按照地理范圍來分類，當前的通信和計算機網絡可以簡單分為局域網和廣域網。局域網負責將一個地理范圍較小的機構內的主機互聯成一個內部網絡，廣域網則負責將這些內部網絡互聯在一起，形成一個相互聯通的互聯網絡。所以，在通信與計算機網絡中，局域網通常位于網絡的邊緣，拓撲結構通常為規則的樹型或基于樹型的擴展類型；而廣域網則位于網絡的核心，負責連接網絡邊緣的局域網、接入網構成地理范圍更大的網絡。廣域網通常由大型電信服務提供商、互聯網服務提供商的骨干網構成。由于這些骨干網通常選擇在行政區域中心城市布點，造成廣域網通常節點稀疏，節點間距大。同時，骨干網由于長期演化，其拓撲結構受地理條件，經濟條件，和國家政策的影響大，結構復雜，難以用常規方法進行描述。當廣域網(Wide Area Network,簡稱WAN)的節點數達到一定數量時，各種基于網絡拓撲的遍歷算法的時間開銷很大。為了降低該時間開銷，通常的方法是對網絡拓撲進行簡化。但由于廣域網具有難以用常規方法描述的復雜拓撲結構，網絡拓撲的描述和簡化難度很大，導致網絡的管理和優化應用難以在實際中得到應用和部署。

復雜網絡(Complex network)一般指網絡結構難以用常規方法進行描述的網絡，如人類的腦組織網絡，社交網絡，病毒的傳播網絡等。稠密度是描述復雜網絡拓撲特性的一種方法。稠密度通常采用聚類系數(Clustering)、密度系數(Density)、多邊形社區系數(Clique Communities)等來描述。聚類系數計算了網絡中構成三角形的邊占總邊數的比例；密度系數計算網絡中已構成的邊占最多可能構成的邊的比例；多邊形社區系數計算了在給定多邊形邊數k的條件下，網絡中存在的所有嵌套的多邊形數。雖然這些系數從不同角度分析網絡的稠密特性，但都不適合描述廣域網，因為廣域網非常稀疏，導致聚類系數(Clustering)、密度系數(Density)、多邊形社區系數都非常小，所以廣域網的網絡拓撲難以用這些系數進行分析和識別。同配系數計算節點間的Pearson相關性，可以在一定程度上反應網絡的拓撲特性。例如具有正同配系數的網絡表示該網絡具有相似的度的節點通常相互連接；具有負同配系數的網絡通常表示該網絡中度差異很大的節點連接在一起，也就是說，正同配系數的網絡可能具有線性或環形的網絡拓撲，負同配系數的網絡可能具有星型網絡拓撲，但是，當兩個網絡具有相同符號的同配系數時，其網絡拓撲的差異依然無法識別。

發明內容

本發明的目的是針對現有技術的不足，而提供一種基于多邊形系數的大型稀疏復雜網絡拓撲分析和簡化方法。這種方法，用以分析并簡化大規模稀疏廣域網的拓撲結構，降低大量基于網絡拓撲的遍歷算法、啟發算法、和近似算法的時間消耗，能在不改變原拓撲基本架構的基礎上減少了網絡所包含的節點數和鏈路數。