工具方法依據(jù)sns軟件教程pajek操作手冊

體的實(shí)例，分章節(jié)討論P(yáng)ajek在分析復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中的應(yīng)用。Theideaofcomplexnetwork,withthousandsofverticesandlines,havebeenwidelyappliedinmanydifferentareas,includingcomputer,biology,physicsandsocialscience,tonamebutafew.Althoughthetypesofcomplexnetworksareinnumerable,allofthemcanbedescribedbyacommonmodel,whichisknownasgraph.Basedongraphsandusingsixdatastructures,Pajek,whichisveryefficientandhumanized,isaprogramdesignedfortheemulationofcomplexnetwork.Thebasicsetofefficientalgorithmsareimplementedinittoyzethetopologyofcomplexnetworks,includingysisofthelocalnatureofverticesand iontogetaglobalviewofnetwork,transformationbetweendifferenttypesofnetworks,generatingrandomnetworksandsoon.Pajekprovidetheuserwithsomepowerfulvisualizationtoolsonathree-dimensionedreferenceframe.Theusercanfurtherimprovethepicturemanuallyorautomaticallybymovingverticesorspin.Moreover,wecandefineanoftenusedsequenceofelementaryoperationsasamacroandrunitasasinglecommand.Usingsystemsofmacros,Pajekisadaptedtospecialgroupsofusers.Inthisarticle,withsometypicalexamples,themainapplicationsofPajekarediscussedtoysisthetopologyofcomplex network,undirectednetwork,weight 引言 Pajek的產(chǎn)生背景Pajek的主要特 可視 抽象 Pajek的數(shù)據(jù)結(jié) Network（網(wǎng)絡(luò)）Partition（分類） Cluster（類）Hierarchy（層次） 復(fù)雜網(wǎng)絡(luò)的直徑K步之內(nèi)的路徑復(fù)雜網(wǎng)絡(luò)的測地矩陣（GeometricMatrices）k近鄰（k-neighbors）CC1--- 利用Pajek分析復(fù)雜網(wǎng)絡(luò)結(jié) 復(fù)雜網(wǎng)絡(luò)圖的 復(fù)雜網(wǎng)絡(luò)圖的連通分量(components) 利用Pajek轉(zhuǎn)換復(fù)雜網(wǎng) 有向邊轉(zhuǎn)換為無向邊無向邊轉(zhuǎn)換為有向邊添加節(jié) 添加兄弟邊（siblingedges） 利用Pajek生成復(fù)雜網(wǎng) ER隨機(jī)網(wǎng)絡(luò) Pajek的可視 繪制復(fù)雜網(wǎng)絡(luò)圖繪制不同類節(jié)點(diǎn)的復(fù)雜網(wǎng)絡(luò)圖 Pajek中的宏結(jié) 究的問題，就是于當(dāng)時的一個小鎮(zhèn)，這個小有一些河流，在此一共建了7Internet而言，每一個真復(fù)雜網(wǎng)絡(luò)。Pajek就是這樣一種軟件[13]。復(fù)雜網(wǎng)絡(luò)圖的結(jié)構(gòu)；第九章介紹了Pajek中宏文件的應(yīng)用。TQuickHeapInsertionO(n2O(n3中可見，當(dāng)節(jié)點(diǎn)數(shù)只有1000時，時間復(fù)雜度為O(n)的算法與復(fù)雜度為O(n3)的算法耗時僅100O(n2.22s，而復(fù)雜度為在Pajek中，所有的算法時間復(fù)雜度都低于O(n2)，即都為O(n)，O(n n)或者網(wǎng)絡(luò)的原因，也就是Pajek的 （源程序代碼參見附錄程序列表中1_1.vgr） 2_1.Pajek1.clu整體，將它作為一個新的節(jié)點(diǎn)得到一個新的網(wǎng)絡(luò)圖。在Pajek中利用菜單命令Operations/ShrinkNetwork/Partitions實(shí)現(xiàn)，在彈出來的框中選擇不要縮減的類的0看作一個整體。這種情況在Pajek中可以利用菜單命令Operations/ShrinkWindow 12341234寫在*Edges行下，則為無向邊。②此種方法實(shí)際上是對前法的一個改善。它不是依次列舉網(wǎng)絡(luò)中所有的邊， 6123123。其他程序中普遍采用的法。③用連接矩陣的方法來表示復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)。這種方法在計(jì)算機(jī)圖形學(xué)中得到較為廣1表示從其他節(jié)點(diǎn)指向節(jié)點(diǎn)j的邊。712345670210000000110000000110000000300000000050000000010，Pajek 點(diǎn)3所屬的類編號為2。 4754637553_2.（leaf而g1又有兩個子節(jié)點(diǎn)g11、g12。他們都是葉子節(jié)點(diǎn)分別包括兩個網(wǎng)絡(luò)中的節(jié)點(diǎn)。vector的文件中。Vector文件的后綴名為.ver。ii利用PajekNet/Partitions/Degree菜單下的In/Out/All三個命令可分別對有向圖的節(jié)點(diǎn)求其入度，出度和總的度。對于無向圖，則只需用All一個命令即可。如圖4_1所示的網(wǎng)絡(luò)，這是社會網(wǎng)絡(luò)學(xué)中的一個經(jīng)典問題[3]。70年代初期，Wayne于這些成員在內(nèi)部及外部的社會關(guān)系，WayneZachary構(gòu)造了他們之間一系列的關(guān)系4_1.Zachary圖 2.net執(zhí)行Net/Pathsbetween2vertices/Oneshortest菜單命令，在彈出來的框中輸入s_102s_506兩個節(jié)點(diǎn)，則可以得到這兩個節(jié)點(diǎn)之間的最短路徑。輸出的結(jié)果為一個若為1，則表示最短路徑經(jīng)過該節(jié)點(diǎn)。上院506。而復(fù)雜網(wǎng)絡(luò)中任意兩個節(jié)點(diǎn)之間的距離的最大值叫做復(fù)雜網(wǎng)絡(luò)的直徑D。路徑就稱節(jié)點(diǎn)ijk步內(nèi)路徑。PajekNet/Pathsbetween2vertices/WalkswithLimitedLength4_2s_1087s_3084_4復(fù)雜網(wǎng)絡(luò)的測地矩陣（Geometric得整個復(fù)雜網(wǎng)絡(luò)的測地矩陣。輸出結(jié)果為兩個矩陣。第一個是最短路徑長度矩陣（thematrix列表5，其中，5_2.net為最短路徑長度矩陣，5_3.net為最短路徑條數(shù)矩陣。近鄰。對于有向圖，如果忽略邊的方向，就可以當(dāng)作無向圖來求其節(jié)點(diǎn)的k近鄰。3.net4_5.4，最近的節(jié)點(diǎn)是tme1-tme5五個節(jié)點(diǎn)，k值為1。即設(shè)為默認(rèn)值。比如，pe0tme1Partitionpe1tem12步，因此，tem1這個節(jié)點(diǎn)所屬的類的編號即為。的類的編號都為。我們由圖中也可以看到，pe0pe0k由結(jié)果可見，tme1最遠(yuǎn)的輸入鄰居是 pm3和pm4，步距為9（如 ；若在4步之內(nèi)可以到達(dá)tem1，則所屬類的編號為這個步距。的k近鄰。CC1類系數(shù)(ClusteringCoefficients)CC1(i)[11]，即：CC1(i)2E1(i)/(ki(ki NCC1 N候，即復(fù)雜網(wǎng)絡(luò)中任意兩個節(jié)點(diǎn)都直接相連時，CC11。程度，因此，不必考慮邊的方向。對于有向圖，Pajek4_6.求得其各個節(jié)點(diǎn)的聚類系數(shù)CC1(i)。 13033

CC(i)E1 E2絡(luò)各個節(jié)點(diǎn)的聚類系數(shù)CC2(i)。，4.net5_1.14_1.per_2.er由這個結(jié)果可知，該無向網(wǎng)絡(luò)圖的深度優(yōu)先遍歷，各節(jié)點(diǎn)的順序?yàn)橄噜彽墓?jié)點(diǎn)j1,j2,j3……jk，接著一個與j1,j2,j3……jk的未 點(diǎn)未被（即該復(fù)雜網(wǎng)絡(luò)圖為不連通網(wǎng)絡(luò)圖，則另選網(wǎng)絡(luò)圖中一個未被的節(jié)點(diǎn)作為4_3.per點(diǎn) v14_4.per)。各節(jié)點(diǎn)的順序同樣為V1V2V3V4V5V6V7。此顯然滿足1-網(wǎng)絡(luò)點(diǎn)的定義。圖5_2.k-網(wǎng)5.net利用PajekNet/Partitions/Core/All求它的k-總，處理的結(jié)果為一個patition的文件。其中，每個節(jié)點(diǎn)對應(yīng)的類的編號即為該節(jié)點(diǎn)所屬的所有k-網(wǎng)絡(luò)中最大的k值，如果該節(jié)點(diǎn)不屬于任何網(wǎng)絡(luò)，則其對應(yīng)類的編號為0。由Pajek的結(jié)果可知：1-網(wǎng)絡(luò)。由圖5_1v1—v5連接，每個節(jié)點(diǎn)都有四個節(jié)點(diǎn)在該網(wǎng)絡(luò)內(nèi)，因此，它們顯然構(gòu)成一個 在Partition文件中k值越大的節(jié)點(diǎn)對于網(wǎng)絡(luò)的作用就越重要。在圖5_2中，Pajek中的ponentsStrongWeak源程序代碼見附錄中6.net）5_3.One、Three、Four、FiveSix通常稱為邊表示活動的網(wǎng)(ActiveOnEdgesAOE[19]AOE5_4.AOE7.net，鍵路徑。其輸出的結(jié)果有四個文件，其中兩個為NetworkVector網(wǎng)絡(luò)的關(guān)鍵路徑圖。如圖5_5所示。5_5.由此可見，該工程有兩條關(guān)鍵路徑，分別是V1V2V5V7V9以及V1V2V5V8V9。其中V1V2V5和V9都包括在兩條關(guān)鍵路徑上，因此，加快它們當(dāng)中的任何一個都可以縮短工程的時間。而V7和V8都分別只屬于一條關(guān)鍵路徑，因此通減復(fù)雜網(wǎng)絡(luò)圖以及2-模與1-模復(fù)雜網(wǎng)絡(luò)圖之間的相互轉(zhuǎn)換提供了一系列算法。圖。該轉(zhuǎn)換利用Pajek中的Net/Transform/Arcs->Edges/All菜單命令來實(shí)現(xiàn)。法：為原來兩條有向邊的權(quán)值和、較大的權(quán)值或者較小的權(quán)值。分別利用Pajek中節(jié)點(diǎn)j也有一條有向邊指向節(jié)點(diǎn)i，且這兩條邊的權(quán)值都為原無向邊的權(quán)值。另外，對于非循環(huán)的有向圖，Pajek 添加兄弟邊（sibling對于有向復(fù)雜網(wǎng)絡(luò)，Pajek允許用戶在復(fù)雜網(wǎng)絡(luò)的兄弟節(jié)點(diǎn)間添加一條邊，稱之為兄弟邊（siblingedge。我們已經(jīng)知道，凡是對于有向圖的操作，都要考慮其邊的兩個方向，在PajekNet/Transform/Add/SiblingEdges菜單下的兩條命令可以在這兩種兄弟節(jié)點(diǎn)間添加兄弟邊。Input執(zhí)行該命令后，Pajek將在原復(fù)雜網(wǎng)絡(luò)中所有有共同父節(jié)點(diǎn)的兩個節(jié)點(diǎn)（即Pajekalledgesallarcsmultiplelines如果兩個節(jié)點(diǎn)間通過多條邊直接相連，就將多余的邊刪除，僅保留一aluesaluealueLinesloops如果一個節(jié)點(diǎn)指向它本身，這樣的一條邊就叫做環(huán)（loopPajek的這lineswithvalue刪除某些特定權(quán)值的節(jié)點(diǎn)。比如，刪除高于（higherthan菜單命個范圍內(nèi)的（用withininterval菜單命令）所有邊。200萬人的工作生活受到影響，而這次事故的原因卻僅僅是因?yàn)閻圻_(dá)Hierarchy（層次）利用該縮減方法，Pajek次關(guān)系（用一個hierarchy的文件保存。Subdivision（分解）用戶還可以進(jìn)一步選擇這個閥值是指入度（input、出度（output)還是總度（all。mode的某種關(guān)聯(lián)。比如說，對于一個科學(xué)家著作的網(wǎng)絡(luò)[21]，我們希望知道若干科學(xué)家參與mode（actors（events表示的就是表示這類節(jié)點(diǎn)的從屬關(guān)系的一種典型的2-模網(wǎng)絡(luò)。表6_1.2-模網(wǎng)絡(luò)點(diǎn)關(guān)系示意著科學(xué) 代代010110101001011001116_1.2-mode21-模復(fù)雜網(wǎng)絡(luò)，從而能夠較直觀地看到同一類節(jié)類別2表示；而8_1.net則給出了兩類節(jié)點(diǎn)之間的從屬關(guān)系。見附錄中8_2.net。邊相連。即科學(xué)家S_4S_5共同參與撰寫的著作有兩篇。代碼見附錄中8_3.net。Include1-模網(wǎng)絡(luò)中，除了用邊表示各節(jié)點(diǎn)（Columns如，加環(huán)以后得到的科學(xué)家的網(wǎng)絡(luò)如圖6_4所示（其程序源代碼見附錄中8_4.net。10_4.Multiple如果該復(fù)選項(xiàng)被選中的話，得到的結(jié)果將會是一個無權(quán)的1-模復(fù)雜網(wǎng)絡(luò)，不過，在同一對Normalize1-1，其他節(jié)點(diǎn)的度除以這個最大的度值。這樣，通過尋找復(fù)雜網(wǎng)絡(luò)中度為1的節(jié)點(diǎn)，就然后再利用最大值標(biāo)準(zhǔn)化使最大的值為1）等。1-模復(fù)雜網(wǎng)絡(luò)是一個有環(huán)的權(quán)值網(wǎng)絡(luò)。下面將簡單介紹這幾種標(biāo)ijGeoij Input

