基于譜分析的復雜網絡脆弱節點發現算法

尹峻松，王曉明，張新強，王春江

(中國電子設備系統工程公司研究所，北京 100141)

?

基于譜分析的復雜網絡脆弱節點發現算法

尹峻松，王曉明，張新強，王春江

(中國電子設備系統工程公司研究所，北京 100141)

未來以網絡為中心的信息化戰爭，節點打擊、毀點癱面成為攻擊敵方信息網絡、奪取信息優勢的重要手段。針對尋找敵方網絡弱點進行攻擊、提升我方體系抗毀能力拒止攻擊等問題，在復雜網絡拓撲連接矩陣的基礎上，引入Laplacian譜分析方法，提出拓撲連接度概念，通過計算網絡中各節點的拓撲連接度，發現脆弱節點并給出脆弱性排序，為信息網絡的健壯性與抗毀性研究提供了一種有效的全新思路。

復雜網絡；社團結構；Laplacian譜分析；脆弱節點

0　引言

隨著軍隊信息化建設的推進，軍隊對于各類信息基礎設施的依賴性也在不斷提高，節點打擊逐漸成為軍事打擊行動中最有效的攻擊方式，能夠以最小的代價破壞敵方的電力網、交通網、通信網、金融網和后勤保障網等網絡鏈路的關鍵樞紐，使敵方指揮與行動受限，為戰爭的最后勝利奠定基礎。相對于日常通信、運輸網絡，軍用網絡更強調在惡劣環境以及節點打擊下的抗毀能力，因為軍事網絡面對的主要是有目的性的攻擊而不是隨機攻擊。因此，如何選擇敵方網絡中的脆弱節點進行打擊，以及對基礎網絡如何優化、重點防護，提高網絡的健壯性與抗毀性，是奪取信息優勢亟需解決的重要課題[1]。

復雜網絡是一種典型的基于圖的數據挖掘方法(Graph-based mining)，將數據對象抽象為節點，將對象間的關系抽象為邊[2]。其骨干網抽取有一定研究，可以為提高網絡的抗毀性提供依據，但對脆弱節點的發現因比較困難，目前研究較少。

本文基于復雜網絡，引入Laplacian譜圖理論，通過計算各節點的拓撲連接度并排序，提出了網絡脆弱節點的發現算法，通過對空手道俱樂部網絡、寬吻海豚網絡、亞馬遜圖書銷售網絡進行仿真分析，實驗結果表明，本算法可以直觀、準確地發現復雜網絡的脆弱節點。

1　基本概念

復雜網絡中的每個節點扮演著一定的角色，稱之為成員，成員之間具有異質性和局部影響差異性，表現為抱團特性[3]，即整個網絡是由若干“群(group)”或“團(cluster)”構成，每個社團內部的節點之間連接相對緊密，而社團之間的連接相對比較稀疏，如圖1所示。圖中包含4個社團，分別對應不同顏色的劃分區域。在社團內部，節點之間的聯系非常緊密，而社團之間的聯系就稀疏得多。

圖1　一個小型的具有社團結構性質的網絡示意圖

在網絡結構分析中，一方面需要找出網絡的各個社團，根據社團劃分分析出各社團的凝聚方式，這在協同推薦中非常必要，比如亞馬遜和淘寶網根據不同的社團劃分推薦不同興趣的書籍和貨物，使讀者能夠更快地檢索到自己感興趣的物品。另一方面，我們也應該注意社團和社團之間的橋接節點，或者兩個社團的交疊節點[4]。這類節點離社團的中心比較遠，表面上看地位不是很重要，但卻是社團和社團之間連接的重要橋梁。這類節點一旦被破壞，將造成網絡中不同社區的孤立，形成非連通區域甚至網絡碎片。因此，對這類節點的發現，在通信網絡的抗毀性分析中具有重要的意義。我們把這類節點稱為脆弱節點(Fragile Node)。

2　脆弱節點發現算法

2.1Laplacian譜分析方法

設G=(V,E)是n階簡單連通圖，D(G)和W(G)分別表示圖G的度對角矩陣和鄰接矩陣，則L(G)=D(G)-W(G)稱為圖G的Laplacian矩陣。

基于譜圖理論，構造相應嵌入空間目標函數為：

(1)

