社會網絡的層次結構發現

成 清，黃 森，黃金才

（1.國防科學技術大學信息系統工程重點實驗室，長沙410073；2.78020部隊 昆明650221）

0 引言

現實生活中很多自然、社會系統都可以用復雜網絡來描述，如社會網絡［1－2］，Internet網絡［3－4］，和生物網絡［5－6］等。網絡通常都具有某些結構特征，如模體、模塊性和層次結構等。其中網絡的層次結構是一種最為常見的組織結構特征，如軍事組織、企業組織等都具有典型的層次結構特征。分析網絡的層次結構不僅有助于揭示網絡自身組織結構與形成機制，使人們更好地理解系統不同層次的結構和功能特性，而且對自然網絡和人工網絡的認識和干預有重要意義，是了解人類行為模式的基礎。目前對網絡層次化結構挖掘的研究主要從如下幾個方面進行：

層次結構就是網絡中節點按照某些值的排序［7］，認為整個網絡具有k層，綜合節點自身屬性或拓撲特征，建立所有節點層次測度指標，計算它們的指標值，將其映射到k層中的某一層，主要有中心性計算方法［8］，k－core測度計算方法［9］和層次指標度量方法［10］等和影響力對比方法。

層次結構是一種嵌套層次［11］，高的層次包含低的層次。主要有層次聚類方法［12－14］，主要思想是把網絡中的節點或邊作為聚類單元，選擇相似性最大的聚類單元進行聚類，得到一些規模比較小的社區，再對這些小社區進行聚類，得到一個大一些的社區，如此聚類，形成一顆樹狀圖，即網絡的層次結構。

以樹結構作為層次結構［15］，如結構匹配方法，此類方法用樹結構來代替層次結構，然后再利用已知信息，生成符合該特征的備選樹，最后再選擇最優匹配結構為該網絡的層次結構。

上述研究大都沒有深入分析現存網絡中層次結構的特征，也未仔細分析網絡內部信息的交互過程。針對此問題，最新的研究提出層次結構是一種流層次結構，并且節點排序和嵌套層次結構都能轉換成流層次結構［16］。流層次結構首先是基于節點對整個網絡的影響排序，然后根據排序高節點到其它節點的局部可達集中性來確定層次結構。但這種方法是基于傳統的社會網絡圖模型的，沒有考慮到社會網絡現實的固有屬性特征，比如一個公司成員的職位高低，兩個人之間朋友關系的親疏等等；另外，流層次結構并未確定流的最佳路徑，即不能挖掘出網絡的骨干層次關系。針對上述問題，本文考慮節點和邊的固有屬性建立社會網絡擴展圖模型，然后在流層次思想的基礎上，定義了面向使命任務的層次結構，并提出基于信息粒子流動的層次結構發現方法。

1 社會網絡的擴展圖模型

在實際網絡中，大部分的節點與節點都存在差異性，且節點之間的連接程度也有所不同。造成這些差異的原因是節點或邊之間的屬性不同。因此，本文考慮節點和邊的屬性，建立擴展圖模型G＝（V，E，δ，μ），其中V為節點集；E為邊集；δ是從點集到［0，1］的映射，代表節點的綜合屬性值；μ是邊集到［0，1］的映射，代表節點與節點的綜合關系屬性。

1.1 節點的抽象

對節點的抽象實際上就是將節點的相關屬性映射到節點的綜合屬性上，即確定G中的δ，其數學描述為：假設節點的屬性向量FV＝｛fv1，fv2，…，fvn｝為自變量，綜合屬性δ為因變量，則需建立一個δ＝f（FV）∈［0，1］的函數映射關系［17］。本節從節點屬性的分布出發，通過投影的方法，將節點的屬性向量FV＝｛fv1，fv2，…，fvn｝，映射到投影特征值z上，由此得到δ＝f（z）。最后，再將節點的綜合屬性映射到［0，1］空間中，即δ→［0，1］。具體過程如下：

首先，進行屬性的歸一化，在實際問題中，影響節點重要程度的屬性很多，其量綱和取值范圍也可能有很大的差異，為有取值的屬性去量綱化和數據歸一化，把屬性數據都變化到［0，1］區間上。