a aOutputaaMin

,a

)

aij,a

a MaxDiraij,aii

的應(yīng)用價值。Pajek就為用戶提供了多種生成復(fù)雜網(wǎng)絡(luò)的方法。義一個partition的文件，其中給出各個節(jié)點(diǎn)的度值。然后利用Partiton/MakeRandom（InputFirstPartitionSecondPartitionPartition兩種生成有向圖的方法：第一，通過指定的邊數(shù)來構(gòu)造隨機(jī)復(fù)雜網(wǎng)絡(luò)。利用Net/RandomNetworks/TotalNo.ofArcs命令，在彈出的兩個框中依次輸入成的復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)和總邊數(shù)即可。第二，通過指定度的范圍來構(gòu)造復(fù)雜網(wǎng)絡(luò)。利用Net/RandomNetworks/VerticesOutputDegree的菜單命令，在彈出的三個框中依次輸入成復(fù)生成ERdv

n(n可能存在的邊數(shù)。比如，對于無向圖而言，M的值即為：M 2d2v

以及雙向非循環(huán)（BipartiteAcyclic）ER隨機(jī)網(wǎng)絡(luò)等?，F(xiàn)。這就是許多復(fù)雜網(wǎng)絡(luò)，包括internet、網(wǎng)以及新陳代謝等網(wǎng)絡(luò)的連接度分布函數(shù)為了揭示冪律分布的產(chǎn)生機(jī)理，BarabasiAlbert[24，網(wǎng)絡(luò)的優(yōu)先連接(PreferentialAttaent)特性，即新的節(jié)點(diǎn)更傾向于與那些具有較大連接度的節(jié)點(diǎn)相連。這種現(xiàn)象就是常說的“富者更富（Richgetricher。

Pr(v)indeg(v)outdeg(v)E

E表示原網(wǎng)絡(luò)中總的邊數(shù)（也就是原網(wǎng)絡(luò)中各節(jié)點(diǎn)的度之和v1。對于式（7-2），可以證明Pr(v1v（Undirected（Acyclic另外，Pajek中Net/RandomNetwork/Scale的菜單下還有一個的復(fù)選項(xiàng)，若選有一個Draw的菜單命令，Pajek就是在這個菜單下為用戶提供了一系列令，允許用戶繪（Numbers標(biāo)記或者不做任何標(biāo)記（Nolabel）等。標(biāo)識邊的方法也在繪圖窗口Options/Lines/MarkLines的菜單下，包括用邊的名稱(withLabels)、權(quán)值（withValues）來標(biāo)記或者不標(biāo)記的，對于復(fù)雜網(wǎng)絡(luò)中不同權(quán)值的邊，Pajek也可以通過繪圖的方法直觀的表示出來。利可以利用繪圖窗口中Options/Transform/FitArea菜單下的兩個命令來實(shí)現(xiàn)。其中，調(diào)整的位置有某些限制。Pajek的繪圖窗口中Move菜單下令為用戶提供了若干限制的條Fixx,y,Radius三條選項(xiàng)，分別表示固定節(jié)點(diǎn)的橫坐標(biāo)、縱坐標(biāo)或者極 圖8_1.CircleGrid的功能類似，它規(guī)定了節(jié)點(diǎn)可移至的圓的個數(shù)，以及各個圓圖8_2.用Spin/Stepindegrees命令，在彈出的框中給出旋轉(zhuǎn)的速度，輸入的數(shù)值越大則旋轉(zhuǎn)用Pajek中提供的相應(yīng)功能逐次操作，就會非常麻煩。因此，用戶希望可以用一個簡單執(zhí)行菜單命令Macro/Record，在彈出的框中為宏文件命名為macro1,其后綴名Pajek默認(rèn)的.mcr。然后，依次執(zhí)行以下命令，并且在每執(zhí)行一條命令都執(zhí)行DegreeofVertices,執(zhí)行Net/Partitions/Degree/AllClusteringCoefficients,執(zhí)行Net/Vector/Clustering③添加注釋W(xué)eakComponentsofNetwork，執(zhí) DepthFirstNumberingofNetwork,執(zhí)行Net/Numbering/DepthPajek支持六種數(shù)據(jù)類型，分別是networkpartition,permutationCluster, 142434412356754664577468879989897555 4 34445555666677777712345678913481248941238517617715681234931561141234671212123329139912345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667 879810.5000ellipsex_fact1lr19lphi110bw1.5fos20ic20.5000ellipsex_fact1lr19lphi110bw1.5fos20ic345670.5000ellipsex_fact1lr19lphi110bw1.5fos20ic891011120.5000ellipsex_fact1lr19lphi110bw1.5fos20i5000boxicBlackx_fact0.1y_fact2lr25lphi105fos180.5000boxicBlackx_fact0.1y_fact2lr25lphi105fos20phi-190.5000boxicBla