式中，權值矩陣Wij采用Wij=exp(-‖xi-xj‖2/t)，t∈R的核函數，在滿足低維結構對域的約束yTDy=1(D為對角矩陣，Dii=sumjWij)及防止網絡節點收縮至單點的約束yTDI=0，最小化誤差方程可對應于求解下式的最小特征向量：

Lf=λDf ，

(2)

式中，D為對角權矩陣，L=D-W即為Laplacian(對稱、半正定)矩陣。

可以證明式(2)近似對應于Laplacian-Beltrami的特征向量求解[5]，因而可以反映復雜網絡中各節點在該社區中的聯接強度。

2.2節點拓撲連接度計算

如果一個網絡由完全獨立的幾個社團組成，即構成他的g個社團之間不存在邊，只有社團內部才存在邊，那么該網絡的Laplacian矩陣L就是一個分成g塊的對角矩陣，其中，每一塊的對角矩陣就對應著一個社團。顯然，該對角矩陣有一個(最小)特征值0，對應特征值0有g個退化的特征向量，從而將網絡劃分為g個社區。

如果一個網絡具有較明顯的社團結構，但這些社團之間并不是完全獨立，即構成他的g個社團并不是完全分離，而是通過少數的幾條邊連接，那么Laplacian矩陣就不是g塊的對角陣了。此時，對應特征值0就只有一個特征向量l。但在0附近還有g-1個比0稍大一點的特征值，這些特征值對應的特征向量大致可以看作是每個社團對應特征向量的線性組合。因此，可以根據次小的g-1個特征值對應的特征向量來劃分g個社區。

還有一種特殊情況，即網絡中僅有2個社團，也就是說該網絡的Laplacian矩陣L對應2個近似對角矩陣塊。我們知道，對一個實對稱矩陣來說，他的非奇異特征值對應的特征向量總是正交的。因此，除最小特征值0以外，矩陣L的其他特征值對應的特征向量總是包含正、負兩種元素。這樣，當網絡由2個社團構成時，就可以根據非零特征值對應的特征向量中各元素對應網絡的節點進行分類，其中，所有正元素對應的那些節點屬于一個社團，所有負元素對應的節點屬于另一個社團。

這里，次小的特征值就是該網絡的代數連接度，其對應的特征向量的絕對值就稱為該網絡中各節點的代數連接度或拓撲連接度。

2.3基于拓撲連接度的脆弱節點發現

借鑒流形學習中Laplacian特征映射算法的思想[6]，構建基于網絡拓撲的Laplacian矩陣L=D-W，D為對角矩陣，對角元素為每個節點的度，W是對稱矩陣，各元素為網絡所有節點之間的拓撲連接，如W(1,5)的值即為節點5對節點1的拓撲連接，有連接為1、無連接為0(簡單地說，W矩陣即為網絡連接矩陣)。對Laplacian矩陣計算特征值，得到節點的拓撲連接度(即次小特征值對應的特征向量的絕對值)。對拓撲連接度進行排序，勢值小的節點即為該網絡的脆弱節點。其核心算法流程如下：

脆弱節點發現算法流程

Step 1:構造網絡拓撲Laplacian矩陣L=D-W，D為對角線元素是各節點度值的對角陣，W為網絡所有節點之間的拓撲連接構成的矩陣。

Step 2:計算拓撲連接度(即矩陣L的次小特征值對應的特征向量)并排序，最小的前N項對應的節點即為脆弱節點。

本算法復雜度較低，比復雜網絡分析中常用的GN算法、K-L算法要低很多(GN算法最差情況下的時間復雜度為O(m2n)，其中m、n為網絡的邊數和節點數)。一般情況下，計算一個n×n矩陣的全部特征向量計算復雜度為O(n3)。但在大多數情況下，實際網絡的Laplacian矩陣是一個稀疏矩陣，因此，可采用Lanczos方法快速計算特征向量和特征值[7]。該方法的計算復雜度大致為m/(λ3-λ2)，其中λ3和λ2分別是第三小和第二小的特征值，而m則表示網絡中邊的條數。由此可見，計算速度會得到很大程度的提高。

