基于BP模型的KAD網絡核心節點識別算法研究

王 建，馮偉森，邱興超，劉 繼，盧 林

WANG Jian1，2,FENG Weisen1,QIU Xingchao1,LIU Ji1,LU Lin1

1.四川大學 計算機學院，成都 610041

2.四川大學 錦城學院 計算機科學與軟件工程系，成都 611731

◎網絡、通信、安全◎

基于BP模型的KAD網絡核心節點識別算法研究

王 建1，2，馮偉森1，邱興超1，劉 繼1，盧 林1

WANG Jian1，2,FENG Weisen1,QIU Xingchao1,LIU Ji1,LU Lin1

1.四川大學 計算機學院，成都 610041

2.四川大學 錦城學院 計算機科學與軟件工程系，成都 611731

針對在KAD網絡中核心節點的識別問題，提出了一種基于BP模型對節點重要程度進行實時判定的方法。結合KAD網絡測量的結果，對網絡中核心節點的屬性特征進行提取和歸一化處理，獲得了一組可分離度較高特征集合。采用MatLab設計相應的學習算法對BP網絡進行訓練，使結果收斂于預定誤差區間。將完成訓練的BP網絡模型應用于對測試節點的判定，實驗結果表明該方法可以實時地完成核心節點的判定，并且識別準確率可達到約70%。

反向傳播算法；KAD網絡；核心節點；識別

1 引言

網絡節點的排序問題是復雜網絡中的一個基本和重要問題，被廣泛應用于數據挖掘、網絡分析、網絡預測、網絡安全與控制等領域。隨著復雜網絡研究的深入發現，大量真實的網絡既不是規則的，也非完全隨機的。因此，有效地評估和度量網絡中節點的重要性，不但是網絡數據挖掘的首要問題，也是復雜網絡、社會關系網和互聯網搜索、系統科學的研究重點[1]。KAD是P2P技術歷經10年發展后的新一代DHT網絡[2]，其去中心化、可測量、易擴展、高容錯性等優點使它迅速滲透到文件共享、即時通訊、分布式存儲、云存儲等領域。這種無中心服務器的設計使得各個節點相對平等，既是服務的提供者，又是服務的請求者。KAD網絡的發展使其并發用戶已達到數百萬級，海量的用戶使得對于網絡的控制和監管變得十分困難。大量網絡測量實驗表明，DHT網絡中節點負載非均衡性廣泛存在[3-5]。可以將那些在KAD網絡中為其他節點提供了更多路由服務或下載服務的節點稱為核心（重要或關鍵）節點。如果能利用這種非均衡性，發現和識別網絡中發揮了核心作用的節點，則是對KAD網絡的監督將有著重要的作用。

2 相關工作

基于鏈接的節點排序是網絡分析中的一個核心任務，它通過圖中節點之間鏈接表現出的重要性不同對節點進行排序。目前國內外研究者對節點排序方法有四種典型的方式[6]：一是基于純粹網絡靜態參數指標來進行衡量節點的關鍵程度，常用評價指標有點中心度、凝聚中心度、子圖中心度、網絡流中心度等等。基于傳統的靜態社會分析方法有著明顯的缺點，它忽略引起網絡狀態變化的重要因素[7]，從而造成信息缺失問題。例如，不注重個體之間的連接關系、相關個體之間的相互影響以及隨時間變化趨勢[8]。二是借鑒圖分割方法中標準來進行衡量，即找出圖中的割點作為核心節點，因為刪除該節點后可以將圖割裂為多個子圖[9]。三是使用搜索引擎中節點排序的思想來進行核心節點發現排序，其主要的思想是基于隨機行走模型[10]。四是使用基于統計方法或數據挖掘的算法，如頻繁項集[11-12]、隱空間模型[13]、兩階聚類等經典模型。數據挖掘算法中以使用頻繁項集的方法最為典型，但目前這些方法存在著節點判斷的滯后性這個明顯的缺點，即對于節點的重要程度的差別需要較大的時間和空間復雜度為代價才能得到，而無法實時地對一個未知節點進行判定。這在一些實時性要求較高的應用場景下將有著較大的限制。

3 核心節點評價算法

在KAD網絡中，核心節點是指那些對網絡的基本服務起著重要作用的節點，它們實際提供了更多其他節點的訪問、路由工作，其定義表示如下[14]：

定義2（關鍵字熱點）在任一區域Zx中，假設該區域中節點的索引Ia，若每個節點接受的訪問數量為Ca。給定一個關鍵字訪問次數閥值c，若Ca＞c則稱Ia為一個關鍵字熱點。當其共有n個索引時，該節點的訪問次數為其所有索引被訪問次數之和：

