小世界現象

Abstract

在社會科學界，「小世界現象」意味著：任一兩個陌生人可以被一條很短的、由彼此相識的人所形成的「鍊」所連結起來。在六○年代，心理學家Milgram設計了一個實驗想要瞭解任一兩位陌生人之間的「距離」有多遠，最後實驗結果得知：這條練的長度是「六」；換句話說，任意一個人想要將一封信寄給一位他素為謀面、只知道名字不知道地址的人，這封信只要經過平均六個人的轉交就可以寄到那位陌生人手上。這即是有名「六度連結」。而在自然界和科技界，小世界 現象也是常見的特徵。早期的實驗已經告訴我們：第一，這條「鍊」是廣泛存在的；第二，一些人只要擁有一些被限制過的資訊，又有能力可以建構幾這條鏈。許多數學家也對小世界現象很有興趣，並試著想要發展出理論模型去幾是小世界現象在邏輯上如何可能與如何運作。Kleinberg提出一組網絡模型和一個演算法，證明了存在一個模型，並使用該演算法可以在O(log2N)的時間複雜度內找倒這條很短的「鍊」。我則以Kleinberg的網絡模型為基礎，提出了三種模型：torus, grid of high dimension, 以及cube。除了cube，我證明了使用相同的演算法，皆可在O(log2N)的時間複雜度找到這條「鍊」。而cube，我則以程式去模擬，實驗數據呈現出一個有力的結果可以支持我所提出的理論假設。

The small world phenomenon, the principle that most of people are linked by short chains of acquaintances, is first studied as a problem in social science. It is also a feature of a range of networks arising in nature and technology. Early experiments showed that it has two properties: first, short chains are widespread, and second, individuals with local information are able to find the chains. Kleinberg proposed a family of network models and a greedy algorithm, showing that there is a unique model within the family for which the greedy algorithm’s running time is O(log2 N). We study Kleinberg’s theorems and give some models based on Kleinberg’s family:torus, grids of high dimension, and cube.