然后，把屬性向量FV＝｛fv1，fv2，…，fvn｝綜合成a＝｛a1，a2，…，an｝為投影方向的一維值zi，即

投影方向實際上反映了各個屬性值對于重要程度的權重。如果有充分的先驗信息或者知識，那么就可以為投影方向的確定提供支持，如AHP方法；如果沒有足夠的先驗信息來提供支持，則可以根據屬性的分布和具體應用采用投影尋蹤［18］的方法確定其投影方向。

最后，將投影值進行伸縮變化，將節點的綜合屬性映射到［0，1］空間中。如采用δi＝zi／zmax。其中，zmax是最大的投影值，zi是某一節點的投影值。

1.2 關系的抽象

社會網絡的擴展圖模型中定義節點間的關系如下：在一個有限的節點集合V中，關系可以定義為μ：V×V→［0，1］，表示為

其中，記rij：＝μ（vi，vj），矩陣R＝（rij）n×n為關系的鄰接矩陣，采用關系的重要性代替關系的存在性，針對特定的社會事件恰當地抽象出它的重要性，并賦予［0，1］之間的相應的權值，來度量社會關系在社會網絡中的表征。

另外，對于某一對相鄰節點而言，可能發生多次社會事件，本文引入文獻［19］中提出的聚合操作來處理多重關系的聚合問題。當圖G中出現平行邊，即某對相鄰節點具有多個關系時，定義聚合操作用來對多個關系進行聚合，若α和β為G中某相鄰節點的兩個社會關系，則α⊕β＝α＋β－αβ。

可見拓展圖實際上是在傳統圖的基礎上增加了節點和邊的權重，但是節點和邊的權重并不像傳統圖一樣是單一屬性的度量，而是采用節點屬性投影和多個關系的聚合操作實現多屬性的綜合映射，模型能夠更好地考慮節點和關系的多屬性特征。雖然由于進行了投影操作，增加了計算復雜度，但投影計算只用在網絡構建中，當網絡構建后不會影響到網絡的分析。

2 網絡的層次結構定義

一個復雜的組織應對具體任務時，它自適應地表現出來的一種層次結構，任務指派是通過節點間的信息流動實現的。面對不同的任務使命時，任務的指派是不同的，所以信息流也是不同的，相應的層次結構也是不同的，這同文獻［16］中認為層次結構是一種流層次結構的思想相似。

指定給組織的使命任務可分解成一組基本任務，稱為任務空間［20］，任務空間中的每一個任務都會被分配給組織中的某個組織成員負責或控制，我們稱這個組織成員為主控成員。在任務空間從頂層到底層的粒化過程中，每生成一個子任務，都會為相應的子任務指定一個主控成員。實際上就是任務樹的生成過程，由此，可以獲得相應的主控成員樹，如圖1所示。

層次結構就是由主控成員與每個主控成員所屬的普通成員構成。從任務流角度看，即確定使命任務的主控成員｛S｝，即根節點，和能具體執行任務的普通成員｛T｝，即葉節點，它們之間存在任務指派流，層次結構的存在，就是為任務指派信息的流通提供一種信道，因為考慮的是連通圖，因此它們之間一定存在一條最優信道（最優信道即在最短時間內能夠通過最多信息量的信道），記為r（·，·），如r（a，b）表示從節點a到節點b的最優信道，最優信道上的節點就位于相應的層次上，如r（a，b）＝（a＝u1，…ui，…，b），則ui位于第i層，當然一個節點可能位于多個層次上，因為這個節點可能位于多條最優信道上。所以層次結構為Г＝∪r（si，tj），其中si∈ ｛S｝，tj∈ ｛T｝。如果把信道看作路徑的話，從根節點到葉節點的最優路徑可能不止一條，造成層次結構的不唯一。因此，本文把最優信道也可看作是一個子圖，該子圖是從根節點到葉節點的連接子圖，旨在能從根節點攜帶最多的信息粒子到達各個葉節點。如圖2所示，根節點為A，它是使命任務的總控成員，H，J，K，L是葉節點。那么根節點A通過信道把信息傳遞給葉節點 H，J，K，L，假設把路徑長度作為最優信道的度量，可分別得到r（A，H）＝ （A，B，D，H），r（A，I）＝（A，B，D，E，I），r（A，J）＝ （A，B，E，F，J），r（A，K）＝ （A，C，F，G，K）和r（A，L）＝ （A，C，F，G，L）5條信道或子圖，將這5個信道的點集和邊集做并操作，得到一個新的集合，很顯然這就是需要挖掘的層次結構，也是骨干層次關系。