定義3（核心節點）在任一區域Zx中，若節點A是一個路由熱點，或節點A是一個關鍵字節點，若在給定的時間T內，A收到的訪問次數R大于給定的閥值c，則A為一個核心節點。

神經網絡是一個多學科交叉領域，它通過模仿人的大腦思維來挖掘海量數據背面的潛在規律，已在各個領域中得到了廣泛應用，并取得了很多重要的成果。采用BP網絡對當前已獲取到的樣本節點進行學習，期望挖掘出有價值的規律，以便對未知節點進行更加實時準確的判定。圖1顯示了使用BP神經網絡進行訓練和測試的整個流程，其中關鍵的環節在于樣本特征提取和處理及網絡訓練兩個步驟。

圖1 樣本數據訓練流程圖

圖1中特征提取是指根據訓練目標，從一組特征集合中選取一組最好的子集。為了處理方便，還需對特征數據進行歸一化預處理，使其值均在[0，1]區間內變化。下面對KAD中可用的特征屬性進行歸納和改進。

（1）R′c：返回節點的有效率

KAD每一次查詢中，若該點不為目標節點時，會為請求者返回α個路由表中更靠近的節點。從KAD路由選擇算法中可看出，當鄰居節點收到請求后，先從對應K桶中選出指定數量的節點，當該桶中節點數量小于指定數量時，則從鄰近的K桶中進行選取。那么，只要路由表中的節點總量不小于指定返回的節點數量，就一定會返回指定數量的節點。當各個鄰居節點若在線，每次提供的下一跳路由節點的數量均相等。因此，采用數量計算并不能使其具有較好地可分離性，這里使用返回節點的有效率來進行衡量，計算公式如下所示：

其中，Bn表示節點I返回的下一跳的路由節點總數，Ln則為當前仍在線的節點數量。對于Ln值的獲取，可以在鄰居節點返回信息后，使用Ping操作探測其中仍在線節點數量。該值反映了一個鄰居節點返回的路由信息中，仍然有效的節點占所有返回總量的比例。

人像蠶一樣拼命織關系的網，但織成之后，卻又千方百計逃之夭夭。范堅強給了一杭一個逃離的機會，可以放下一切，每日枕著書香入眠。一杭成為這間石屋實質上的主人以后，范堅強給他送來了書，讓他在漫長的白天與黑夜，不至于孤獨。但單純的生活結束了，石屋的門終于打開來。

（2）S′c：平均異或距離

在KAD中以跳數作為度量依據，并不能準確地表明節點之間的距離，這里采用平均異或距離進行度量。此值描述了對一個節點進行詢問后，返回結果能更接近目標節點的程度，反映了該點在一次查詢過程中所起到的作用。若節點I共返回n個路由節點，則節點I的平均距離值由下列公式計算得到：

式中，ri代表I的一個返回節點，s與d分別代表請求節點與目標節點。從上式容易看出，當返回的距離越大，則表明通過節點I的查詢后，與目標節點的位置將更接近。

（3）T′t：處理查詢返回時間

該值越大表明了被查詢節點處理性能更高。通常將發出消息和接收消息的時間間隔作為其往返時間。為了處理的方便，設定一個固定的TTL基數作為參照物，若小于此值則也近似地認為與此值相等，這里將TTL設定為2 000 ms。則該值由以下公式決定，其中Mt為返回時間中最大的一個值，也可設置一個固定的較大數值：

（4）R′i：節點返回查詢數量比

該值反映了一個目標節點返回的文件數量占所有返回結果數量中的比例。采用如下公式進行計算：

其中，Rc表明本次查詢所有節點返回的文件總和，但該值僅針對有返回結果的節點才可適用。由于不能保證測試的節點均為有存儲結果返回的節點，因此，需要對經過多個節點路由轉發得到的R′i進處理，確定每個節點的R′i值的大小。這里的基本思想是按各點的S′c的大小來按比例分配，S′c反映了節點推薦的路由節點接近目標的程度。即節點I推薦節點的距離越大，使得請求節點能更接近目標，則I所分到的R′i值則越多。其值的計算公式如下：

（5）F′d：節點返回查詢質量比

該值反映了某點對查詢返回結果文件名與查詢詞的平均匹配程度，它的計算公式如下：

Fi代表了一個返回文件與查詢關鍵字的匹配程度；n代表某點所有返回的文件數量；c為不同節點返回的文件索引數量的總和。其值越大，表明本次查詢所返回的值更好地匹配了關鍵字查詢要求。

由于該值也僅適合于計算有返回結果的情況，因此，參照上一特征值處理過程，對其值使用以下公式進行轉化：

通過以上的處理過程，可以得到一個歸一化后的特征集合＜R′c，S′c，N′m，R′i，F′d＞。該集合中所有取值都已限定在[0，1]范圍中變化。

