社會網(wǎng)絡(luò)的層次結(jié)構(gòu)發(fā)現(xiàn)

成 清，黃 森，黃金才

（1.國防科學(xué)技術(shù)大學(xué)信息系統(tǒng)工程重點實驗室，長沙410073；2.78020部隊 昆明650221）

0 引言

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

層次結(jié)構(gòu)就是網(wǎng)絡(luò)中節(jié)點按照某些值的排序［7］，認(rèn)為整個網(wǎng)絡(luò)具有k層，綜合節(jié)點自身屬性或拓?fù)涮卣?，建立所有?jié)點層次測度指標(biāo)，計算它們的指標(biāo)值，將其映射到k層中的某一層，主要有中心性計算方法［8］，k－core測度計算方法［9］和層次指標(biāo)度量方法［10］等和影響力對比方法。

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

以樹結(jié)構(gòu)作為層次結(jié)構(gòu)［15］，如結(jié)構(gòu)匹配方法，此類方法用樹結(jié)構(gòu)來代替層次結(jié)構(gòu)，然后再利用已知信息，生成符合該特征的備選樹，最后再選擇最優(yōu)匹配結(jié)構(gòu)為該網(wǎng)絡(luò)的層次結(jié)構(gòu)。

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

1 社會網(wǎng)絡(luò)的擴(kuò)展圖模型

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

1.1 節(jié)點的抽象

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

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

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

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

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

1.2 關(guān)系的抽象

社會網(wǎng)絡(luò)的擴(kuò)展圖模型中定義節(jié)點間的關(guān)系如下：在一個有限的節(jié)點集合V中，關(guān)系可以定義為μ：V×V→［0，1］，表示為

其中，記rij：＝μ（vi，vj），矩陣R＝（rij）n×n為關(guān)系的鄰接矩陣，采用關(guān)系的重要性代替關(guān)系的存在性，針對特定的社會事件恰當(dāng)?shù)爻橄蟪鏊闹匾?，并賦予［0，1］之間的相應(yīng)的權(quán)值，來度量社會關(guān)系在社會網(wǎng)絡(luò)中的表征。

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

可見拓展圖實際上是在傳統(tǒng)圖的基礎(chǔ)上增加了節(jié)點和邊的權(quán)重，但是節(jié)點和邊的權(quán)重并不像傳統(tǒng)圖一樣是單一屬性的度量，而是采用節(jié)點屬性投影和多個關(guān)系的聚合操作實現(xiàn)多屬性的綜合映射，模型能夠更好地考慮節(jié)點和關(guān)系的多屬性特征。雖然由于進(jìn)行了投影操作，增加了計算復(fù)雜度，但投影計算只用在網(wǎng)絡(luò)構(gòu)建中，當(dāng)網(wǎng)絡(luò)構(gòu)建后不會影響到網(wǎng)絡(luò)的分析。

2 網(wǎng)絡(luò)的層次結(jié)構(gòu)定義

一個復(fù)雜的組織應(yīng)對具體任務(wù)時，它自適應(yīng)地表現(xiàn)出來的一種層次結(jié)構(gòu)，任務(wù)指派是通過節(jié)點間的信息流動實現(xiàn)的。面對不同的任務(wù)使命時，任務(wù)的指派是不同的，所以信息流也是不同的，相應(yīng)的層次結(jié)構(gòu)也是不同的，這同文獻(xiàn)［16］中認(rèn)為層次結(jié)構(gòu)是一種流層次結(jié)構(gòu)的思想相似。

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

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

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

圖2 簡單的層次結(jié)構(gòu)示意Fig.2 The schematic diagram of the hierarchical structure

3 網(wǎng)絡(luò)的層次結(jié)構(gòu)發(fā)現(xiàn)方法

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

3.1 骨架點的挖掘

