Community Detection in Social Network

在Social Network中偵測社群(Community Detection)或對一個graph的節點進行分群(graph clustering)可說是被做到爛的議題，社群偵測的架構可大致歸納為下述步驟：

Step 1.
首先，將social network/graph萃取並建構起來，其中節點表示個體，邊表示個體之間存在的互動關係。例如節點表示人們，邊代表朋友關係。
Step 2.
定義community是什麼。99%社群偵測的研究都建立在「所謂社群即為"內部個體彼此間之互動關係"遠較"內部與外部個體之互動關係"緊密、強烈而頻繁」之前提假設上，換句話說，社群內部高互動密度，社群之間低互動密度。
Step 3.
定好要找的community後，必須設法歸納出一個符合community定義的目標函數(objective function)，其中通常會伴隨幾個參數或門檻值，如(1)community之大小、(2)共要多少個community、(3)community之密度等等。
Step 4.
設計演算法以達成上述目標函數或儘量做到近似最佳化(approximately optimize)。
Step 5.
評估找出來的communities之好壞。這又可分為兩大類：第一類是去看真實資料來源，看找出來被歸屬特定社群的那些個體是否make sense；第二類是該網路其實早有社群的標準答案(ground truth)，因此可計算precision與recall以衡量之。

針對步驟五，如果剛好不知道真實資料來源，而且又沒有標準答案，那該怎麼衡量一個community的好壞呢？這裡介紹另一種指標－－Conductance。給定一個graph G=(V,E)，一個V的子集合S之conductance定義如下：設v為S中所有節點之degree的總和，在S'為S的補集下，s為「一端節點在S中且另一端節點在S'中」之邊的數目，那麼conductance(S)=s/v，或等於s/(s+2e)，其中e為「兩端節點均在S中」之邊的數目。可以用另一種角度來解釋，假設A是G的相鄰矩陣(Adjacency Matrix)，那麼S之conductance定義如下：
其中A(S)定義如下：

可以看到conductance度量了特定社群偵測下，community內部(即S)與community外部(即S')之劃分到底好不好，為符合了社群「內部緊密、外部鬆散」的定義，一般來說conductance要愈小愈好。

關於如何衡量social network中一個community的好壞，可以進一步閱讀這篇論文：
R. Kannan et al., "On Clusterings: Good, Bad and Spectral", Jour. of the ACM, 51(3), 2004.

Diameters of Social Network

社會心理學家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分析上使用。

The Bow-Tie Structure

World Wide Web(WWW)到底能不能被視為一種Social Network？至少，他們之間存在一個特性上的差異－－WWW具有蝴蝶結結構(Bow-Tie Structure)，而Social Network則未必。Bow-Tie Structure是Broder等人於2000年發現的，他們設計Web Crawler從整個網際網路抓回網頁當作節點(vertex)，並透過Hyperlink將網頁與網頁之間建立邊(edge)，整理歸納出了的類似下圖的圖形(graph)，展示WWW的結構與蝴蝶結極為相似。這些研究人員將此結構分為五大部分作進一步的解釋：


(1) SCC: WWW的核心是其結構中的Strongly Connected Component (SCC)，所有SCC中的網頁均存在「具方向性的路徑」(directed path)與該SCC中的其他網頁相互連通。
(2) OUT: 能夠被SCC中的網頁以「具方向性的路徑」到達的網頁集合，稱為OUT元件。
(3) IN: 能夠以「具方向性的路徑」與SCC中所有網頁連通的網頁集合，稱為IN元件。
(4) TENDRILS: 所有能夠以「具方向性的路徑」到達OUT Component的網頁，以及所有能夠被IN Component中的網頁以「具方向性的路徑」到達的網頁，所形成的網頁集合，稱之。TUBE: 所有能夠從IN Component以「具方向性的路徑」到達OUT Component之網頁集合，稱之。
(5) 不符合上述四大類的網頁，即Disconnected Components。在WWW中，這類網頁佔有率高達50%。

P.S. 「具方向性的路徑」是不容許反向的，必須順從超連結hyperlink的方向。

後來2001年，Dill等人以不同scales之subgraphs of WWW Graph進一步闡述Bow-Tie Structure，其中這些subgraph是具有具有相似特性的網頁所組成，如內容主題類似、同屬某一地理位置的網頁。

(1) Recursive Bow-Tie Structure:
對整個Web Graph來說，Bow-tie結構是階層式的(Hierarchy)，如下圖。換句話說，根據網頁特性將WWW的網頁分成多個Subgraphs，各subgraph依舊存在bow-tie structure。
(2) Ease of Navigation:
所以具有bow-tie structures之subgraphs中的SCCs是透過最上層(最大的)SCC而緊密連結的，這提供我們很好的網頁瀏覽機制：可透過該目的網頁所屬之bow-tie structure之SCC來與整個WWW的相通。
(3) Resilience:
由於Bow-Tie Structures中的SCCs緊密連結的特性，使得當WWW Graph中某些網頁突然失聯時，還能夠透過其他網頁(也就是透過其他瀏覽路徑)來保持整個Web Graph之特性。此與Social Network之Resilience from Scale-free有異曲同工之妙。