圖1 主控成員樹生成圖Fig.1 Spanning graph of the master tree

圖2 簡單的層次結構示意Fig.2 The schematic diagram of the hierarchical structure

3 網絡的層次結構發現方法

根據所定義的層次結構，我們分兩步對層次結構進行挖掘：首先挖掘出根節點和葉節點（根節點和葉節點下文稱骨架點）；然后再挖掘出它們之間的信息流通信道，即層次結構。

3.1 骨架點的挖掘

根據數據場理論，針對給定網絡G＝（V，E，δ，μ），網絡中節點表示數據場中的數據對象，每個節點周圍存在一個作用場，位于場中的任何節點都將受到其它節點的聯合作用，根據真實網絡的特性，我們認為，節點間的相互作用具有局域特性，每個節點的影響能力會隨著網絡距離的增長而快速衰退，采用短程場且具有良好數學性質的高斯勢函數描述節點間的相互作用［21］，綜合考慮網絡拓撲性質和節點固有屬性，可以得到任意節點vi∈V的拓撲勢可表示為

其中，dij為節點vi與vj間的拓撲距離；影響因子σ表示節點的作用范圍；mi≥0表示節點vi（i＝1，2，…，n）的質量。

相比較傳統的社會網絡而言，社會網絡擴展圖最大的不同就在于它的每一個節點和每一組關系都是一個綜合屬性值。本文以節點的綜合屬性值作為其節點質量的度量。聯系的屬性值來源于對引發聯系的社會事件的抽象，代表其強弱程度。在擴展圖中，關于點到點之間的路徑的選擇采用基于邊的綜合關系屬性值映射的距離定義，即d：E→R＋，R＋＝［0，＋∞），對于任意e∈E，稱d（e）為枝e的長度，設P＝ue1v1…vk－1ekv是G中連接u與v的路，稱為路P的長度。

在G中，有μ：E→［0，1］是從邊集到［0，1］的映射。因此，必須設計一種綜合關系屬性值到距離值的函數映射d：E→R＋，它滿足條件：

1）定義域為［0，1］，而值域為［0，＋∞）；

2）d（μ（e））＝0，當且僅當μ（e）＝1；

3）當μ（e）→0時，d（μ（e））→＋∞；

4）d（μ（e））在定義域上是單調遞減、連續光滑的函數。

本文使用函數d（x）來實現這個映射，即

可得

當存在路徑P＊，使得D（P＊）≤D（P），那么P＊就是兩點之間的最短路。顯然從式（5）可知，這條路上全部枝的綜合關系屬性值的乘積，是所有路徑上全部枝的綜合關系屬性值的乘積的最大值。

另外存在一個參數，影響因子σ，根據數據場中關于影響因子的討論［21］，可以引入拓撲勢場的勢熵來衡量σ值的合理性，令節點v1，v2，…，vn的勢值為TP（1），TP（2），…，TP（n），則勢熵可定義為

在一個社會網絡中，如果將節點u斷開，與之相關的聯系也認為失效，就會導致網絡結構的變化，這種變化就會讓另一個節點v的重要性發生變化，這種現象叫做v在某種程度上依賴于u，反過來看，便是u在某種程度上支持v。這種現象反映了節點在網絡中的一種社會性，表現一個節點對另一個節點重要性的支持。在對節點拓撲勢的計算中，已經包含了這種思想，因為拓撲勢的形成，就是由其他節點的能量輻射造成的，這種能量的輻射也是給力的一種表現形式，所以本文將某一節點對另一節點拓撲勢的支持程度，叫做勢支持，則有φG（vi）為節點vi在網絡G中的拓撲勢，又vi，vj∈V，那么vi對vj的勢支持Supp（vj→vi）為