也可以對Laplacian矩陣進行拓展，引入拓撲勢的計算方法[8]，將對角矩陣D中對角元素表示為每個節點的拓撲勢，將對稱矩陣W的各元素表示為該節點的拓撲勢值，則矩陣L中的元素就不是簡單的拓撲距離，而是代表局域影響特征的拓撲勢的值。計算得到的結果將更能反映節點在局部區域(社團)中的重要性。

3　實驗結果分析

3.1實驗網絡數據描述

(1) Zachary空手道俱樂部網絡

Wayne Zachary從1970～1972年觀察美國一所大學空手道俱樂部成員間的社會關系，構造其成員關系網[9]，如圖2所示。節點表示成員，節點間的連接表示2個成員經常一起出現在俱樂部活動之外的其他場合。因俱樂部主管John A.(節點1)與教練Mr.Hi(節點34)之間的爭執而分裂成2個各自為核心的小俱樂部。網絡包含34個節點，78條邊。

(2) 寬吻海豚網絡

D.Lusseau等人對棲息在新西蘭Doubtful Sound峽灣的一個寬吻海豚群體進行長達7年的觀察，構造海豚關系網[10]，如圖3所示。網絡中節點代表一個個海豚，邊表示2個海豚之間接觸頻繁，網絡共有62個節點159條邊。

圖2　Zarchy俱樂部關系圖

圖3　Dolphin寬吻海豚家族關系網絡

(3) 亞馬遜圖書銷售網絡

亞馬遜圖書銷售網絡由105個節點441條邊組成[11]，其中節點為各類書籍名稱，邊為一個人如果同時購買2本書，則2本書之間有一條邊。Mark Newman根據節點的類型，以及Amazon網站購買者的評論，將節點標記為“自由派”、“中立派”和“保守派”三類。其中49本書被標記為“保守派”，43本書被標記為“自由派”，13本書被標記為“中立”。

3.2相關算法實驗結果

在Zarchary俱樂部球員的關系聯接圖中，節點1是俱樂部主管(校長)，節點34是俱樂部教練。那么節點3扮演什么角色呢？我們查閱了一些相關文獻，發現中科院數學與系統學院章祥蓀[12]和Amaral實驗室Andrea Lancichinetti等[13]也對這一問題給出了他們的解答。章祥蓀等給出的結果是節點1與節點9、10、31分別是3個社區的交疊節點，屬于脆弱節點，如圖4所示。Andrea Lancichinetti等提出了多級結構分析方法，在對Zarchary網絡進行分析時給出的結果顯示，分屬于校長社團的節點14和分屬于俱樂部教練社團的節點3、9、10、31是2個社區的交疊部分，屬于脆弱節點，如圖5所示。

圖4　中科院數學與系統學院章祥蓀等給出的脆弱節點角色發現結果

圖5　多級結構分析方法對Zarchary網絡的脆弱節點發現

3.3基于拓撲連接度的脆弱節點發現算法實驗結果

實驗中，分別對Zachary俱樂部網絡、海豚網和亞馬遜政治書銷售網絡進行了脆弱節點發現。

在Zarchary網絡中，可以得到節點3、14、20屬于2個社團的橋接節點(脆弱節點)，如圖6所示。其中節點14與Andrea Lancichinetti的結果一致，節點8與節點20前面的分析方法均未能得到。節點3與兩個社團的多個節點均有聯接，屬于周旋于2個社團的游離人士，屬于典型的脆弱節點。節點20同時聯接節點1(校長)和節點34(俱樂部教練)，與兩個社團其他節點基本不聯系，是傳遞兩個社團核心節點之間消息的秘書節點，也屬于脆弱節點。另一方面，如果將這3個節點移走，2個社團將出現明顯的分裂，僅有3條聯接，而前述算法均超過這一數量(或移走的節點數量過多)。因此，本算法給出的結果是正確的。

圖7是對亞馬遜書店政治書銷售網絡進行算法分析結構，可以看出節點5、8、50、52四個節點為脆弱節點。查閱這4個節點后發現，他們是圣經、炒股類書籍，屬于經濟、信仰和自然科學類，均不屬于2個陣營，卻為2個陣營共同購買。本算法獲得結果與事實相符。

本文對Dolphines網絡進行了分析，并給出了拓撲連接度的熱力圖，如圖8所示。可以看出節點8、29、31、37的顏色最深，其拓撲連接度最低。因此，這4個節點應該屬于2個社團的脆弱節點。其網絡聯接如圖所示，如果移除這4個節點，Dolphines網絡將會分裂為2個獨立的網絡。

