基于Hopfield網絡的復雜網絡社團提取

代婷婷， 梅 端

(1.昭通學院 數學與統計學院， 云南 昭通 657000； 2.廣東海洋大學 理學院， 廣東 湛江 524088)

●數學研究

基于Hopfield網絡的復雜網絡社團提取

代婷婷1， 梅 端2

(1.昭通學院 數學與統計學院， 云南 昭通 657000； 2.廣東海洋大學 理學院， 廣東 湛江 524088)

針對復雜網絡中的社團提取問題，提出了一種基于離散Hopfield神經網絡的社團結構提取算法，該算法的思想為：首先，對復雜網絡數據的進行處理；其次，結合社團提取準則模塊度函數Q的形式設計Hopfield神經網絡的權值向量W和閾值T；最后，根據網絡穩定點的輸出值提取出網絡中的社團結構.仿真實驗表明，本文中的Hopfield神經網絡算法比譜分算法得出的Q值更優，對網絡的劃分更接近實際網絡.針對復雜網絡中的社團提取問題，提出了一種基于離散Hopfield神經網絡的社團結構提取算法，該算法的思想為：首先，對復雜網絡數據的進行處理；其次，結合社團提取準則模塊度函數Q的形式設計Hopfield神經網絡的權值向量W和閾值T；最后，根據網絡穩定點的輸出值提取出網絡中的社團結構.仿真實驗表明，文中的離散Hopfield神經網絡算法比譜分算法得出的Q值更優，對網絡的劃分更接近實際網絡

復雜網絡； 社團提取；Hopfield神經網絡

1 引言

圖1 三個社團組成的復雜網絡[1]

近些年來，復雜網絡吸引了很多領域研究人員的關注，諸如物理學、生物學、社會學、工程等領域的極大關注，因為復雜網一般是指節點眾多，連接關系復雜的網絡，這是因為這種靈活普通的描述能力，使得它可以用于各學科領域對復雜系統建模、分析.因此，對于復雜網絡的研究越來越多.隨著對復雜網絡的深入研究，發現復雜網絡有一些共同特征即它門中都存在社團結構，這些社團的共同特點是外部鏈接稀疏，內部鏈接緊密，如圖1所示[1-2].事實上，社團結構在實際系統中有著重要的意義：在人際關系網絡中，社團結構可能是代表每個家庭、可能是代表某種職業、可能是代表某個地區或者是年齡的群體；在萬維網中，不同的社團可能代表了不同的網頁[3]；在新陳代謝網絡及神經網絡中可能代表了某種功能單位；在食物鏈網中，社團代表了生態系統中的子系統.在研究網絡的性質及功能時，社團結構也有相當顯著的表現.例如，在網絡動力學的研究中，當外加能量處于較低的水平時，同一社團的的個體就能達到同步狀態；在網絡的演化研究中，相同社團內的個體可能始終連接在一起[4].總之，如果要了解網絡結構和功能，那么研究網絡中的社團結構是一個很好的途徑.因此，用什么樣的的方法將網絡中的社團結構提取出來表現的相當重要.針對提取出復雜網絡中的社團結構這課題，很多研究人員提出了很多的算法，其中最早的就是2003年Newman和Girvan[5]提出的GN算法，繼次之后國際上掀起了一股社團提取的熱潮，不同領域的科學家提出了很多新穎的方法.

2 算法與理論

2.1 模塊度函數[6-8]

針對復雜網絡的社團提取，2004年Nweman和Girvan定義了一個量化的社團提取標準——模塊度函數Q，每個社團劃分的是否合理可以由模塊度Q來度量，較合理的劃分擁有較高的模塊度Q，給定具有n個節點的網絡G=(V,E),模塊度含義是指落在同一社團內的兩個節點實際的邊減去這兩個節點有邊的概率，然后將這些差值相加就是模塊度，表達式如下:

(2-1)