其中，G－vj表示在圖G中去掉節點vj之后的子圖，φG－vj（vi）表示在圖G－vj中節點vi的拓撲勢。勢支持的思想可以從描述兩點之間的關系，推廣到整個網絡上，定義某個節點對整個網絡的勢支持。先定義網絡的拓撲勢為

由此，定義節點vj對整個網絡的勢支持為

節點勢支持的應用意義在于，它主要描述的是某一節點所擁有的能量在多大程度上依賴于另一節點的存在。網絡勢支持主要描述的是整個網絡的能量在多大程度上依賴于某一節點的存在。

從結構意義上來看，根節點只有出度沒有入度，也就是說，它主要根據自身的屬性和能量對下層的節點進行支持，而被支持的節點對其依賴程度是很大的。葉節點只有入度沒有出度，也就是說它不再支持別的節點，而主要是被支持。

從信息流動的角度，根節點對使命任務、外部環境和整個網絡組織都具有較為全面的信息了解，所以它主要是進行任務信息的初始發送，對整個網絡的信息提供支持。而葉結點可能只需掌握自身的子任務與之相關的信息，所以它是信息流動的匯，所有的任務信息最終都流向這些葉節點。

可見不管是從結構意義、信息流動，還是從實際的物理意義而言，根節點對整個網絡結構都應該具有最大的勢支持，而葉節點則對整個網絡結構具有最小的勢支持，因為它基本屬于完全被支持的地位。

3.2 層次結構的發現

根據節點對網絡的勢支持確定根節點和葉節點之后，需要挖掘根節點和葉節點之間的流通信道。根據層次結構的定義，流通信道是一個從根節點到葉節點的連接子圖，旨在從根節點攜帶最多的信息粒子到達各個葉節點。因此，流通信道的挖掘問題歸結為根節點分別與不同葉節點之間的最優子圖挖掘。

該問題描述為：對于給定圖G＝ （V，E，δ，μ），兩個節點s和t，s，t∈V 且s≠t，s為根節點，t為葉節點。定義一個子圖質量函數f（·），找到一個包含s和t的連通子圖C，使得f（C）最大。所以首先需要確定圖質量函數。受文獻［22］的啟發，本文引入電流網絡的計算方法來分析信息粒子在根節點和葉節點之間的流動過程。通過使用模擬信息粒子的隨機游走過程，使得最優子圖中能在s和t中運送最多粒子，這些粒子是一直都在該子圖中，并且最優子圖包含的節點最少。由此提出最優子圖的挖掘方法。

在粒子流與電子流的類比分析中，如果將1V的電壓加在節點s和t之間，V（s）＝1，V（t）＝0，則任何一點的電壓則可以理解為粒子從該點出發，到達t點之前到達s點的概率；而電流則可以理解為1A的電子流從s出發流到t被其吸收，而流過邊的電流的大小表示粒子在游走期間，通過該邊的概率值。因此可以假設I（u，v）便是從節點u到節點v的電流，U（u）為節點u處的電勢，那么根據歐姆定律，在同一電路中，導體中的電流跟導體兩端的電壓成正比，跟導體的電阻阻值成反比，可以得到：

其中，C（u，v）為節點u和v之間的電導系數，在本文中C（u，v）＝μ（u，v），μ（u，v）表示節點u和v的綜合關系屬性值。

另根據基爾霍夫電流定律的描述，流入一個節點的電流總和，等于流出節點的電流總和，可以得到：

所以，根據歐姆定律和基爾霍夫電流定律，可以得到計算這個網絡中所有節點處的電勢就可以轉化為求解如下一個線性系統：

這種方法與粒子在圖上的隨機游走過程本質是一樣的，假設s是發射態，t是吸收態，則可能存在s1到t1和s2到t2的最優路徑，有P1＝s1a1t1且P2＝s2a2t2，認為兩條路徑完全一樣。事實上，應該對度高的節點采取一種懲罰措施，因此引入沉沒點z的概念，與t一樣，它也處于吸收態，一旦粒子到達這一點，它就不再游走，所以V（z）＝0，并且設定與沉沒點連接的那條邊的電導系數為［22］

