[發明專利]一種基于鄰居拓撲的復雜網絡層次分析系統及方法

有效

• 申請號: 201810958173.2
• 申請日: 2018-08-22
• 公開（公告）號: CN109255722B
• 公開（公告）日: 2020-09-18
• 發明（設計）人: 羅俊海
• 申請（專利權）人: 電子科技大學
• 主分類號: H04L29/08
• 分類號: H04L29/08
• 代理公司: 成都虹盛匯泉專利代理有限公司 51268
• 代理人: 王偉

本發明公開一種基于鄰居拓撲的復雜網絡層次分析方法，針對現有復雜網絡結構分析技術存在的問題，本發明的方法通過將不利于處理的實際網絡轉化為便于計算機存儲和運算的鄰接表，尤其對于大規模稀疏網絡，減小了運算過程中的空間占用；并設計了一種新的節點間鏈接性質的評估機制；根據鏈接評估的結果，反復移除較可能處于社團間的鏈接，以極小代價重新評估少數鏈接，以連通分支的形式呈現網絡的社團結構。

技術領域

本發明屬于復雜網絡結構分析技術領域，特別涉及一種全光纖分布式聲波傳感技術。

背景技術

復雜網絡(complex network)是描述現實世界復雜系統的抽象模型，例如社會中的經貿網絡、社交網絡，自然界中的食物鏈網、生物種群網，生物體中的神經網絡、代謝網絡。網絡的社團結構(community structure)是傾向內聚的網絡所具有的拓撲結構。復雜網絡的層次分析(hierarchical analysis)是采用分層聚類技術，以不同的粒度挖掘網絡中的社團。它不僅能夠給出網絡可能的社團結構，還能夠層次地分析網絡結構，揭示網絡的多級結構，有利于識別社交網絡頂級傳播者，通信網絡故障恢復等底層任務。復雜網絡層次分析系統設計通常包括兩個部分：(1)系統輸入；(2)系統建模分析。

由于復雜網絡的復雜性，社團定義包括從基于強度的定義，基于全局或局部的定義，基于相似性的定義等。盡管目前沒有廣泛認可的定量或定性定義，但大多數網絡分析系統都是基于社團強度的定義分析網絡的結構。在基于強度的定義下，社團結構表現為網絡中同一社團間連接緊密，而不同社團間連接稀疏。

復雜網絡的社團結構分析是指以網絡拓撲結構、連接信息為主，輔以可能的節點特性或成對關系等額外信息，分析、挖掘網絡中社團結構，將大規模網絡劃分為多個連接相對緊密的子網絡。社團中的節點通常功能相近或性質相似，通過層次分析網絡的社團結構可以從宏觀上把握網絡的功能模塊，還可以從微觀上把握網絡局部的結構。對不同層次挖掘出的社團結構，統一采用模塊度進行評價，模塊度越大，表明網絡在這一層次下表現出的社團結構越明顯。

目前，大部分復雜網絡分析的研究存在以下缺點：(1)局限于理論和方法模型的建立，不存在系統化的設計；(2)局限于單一粒度的社團結構，沒有多層次地分析網絡；(3)網絡拓撲結構信息利用不夠充分，局限于節點與鄰居的連接關系；(4)已有的層次分析網絡社團結構的方法無法同時保證分析性能和計算速度。

綜上所述，現有的復雜網絡層次分析的研究及實現存在缺乏系統化、分析粒度單一、信息利用不充分、不能平衡分析性能和計算速度等問題。

發明內容

為了解決上述技術問題，本發明提供一種基于鄰居拓撲的復雜網絡層次分析系統及方法，充分利用網絡的結構信息，評估鏈接的性質；基于自適應地迭代移除部分鏈接，自動以連通分支的方式呈現網絡的社團結構；基于鏈接評估方式的對稱性，快速評估每次迭代過程中少部分發生改變的鏈接。

本發明采用的技術方案為：一種基于鄰居拓撲的復雜網絡層次分析系統及方法，通過將不利于處理的實際網絡轉化為便于計算機存儲和運算的鄰接表，尤其對于大規模稀疏網絡，減小了運算過程中的空間占用；并設計了一種新的節點間鏈接性質的評估機制；根據鏈接評估的結果，反復移除較可能處于社團間的鏈接，以極小代價重新評估少數鏈接，以連通分支的形式呈現網絡的社團結構；具體包括以下技術：

1、基于鄰接表的網絡建模；

首先，系統的輸入包括以下幾個部分：

(1)網絡節點總數：N；網絡鏈接總數：M；

(2)網絡節點集合Nodes＝{n₁,n₂,...,n_k,…}，n_i表示第i個節點的標簽；