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

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

?

基于譜分析的復雜網(wǎng)絡(luò)脆弱節(jié)點發(fā)現(xiàn)算法

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

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

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

復雜網(wǎng)絡(luò)；社團結(jié)構(gòu)；Laplacian譜分析；脆弱節(jié)點

0　引言

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

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

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

1　基本概念

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

圖1　一個小型的具有社團結(jié)構(gòu)性質(zhì)的網(wǎng)絡(luò)示意圖

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

2　脆弱節(jié)點發(fā)現(xiàn)算法

2.1Laplacian譜分析方法

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

基于譜圖理論，構(gòu)造相應(yīng)嵌入空間目標函數(shù)為：

(1)

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

Lf=λDf ，

(2)

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

可以證明式(2)近似對應(yīng)于Laplacian-Beltrami的特征向量求解[5]，因而可以反映復雜網(wǎng)絡(luò)中各節(jié)點在該社區(qū)中的聯(lián)接強度。

2.2節(jié)點拓撲連接度計算

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

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

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

這里，次小的特征值就是該網(wǎng)絡(luò)的代數(shù)連接度，其對應(yīng)的特征向量的絕對值就稱為該網(wǎng)絡(luò)中各節(jié)點的代數(shù)連接度或拓撲連接度。

2.3基于拓撲連接度的脆弱節(jié)點發(fā)現(xiàn)

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

脆弱節(jié)點發(fā)現(xiàn)算法流程

Step 1:構(gòu)造網(wǎng)絡(luò)拓撲Laplacian矩陣L=D-W，D為對角線元素是各節(jié)點度值的對角陣，W為網(wǎng)絡(luò)所有節(jié)點之間的拓撲連接構(gòu)成的矩陣。

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

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

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

3　實驗結(jié)果分析

3.1實驗網(wǎng)絡(luò)數(shù)據(jù)描述

(1) Zachary空手道俱樂部網(wǎng)絡(luò)

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

(2) 寬吻海豚網(wǎng)絡(luò)

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

圖2　Zarchy俱樂部關(guān)系圖

圖3　Dolphin寬吻海豚家族關(guān)系網(wǎng)絡(luò)

(3) 亞馬遜圖書銷售網(wǎng)絡(luò)

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

3.2相關(guān)算法實驗結(jié)果

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

圖4　中科院數(shù)學與系統(tǒng)學院章祥蓀等給出的脆弱節(jié)點角色發(fā)現(xiàn)結(jié)果

圖5　多級結(jié)構(gòu)分析方法對Zarchary網(wǎng)絡(luò)的脆弱節(jié)點發(fā)現(xiàn)

3.3基于拓撲連接度的脆弱節(jié)點發(fā)現(xiàn)算法實驗結(jié)果

實驗中，分別對Zachary俱樂部網(wǎng)絡(luò)、海豚網(wǎng)和亞馬遜政治書銷售網(wǎng)絡(luò)進行了脆弱節(jié)點發(fā)現(xiàn)。

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

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

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

圖6　Zarchary網(wǎng)絡(luò)脆弱節(jié)點的發(fā)現(xiàn)

圖7　亞馬遜書店政治書銷售網(wǎng)絡(luò)脆弱節(jié)點的發(fā)現(xiàn)

圖8　Dolphines網(wǎng)絡(luò)拓撲連接度熱力圖

4　結(jié)束語

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

[1]譚躍進,呂欣,吳俊,等.復雜網(wǎng)絡(luò)抗毀性研究若干問題的思考[J].系統(tǒng)工程理論與實踐,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]尹峻松,肖 健,周宗譚,等.非線性流形學習方法的分析與應(yīng)用[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].北京：國防工業(yè)出處社,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

引用格式：尹峻松，王曉明，張新強，等.基于譜分析的復雜網(wǎng)絡(luò)脆弱節(jié)點發(fā)現(xiàn)算法[J].無線電通信技術(shù),2016,42(5):48-52.

2016-06-03

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

TN915.08

A

1003-3114(2016)05-48-5