因此，粒子流不一定全部都由s出發流向t，它有一部分也可能流向沉沒點z，很顯然，度為1的點都可以設置為沉沒點，這就是對度多的點和節點多的子圖的懲罰，因為度越多，粒子流向沉沒點的可能性越大。電子流是從電勢高的節點流向電勢低的節點。如有V（u）＞V（v），則I（u，v）＞0，即電子流從u流向v，記為u→v。路徑P是從s節點到ui節點，記為P＝（s，…，ui），其中對于路徑中的任意j都有uj→uj＋1，由于電子流是從電勢高的節點流向電勢低的節點，所以路徑中不存在環路。據此有

定義1［22］在路徑P ＝ （s＝u1，…，ui）上，傳遞的電流DF（P）為

定義2［22］在原圖G中的一個子圖G＊，它所具有的傳遞電流為所包含的所有路徑的傳遞電流之和：

如果s，t∈G＊且G＊假設為從節點s到節點t的最優子圖，則對于任何一個子圖G′，都有

其中，｜G＊｜是G＊中所擁有的節點數。代表從s流出的信息粒子通過G＊流向t，是以最小的代價攜帶了最多的粒子流。所以，f（G＊）＝DF（G＊）符合最優子圖質量特征的函數定義。

根據定義的圖質量函數，可以采用文獻［22］中的最優連接圖發現算法發現最優子圖。

然后根據層次結構的定義，可知層次結構是最優子圖的并集，它的物理意義是，希望找到組織在信息流動層面上的骨干層次結構，所以只需動態挖掘出這些最優子圖，然后將它們做并操作，就是所定義的層次結構。

綜合上述，整個層次結構的挖掘過程是：設層次結構為Г（V，E），節點和邊都初始化為空。首先，根據節點的網絡勢確定最大的勢支持點s和若干最小勢支持點t＝｛t1，t2，…｝；然后計算出它們之間的最優子圖，如s到t1的最優子圖Gsub1，然后在原圖中刪除最優子圖除s的部分，繼續找到剩下的圖中勢支持最小的點t2，并計算s與t2的最優子圖Gsub2，刪除Gsub2中除s的部分，繼續重復操作，直到所有的點都被包含，最后Г（V，E）＝∪Gsubi（i≤｜V｜）。具體算法偽代碼為：

4 實驗分析

2002年1月2日，Enron公司宣布申請破產保護。之后，聯邦能源規劃委員會開始了對Enron公司的財務調查，其中一項是通過調查公司員工的郵件進行的，并于2003年10月14日將郵件系統公布在網上以視公正。最初Enron郵件語料集包含了158個用戶的619 446封郵件信息，除去附件后有用戶151個，郵件信息文件約517 431個，有很多研究者對Enron郵件數據做過處理，對應不同的版本，本文用到的Enron Email數據集見文獻［23］?？疾鞆?998年10月到2002年9月這47個月的郵件發送量，便可以得到每個月份的郵件發送量分布（見圖3）。

另外本實驗還用到另一份人名與職位的對應表和一份人名與郵箱的對應表，其中只有104個人的職位是確定的，為了使后續實驗更加精細，所以我們的分析對象就是這104個人所構成的郵件通信網絡。

本實驗旨在研究Enron公司在應對日常業務和財務危機時的層次結構。在建模時，主要考慮的是與完成使命任務相關的屬性，對于節點，主要考慮成員職位，本文把組織中的9種職位大致歸為5個等級［24］（見圖4）。同時也綜合了成員郵件的發送量，成員郵件的接收量和成員郵件的平均回復時間3個屬性，不過只對職位屬性值進行差異性調整，所占比例較小。所以節點的綜合屬性主要反映了節點的職位等級。

圖3 每個月份郵件的發送量統計圖Fig.3 Distribution of sent eamils over time（month）

