基于熵的有序性網(wǎng)絡(luò)演化研究

基于熵的有序性網(wǎng)絡(luò)演化研究

1通信網(wǎng)絡(luò)演化的研究內(nèi)容和方法一個人或兩個群體根據(jù)某種關(guān)系而成稱社會網(wǎng)絡(luò)。隨著新的結(jié)點不斷加入,或結(jié)點之間建立新的聯(lián)系,社會網(wǎng)絡(luò)不斷地進(jìn)行演化.在社會網(wǎng)絡(luò)中,除去外部的影響,個體之間的連帶由于個體相互之間的個人、政治或文化信息而產(chǎn)生.隨著網(wǎng)絡(luò)中個體大規(guī)模地局部交互,社會網(wǎng)絡(luò)涌現(xiàn)出一些整體現(xiàn)象,例如小世界特性、無標(biāo)度特性和自相似特性.這些全局屬性能夠幫助對一些網(wǎng)絡(luò)行為給出建議,例如網(wǎng)絡(luò)上的傳播、網(wǎng)絡(luò)上的相繼故障或網(wǎng)絡(luò)中的搜索.社會網(wǎng)絡(luò)的結(jié)構(gòu)是網(wǎng)絡(luò)動態(tài)的形成和演化的結(jié)果,并且它能夠被一些統(tǒng)計測度來進(jìn)行觀察,比如度分布、結(jié)點度相關(guān)、群集系數(shù)等.盡管這些測度在某些情況下是非常有用的,但是它們還不足夠去描述社會網(wǎng)絡(luò)的動態(tài)特征.而人們研究郵件網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和動態(tài)演化,其主要原因是郵件作為通訊的媒介反映了我們的社會行為.同時,郵件日志存檔了發(fā)送郵件的通信信息,所以被認(rèn)為是在社會網(wǎng)絡(luò)分析領(lǐng)域中十分有用的資源.另外,病毒在郵件網(wǎng)絡(luò)中的傳播以及過濾垃圾郵件也是郵件網(wǎng)絡(luò)的研究內(nèi)容.郵件的通信關(guān)系可被表達(dá)為一個郵件加權(quán)網(wǎng)絡(luò),郵件地址作為網(wǎng)絡(luò)中的結(jié)點,而地址間的通訊次數(shù)作為邊的權(quán).郵件網(wǎng)絡(luò)具有自相似結(jié)構(gòu)和無標(biāo)度特性,但是關(guān)于郵件網(wǎng)絡(luò)的動態(tài)演化還沒有被涉及.郵件網(wǎng)絡(luò)對于時間的變化進(jìn)行研究是為了預(yù)測依靠社會關(guān)系聯(lián)系的網(wǎng)絡(luò)怎樣通過時間改變、預(yù)測連帶變強或變?nèi)鯇π畔⒘鞯挠绊憽⒈嬲J(rèn)有特性的人、知道連帶怎樣去影響節(jié)點的行為.通常的網(wǎng)絡(luò)演化理論有,物以類聚、互惠、平衡理論及優(yōu)先連接.但是,網(wǎng)絡(luò)隨著時間的發(fā)展在不同的尺度上卻表現(xiàn)出不一致性,這是現(xiàn)有理論沒有涉及的.另外,描述節(jié)點信息的度分布、聚集系數(shù)、特征向量中心性及點介數(shù)等靜態(tài)統(tǒng)計不僅對噪音敏感、相互強關(guān)聯(lián),而且是不“充分”的統(tǒng)計.他們往往不足夠地關(guān)注所有信息.特別地,本文使用圖熵(GraphEntropy)的概念來具體描述在網(wǎng)絡(luò)演化過程中的有序性.人們可以通過熵參與度(EntropyParticipationRatio,EPR)來探測某一結(jié)點在網(wǎng)絡(luò)中的重要程度.最關(guān)鍵的是,本文通過定義兩種截然不同的概率分布來分別描述全局屬性(GlobalProperty)和局部屬性(LocalProperty)的變化趨勢.本文將使用網(wǎng)絡(luò)中心性的相關(guān)概念.關(guān)于網(wǎng)絡(luò)的中心性方面的研究從二十世紀(jì)五六十年代就已由一批社會學(xué)家開始.Nieminen和Freeman等人具有代表性.中心性可量化個體在網(wǎng)絡(luò)中的地位,或描述和分析網(wǎng)絡(luò)的信息流動.本文將著重于對社會網(wǎng)絡(luò)的時間演化性質(zhì)進(jìn)行分析.它主要被研究者分為兩個方面:1)對于網(wǎng)絡(luò)的分析大部分工作盡管可以通過計算機生成網(wǎng)絡(luò)進(jìn)行研究,但是統(tǒng)計物理學(xué)中的常用技術(shù),比如系綜理論、平均場近似、生成函數(shù)方法和重整化群,也可解析得到網(wǎng)絡(luò)性質(zhì)的近似表達(dá)式.2)網(wǎng)絡(luò)隨著時間進(jìn)行演化,同時它也會在一定程度上改變網(wǎng)絡(luò).所以,對于網(wǎng)絡(luò)演化性質(zhì)的研究對于復(fù)雜網(wǎng)絡(luò)和其動力學(xué)模型都是非常有意義的.當(dāng)前大多數(shù)對網(wǎng)絡(luò)演化的研究主要是基于實證分析的.其中,研究較多的網(wǎng)絡(luò)是合作者網(wǎng)絡(luò)與WWW網(wǎng)絡(luò),而郵件社會網(wǎng)絡(luò)的研究則只是一些基本性質(zhì)和對信息流動的分析.網(wǎng)絡(luò)演化的研究內(nèi)容大概分為兩部分:時間演化性質(zhì)和演化機制模型的檢驗.對于時間演化性質(zhì)的研究,不僅包括一些靜態(tài)量隨時間的變化,還包括網(wǎng)絡(luò)上特定動力學(xué)過程的演化性質(zhì),比如傳染病傳播、輿論的傳播與信任的建立等.本文利用安然數(shù)據(jù)集(EnronEmailDatabase),采用圖熵的概念來分析和描繪實證的郵件社會網(wǎng)絡(luò)的演化規(guī)律,并依據(jù)它找出突出的個體.特別地,文獻(xiàn)定義不同的事務(wù)關(guān)系的序列,通過圖熵來發(fā)現(xiàn)網(wǎng)絡(luò)的隱藏組織結(jié)構(gòu)、尋找網(wǎng)絡(luò)中關(guān)鍵的人或組織.文獻(xiàn)則通過圖熵和熵參與度的概念分析城市布局中的智能性.本文發(fā)現(xiàn),當(dāng)全局熵隨著網(wǎng)絡(luò)的演化逐漸增加時,由于“部門化”的趨勢,局部熵呈逐漸減小,最后趨于穩(wěn)定.同時,由于在社會網(wǎng)絡(luò)中分別從局部和全局角度描述網(wǎng)絡(luò)中結(jié)點重要程度的兩種熵參與度呈現(xiàn)線性正相關(guān),可以使用熵參與度來度量和比較結(jié)點的重要程度.2社會網(wǎng)絡(luò)模型本文引用熵的參數(shù)來度量網(wǎng)絡(luò)的不確定性,以幫助認(rèn)識社會網(wǎng)絡(luò)的演化過程.如果P是點集N上的一個概率分布,那么對于每個結(jié)點i∈N可表現(xiàn)為pi∈,并且有∑pi=1.在社會網(wǎng)絡(luò)模型中,這個概率分布可定義為各種已提出過的相關(guān)的度量.為了更加確定,我們具體提出兩個分布的例子.2.1改進(jìn)的局部連接性人們依靠結(jié)點的度定義概率分布D來度量局部連接性(LocalConnectivity).局部連接性能夠反映在微觀層面上交通樞紐的能力大小:Di=Ιnt(i)2Μ,Di=Int(i)2M,其中,Int(i)表示結(jié)點i在網(wǎng)絡(luò)中的強度,M表示網(wǎng)絡(luò)中邊的總數(shù).局部連接性實際上就是將結(jié)點的度作歸一化處理.2.2響應(yīng)力的計算另一個概率分布B依據(jù)點介數(shù)來定義全局中心性(GlobalCentrality).全局中心性能夠反映宏觀層次上在全局結(jié)構(gòu)中結(jié)點對于信息流動的影響力:Bi=∑j＜kzjk(i)zjk∑i∑j＜kzjk(i)zjk,Bi=∑j＜kzjk(i)zjk∑i∑j＜kzjk(i)zjk,其中,zjk表示結(jié)點j到結(jié)點k的最短路徑的總數(shù);zjk(i)表示結(jié)點j到結(jié)點k、而且經(jīng)過結(jié)點i的最短路徑的總數(shù),分母為歸一化處理.在這里,最短路徑使用邊的權(quán)重信息.由于社會網(wǎng)絡(luò)的權(quán)是相似權(quán),所以使用權(quán)重的倒數(shù)作為通常意義上的相異權(quán).全局中心性實際上就是Freeman的結(jié)點的介數(shù)指標(biāo)的歸一化處理.2.3網(wǎng)絡(luò)復(fù)雜性的表征對于一個圖上的任何概率分布都可直接計算圖熵:Η(G,Ρ)=Ν∑i=1pilog2(1pi),H(G,P)=∑i=1Npilog2(1pi),其中,0×log(1/0)=0.由此,我們可以根據(jù)前面介紹的兩個概率分布來計算圖熵,他們可以分別稱為連接熵(ConnectivityEntropy)和中心熵(CentralityEntropy).社會網(wǎng)絡(luò)具有自相似的特性,也就是說在不同的尺度上網(wǎng)絡(luò)具有相似的結(jié)構(gòu).但是,在度量網(wǎng)絡(luò)的復(fù)雜性上,復(fù)雜網(wǎng)絡(luò)卻有多尺度上的不一致.具體地說,就是復(fù)雜網(wǎng)絡(luò)可能在宏觀上是有序的,而在微觀上是無序的;或者在宏觀上是無序的,在微觀上是有序的.例如,在經(jīng)濟(jì)領(lǐng)域,隨著不斷的全球化,發(fā)達(dá)國家與發(fā)展中國家差距越來越大,富者越富.而在微觀層次上,卻存在著大量的負(fù)反饋與平衡,例如供求關(guān)系.隨著時間的推移,社會網(wǎng)絡(luò)的結(jié)構(gòu)與屬性總是處在不斷的可逆的運動與不可逆的演化之中.正如Prigogine將熱力學(xué)第二定律納入的新觀點一樣,熵不僅向著無組織性滑去,在某些條件下熵本身會成為有序的根源.熵的概念既考慮到了局部性質(zhì),又考慮到了層次性質(zhì).在這里使用圖熵的測度分析社會網(wǎng)絡(luò)的有序性是非常適合的.2.4概率分布熵與epri由于熵的概念考慮了全局屬性和局部屬性的關(guān)聯(lián),那么結(jié)點對于熵值的貢獻(xiàn)越大,該結(jié)點就越能從局部探知整個網(wǎng)絡(luò)的結(jié)構(gòu),從而對環(huán)境越重要.所以,人們可以定義概率分布熵參與度來尋找重要結(jié)點,即EΡRi=pilog2(1pi)Η(G,Ρ).EPRi=pilog2(1pi)H(G,P).相應(yīng)地,在前面定義的兩個圖熵在這里可以定義兩個EPR,分別稱作連接EPR(ConnectivityEPR)和中心EPR(CentralityEPR).這兩個EPR都可對網(wǎng)絡(luò)中的重要結(jié)點進(jìn)行度量,具體的分析過程見實驗部分.3社會網(wǎng)絡(luò)的發(fā)展中的圖熵3.1文獻(xiàn)版—數(shù)據(jù)描述在具體介紹應(yīng)用圖熵的實驗結(jié)果前,本文先介紹安然數(shù)據(jù)集.安然數(shù)據(jù)集源自于美國聯(lián)邦能源監(jiān)管委員會對于安然公司的調(diào)查,而后由CALOProject收集.最后,經(jīng)過MIT、SRI和CMU人們的工作,原數(shù)據(jù)集被清洗可用.它是一個空前的以研究為目的數(shù)據(jù)集,廣泛被各個領(lǐng)域的研究人員所使用.本文使用它的其中一個由AndrewFiore和JeffHeer建立的Mysql版本來進(jìn)行研究.這個版本共包含1143個人和用905封郵件建起的2106條邊,主要關(guān)注于公司生意和加州能源危機的相關(guān)郵件,排除了一些非常個人化或玩笑之類的郵件.依據(jù)這個版本的數(shù)據(jù)集建立起來的加權(quán)網(wǎng)絡(luò)的平均距離為0.656,在這里距離是相似權(quán)意義下的距離;聚集系數(shù)為0.287.圖1(a)顯示了該網(wǎng)絡(luò)的度分布.由此圖看出網(wǎng)絡(luò)明顯呈冪率分布.圖1(b)顯示了用戶發(fā)送接收郵件數(shù)目按時間的分布,該圖清楚地顯示絕大多數(shù)的郵件在2001年發(fā)送或接收.2001年也正是安然危機大爆發(fā)的時段.3.2網(wǎng)絡(luò)演化中的熵值本文將圖熵應(yīng)用到安然數(shù)據(jù)集中去,用前面所述的連接熵和中心熵來分別描述網(wǎng)絡(luò)全局屬性和局部屬性隨著時間演化的有序性.本文以月為單位用圖熵來進(jìn)行分析.如果對于概率分布P,所有的結(jié)點為等概率,結(jié)點總數(shù)為N,那么其對應(yīng)的熵值為最大值NlogN.由于網(wǎng)絡(luò)規(guī)模是逐漸增大的,所以在對圖熵進(jìn)行比較時,本文將熵值除以最大值以歸一化.結(jié)果如圖2所示,圖中顯示了連接熵和中心熵隨著網(wǎng)絡(luò)的演化分別的變化趨勢.隨著網(wǎng)絡(luò)的演化,全局熵越來越大,局部熵越來越小,最后趨于平穩(wěn).這可以解釋為微觀上網(wǎng)絡(luò)逐漸有序,少數(shù)的結(jié)點就提供了很強的連接;宏觀上逐漸無序,結(jié)點對于信息流動的影響力逐漸平滑,網(wǎng)絡(luò)流動的效率越來越大.本文根據(jù)前面所述的EPR來判斷結(jié)點的重要程度.如圖3(a)所示,連接EPR和中心EPR隨著網(wǎng)絡(luò)的演化由初期的線性負(fù)相關(guān)到正相關(guān).所以,連接EPR和中心EPR都可以用來進(jìn)行判斷.為清楚起見,如圖3(b)所示,結(jié)點的序號根據(jù)中心EPR的大小排序,分別顯示連接EPR和中心EPR.在圖中可以看到連接EPR和中心EPR具有相同的變化趨勢,但中心EPR變化幅度比較大.根據(jù)這一原理,我們可以根據(jù)中心EPR來判斷重要節(jié)點,得出EPR最大的結(jié)點是JeffDasovich.根據(jù)相關(guān)信息,他是政府相關(guān)的執(zhí)行官,在加州能源危機中舉足輕重,操縱了游說共和黨議員來反對聯(lián)邦能源監(jiān)管委員會的政策.這樣看來,本文使用的策略確實能夠找到最重要的結(jié)點.4圖熵發(fā)展的理論分析4.1網(wǎng)絡(luò)的演化過程為了在理論上對連接熵和中心熵的演化進(jìn)行分析,本文建立基于邊權(quán)逐漸加強機制的網(wǎng)絡(luò)演化模型來進(jìn)行分析.為簡單起見,我們假設(shè)網(wǎng)絡(luò)在環(huán)境中是孤立的,而且在演化過程中沒有新的結(jié)點加入.其演化規(guī)則如下:每個時間步將m條邊按偏好將權(quán)值更新增一,其更新的概率為πij=sisj∑a＜bsasb,πij=sisj∑a＜bsasb,其中si為網(wǎng)絡(luò)中結(jié)點i的強度.4.2網(wǎng)絡(luò)初始至網(wǎng)絡(luò)初始點強度的動力學(xué)方程由于局部連接性反映了結(jié)點的連接能力,我們將分析網(wǎng)絡(luò)內(nèi)各個結(jié)點強度的演化,以得到連接熵隨時間演化的規(guī)律.因為到t時間步網(wǎng)絡(luò)總的權(quán)值共增加了mt,那么所有結(jié)點的強度和共增加了2mt,根據(jù)連續(xù)場理論:∑iki≈2mt.結(jié)點i與結(jié)點j的邊權(quán)值滿足下述動力學(xué)方程:dwijdt=sisj∑a,b(a≠b)sasbm,其中Si表示結(jié)點i的強度.顯然,邊的逐漸加強是按照點強度驅(qū)動的.那么,隨著權(quán)值的更新,點的強度的動力學(xué)方程為dsidt=∑j(i≠j)sisj∑a,b(a≠b)sasbm=si∑j(i≠j)sj∑asa∑b(a≠b)sbm≈si×2mt2mt×2mtm=si2t,上述動力學(xué)方程的解為si(t)=si(1)t12,其中Si(1)為網(wǎng)絡(luò)初始結(jié)點i的強度.那么表示局部連接性的概率分布D有di(t)=si(t)∑jsj(t)=si(1)∑jsj(1).顯然,概率分布D隨著時間是相對不變的.所以,連接熵也相對不變,并沒有出現(xiàn)熵增的情況.4.3同配網(wǎng)絡(luò)中點介數(shù)的定義全局中心性反映了結(jié)點作為媒介的能力或影響,我們可分析對應(yīng)于點介數(shù)的網(wǎng)絡(luò)流動中每個結(jié)點的負(fù)載能力,以得到中心熵隨著時間演化的變化規(guī)律.文獻(xiàn)通過它所定義的演化模型得出點介數(shù)也是呈現(xiàn)負(fù)指數(shù)分布,而且每個頂點的介數(shù)g與度k成下列關(guān)系:g～kγ-1ˉη-1,其中,γ是度分布指數(shù),η是介數(shù)分布指數(shù).也就是說,結(jié)點介數(shù)的相關(guān)性(CorrelationofNodeBetweennessCentrality)類似于結(jié)點度的相關(guān)性(CorrelationofNodeDegree).但是,文獻(xiàn)指出上式是非平凡的,只有網(wǎng)絡(luò)是異配網(wǎng)絡(luò)(DissortativeNetwork)或獨立網(wǎng)絡(luò)(NeutralNetwork)時,它才成立.而當(dāng)網(wǎng)絡(luò)是同配網(wǎng)絡(luò)(AssortativeNetwork)時,結(jié)點介數(shù)的相關(guān)性具有極弱的同配性.換句話說,一個結(jié)點的介數(shù)幾乎獨立于它的鄰居的點介數(shù).如果結(jié)點介數(shù)是完全獨立于它的鄰居的點介數(shù),那么對于充分大的時間t,網(wǎng)絡(luò)的點介數(shù)呈possion分布,而且演化過程是近似各態(tài)歷經(jīng)和細(xì)致平衡的.因此,整個演化的過程也是全局中心性熵增的過程,最終達(dá)到狀態(tài)平衡.而社會網(wǎng)絡(luò)一般是同類匹配的,所以如果點介數(shù)可度量中心性的話,上述結(jié)論可以解釋為從平均意義上講社會連帶多的人的周圍同樣是社會連帶多的人.由于在同配網(wǎng)絡(luò)中度數(shù)大的結(jié)點相互緊鄰,那么某些結(jié)點對的最短路徑就沒有必要通過鄰近的中心結(jié)點.所以,盡管某一結(jié)點介數(shù)隨著它鄰居介數(shù)的增長而增長,但是非常弱甚至可認(rèn)為是獨立的.這樣的行為表示度數(shù)大的結(jié)點的介數(shù)并不一定是非常高的,它可能涵蓋一個較大的數(shù)值范圍.所以,由于在社會網(wǎng)絡(luò)的演化中概率分布B出現(xiàn)一種“平均化”的趨勢,中心熵逐漸增加.5結(jié)論:網(wǎng)絡(luò)的完善程度本文使用新的測度,即圖熵的概念來具體描述在網(wǎng)絡(luò)演化過程中的有序性.通過定義兩種截然不同的概率分布用圖熵的計算來分別描述全局屬性和局部屬性,在實證網(wǎng)絡(luò)上得到它們在網(wǎng)絡(luò)演化中有序性的不同趨勢,并通過熵參與度來探測某一結(jié)點在網(wǎng)絡(luò)中的重要程