【正文】 parentNode = (k) 。 childNode = (k) 。 k++ 。 ().remove(childNode) 。 if ( (fold_level)) (fold_level).add(childNode) 。 else { 容器 葉子節(jié)點集合1 = new 容器( ) 。 (childNode) 。 (fold_level ,葉子節(jié)點集1 ) 。 } } } fold_level = fold_level+1 。 End program 4. 算法驗證經(jīng)過層次折疊收縮算法的處理，網(wǎng)絡(luò)中所有核數(shù)為0的邊緣樹狀節(jié)點全部收縮到它們的根節(jié)點上。，核數(shù)為0的節(jié)點以及全部被去掉，圖中所有節(jié)點的度值都大于等于2，這就說明本算法執(zhí)行成功。但是本算法的最終目的是發(fā)現(xiàn)局域網(wǎng)絡(luò)樹狀結(jié)構(gòu)組織，那么該如何還原這樹狀結(jié)構(gòu)組織呢？在反復(fù)刪除度值為1的葉子節(jié)點的過程中，本算法都在孜孜不倦的把這些刪除的節(jié)點信息一一保存到與之相鄰的父節(jié)點的數(shù)據(jù)結(jié)構(gòu)中，即所有被刪除的節(jié)點信息最終都保存在尚未被刪除的核數(shù)大于零的那些根節(jié)點中，只要找到根節(jié)點，就可以還原此根節(jié)點下面的所有的子孫節(jié)點以及這些子孫節(jié)點的連接情況，？在本算法中，每個節(jié)點都有一個childrenSum屬性，只有屬性childrenSum的值大于0的那些節(jié)點才是根節(jié)點。，找到這樣的根節(jié)點，再根據(jù)根節(jié)點中的數(shù)據(jù)結(jié)構(gòu)保存的子孫節(jié)點信息根據(jù)一定的遞歸算法即可復(fù)原整個網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，具體的遞歸算法不再累述，本文直接給出局部的樹狀結(jié)構(gòu)圖，可以明顯的看到，同屬于一個根節(jié)點下的所有的核數(shù)為0的節(jié)點的顏色是一樣的，這說明本文的復(fù)原算法也是有效的。 圖 層次折疊之后的全局圖 Fig. The globle graph after level folding 圖 層次折疊算法局部效果圖 The local result graph of level folding algorithm 為簡化網(wǎng)絡(luò)，便于觀察，反復(fù)折疊收縮葉子節(jié)點到它的父節(jié)點中，最終得到一個1核網(wǎng)絡(luò)拓?fù)?，此拓?fù)渲?，?jié)點度值大于等于2。下面所有的研究將在這個簡化的1核網(wǎng)絡(luò)（）上進(jìn)行。1. 算法提出，黑色節(jié)點表示尚未被層次折疊算法探測到的節(jié)點，即不屬于局部區(qū)域樹狀結(jié)構(gòu)，其它顏色節(jié)點表示局部區(qū)域樹狀結(jié)構(gòu)特征的根節(jié)點。，在剝?nèi)フ麄€網(wǎng)絡(luò)拓?fù)渥钔鈱雍藬?shù)為0的節(jié)點后，即剝?nèi)フ麄€局域網(wǎng)結(jié)構(gòu)后，整個網(wǎng)絡(luò)拓?fù)渥兊南鄬唵?，并且一個很明顯的結(jié)構(gòu)便是鏈狀結(jié)構(gòu)，圖中有很多由尚未被探測算法探測到的黑色節(jié)點組成的鏈狀結(jié)構(gòu)。如果能把這些鏈狀結(jié)構(gòu)探測出來作為一個基本的網(wǎng)絡(luò)組織結(jié)構(gòu)，效果將會不錯。如何探測這種結(jié)構(gòu)呢？探測到的鏈狀結(jié)構(gòu)必須是一個只包含黑色節(jié)點的鏈狀結(jié)構(gòu)，如果包含了其它顏色節(jié)點，即使在此圖中看起來是一個鏈狀結(jié)構(gòu)，可是在把最外層核數(shù)為0 的節(jié)點還原到整個網(wǎng)絡(luò)拓?fù)浜螅@些包含著其它顏色的鏈狀結(jié)構(gòu)將不再是一個真實的鏈狀結(jié)構(gòu)。下面將探討一下探測此種結(jié)構(gòu)的具體的算法設(shè)計。 2. 算法設(shè)計1）初始化 munity = 0 。 2）依次遍歷當(dāng)前1核網(wǎng)絡(luò)中的每一個節(jié)點N 。如果遍歷完畢則直接跳轉(zhuǎn)到第7步。3） 如果節(jié)點N是黑色節(jié)點，度值不大于2，返回第2步 ，否則執(zhí)行下一步。4）依次遍歷N的鄰居節(jié)點集合N[i]，munity++。遍歷完畢時返回第2步。5）當(dāng)N的鄰居節(jié)點N[i]的度值不等于2或者此鄰居節(jié)點是非黑色節(jié)點時，返回第4步 ； 否則N[i].munityNum = munity 。執(zhí)行下一步。 6），返回第5步。7）算法結(jié)束。3. 算法流程圖 圖 鏈狀探測算法流程圖 Fig. The flow chart of Chain detecting4. 算法驗證，很明顯的可以看到，那些度值為2的節(jié)點中是顏色一致的，說明本文的鏈狀探測算法成功的探測到了網(wǎng)絡(luò)中的鏈狀結(jié)構(gòu)組織。 圖 鏈狀探測算法效果圖 Fig. The result graph of Chain detecting1. 算法提出通過之前兩個算法，可以探測到兩種基本的互聯(lián)網(wǎng)拓?fù)涮卣鹘Y(jié)構(gòu)。下面介紹第三種拓?fù)浣Y(jié)構(gòu)的探測方法。在觀察本文所用的可視化的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)時，為了能更清晰的看到網(wǎng)絡(luò)中的每個節(jié)點大致在網(wǎng)絡(luò)中所處的位置，本文設(shè)計一個網(wǎng)絡(luò)拓?fù)涞腒核解析算法，通過此算法，可以得到每個節(jié)點的核數(shù)，即在網(wǎng)絡(luò)中的層次。圖 。 圖 K核解析 KCore analysis a) 網(wǎng)絡(luò)拓?fù)渲械墓?jié)點層次分布從上圖（刪除了0核節(jié)點）可以清晰的看到：簡化的1核的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的最高核數(shù)是4；大部分節(jié)點分布在一個較低的核數(shù)為1的層次上；在一些局部區(qū)域，出現(xiàn)了高核節(jié)點的聚類現(xiàn)象，他們之間連接較為緊密，而它們與周圍的低核節(jié)點連接先對稀疏，這是典型的高內(nèi)聚低耦合現(xiàn)象，并且這些高核節(jié)點的核數(shù)要比周圍的節(jié)點的核數(shù)大，以這些局部區(qū)域的最高核節(jié)點為中心向四周擴(kuò)散時節(jié)點的核數(shù)越來越低。當(dāng)一片局部區(qū)域越大時，一般來說，中心區(qū)域的節(jié)點核數(shù)越大，這種情況使在這片區(qū)域中更容易出現(xiàn)較小的類似于整體特征結(jié)構(gòu)的分形特征結(jié)構(gòu)。但也有一些區(qū)域的高核節(jié)點并沒有出現(xiàn)低耦合現(xiàn)象。是什么導(dǎo)致了互聯(lián)網(wǎng)的這種特征呢？b) 原因分析本文的理解：由于互聯(lián)網(wǎng)的節(jié)點分布非均質(zhì)特征、聚類特征、以及在不同規(guī)模尺度上的分型特征，導(dǎo)致互聯(lián)網(wǎng)出現(xiàn)了某些特定核數(shù)的節(jié)點的聚集現(xiàn)象，這些節(jié)點的核數(shù)一般要比它們周圍的節(jié)點的核數(shù)要高，即這些節(jié)點是這片區(qū)域中核數(shù)最高的節(jié)點，反應(yīng)到物理層面上，可理解為，這些節(jié)點是這片區(qū)域的中心節(jié)點，所以可以把具有這類特征的節(jié)點，理解為一個特定的網(wǎng)絡(luò)組織。其實在現(xiàn)實的社會網(wǎng)絡(luò)中，也很容易去舉出具有這種特征的例子。例子：在社會網(wǎng)絡(luò)中，有4個公司，華為（10萬員工）、58同城（5千員工）、東大新業(yè)（300員工）、東科電力下屬的研發(fā)中心（30員工）。本文故意拿出這四個具有不同規(guī)模尺度上的公司，以便說明問題。也許這4個公司在業(yè)務(wù)上沒有往來，即沒有直接連接的邊，但放眼整個社會網(wǎng)絡(luò)，他們肯定可以通過社會的一些其他團(tuán)體或公司間接到達(dá) ；這4個公司均具有內(nèi)部人員關(guān)系高度聚類，內(nèi)部與外部關(guān)系相對生疏的現(xiàn)象；這4個公司在不同規(guī)模尺度上出現(xiàn)了類似的分形特征，在結(jié)構(gòu)上，大致具備“領(lǐng)導(dǎo)核心、中層領(lǐng)導(dǎo)、低級領(lǐng)隊、普通成員”這種類型的層次特征，只是在較小的團(tuán)體內(nèi)部，它的這種組織結(jié)構(gòu)相對簡單，不全具備復(fù)雜團(tuán)體的那種明顯的層次特征結(jié)構(gòu)的復(fù)雜的層次性。比如華為員工的級別可以劃分到118級，而規(guī)模尺度較小的東科電力的員工只有4個級別：普通員工、工程師，副高、教高。在自然界中也會出現(xiàn)這種現(xiàn)象：作為高級靈長類的人，它的生命系統(tǒng)具有非常的組織結(jié)構(gòu)，大致有血管系統(tǒng)、皮膚系統(tǒng)、神經(jīng)系統(tǒng)、聽覺系統(tǒng)、視覺系統(tǒng)、消化系統(tǒng)、呼吸系統(tǒng)、泌尿系統(tǒng)等；而進(jìn)化相對低級的蚯蚓就不具備聽覺系統(tǒng)、視覺系統(tǒng)、泌尿系統(tǒng)等。人與蚯蚓的這種生命系統(tǒng)都是整個大自然生物的生命之“道”的不同但又相似的分形系統(tǒng)。即使是在一個公司內(nèi)部，也會出現(xiàn)高核節(jié)點聚類的現(xiàn)象，比如在華為內(nèi)部，作為華為最高行政的董事管理層可能每個人都相互熟悉，可是對于處在華為最外層的任意的兩個普通員工，他們之間相識的概率估計會很?。?0萬人呢），這就是典型的內(nèi)層耦合性強(qiáng)外層相對分散的結(jié)構(gòu)特征，在華為的介于最內(nèi)層和最外層之間也會分布許許多多的類似于整體結(jié)構(gòu)特征的分形小群落。c) 大道無形，生育天地中國有句俗語叫“麻雀雖小，五臟俱全”，人有五臟，麻雀亦有五臟，只是形體不同而已，功能卻何其相似！于子云：“混沌自有相似處，分形藏身于森木；待到回歸奇點時，萬事萬物終化無”。天地統(tǒng)一于“道”，生物和非生物都在某種神秘力量的驅(qū)使下延續(xù)著不同但又相似的演化，外部的分形特征，如草、農(nóng)作物、樹木，內(nèi)部的分形特征，如白樺樹、洋槐樹、橡樹，再內(nèi)部的分形特征，如葉子、小枝條、較大的枝條、大枝條、整棵樹，再比如，江流、河流、小溪，再比如，大海、湖泊、池塘、小水坑等等，看似無序繁雜往復(fù)的大自然又是多么有序多么相似啊，探索發(fā)現(xiàn)有這樣一句話：Nature is a miraculous place where order exists within disorder。d) 此類特征的網(wǎng)絡(luò)組織結(jié)構(gòu)的探測那么如何尋找這些具有此類特征的網(wǎng)絡(luò)組織結(jié)構(gòu)呢？首先需要一個K核解析算法，計算網(wǎng)絡(luò)中每個節(jié)點的核數(shù)；其次需要一個探測具有聚類特征的高核組織結(jié)構(gòu)的算法。2. 算法設(shè)計216。 K核解析算法算法思想 1）對于一個網(wǎng)絡(luò)拓?fù)?，初始化全局變量core= 0 。2）依次遍歷網(wǎng)絡(luò)中每一個節(jié)點N 3）如果N度值小于或等于(core+1)（N是葉子節(jié)點）,= core，并且從此拓?fù)浣Y(jié)構(gòu)中刪除節(jié)點N，N的核數(shù)信息必須在其他數(shù)據(jù)結(jié)構(gòu)下保留；4）如果網(wǎng)絡(luò)中不存在節(jié)點度值小于等于（core+1）的情況，則core++ 。5）如果網(wǎng)絡(luò)中所有節(jié)點都被刪去，則算法結(jié)束；否則返回第2步。以上只是本算法的簡單思想介紹，限于篇幅，具體算法流程圖和實現(xiàn)將不再給出，直接給出本算法的驗證。算法驗證 圖 K核解析驗證圖 verification graph of KCore analysis 從K核解析算法驗證圖來看，本算法是正確的，能準(zhǔn)確解析網(wǎng)絡(luò)中每個節(jié)點的核數(shù)。216。 聚類特征的高核組織結(jié)構(gòu)探測算法算法思想以K核解析算法為基礎(chǔ)，解析出每個節(jié)點的核數(shù)。高核聚類特征應(yīng)該至少從核數(shù)為2的節(jié)點開始的，因為0核是網(wǎng)絡(luò)的最外層，現(xiàn)在需要探測的是局部網(wǎng)絡(luò)最內(nèi)層的聚類特征。在探測此類結(jié)構(gòu)時，需要遍歷1核網(wǎng)絡(luò)中的每一個節(jié)點N，記錄此節(jié)點N的核數(shù)core，然后在順著節(jié)點N尋找所有核數(shù)為core且能通過核數(shù)為core的節(jié)點與N聯(lián)通的節(jié)點，計算這些節(jié)點集合的總度值TD，然后在計算這些節(jié)點與其它核節(jié)點的連接的總邊數(shù)TE，當(dāng)TE/TD的比值小于一定值V時，可認(rèn)為這些節(jié)點集合具有高核聚類特征，值V可根據(jù)具體情況設(shè)定。算法設(shè)計1） = false ,全局變量munity = 0 。2） 遍歷1核集合網(wǎng)絡(luò)拓?fù)渲忻恳粋€節(jié)點N，遍歷完畢時，跳轉(zhuǎn)第7步。==ture =1則重復(fù)執(zhí)行這一步，否則執(zhí)行下一步。3） =true，munity++ ，=munity。4） 利用廣度優(yōu)先遍歷策略，依次遍歷N的鄰居節(jié)點N[i]，如果N[i].core==，則N[i].munity=munity，(N[i])。5） 依次遍歷ajacentNodeVector中的每一個元素E[i]，對于每一個元素E[i]，設(shè)置E[i].visited=true，依次遍歷E[i]的每一個鄰居節(jié)點J[i]，如果J[i].core==，則J[i].munity=munity，(J[i])。6） ()==0，返回第二步；否則，返回第5步。3. 下面給算法流程圖。圖 高核聚類探測算法流程圖 The flow chart of highCore cluster算法驗證從下圖可看出，那些非黑色的節(jié)點處在一個個的團(tuán)落中，相互之間連接緊密，直觀上，本算法在探測具有高核聚類特征的網(wǎng)絡(luò)結(jié)構(gòu)組織時是合理的；在于此前的1核網(wǎng)絡(luò)K核解析圖相比較，那些高核聚類特征的網(wǎng)絡(luò)結(jié)構(gòu)組織大致的位置分布及其相似；根據(jù)這兩點，可以認(rèn)為，對于探測高核節(jié)點聚類特征，本算法是有效的。圖 高核聚類探測效果圖 The result graph of highCore cluster detecting 1） 算法思想經(jīng)過前幾種探測算法的探測，網(wǎng)絡(luò)中的局域樹狀拓?fù)浣Y(jié)構(gòu)組織、鏈狀拓?fù)浣Y(jié)構(gòu)組織、高核聚類拓?fù)浣Y(jié)構(gòu)組織都已經(jīng)被探測出來，接下來需要做的是，在剩下的尚未被探測的網(wǎng)絡(luò)中，探測中心節(jié)點拓?fù)浣Y(jié)構(gòu)組織，這里的中心節(jié)點用度值衡量，度值越大，節(jié)點的中心性越強(qiáng)。 根據(jù)二八定律，本文選取剩下的尚未被探測的度值最大的20%的節(jié)點作為中心節(jié)點，而中心節(jié)點拓?fù)浣Y(jié)構(gòu)即使中心節(jié)點與它的鄰居節(jié)點及相連邊的集合。但是也有可能出現(xiàn)這種情況，即某個中心節(jié)點N的鄰居節(jié)點M是另一個中心節(jié)點，如果把這樣的既是中心節(jié)點又是鄰居節(jié)點的M與N歸并到同一網(wǎng)絡(luò)組織C，可能會出現(xiàn)這個網(wǎng)絡(luò)組織內(nèi)部耦合性不高，因為當(dāng)以M為中心的拓?fù)浣Y(jié)構(gòu)組織與以N為中心的拓?fù)浣Y(jié)構(gòu)組織只有一條邊即E（M,N）時，C的內(nèi)部會出現(xiàn)強(qiáng)烈的分裂現(xiàn)象。，1號節(jié)點和11號節(jié)點是中心節(jié)點，如果把以1號中心節(jié)點為中心構(gòu)成的結(jié)構(gòu)組織與以11號中心節(jié)點為中心構(gòu)成的結(jié)構(gòu)組織合為一個中心節(jié)點拓?fù)浣Y(jié)構(gòu)組織，那么這個拓?fù)浣Y(jié)構(gòu)組織的內(nèi)部將初一一種分裂狀態(tài)，不符合結(jié)構(gòu)組織定義。 圖 中心節(jié)點例子