圖4 職位的分層圖Fig.4 Dierarchical diagram of position

對于關系，設置一個閾值2，當郵件通信量高于這個閾值時，才將這個關系抽象為一條邊，而且綜合郵件通信的通信頻度和郵件平均回復時間計算其綜合關系。

4.1 應對日常業務

我們選擇發生財務危機之前半年的郵件數據作為實驗的基礎數據，即2001年2月到2001年7月這6個月的數據，也就是圖3中顯示的第1段數據。在這半年中，綜合考慮節點和關系的固有屬性，可以得到如圖5所示的社會網絡擴展圖。同時，根據公式（9）可以計算節點的網絡勢支持（見圖6）。

圖5 應對日常業務的社會網絡屬性圖模型Fig.5 The attribute－graph model of social network of enron＇s daily business

圖6 應對日常業務的網絡勢支持分布圖Fig.6 Distribution of network potential support for enron dealing with the daily business

由圖6可知，網絡勢支持最大的節點為3，其次是節點68，而節點8，12，45，46，55，57，76，88，89，90，92，93，99和103的網絡勢支持較小，幾乎為0?？梢园丫W絡勢最大的節點作為根節點，如節點3，網絡勢支持較小的點作為葉節點，采用HierarchicalMining算法可以得到整個網絡的層次結構，如圖7所示。

因為節點的綜合屬性值基本反映了現實網絡中節點的職位等級，從圖7可以看出，整個挖掘出的骨干層次網絡基本符合現實網絡中職位的高低，即綜合屬性值較小的基本在綜合屬性值較大的下一層。但是個別綜合屬性小的節點卻位于綜合屬性大的節點的上層，如節點68，現實職位雖然不高，但在應對日常業務中，它同節點3的綜合關系強度較大，而且節點3到節點5，6大部分通信都頻繁通過3進行，是高層之間的紐帶，還有如圖6，節點68對的網絡勢支持僅次于節點3，可見其對整個網絡的影響很大，所以綜合其固有屬性和拓撲結構，從信息流角度分析節點68位于層次結構的高層是合理的，而且這也符合現實Enron公司中，節點68的職位雖然是職員，但是他的工作卻是負責管理關系的。另外，如職位等級較高的節點19，22，35，42等節點都是位于層次結構的葉節點，是由于在現實網絡中，他們本身就處于網絡的邊緣（見圖5），所以從信息流角度認為他們在層次結構的底層。

4.2 應對財務危機

Enron公司的破產源于一次偶然的財務危機，從每個月的郵件數據庫中的數據多少就可以看出，這次危機讓整個公司處于超負荷運轉。為了研究其應對財務危機時，公司組織的層次結構，我們選擇2001年9月到2002年2月這半年的郵件數據作為應對財務危機的基礎數據，也是圖3中虛線顯示的第2段數據。

綜合這段時間節點和關系的固有屬性，可得到如圖8所示的社會網絡擴展圖。同樣根據公式（9）可以計算節點的網絡勢支持（見圖9）。由圖9可知，網絡勢支持最大的節點為3，其次是節點85，而節點5，7，34，52，54，55，61，75，76，80，81，86和100的網絡勢支持幾乎為0。

圖7 應對日常業務的層次結構圖Fig.7 Hierarchical graph of enron＇s daily business

圖8 應對財務危機的社會網絡屬性圖模型Fig.8 The attribute－graph model of social network of enron＇s handing of the financial crisis

可以把網絡勢最大的節點作為根節點，如節點3，網絡勢支持較小的點作為葉節點，采用HierarchicalMining算法就可以得到整個網絡的層次結構如圖10所示。由圖10可見整個挖掘出的骨干層次網絡基本符合現實網絡中職位的高低，即綜合屬性值較小的基本在綜合屬性值較大的下一層，并且呈現星型層次結構，高層之間的通信更加緊密，由圖10中綜合關系強度可以看出，不像在應對日常業務時頻繁通過節點68進行通信，而是直接進行通信。但是在發現層次結構中，個別綜合屬性小的節點卻位于層次結構的較高層，如節點85，現實網絡中他的職位雖然是職員，但他直接位于根節點3的下層，而且他們之間的綜合關系很強，這同他在應對財務危機中扮演著首席運營官的角色的現實是相符合的。另外，在現實網絡中處于邊緣的節點在層次結構中也處于底層，如節點11，18，42等。