根據(jù)數(shù)據(jù)場理論，針對給定網(wǎng)絡(luò)G＝（V，E，δ，μ），網(wǎng)絡(luò)中節(jié)點表示數(shù)據(jù)場中的數(shù)據(jù)對象，每個節(jié)點周圍存在一個作用場，位于場中的任何節(jié)點都將受到其它節(jié)點的聯(lián)合作用，根據(jù)真實網(wǎng)絡(luò)的特性，我們認(rèn)為，節(jié)點間的相互作用具有局域特性，每個節(jié)點的影響能力會隨著網(wǎng)絡(luò)距離的增長而快速衰退，采用短程場且具有良好數(shù)學(xué)性質(zhì)的高斯勢函數(shù)描述節(jié)點間的相互作用［21］，綜合考慮網(wǎng)絡(luò)拓?fù)湫再|(zhì)和節(jié)點固有屬性，可以得到任意節(jié)點vi∈V的拓?fù)鋭菘杀硎緸?/p>

其中，dij為節(jié)點vi與vj間的拓?fù)渚嚯x；影響因子σ表示節(jié)點的作用范圍；mi≥0表示節(jié)點vi（i＝1，2，…，n）的質(zhì)量。

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

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

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

2）d（μ（e））＝0，當(dāng)且僅當(dāng)μ（e）＝1；

3）當(dāng)μ（e）→0時，d（μ（e））→＋∞；

4）d（μ（e））在定義域上是單調(diào)遞減、連續(xù)光滑的函數(shù)。

本文使用函數(shù)d（x）來實現(xiàn)這個映射，即

可得

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

另外存在一個參數(shù)，影響因子σ，根據(jù)數(shù)據(jù)場中關(guān)于影響因子的討論［21］，可以引入拓?fù)鋭輬龅膭蒽貋砗饬喀抑档暮侠硇?，令?jié)點v1，v2，…，vn的勢值為TP（1），TP（2），…，TP（n），則勢熵可定義為

在一個社會網(wǎng)絡(luò)中，如果將節(jié)點u斷開，與之相關(guān)的聯(lián)系也認(rèn)為失效，就會導(dǎo)致網(wǎng)絡(luò)結(jié)構(gòu)的變化，這種變化就會讓另一個節(jié)點v的重要性發(fā)生變化，這種現(xiàn)象叫做v在某種程度上依賴于u，反過來看，便是u在某種程度上支持v。這種現(xiàn)象反映了節(jié)點在網(wǎng)絡(luò)中的一種社會性，表現(xiàn)一個節(jié)點對另一個節(jié)點重要性的支持。在對節(jié)點拓?fù)鋭莸挠嬎阒校呀?jīng)包含了這種思想，因為拓?fù)鋭莸男纬桑褪怯善渌?jié)點的能量輻射造成的，這種能量的輻射也是給力的一種表現(xiàn)形式，所以本文將某一節(jié)點對另一節(jié)點拓?fù)鋭莸闹С殖潭?，叫做勢支持，則有φG（vi）為節(jié)點vi在網(wǎng)絡(luò)G中的拓?fù)鋭?，又vi，vj∈V，那么vi對vj的勢支持Supp（vj→vi）為

其中，G－vj表示在圖G中去掉節(jié)點vj之后的子圖，φG－vj（vi）表示在圖G－vj中節(jié)點vi的拓?fù)鋭荨葜С值乃枷肟梢詮拿枋鰞牲c之間的關(guān)系，推廣到整個網(wǎng)絡(luò)上，定義某個節(jié)點對整個網(wǎng)絡(luò)的勢支持。先定義網(wǎng)絡(luò)的拓?fù)鋭轂?/p>

由此，定義節(jié)點vj對整個網(wǎng)絡(luò)的勢支持為

節(jié)點勢支持的應(yīng)用意義在于，它主要描述的是某一節(jié)點所擁有的能量在多大程度上依賴于另一節(jié)點的存在。網(wǎng)絡(luò)勢支持主要描述的是整個網(wǎng)絡(luò)的能量在多大程度上依賴于某一節(jié)點的存在。

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

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

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

3.2 層次結(jié)構(gòu)的發(fā)現(xiàn)

根據(jù)節(jié)點對網(wǎng)絡(luò)的勢支持確定根節(jié)點和葉節(jié)點之后，需要挖掘根節(jié)點和葉節(jié)點之間的流通信道。根據(jù)層次結(jié)構(gòu)的定義，流通信道是一個從根節(jié)點到葉節(jié)點的連接子圖，旨在從根節(jié)點攜帶最多的信息粒子到達(dá)各個葉節(jié)點。因此，流通信道的挖掘問題歸結(jié)為根節(jié)點分別與不同葉節(jié)點之間的最優(yōu)子圖挖掘。

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

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