圖6　Zarchary網絡脆弱節點的發現

圖7　亞馬遜書店政治書銷售網絡脆弱節點的發現

圖8　Dolphines網絡拓撲連接度熱力圖

4　結束語

針對有目標性的網絡攻擊，本文提出了復雜網絡的脆弱節點概念，創新性地引入Laplacian譜圖理論，通過計算拓撲連接度并進行排序，發現網絡中社團之間的關鍵橋接節點，為通信網絡的抗毀性與魯棒性研究提供了一種全新的思路。

[1]譚躍進,呂欣,吳俊,等.復雜網絡抗毀性研究若干問題的思考[J].系統工程理論與實踐,2008，28(增刊):116-120.

[2]Albert R,Barabási A L.StatisticalMechanicsof Complex Network[J].Review of Modern Physics,2002，74:47-97.

[3]Newman M E J.Modularity and Communities Structure in Networks[J].Proc.of the National Academy of Science,2006,103(23):8577-8582.

[4]Palla G,Derenyi I,Farkas I,et al.Uncovering the overlapping Community Structures of Complex networks in nature and society[J].Nature,2005,435(7043):814-818.

[5]尹峻松,肖 健,周宗譚,等.非線性流形學習方法的分析與應用[J].自然科學進展,2007,17(8):1015-1025.

[6]Belkin M,Niyogi P.Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering,Advances in Neural Information Processing Systems 14[M].Cambridge,MA:MIT Press,2002.

[7]Pothen A,Simon H,Liou K P.PartitioningSparseMatrices with Eigenvectors of Graphs[J].SIAM Journal on Matrix Analysis and Applications.1990,11(3):430-452.

[8]李德毅,杜 鹢.不確定性人工智能[M].北京：國防工業出處社,2005.

[9]Zachary W W.An Information Flow Model for Conflict and Fission in Small Groups[J].Journal of Anthropological Research,1977,33:452-473.

[10]Lusseau D,Schneider K,Boisseau O J,et al.The Bottlenose Dolphin Community of Doubtful Sound features a Large Proportion of Long-lasting Associations[J].Behavioral Ecology and Sociobiology,2003,54:396-405.

[11]Koschiitzki D,Schreiber F.ComparisonofCentralitiesfor Biological Networks [J].Proc.German Conf.Bioinformatics.2004,53(1):199-206.

[12]Zhang S,Wang R S,Zhang X S.Identification of overlapping Community Structure in Complex Networks Using Fuzzy C-means Clustering[J].Physica A Statistical Mechanics & Its Applications,2007,374(1):483-490.

[13]Lancichinetti A,Kivel? M,Saram?ki J,et al.Characterizing the Community Structure of Complex Networks[J].Plos One,2010,5(8):11976-11976.

Novel Fragile Nodes Detection Algorithm for Complex Network Based on Laplacian Spectrum Analysis

YIN Jun-song,WANG Xiao-ming,ZHANG Xin-qiang,WANG Chun-jiang

(Chinese Institute of Electronic and SystemEngineering,Beijing 100141,China)

In the future net-centric information warfare,the node attack and cascading failure become important means for striking enemy information network,and seizing information superiority.In order to optimize the information infrastructure connection topologies,and enhance the network robustness and survivability,based on complex network topology connection matrix,the Laplacian spectrogram theory is introduced,and a novel fragile nodes detection algorithm for communication network is proposed,providing an effective brand-new thought of studying the robustness and invulnerability of information network.

complex network;community structure;Laplacian spectrum analysis;fragile node

10.3969/j.issn.1003-3114.2015.04.18

引用格式：尹峻松，王曉明，張新強，等.基于譜分析的復雜網絡脆弱節點發現算法[J].無線電通信技術,2016,42(5):48-52.

2016-06-03

尹峻松(1978—)，男，博士，副研究員，主要研究方向：軍事通信、指揮自動化、人工智能和復雜網絡。王曉明(1978—)，男，碩士，工程師，主要研究方向：軍事通信、指揮自動化、復雜網絡。

TN915.08

A

1003-3114(2016)05-48-5