記錄：小魚 主講人：台大電信所孔令宏學長
12/29 19:00 ~ 21:30 博理館217
講座大綱
壹、研究複雜網路的動機
貳、測量複雜網路的幾個概念
参、小世界網路模型(Small-world network model)
肆、無尺度網路模型(Scale-free network model)
伍、應用
2011年5月22日陸、未來展望
柒、參考資料
壹、研究複雜網路的動機
日常生活中有哪些網路？不限電腦網路，與會人自由舉例：
MSN
人際關係
小道消息
手機聯絡人
用來傳遞訊息的routers
物流
體內循環系統
楚盛家具國際貿易等
綜合以上所提，日常生活中的網路有以下幾類：
一、社交網路
二、訊息網路
如引用學術論文、網際網路的超連結等
三、科技網路
如電力網路、電話網路、電子電路、飛機航線等
四、生物網路
如代謝途徑、食物網、神經網路等
圖只呈現了一部份的分子交互作用。
(From ref. 4.)
Fig 2. 威斯康辛州小岩湖(Little Rock Lake)
的食物網。(From ref. 4.)
什麼樣的東西可被稱為網路？與會人自由舉例：
(2)連結節點的路徑。
具有牽一髮而動全身的特性。
連結強度可能有強弱之別。
組成的點之間有同質性。
連結後的行為和各自獨立時不同。杜香油
複雜程度可大可小。
或point﹞與邊﹝或稱Links﹞構成，各個node之
間由edges連結。
Fig.3.
了解複雜網路的方法
一、Bottom-up approach
由下而上，將複雜系統拆解成基本物質，再重新組合而成。如同尋物理的基本力一般。
二、Top-down approach
由整體網路的架構方法研究網路。
今天我們將主要以此途徑探討複雜網路。
了解網路的困難點
一、結構的複雜性
二、網路的進化
網路可能隨著時間的進行而變。
三、邊的多樣性
儒学联合论坛各個edge可能有不同的權重、正負號和方向。
四、節點的多樣性
各個node可能有不同的功能和層級。
小世界問題
兩個陌生人在派對中碰面了，他們交談後發現彼此竟然擁有一些共同的朋友。他們或許會說：「這真是一個小世界。」。
社會心理學家Stanley Milgram是第一個做實驗證明了「小世界現象」的人(1967)。 他同時也以「電擊實驗」顯示人們對權威不可理喻的服從而出名。
Stanley Milgram的實驗程序
從Nebraska州隨機選出受試者，將他們的姓名、職業、居住地的大約位置寄給住在Boston的陌生人。
Boston人收到後，若不認識此寄件者，可將此信轉寄給可能更認識寄件者的人，不過轉寄人和接收轉信的人必須已熟到可以叫出名字的程度。
由於接到信的人並沒有誘因協助完成實驗，多數的信件在半途遺失了，只有四分之一成功回到Nebraska人的手上。
不過在這些成功回收的信件中，平均而言竟然只需經過六個人信件就能回到原寄件者的手中。
以網路的理論嘗試做出小世界現象的模型
基本假設：
一、每個node都位於相同的層級，也有著相同的功能。
二、每個edge都沒有方向性、正負號及權重。
三、網路中任兩個node間不存在二以上的edges，也不存
在自己連到自己迴圈。
Fig. 4.
貳、測量複雜網路的幾個概念
名詞解釋
相鄰節點(neighboring nodes)：有edge相連的兩個nodes。
步伐(walk)：由nodes和edges構成的序列，可從一個node走到不直接相鄰的另一個node。
路徑(path)：不重複經過任何一個node兩次的walk；有起點、終點，且起終點不同的「步伐(walk)」。
最短路徑(shortest path)：連接某兩個節點而通過最少edge的路徑。
連結性(degree/connectivity)：通過某一個節點的edge數目。
描述網路拓樸的幾個參數
平均路徑長度(Average Path Length, L)：
出圖形中任兩個節點之間最短路徑長，取這n(n-1)/2個
最短路徑長度的算術平均數即得。
意義：兩個隨機選出的節點彼此之間有多遠？
聚係數(Clustering Coefficient, C)：
若節點A有B、C兩個鄰居，那麼B和C同時也是相鄰節點的
機率是多少？逐一統計網路每個節點的鄰居即得。
意義：「你的朋友的朋友」和「你」也是朋友的機率是多少？
連結性分配(Degree Distribution, P(k))：
整個網路中「連結性」恰為k的節點占了多少比例？亦可理解
為隨機抽出一個節點，它的「連結性」恰為k的機率是多少？
意義：整個網路中節點的「連結性」呈現什麼樣的分布？
規則的網路舉隅
一、完全連結(globally coupled)：每個人都是每個人的鄰居。當n=8時：
L = 1
因為每個人都可以在隔壁到所有人。
C = 1
因為你的鄰居A和你的鄰居B彼此也是鄰居。
P(7)
= 1
每個人都有n-1=7個鄰居，因此P(7)=100%。
Fig. 5. n=8時的globally coupled
二、最接近的鄰居(nearest neighbor)：每個人只認識隔壁，和隔壁的隔壁。當n=16時：
L = 2.4
對每個node 而言，L=1的有4個；L=2的有4個；L=3的有4個；L=4的有3個。
(1*4+2*4+3*4+4*3)/15 = 2.4。 又因為每一個節點的情況都相同，因此可知整個網路的L = 2.4。
C = 0.5
你的鄰居有四個，由左至右編號為A 、B 、C 、D 。
其中A 、B ；B 、C ；C 、D 為鄰居。
3/C(4取2)=3/6=0.5。 又因為每一個節點的情況都相同，因 此可知整個網路的C=0.5。
P(4) = 1
每個人都有4個鄰居，因此P(4)=100%。
Fig. 6. n=16時的nearest neighbor 網路。
三、星狀連結(star-shaped coupled)當n →無限大： L → 2
黑幫小弟很多，老大哥只有一個。
隨機抓出兩個人就抓到老大哥的機率很低，
只有(n-1)/ [n(n-1)/2]，因此連到老大哥(L=1) 可以忽略。
Fig. 7. n=16時的
star-shaped coupled 網路。考德威尔
另外，小弟連到小弟的情形的機率很高，有 [(n-1)(n-2)/2]/ [n(n-1)/2]。這些情況的L 都等於2。
故對於整個網路而言，L → 2。 正式的說法為 lim { (n-1)*1 + [(n-1)(n-2)/2]*2 }/[n(n-1)/2] = 2
n →∞
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议