《網絡科學-原理與應用》要點總結1——圖論

由于畢設的需要，寒假一直在看《網絡科學-原理與應用》這本書，到現在為止粗粗的看了一遍，現在把一些要點都記錄一下，當然裡面好多數學推算都沒懂，o(╯□╰)o

圖是一個3元組：G=(N,L,f),N為節點集合，L為鍊路集合，f為将鍊路映射到節點對的映射函數。圖有很多屬性，例如平均路徑長度，密度，熵，聚類系數，介數和緊度，譜半徑，譜系，度序列分布等。節點度等于将節點連接配接到圖上的鍊路數量。路徑長度是兩個節點間的最短路徑，平均路徑長度是所有最短路徑的平均值，又稱為特征路徑長度。循環的回路長度是1，意味着節點連接配接到自身。在圖G中任何兩個節點之間最長的路徑稱為圖G的直徑。從一個節點u到連通圖的所有其他節點的最長路徑定義成節點u的半徑，具有最小半徑的節點為圖的中心。具有最大的半徑的節點稱為邊沿節點。密度是實際鍊路數與最大可能鍊路數之比。聚類系數是對“有多少節點與他們的鄰接節點形成三角子圖”的一種測量。介數和緊度是對一個節點的中介或中間者的有用性的測量。。譜半徑是圖的鄰接矩陣的最大非平凡特征值：det[A(G)-λI]=0，譜半徑完全由圖的拓撲（度序列）來決定。譜系是圖的拉普拉斯矩陣的最大非平凡特征值：det[L-λI]=0。如果度序列為[0,0,3,0,1],則度序列分布g'=[0,0,0.75,0,0.25].熵是對“資訊量”或資訊傳遞的“不确定”的度量，熵的測量機關是比特:I(G)=-∑hi(㏒2(hi)),其中g'=[h1,h2......h(max_d)].

圖的四種基本形式的矩陣表示：連接配接矩陣，鄰接矩陣，路徑矩陣和拉普拉斯矩陣。連接配接矩陣就是節點u和節點v之間有多少條直接連着的線，注意要不經過其他的節點：如果Vi~Vj,Cij=k,否則Cij=0,k就是Vi~Vj的鍊路數。鄰接矩陣隻需要把連接配接矩陣稍作修改即可，如果k>1,那麼在鄰接矩陣中仍用1來表示：如果Vi~Vj, Aij=1,否則，Aij=0. 拉普拉斯矩陣L=A-D.這裡A是鄰接矩陣，D為對角矩陣。對角矩陣式一個具有非零對角元素并且對角元素d(i,i)等于節點Vi的度的一緻性矩陣。路徑矩陣存儲了沿着途中所有節點對之間有向路徑的跳數。

圖按照結構分類，可以分為随機圖，小世界類，無标度類和k-規則圖。随機圖具有随機結構（具有最小的聚類系數），k-規則圖具有純的确定性的結構。小世界類是大部分結構化的，部分随機的圖。小世界圖是具有相對較小的平均路徑長度，相對較高的聚類系數CC的圖。聚類系數的算法：假設鄰居共享c條鍊路，那麼節點u的聚類系數CC(u)=2c/(degree(u)*(degree(u)-1)).聚類系數是三角子圖c的實際數與最大可能數之比。無标度類是大部分是随機的，部分結構化的圖。

随機圖服從泊松分布，無标度圖服從幂律分布(厚尾分布，随着k的增加不會像指數或正太分布那樣快的減少)，小世界圖具有高平均聚類系數，k-規則圖具有0熵。