為了進行訓練，需要收集正反例樣本進行學習與測試。訓練樣本的采集工具使用了自設計的軟件KFetch[14]對網絡拓撲快照進行獲取，采用社會網絡中凝聚中心度指標和隨機行走算法對節點進行評價，將兩種算法共同評價為核心和非核心的節點選出。測試的時間開始于2012年2 月4日20：00，采樣時間持續40 min。這里選取了已有的核心節點作為正例樣本，選擇其中60%的節點作為訓練樣本，將余下的節點作為測試樣本，產生了所需的訓練樣本和測試樣本集。

4 實驗過程與結果分析

針對不同的目的，可以在上述特征集中選取適合的子集進行訓練。從KAD的消息類型可知，其主要有四種基本的RPC（Remote Process Command，RPC）。與查詢相關的包括節點查詢和關鍵字查詢操作。由于兩種消息用于不同的場景，因此其特征值子集也不相同。將兩種消息命令與上面的特征集合進行一個映射后，選取適合的特征屬性建立對應的特征子集。

將與Find_Node相關的特征集合標記為Cn，選取與其對應的特征有＜R′c，S′c，N′m＞。因為在以節點為目標的查詢中，其返回的結果只有兩種可能性，即能命中或不能目標。因此，對于返回結果的處理相對簡單，則記為C′n=＜R′c，S′c，N′m＞。選擇與Find_Value相關的特征集合標記為Vn，則與其對應的特征有＜R′c，S′c，N′m，R′i，F′d＞。該特征集合中含有查詢結果索引及索引結果質量，這樣可以更全面地考核用戶查詢后結果的命中情況，記為Vn= ＜R′c，S′c，N′m，R′i，F′d＞。

使用Find_Node采集節點的特征屬性。先將該區域劃分為?個部分，在各部分中隨機挑選一個節點ID作為待查詢目標ID。這樣做的目的是更有效地考察某點到各個距離位置的情況。?個測試服務器分別選定一個ID的鄰居來生成客戶端ID。開始測試時需保證一定的節點已將?個節點的加入自己的路由表中。實驗中參數?設定為8，先對通過前面選的核心節點進行特征采集，測試時間持續25 min，完成所有待訓練和測試節點的樣本所需特征值的獲取。

將得到的歸一化處理后的樣本數據組成為學習和訓練樣本，格式為：L=T=＜R′c，S′c，N′m，E＞。E為該節點的對應期望取值，即該節點為核心節點的概率。由于希望輸出結果為一個概率值，因此在進行重要程度排序的時候，不能將一個最重要的節點與一般重要節點進行等同，這樣將降低結果的精度。因此，需要將上述兩種算法得到的核心節點進行相應變換操作。其方法是取兩種方式所共同選中的核心節點，按重要程度排序后，對應指定結果的概率范圍為[0.6，1]。即將所有核心節點進行5等分，每一部分區域中的節點給定一個對應的概率期望值，對反例樣本的處理也是按此方法進行。將這樣組成后的訓練樣本送入網絡中進行學習，這里的實驗中對學習誤差設置為0.001。隱層神經元個數取輸入層的1.4倍，即設置為5個，輸入層的傳遞函數設置S型正切函數tansig，輸出層的傳遞函數S型對數函數logsin，采用負梯度權值修正方法。為了降低編碼的難度，其學習和測試過程均使用了MatLab[15]工具箱中的神經元組件進行實驗，程序清單如下所示，其中輸入數據整理為矢量形式，其值對應變量P，輸出的期望值也按矢量方式賦值于變量T。

上面代碼中minmax（P）是指以輸入數據中的最大和最小值為訓練數據的變化范圍，net_1為訓練后得到的輸出網絡。

通過多步的網絡訓練可得到了滿足誤差要求的樣本數據擬合情況，實驗結果如圖2所示。

圖2 Find_Node特征學習擬合效果圖

由圖2可以看出，當學習的次數到達889時，則誤差已經控制在指定的范圍了。將該訓練完成的網絡輸出結果概率與期望值進行對比，將誤差范圍在0.2之內的均認為成功。那么，其中正例樣本識別達到78.3%，反例樣本的識別率達到了67.1%。將訓練好的網絡模型在實際的KAD中進行了驗證，采用KFetch工具對節點關系進行獲取后，抽取出在線節點的對應屬性集送入模型中進行判定。每次實驗時間持續30 min，實驗共重復5次，對實驗結果進行統計和分析。同時，將識別結果與使用凝聚中心度與隨機行走算法所篩選出的核心節點進行對比，結果顯示采用BP模型的核心節點識別率平均為63.8%。雖然實際網絡中識別率略低于訓練結果，但仍可證明該方法具有一定的可行性和實用性。