其中，C（u，v）為節(jié)點u和v之間的電導(dǎo)系數(shù)，在本文中C（u，v）＝μ（u，v），μ（u，v）表示節(jié)點u和v的綜合關(guān)系屬性值。

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

所以，根據(jù)歐姆定律和基爾霍夫電流定律，可以得到計算這個網(wǎng)絡(luò)中所有節(jié)點處的電勢就可以轉(zhuǎn)化為求解如下一個線性系統(tǒng)：

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

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

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

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

如果s，t∈G＊且G＊假設(shè)為從節(jié)點s到節(jié)點t的最優(yōu)子圖，則對于任何一個子圖G′，都有

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

根據(jù)定義的圖質(zhì)量函數(shù)，可以采用文獻(xiàn)［22］中的最優(yōu)連接圖發(fā)現(xiàn)算法發(fā)現(xiàn)最優(yōu)子圖。

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

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

4 實驗分析

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

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

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

圖3 每個月份郵件的發(fā)送量統(tǒng)計圖Fig.3 Distribution of sent eamils over time（month）

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

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

4.1 應(yīng)對日常業(yè)務(wù)

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

圖5 應(yīng)對日常業(yè)務(wù)的社會網(wǎng)絡(luò)屬性圖模型Fig.5 The attribute－graph model of social network of enron＇s daily business

圖6 應(yīng)對日常業(yè)務(wù)的網(wǎng)絡(luò)勢支持分布圖Fig.6 Distribution of network potential support for enron dealing with the daily business

由圖6可知，網(wǎng)絡(luò)勢支持最大的節(jié)點為3，其次是節(jié)點68，而節(jié)點8，12，45，46，55，57，76，88，89，90，92，93，99和103的網(wǎng)絡(luò)勢支持較小，幾乎為0。可以把網(wǎng)絡(luò)勢最大的節(jié)點作為根節(jié)點，如節(jié)點3，網(wǎng)絡(luò)勢支持較小的點作為葉節(jié)點，采用HierarchicalMining算法可以得到整個網(wǎng)絡(luò)的層次結(jié)構(gòu)，如圖7所示。

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

4.2 應(yīng)對財務(wù)危機(jī)

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

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

圖7 應(yīng)對日常業(yè)務(wù)的層次結(jié)構(gòu)圖Fig.7 Hierarchical graph of enron＇s daily business

圖8 應(yīng)對財務(wù)危機(jī)的社會網(wǎng)絡(luò)屬性圖模型Fig.8 The attribute－graph model of social network of enron＇s handing of the financial crisis

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

圖9 應(yīng)對財務(wù)危機(jī)的網(wǎng)絡(luò)勢支持分布圖Fig.9 Distribution of network potential support of enron＇s handing of the financial crisis

圖10 應(yīng)對財務(wù)危機(jī)的層次結(jié)構(gòu)圖Fig.10 Hierarchical graph of enron＇s handing of the financial crisis

通過對面向日常業(yè)務(wù)和財務(wù)危機(jī)兩個不同的任務(wù)的層次結(jié)構(gòu)發(fā)現(xiàn)，可以發(fā)現(xiàn)：

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

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

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

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

5 結(jié)語

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

［1］ Wasserman S，F(xiàn)aust 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，F(xiàn)aloutsos P，F(xiàn)aloutsos 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］成清.社會網(wǎng)絡(luò)的節(jié)點重要度和重疊社區(qū)發(fā)現(xiàn)研究［D］.長沙：國防科技大學(xué).2012.Cheng Qing.Research on node importance evaluation and community discovery in social networks［D］.Changsha：National University of Defense Technology，2012.

［18］付強(qiáng)，趙小勇.投影尋蹤模型原理及其應(yīng)用［M］.北京：科學(xué)出版社.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］.長沙：國防科技大學(xué).2009.Liu Zhenya.A research of exploratory analysis for measure of C2organizational effectiveness［D］.Changsha：National University of Defense Technology，2009.

［21］李德毅，杜鹢.不確定性人工智能［M］.北京：國防工業(yè)出版社.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.