圖9 應對財務危機的網絡勢支持分布圖Fig.9 Distribution of network potential support of enron＇s handing of the financial crisis

圖10 應對財務危機的層次結構圖Fig.10 Hierarchical graph of enron＇s handing of the financial crisis

通過對面向日常業務和財務危機兩個不同的任務的層次結構發現，可以發現：

1）節點在不斷更新。全時間段的社會網絡包含了所有的104個成員，然而第1時間段的社會網絡中沒有8，12，45，46，55，57，76，88，89，90，92，93，99和103這14個節點，在第2時間段的社會網絡中沒有5，7，34，52，54，55，61，75，76，80，81，86和100這13個節點，其他節點均有出現和退出現象，這些現象可以在Enron公司發生的解聘和聘用事件中找到根源，比如節點8就是在第1時間段之后被公司解聘了。

2）通過圖7和圖10對比可知面向不同任務時，組織網絡的層次結構是不同的。也驗證了網絡層次結構的形成依賴于具體的使命任務，面對不同使命任務時，相應的層次結構是不同的。如節點68在應對日常業務任務中為第2層中最重要的節點，其下層還連接著許多第3層節點；而在應對財務危機中，除了68外，還有85，49等第2層中比較重要的節點，可見在面向不同任務時，節點扮演的角色也不同，節點所處的層次也不同。

3）通過圖7和10對比可知為了有效應對財務危機，公司的高層之間聯系緊密，完全以節點3為核心，而面向日常業務時層次結構相對較稀疏。同時，在應對日常業務時，兩相鄰節點之間的平均緊密度為0.42，平均長度為0.86，根節點到各個節點的平均長度為2.22，平均緊密度為0.11，最大長度為7.59；在應對財務危機時，兩相鄰節點之間的平均緊密度為0.63，平均長度為0.47，根節點到各個節點的平均長度為1.22，平均緊密度為0.29，最大長度為7.02?？梢娫趹獙ω攧瘴C中頂層到底層的緊密度更高，距離更短。

4）通過層次結構的發現，精簡了網絡，從復雜的原始網絡中挖掘出了網絡的骨干關系，能夠清晰地展現公司在面向不同任務時的組織模式和運作流程。同時，也有利于分析節點所扮演的不同角色，和節點的負載情況。如節點68在面對日常業務中比在面對財務危機中扮演著更重要的角色；另外，在面對財務危機中節點3的下層次節點數比日常業務中大得多，可見其在財務危機中的負載比日常業務中的大得多。

5 結語

社會網絡分析由于其巨大的應用價值而成為近年來研究的熱門課題之一，受到了越來越多研究人員的關注。社會網絡的層次結構發現也是社會網絡研究的一個重要方面。針對傳統的建模手段無法刻畫出真實社會網絡的屬性特征，本文建立了社會網絡的擴展圖模型。雖然此框架并未考慮所有可能的投影情況，但可以為以后對不同的社會網絡進行建模起到一個借鑒的作用。在流層次結構思想基礎上，認為網絡的層次結構是受使命任務驅動形成的，并定義了面向使命任務的層次結構。然后，提出了基于勢支持的層次結構中骨架節點的發現方法，并通過對比信息粒子的游走過程和電流網絡的計算原理，引入電流網絡的計算方法來分析信息粒子在骨架節點之間的流動過程，提出了基于勢流動的層次結構發現方法。最后通過對Enron公司郵件數據的分析，挖掘出Enron應對日常業務和財務危機的層次結構，并闡述了其價值。但是本文雖然對網絡組織面向兩種不同使命時，呈現出的不同層次結構進行了挖掘和對比，但其本質思想仍是靜態分析，在未來的工作中，我們應該更多考慮對結構的動態演化特征進行挖掘和學習，能夠進一步對結構未來的變化進行準確預測。