m表示網絡的總邊數，若頂點i,j被劃分到一個社團內，則δij=1，否則δij=1，didj表示節點i,j所具有的度，Aij表示網絡的鄰接矩陣.為了最大化(2-1)，引入決策變量，定義了n維決策變量.引入n維決策向量((x1,x2…x)′∈Rn,其中

則(2-1)就可以用模塊度矩陣B表示為：

(2-2)

因此，模塊度復雜網絡的社團提取問題就變成了數學優化問題：

(2-3)

(2-4)

2.2 基于模塊度的譜算法[9]

Gewman和Girvan在2004年定義模塊度函數Q時，為了最大化模塊度Q，采用的是基于′模塊度矩陣的譜算法，通過計算模塊度矩陣的最大特征值對應的特征向量來決定決策向量的符號，下面給出此算法的具體步驟：

Step 1:輸入復雜網絡的鄰接矩陣A和度向量d；

Step 3:計算矩陣B的特征值及特征向量；

Step 4：根據最大特征值λmax對應的特征向量umax確定決策向量x的符號，其中

Step5：將決策向量x中+1對應的節點組成的社團P提取出來.

2.3Hopfield神經網絡理論[10]

Hopfield網絡是由美國加州理工學院物理學家J.J.Hopfield教授于1982年提出的一種單層反饋神經網絡，Hopfield網絡在輸入的激勵下，可以得到Hopfield網絡的輸出，這個輸出反饋到輸入又會得到新的輸出，那么當這個反饋過程已知進行下去，如果Hopfield網絡是一個能收斂的穩定網絡，則這個反饋與迭代的計算過程所產生的變化就越來越小,一旦達到穩定狀態，Hopfield網絡就會輸出一個穩定的恒值.這就是Hopfield網絡的穩定性，也是Hopfield網絡在很多領域被廣泛應用的基礎，而分析Hopfield網絡穩定性的工具就是能量函數.

一個n介Hopfield網絡H=(W,T)由n個神經元、權值矩陣和閾值向量組成，W=(wij)為n×n階權矩陣，其元素表示神經元j到神經元i的權重，T=(ti)為n維列向量，稱為閾值向量，其元素ti表示神經元i的閾值，網絡的輸入輸出是關于時間t的函數，輸入用x(t)=(x1(t),x2(t),x3(t),…,xn(t))′表示，輸出用v(t)=(v1(t),v2(t),…,vn(t))′表示，Et是Hopfield網絡在t時刻的能量函數，f是激活函數.

依據不同的激活函數，將Hopfield網絡分成離散型(DHNN)和連續型(CHNN)兩種,在DHNN下的激活函數f的值一般取1，-1或者1,0.DHNN的工作方式一般有同步和異步兩種工作方式，我們重點介紹第一種同步工作方式.

DHNN的同步工作方式(并行)

在某一時刻n個神經元同時改變狀態，更新方式如下：

(2-5)

同步能量函數

(2-6)

下面我們介紹一個定理，這是根據設計出的網絡權矩陣判斷DHNN網絡同步工作時是否收斂的依據.

定理：網絡以同步方式工作時，若權矩陣 為對稱矩陣，那么對于任意初態離散型的Hopfield網絡將收斂到一個穩定點或一個長度為2的極限環，即網絡收斂的狀態滿足：

2.4 基于Hopfield神經網社團提取算法

現階段，Hopfield網絡主要是利用漸進穩定點來解決實際問題，將能量函數視為一個優化問題的目標函數，把系統的穩定點作為能量函數的極小點，那么從一個初始狀態朝這個穩定點的迭代過程就是求解該優化問題的過程.此方法的優點在于只要構成這種反饋網絡，適當的設計其權矩陣和閾值向量就可以達到目的.

本文方法的基本思路：第一步，根據模塊度準則設計Hopfield網絡的權值向量W和閾值T，同時依據上面提到的定理，保證此網絡最終能夠收斂；第二步根據復雜網絡節點的數目隨機生成Hopfield網絡的初值，這里的初值首先假定為1和-1，帶入設計的 和 中；第三步將以上兩步的計算結果帶入Hopfield網絡的能量函數中進行迭代直到Hopfield網絡收斂；第四步，輸出Hopfield網絡收斂結果x(t)，提取出社團P={vi|xi(t)=+1}.

能量函數穩定點就對應于如下模塊度準則的一個局部最優解，其中B為模塊度矩陣.

(2-7)

3 實證分析

3.1 數據來源及處理[11]

本文中的實驗數據來自復雜網絡數據庫(Networkdata)，我們可以在網站http://www-personal.umich.edu/～mejn/netdata/下載.本文下載了一些具有代表性的實際復雜網絡數據Zachary空手道俱樂部網絡，它是一個社會網絡，共有34個成員，因為某種意見形成了以校長和主管為代表的兩個社團.節點0和33分別代表校長和主管；寬吻海豚網絡62個成員，在研究期間由于一個關鍵成員的離開，海豚群落自然分為兩個小的群落，還有美國政治書籍網絡、美國大學足球賽網絡等.在實驗過程中本文所用的工具是Watlab2014.

3.2 實驗結果分析

本文中對Zachary空手道俱樂部網絡進行了重點實驗，利用 2014采用已有的方法和本文提出的方法在Zachary空手道俱樂部網進行了實驗，主要是從提取的指標函數值能否達到最優以及當指標函數值達到最優時社團結構方面將本文提出的算法和之前已經有的算法進行了比較.

3.2.1 模塊度指標檢驗Zachary空手道俱樂部網絡

使用模塊度Q指標對Zachary空手道俱樂部網絡進行社團提取，譜算法得到的最大的Q=0.371 5，在此目標函數值下Zachary網絡社團劃分的結果是唯一的見圖2(a)，Hopfield神經網算法得到的 ，在此目標函數取得最優的情況下，Zachary網絡的劃分結果如圖2(b)所示.在Hopfield神經網算法迭代計算的過程中網絡收斂穩定時得到的Q值按從大到小的順序排列，不同的Q值其所對應的頻數見表1.

表1 Hopfield神經網算法得到的目標值Q及對應的頻數和劃分

圖2(a)

圖2(b)圖2.Zachary網絡在譜分算法和Hopfield方法下劃分結果

圖2(a)譜算法在Q=0.371 5的網絡劃分結果,圖2(b) Hopfield神經網算法在Q=0.371 8時的劃分結果，在Hopfield神經網絡算法計算迭代的過程中我們發現Q=0.371 5是該算法的次最大，這時候劃分也是相同的.但是Hopfield神經網算法可以得出一個最大的Q=0.371 8，那么在Hopfield神經網算法這兩個目標值下所對應的網絡狀態有什么聯系呢？通過實驗數據發現，圖2(b)是某一初值收斂到極限環的最終狀態，而圖2(a)就是它的前一個狀態，當9號點被劃分到另外一個社團后，Hopfield神經網絡就穩定了，這兩個狀態稱為極限環的一組對偶解.

3.2.2 模塊度指標檢驗海豚網絡

寬吻海豚網絡是一個具有62個節點的網絡，同樣也使用模塊度函數Q作為目標函數，分別使用本文的Hopfield神經網絡算法和譜分算法對寬吻海豚網絡進行劃分，隨機生成了800個Hopfield網絡初值，有85個初值收斂到網絡的穩定解，剩下的收斂到了極限環，將Hopfield網絡算法得到的模塊度函數Q值從小到大進行排序，發現Hopfield網絡算法的前5個Q均大于譜分算法的最大的Q值，譜分算法得到的最大Q值是0.385 6具體結果如表2.劃分后的可視化圖形如圖3所示.

表2 Hopfield網絡算法在寬吻海豚網絡上劃分結果

圖3 (a)

圖3 (b)

圖3 (c)

圖3 (d)

圖3 (e)圖3.dolphin在Hopfield算法下前5個最大特征值對應的網絡劃分結果圖

注：只列出了Hopfield網絡算法前面最大的5個Q值

上面的結果說明了，以模塊度函數Q能取得最大的值作為復雜網絡社團提取的準則，那么本文的Hopfield網絡算法優于其他的算法， 圖3(e)的劃分結果對應于譜分算法的最優值的劃分，但是實際中寬吻海豚網絡對應于圖3(a)的劃分，除此之外，我們在Zachary空手道俱樂部網絡上實驗時，Hopfield神經網算法可以得出一個最大的Q=0.371 8比譜分算法得到的Q值要大，且對應的劃分也比譜分算法得到的劃分更接近實際網絡，即只要能根據社團提取指標設計出新的Hopfield神經網算法網絡矩陣與閾值向量，就可以用它來提取出復雜網絡中的社團結構.

4 總結與展望

隨著信息技術的產生，數據規模的迅速膨脹，人們現實中的許多復雜系統抽象成許多復雜網絡來研究，然而復雜網絡是由一些社團構成，而且這些社團的的結構和功能決定和反應的復雜網絡的功能特性.因此，如何提取出復雜網絡中的社團結構就成了相關領域的研究熱點，本文針對這個問題提出了一個新的社團提取算法即Hopfield神經網算法，該方法通過簡單的迭代，當網絡達到穩定狀態能量函數取得最小值時，根據網絡的穩定點輸出就可以提取出復雜網絡中的社團結構簡單快速，但是也存在一些不足，即網絡的規模超級大的時候，大規模的數據用迭代的方法操作會耗費很長的時間，甚至一般的家用計算機因為配置的原因都無法操作.所以在以后的研究中要進一步的完善該方法，或者設計出更有效的社團提取方法.

[1]S.Fortunato.Communitydetectioningtaphs.Rep[J]. 2010,486(3):75—85.

[2]D.Wats,Sstrogatz.Collectivedynamicsof’small-world’[J].Nature,1998, 393(6):440—442.

[3]A.L.Barabasi,R.Albert.Emergenceofscallinginrandomnetworks[J].Science,1999,286(5439):509—512.

[4]王樹禾. 圖論[M]. 北京：科學出版社，2009.

[5]M.E.J.Newman.Thestructureandfunctionofcomplexnetworks[J].SIAMReview，2003,45(2):167—256.

[6]Newman.M.E.J.Detectingcommunitystructureinnetworks[J].TheEuropeanPhysicalJournalB:CondensedMatterandcomplexSystems,2004,38(2):321—330.

[7]NewmanM.E.J.modularityandcommunityStructureinnetworks[J].proceedingsoftheNationalAcademyofSciencesoftheUnitedStatesofAmerica,2006,103(23):8577—8582.

[8]Newman.M.E.J.Findingandevaluatingcommunitystructureinnetworks[J].PhysicalReviewE,2004,69(2):026113.

[9]Newman.M.E.J.FindingandevaluatingcommunitystructureinnetworksUsingtheeigenvectorsofmatrices[J].PhysicalReviewE,2006,74(3):036104.

[10]HopfieldJ.J.Neuealnetworksandphysicalsystermswithemergentcollectivecomputationalabilities[J].PreceedingsoftheNationalAcademyofScienceoftheUSA,1982,79:2554—2558.

[11]http://www-personal.umich.edu/～mejn/netdata/.

Based on discrete Hopfield network is a complex network of associations

DAI Ting-ting1， MEI Duan2

(1.School of Mathematics and Statistics, Zhaotong University, Zhaotong 657000， China； 2.College of Science, Guangdong Ocean University, Zhanjiang 524088, China)

For community extraction problem in complex networks, this paper proposes a community structure extraction algorithm based on discrete Hopfield neural network, the algorithm ideas as follows: first, to deal with complex network data; Secondly, combining with community extraction criterion module function design Hopfield neural network, in the form of weight vector and the threshold value; Finally, according to the output value of the stable point to extract the network of community structure. Simulation results show that in this paper, a discrete Hopfield neural network algorithm is better than it is concluded that the value of the spectrum points algorithm, the division of the network closer to the actual network.

Complex network; Associations extract; Hopfield neural network

2016-08-06

代婷婷(1986— )，女，甘肅慶陽人，助教，碩士，主要從事智能計算研究.

O157.5，TP

A

2095-7408(2016)05-0019-08