5 小結

本文通過利用測量實驗收集KAD節點的屬性特征，并根據查詢命令選取了對應的特征子集進行實驗。從實驗結果可以看出，由于網絡中節點的動態性命使得識別效率仍有待提高，但這種實時的判定方法可有效地解決判定的滯后性，具有更廣闊的應用前景。為了改進識別的準確性，今后，將重點對節點的屬性進行更為深入的研究。從上可知，BP網絡性能的高低主要取決于兩個因素：抽取的節點屬性特征數量和選擇的屬性特征質量。尋找有效的節點屬性特征需要更深入地對KAD網絡中節點進行分析，抽取出節點有效屬性特征來豐富屬性集合。其次，嘗試采用其他模式識別的方法，如模擬退火算法、Tabu搜索算法和遺傳算法等[16]，可以對現有的特征屬性進行適當地變形、計算和提取，以得到更佳的具有可分屬特征值，從而有效地提升核心節點識別的準確率。

[1]何建軍，李仁發.改進的隨機游走模型節點排序方法[J].計算機工程與應用，2011，47（12）：87-89.

[2]Maymounkov P，Mazieres D.Kademlia：a peer-to-peer informaticssystem based on theXOR metric[C]//Proceedings of the 1th International Workshop on P2P Systems，2002：53-65.

[3]蔣君，鄧倩妮.eMule系統中的非均勻性分布[J].微電子學與計算機，2007，24（10）：153-156.

[4]熊偉，謝冬青，焦炳旺，等.一種結構化P2P的自適應負載均衡方法[J].軟件學報，2009，20（3）：661-663.

[5]李振宇，謝高崗.基于DHT的P2P負載均衡算法[J].計算機研究與發展，2006，43（9）：1579-1580.

[6]周春光，曲鵬程，王曦，等.DSNE：一個新的動態社會網絡分析算法[J].吉林大學學報：工學版，2008，38（2）：408-411.

[7]Cai Hua，Zhou Chunguang，Wang Zhe，et al.Algorithm research on community mining from dynamic social network[J].Journal of Jinlin University，2008，26（4）：380-382.

[8]Berger-Wolf T Y，Saia J.A framework for analysis of dynamic social networks[C]//Proceeding of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2006，12：523-528.

[9]赫南，李德毅，淦文燕，等.復雜網絡中重要性節點發掘綜述[J].計算機科學，2007，34（12）：1-4.

[10]郭軍，李明輝，董社勤，等.隨機行走的電路分析應用及并行化改進[J].計算機工程與應用，2010，46（18）：199-201.

[11]鄧忠軍，宋威，鄭雪峰，等.P2P網絡中最大頻繁項集挖掘算法研究[J].計算機應用研究，2010，27（9）：3490-3492.

[12]宋文軍，劉紅星，王崇駿，等.以圖頻繁集為基礎的核心節點發現[J].計算機科學與探索，2010，4（1）：82-85.

[13]Sarkar P.Dynamic social network analysis using latent space models[C]//ProceedingsoftheACM SIGKDD Explorations Newsletter，2005：31-35.

[14]王建.基于KAD網絡監督的關鍵技術研究與實現[D].成都：四川大學，2012.

[15]飛思科技產品研發中心.神經網絡理論與MATLAB7實現[M]// MATLAB應用技術.北京：電子工業出版社，2005：4-90.

[16]邊肇祺，張學工.模式識別[M].北京：清華大學出版社，2006：176-208.

1.College of Computer,Sichuan University,Chengdu 610041,China

2.Department of Computer Science and Software Engineering,Jincheng College of Sichuan University,Chengdu 611731,China

In view of the core node recognition in the KAD（Kademlia）,a model based on BP is presented to determine whether a node is core node in real time.According to the result of the measurement for KAD,some attribute characteristics extraction and normalization processing is implemented to obtain an attribute set with higher separable degree.An algorithm in MatLab is designed to train the BP network until the results limit in a predetermined error range.In addition,the trained BP model is adapt to test prepared data,the results of the experiment show that the method can judge a node degrees of importance,and the recognition accuracy rate is up to about 70%.

Back-Prorogation（BP）;KAD network;core node;recognition

A

TP393

10.3778/j.issn.1002-8331.1210-0276

WANG Jian,FENG Weisen,QIU Xingchao,et al.Study of recognition algorithm for core node in kad network based on BP model.Computer Engineering and Applications,2013,49（7）：72-75.

王建（1979—），男，博士，講師，研究領域為網絡安全與應用；馮偉森（1962—），男，副教授，研究方向為網絡信息系統。E-mail：wj_98@163.com

2012-10-26

2012-12-28

1002-8331（2013）07-0072-04