［1］ Wasserman S，Faust K.Social Network Analysis［M］.Cambridge：Cambridge University Press，1994.

［2］Scot J.Social Network Analysis：A Handbook［M］.2nd.London：Sage Publications Ltd，2000.

［3］ Faloutsos M，Faloutsos P，Faloutsos C.On power－law relationships of the internet topology［J］.Computer Communication Review，1999，29：251－262.

［4］Pastor－Satorras R，Vespignani A.Evolution and Structure of the Internet［M］.Cambridge：Cambridge University Press，2004.

［5］ Barabasi A－L，Oltvai Z N.Network biology：understanding the cell′s functional organization［J］.Nature Reviews Genetics，2004，5（2）：101－113.

［6］ Barabasi A－L，Gulbahce N，Loscalzo J.Network medicine：a network based approach to human disease［J］.Nature Reviews Genetics，2011，12（1）：56－68.

［7］ Lane D.Hierarchy，Complexity，Society［M］.Dodrecht，the Netherlands：Springer，2006：81－120.

［8］ Memon N，Larsen H L，Hicks D L，et al.Detecting hidden hierarchy in terrorist networks：Some case studies［C］／／Proceedings of the IEEE ISI 2008PAISI，PACCF，and SOCO international workshops on Intelligence and Security Informatics.Berlin，Heidelberg：Springer－Verlag，2008：477－489.

［9］Seidman S.Network structure and minimum degree［J］.Social Networks，1983，5：269－287.

［10］Daniel W M.The hierarchical structure of organisms：a scale and documentation of a trend in the maximum ［J］.Paleobiology，2001，27（2）：405－423.

［11］Wimberley E T.Nested ecology.The Place of Humans in the ecological Hierarchy［M］.Baltimore，MD：John Hopkins University Press，2009.

［12］Newman M E J.Detecting community structure in networks［J］.European Physical Journal B，2004，38（2）：321.

［13］Fortunato S.Community detection in graphs［J］.Physics Reports，2010，486：75－174.

［14］Newman M E J.Communities，modules and large－scale structure in networks［J］.Nature Physics，2012，8：25－31.

［15］Arun S M，Tanya Y B.Inferring the maximum likelihood hierarchy in social networks［C］／／Proceedings of the 2009International Conference on Computational Science and Engineering.Washington DC：IEEE Computer Society，2009：273－283.

［16］Mones E，Vicsek L，Vicek T.Hierarchy measure for complex networks［J］.PLoS ONE，2012，7（3）：e33799.

［17］成清.社會網絡的節點重要度和重疊社區發現研究［D］.長沙：國防科技大學.2012.Cheng Qing.Research on node importance evaluation and community discovery in social networks［D］.Changsha：National University of Defense Technology，2012.

［18］付強，趙小勇.投影尋蹤模型原理及其應用［M］.北京：科學出版社.2006：47－50.

［19］Premchand S N，Suseela T S.Data mining through fuzzy social network analysis［C］／／Proceedings of the 26th Annual Meeting of the North A－merican Fuzzy Information Processing Society.San Diego：Institute of Electrical and Electronics Engineers Inc，2007：251－255.

［20］劉振亞.面向C2組織效能測度的探索性分析方法研究［D］.長沙：國防科技大學.2009.Liu Zhenya.A research of exploratory analysis for measure of C2organizational effectiveness［D］.Changsha：National University of Defense Technology，2009.

［21］李德毅，杜鹢.不確定性人工智能［M］.北京：國防工業出版社.2005：197－212.

［22］Faloutsos C，McCurley K S，Tomkins A.Fast discovery of connection subgraphs［C］.／／Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining.New York：Association for Computing Machinery，2004：119－127.

［23］Shetty J，Adibi J.The enron email dataset：database schema and brief statistical report［DB／OL］.［2013－07－20］.http：／／www.isi.edu／？adibi／Enron／Enron Dataset Report.pdf

［24］Gilbert E.Phrases that signal workplace hierarchy［C］／／Proceedings of the ACM 2012Conference on Computer Supported Cooperative Work.New York：Association for Computing Machinery，2012：1037－1046.