Planet of NCCUCS

社會心理學家Stanley Milgram於1969年實驗得到的「六度分離」(Six Degree of Separation)的”6″，揭示原來你和我的距離在這茫茫人海中原來如此接近，後來人們稱這個”6″為social network或graph的直徑(diameter)。關於這個diameter的想法，後來可有幾種不同的變形哩！

1. Expansion and the hop-plot
Expansion是由Tangmunarunkit於2001年所提出的，它被用來量測graph中節點的鄰居(neighborhood)隨著步數(h-hops)的成長速率(growing rate)。這和Faloutsos三兄弟(M. Faloutsos, P. Faloutsos, and C. Faloutsos)所提出的hop-plot不謀而合。Hop-plot指的是，對於graph中每一個節點u，都去計算它h步之內的節點個數Nh(u)，然後將所有點之h=1,2..分別加總所得到之Nh畫出來，便是expansion與hop-plot了。注意hop-plot是畫Nh versus h。

2. Effective diameter (or called Eccentricity)
Hop-plot同時可以被拿來計算effective diameter。所謂effective diameter指的是對於所有連通配對的節點(connected pairs)，其可達某一設定之節點門檻值(例如整個90%的節點數)之最小的hops數目。參見上圖，可以看到在hop數目大於6後，可連通之節點的成長趨勢就近乎水平了，該圖的effective diameter即為6。

3. Characteristic path length
對於一個graph中每個節點，都去計算它到其他n-1個節點的最短路徑長度，取n-1個長度之平均值avg，於是一個有n個節點的graph會有n個avg值，它們的median，即為特徵路徑長度。

4. Average diameter
與characteristic path length極為相似，差就差在average diameter不取median，改取mean。

Expansion較常被拿來區分鄰居節點的成長趨勢(exponential或subexponential)；使用eccentricity的好處在於它不限於graph是否連通(connected)；然而，characteristic與average diameter均只能使用在largest component；此外，由於characteristic diameter取median，它較不受outlier的影響，而average diameter較常在worst case分析上使用。