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有異曲同工之妙。

Social Computing: A Snapshot

隨著Web2.0的演進以及計算媒介愈來愈容易取得，使得一些事物在近幾年正快速變化，如社交方式、經濟模式、大眾文化等，背後本質上的改變，正從以個體為中心的思維，逐漸轉移到群體間合作、互動所產生的一連串社交反應(Social Dynamics)，而社會計算(Social Computing)正是一種透過資訊技術來輔助這些社交資訊(Social Information, User-Generated Content, Consumer-Generated Media)或社交行為(Social Behaviors, Social Interaction)之收集、分析、整合、呈現的新興領域，以現有的Web服務來舉例，Facebook, Flickr, Del.icio.us, Blogger, MSN均為社交服務下的平台(可參考下圖)，或被稱作社交軟體(Social Software)，以現有的技術來舉例，協同過濾(Collaborative Filtering), 病毒式行銷(Viral Marketing), 標籤分類(Tagging), 計算社交決策(Computational Social Choice)等均為社會計算在技術上的例子。社會計算的不止於學術研究，目前軟體產業、線上遊戲、商業策略、甚至政治分析等相關領域也相繼投入。


從產業界進入社會計算應用的角度來看Social Computing，Dion Hinchcliffe在The shift to Social Computing一文提到了三個根本的原則：
1. Innovation is moving from a top-down to bottom-up model
(創新正逐漸朝下而上的方式演進)
2. Value is shifting from ownership to experiences
(價值不在只是擁有，更重要的是體驗)
3. Power is moving from institutions to communities
(力量將來自於社群，遠過組織本身)

從學術研究的角度來看，Social Computing跨足計算科學與社會科學，Social Computing的概觀可從下面這張圖來看。其基礎主要建構於：社會心理學(Social Psychology)、人機互動(Human-Computer Interaction)、社群網路分析(Social Network Analysis)、人類學(Anthropology)、組織理論(Organization Theroy)、社會學(Sociology)與計算理論(Computing Theory)。資訊技術與社會理論對於社會計算可說是相輔相成，一方面得思考如何將上述人文學科整合成socio-technical system，另一方面得思考對於現有的技術如Database, Multimedia, Software Engineering, Wireless該如何設計以達到社交資訊處理(Social Information Processing)的目的：1) 探勘群體行為中的知識, 2) 群體智慧作為決策, 3) Social Web的形成，這是「分析」的觀點。另一種觀點為「合成」，偏向Agent-based Modeling、或是人工生命（可參考紅虫寫的科普「混沌邊緣的藝術－人工生命」）。


IEEE International Conference on Social Computing

Rank-by-feature Visualization

Linton C. Freeman在2000年Journal of Social Structure發表的"Visualizing Social Networks"指出，對於social network的visualization design，有兩個主要的patterns是必須被考慮進去的。(1) Social Positions: sets of actors who are linked into the total social system in similar ways. (2) Social Groups: collections of actors who are closely linked to one another. 針對這兩個議題Adam Perer在ACM CHI 2006提出了一種"Ranking-by-feature"的架構來視覺化社群網路，其主要的概念是讓使用者能自行選擇感興趣的準則(ranking citerion)或項目(他把它稱作"feature")，而呈現出來的social graph上的所有nodes與relations就會根據使用者的選擇來做filtering或ranking。我覺得挺直覺的。Perer列出以下幾項他們設計的scenarios。

Entity Rankings

簡單講，就是根據某種衡量指標來對network的所有節點ranking，然後列出來。系統設計者可以根據多種衡量social network的指標來訂定所謂的feature。然而，由於單對值的排序並無法看出排名較前面的在network扮演的角色或意義，因此可以在graph上做一進步的視覺化解釋。例如，當feature是betweenness centrality時(被all-pairs shortest path經過的次數)，秀出ranking list的同時，也將graph上使用者選定的node對應的shortest path levels之edges用alpha值的層次表示出來。

Relationship Rankings

關連，也就是relationship，在social network是最主要的成員，在rank-by-feature的架構下，relation的呈現分為兩個部份，一個是用類似陣列的方式呈現(half-matrix for undirected, full-matrix for directed)，如下圖。該矩陣的維度是network中nodes的個數。其中每個cell代表兩個entities彼此在特定feature下的相似度或可接近程度(affinity)，透過不同顏色或是同顏色不同alpha值的方式，讓使用者清楚relation的程度與關係。另一方面，當使用者點選matrix上某個cell時，繪出該matrix的graph會同步highlight秀出對應的path，作為一種visual explanation。

Cohensive Subgroups

然而，當graph的內容很大時，過量的視覺化內容將不利呈現與分析，此時，互動性(interactive procedures)就扮演了關鍵的角色，也就是透過互動瀏覽，以及feature的選定，如connected component或community(attribute-based or link-based)，動態且即時地將node的結合形成subgroups。此外，為了能夠做比較，使用者能夠任意選取特定多個subgraph來呈現，並列出他們在一些衡量標準上的差異。

Ego-Centered Exploration

最後，也是最直覺的一項，就是選定某一node，以該節點為中心，如tree的root般，依據depth(or level)逐層以同系列的視覺化效果顯示，而使用者可以調整想秀出幾層。如下圖。

OpenSocial

PK with Facebook for standard? 一個想吸引developer的social network應用程式開發介面(結合各家之力來跟Facebook抗衡？更有想要一統SNS江湖的意味？)。只要開發者以OpenSocial為標準來推出Social Network Service，那麼只須寫一支應用程式，可以直接移植到不同social network平台(Container)上使用，甚至可以把不同社群服務網站的user profile做跨平台的流通？打破各個Social network平台互為封閉的侷限，這也正是Web2.0的精神之一：Open and Share。其實它概念的類似於Fackbook提供API讓開發人員自行撰寫一些有趣的application，而對比於Facebook自成一個系統。目前加入Google OpenSocial計畫的廠商有：MySpace(有效會員最多), Friendster, hi5, LinkedIn, Ning, orkut, Six Apart, Tianji(中國最大), Viadeo, Bebo(歐洲最大), and XING。對Google而言，OpenSocial幫助最大的還是拓展其廣告利益來源啊！XD

Google的官方簡介：
OpenSocial is a set of common APIs for building social applications on the web. These common APIs mean that developers only have to learn once in order to start building social applications for multiple websites, and any website will be able to implement OpenSocial and host social applications.

OpenSocial API目前只提供的主要以HTML + JavaScript + XML為程式基礎，主要由三大部份組成：People Data API -使用者資料、Activities Data API -使用者活動或事件處理、Persistence Data API -儲存使用者key/value的記錄。目前已經有一些網站利用OpenSocial API做了簡單的應用，可以到這邊看看OpenSocial Example。

其實類似SNS的發展趨勢，大致是兩大部份：透過使用者所提供的資訊與其彼此的link所形成的social network，以及開發者利用使用者資料所開發提供的application。二者交相影響，使得平台上的互動與資訊愈加豐富，讓使用者更願意分享自己，自然商機也就隱含於其中了。

Weak Ties

弱連結(Weak Ties)是社會學家Mark Granovetter所提出來的，他認為當人們想要尋求管道與人交流資訊時，經常是從與自己關係不是那麼密切的(Weak Ties)人際網路中找尋，因為與自己關係程度較為強烈(或者說是生活圈接近、互動頻繁)的那些人同質性太高了(物以類聚)，所能提供的資訊多數會與我們原本認知的重疊。也就是說，多數的群體運動較不容易發生在彼此關係相當緊密的強連結(Strong Ties)中，而在於人與人彼此並不是相當熟識、並且沒有任何共通點的Weak Ties中。

我們可以從另外一個角度，也就是資訊散播(information diffusion)的觀點來看weak ties。舉個例子，與一個人來往的朋友們容易彼此也都互相認識，於是，在這種community中，我們從某一個人聽到的話，可能這圈子裡的另一個人早就說過了(老梗了XD)。資訊的交流在一個群體中，隨著時間裡會漸漸變成多餘的.. 也就是強連結的資訊活動範圍是較為封閉的，而新的資訊的進入通常來自群體成員對外的弱連結。我覺得Strong ties的價值在於群體凝聚力的形成，而Weak ties的價值在於對不同資訊的取得。

值得注意的是，Mark Granovetter的所謂strong ties與weak ties並非由個體主觀來認定的，而是一種從群體的角度"個體與群體互動的程度"的客觀概念，換句話說，如果我們突然與一位朋友發生衝突，並不表示說我們想要把對方從原本的strong ties轉為weak ties就說了算，因為他與群體之間的互動程度是依舊保持原樣的。我覺得這種客觀的精神有點類似Facebook的一個application - "Define me"，從他人/群體的角度來看自己，如果可以的話，或許我們可以仔細觀察看看，被下的tags中，除了一些common impressions外，那些比較特別的tags是不是從你的不同weak ties來源下的呢？另外，一個人的relationship中若存在愈多weak ties，所代表的意義又是什麼呢？是他的social impact比較強呢？還是他本身能納百川，交友、見識都很廣闊？

再來簡單說說weak ties與目前當紅的Social Network Services (SNS)的關係。我認為一些IM軟體，如MSN Messager, Google Talk, 或者Yahoo!即時通，所形成的網路關係比較傾向strong ties(概念上)，也可以說當我們正在IM上與某一位朋友對談時，那種形式是跟講電話是類似的，而一般來說，我們比較會與強連結的朋友比較有話聊，並且所聊的話題是不常發生在那些弱連結的對象上的。但SNS，如facebook, LinkedIn, Orkut等，就有點不一樣了，就facebook來說，我覺得它藉由一些吸引人、有趣、具創意的遊戲、測驗的互動式social applications，打破了現實世界的時空限制、文化與生命歷程的隔閡等，提供一個與弱連結(具共同偏好、或者特定屬性欄位接近的認識或不認識的人)建立溝通互動的平台，使我們有機會在任何時刻、任何地點同步地和強與弱連結進行訊息的傳遞，並保有IM強連結的資訊流通價值.. (已經不知道自己在寫什麼了 orz)

最後，以一個譬喻作為這篇介紹弱連結的結尾。Strong ties: 親情; Weak ties: 愛情。親情是一種建立在血緣上的關係，"strong"的意謂不言而喻；愛情是發生在原本毫無關係的兩個人身上，並且這種關係必須經過努力才能建立起，維持更得要有雙方的用心經營，它是吸引人的，但它更是脆弱的..

The Rule of 150

社會心理學家Stanley Milgram所提出來的六度分離(Six Degrees of Separation)是Social network最廣為人知的社會性實驗，然而，六度分離只是Social Network兩大理論基礎之一，另一個反應真實世界網路關係的理論正是英國演化心理學家(兼社會生物學家)Robin Dunbar所提出的「150法則」(The Rule of 150)，其中150又被稱作Dunbar's number。

簡單來說，「150法則」中的150代表個體能夠與周圍其他人維持正常往來的社交關係(social relationship)的理論最大值，當群體數目大於150，若想繼續保有如150以下的穩定關係，個體就必須想更多方式、花更多時間來維持群體內凝聚。換一種角度來看，只要能夠將具有關係的人群數目控制在150人以下，個體之於人群便能獲得最有效的管理方式，換句話說當一個群體的人數超過了150後，群體對個體的影響力將會下降。舉一個最明顯的例子，為何許多Instant Messaging Service(如MSN)最初設定每個人最多能夠加入好友列表的數目是150人(雖然目前上限已經增加到600人XD)，因為150是一個人維持人際關係網路的極限。其他如某些手機sim卡儲存號碼的上限數目是150，某些軍事管理上也有用到150。

關於「150法則」，Malcolm Gladwell更在《The Tipping Point: How Little Things Can Make a Big Difference》一書中將150具像化為：「在一次不期而遇的聚會上，令你不會感到尷尬的人數最大值。」書中還舉了另一個例子：一個發源於歐洲的、自給自足的農民自發性組織，以一種有趣的不成文規定長期維持了當地的民風，即聚落人數一旦超過150人的規模，就必須將此群體拆成兩個，各自發展。

Robin Dunbar認為人類的神經系統與學習能力存在某種先天上的限制，使得人類的溝通互動能力侷限於某一水平，這跟人腦是無法同時理解7種以上的事情相似的。而150這個數字是從何得來的呢？Robin Dunbar在研究中指出，此一法則與人腦進化程度有關，若個體的社交網路很大、經常必須連繫的人過多，人腦智力的負擔得隨之有級數的變化才能應付。Robin Dunbar為此實驗提出了一個數學模型，以物種本身的大腦新皮質相對腦的比例，計算出該物種所能擁有的活動群體之最大值，而輸入的是現代人類(Homo Sapiens)的比例時，得到的數值為147.8，約等於150。

Dunbar's number針對的是個體，那麼如果我們從150來思考由個體所形成的社群(Community)，在保有community功能上的意義下，還會是接近這個數字嗎？或者更大呢？另一方面，我覺得Dunbar's number與community的形成又隱約與Mark Granovetter所提出的弱連結(The Strength of Weak Ties)有所關連。

對Dunbar's number有興趣的人，可以看他的原始論文: Dunbar, R. (1993) Coevolution of neocortical size, group size and language in humans. Behavioral and Brain Sciences 16: 681-735

Random Rewiring

之前幫SD老師簡介social network時，有個地方含糊帶過(就是最下面那張圖)，這邊再簡單說明一下好了(雖然說沒人看得到XD)。首先，什麼是regular graph: graph上有n個點，每個點只與離它最近的k個點建立edge。什麼是random graph: graph上的每一點與其它點建立edge的機率都同為p。如果世界上每個人與隨機與其它50個人建立認識的關係，那麼60億人就滿足六度分離(Six Degrees of Separation)的特性。所謂的small world會是regular還是random graph? 這個問題先擱著，我們要先知道小世界最主要的精神: network裡面，人與人建立edge的機率是不一樣的，這個機率可能同時受到時空、文化、年齡、性別等等很多因素的影響，也就是network具有群聚現象(Clustering Effect)。

接著，我們簡單定義兩個衡量network的指標: 群聚度(Degree of Clustering)與分離度(Degree of Separation)。特定一個node的群聚度指的是network中，你的朋友的朋友也會是你的朋友的程度(好像在繞口令XD)，假設某個node有k個朋友，則此k個朋友彼此間所有可能形成的edge總數為k(k-1)/2，那麼該node的群聚度為此k個朋友間真正形成edge的總數除以可能形成的edge總數，如下圖，該點的群聚度為3/6=0.5。整個network的群聚度為所有node群聚度的平均值。network中，任兩個node的分離度為此二nodes的shortest path之長度，整個network的分離度為所有node pair分離度的平均值。

OK. 回到small world，剛才提到它必須具有clustering effect，也就是說，必須兼具高群聚度與低分離度的特性，從generative model的角度來看，如何建立出符合這兩個特性的small world network呢? 所要用到的概念就是edge的random rewiring了。Edge rewiring簡單說就是edge的重連，那麼，是要對誰做rewiring呢? 回憶一下比較容易被產生出來的regular graph與random graph，套用這兩個衡量標準來看，regular graph具有的是高群聚度與高分離度，而random graph則具有低群聚度與低分離度，這樣看起來small world似乎就處於此二者之間了，因此rewiring就是在他們之間做適度的調整。

對於有n個nodes，每個node有k條edge的ring lattice(regular graph)，以機率p來rewire它的edges，當p=0，所有edges沒有改變，還是regular graph；當p=1，所有nodes彼此必定隨機重新建立edges，形成random graph；當0<p<1時network的特性，就接近small world的群聚現象囉！如下圖是由regular graph向random graph做rewiring的示意過程(可以注意到過程中node總數與和edge總數都是不變的)。

或許有人會問，rewiring具體過程是怎麼跑的呢? 就用上面這張圖來說明吧！最左邊是一個具有20個nodes(n=20)、每個node有4條edges(k=4)的regular graph。我們可以依順時針方向，隨機選一個node和一條連到這個node最接近(length=1)的node的edge，以機率值p將該node重新連接(rewire)到其他node，其中target node是以相同的機率值p在整個network中挑出來的(如果這兩個nodes彼此間早已存在edge，就不用rewire了，繼續順時針往另一個node做下去)。當處理完所有nodes都跑過一次後，接著考慮到與該node第二接近(length=2)的node的edge，rewiring的方法和之前一樣。如此隨著每回合length漸增，最後當所有的edges都被rewire過後，就可以停止了(大概是在跑了k/2個回合後會停)。

這篇寫得很亂，看看就好orz

Elastic Tag Maps

Tag cloud是最常用來表示一個resource來源的tags出現頻率，但它並不能呈現該resource所隱含的terms的結構，也就是它忽略了tags彼此間的關係(relation)，最直覺改進tag cloud這種缺點的作法或許是秀出指定的tag的同時也將與該tag相關的tags一併連結秀出來，如此該tags相關性(經常可能被同時使用)就顯而易見，對使用者而言，該resource的結構也就不言而喻了。

想說去找看看這個idea有沒有人做了(在找之前其實就覺得這麼直覺的東西應該有人把它做出來了吧XD)，果然.. Elastic Tag Maps用Flash實作了這個想法，當你滑鼠移到tag cloud上的某一個tag時，它會將與該tag相關的tags同時link起來秀了出來。此外，它也把tag's frequency的histogram畫了出來，相關的tags被點擊後，histogram會同時動態秀出對應的分佈。我在想，del.icio.us的tag prediction或許是用類似的概念做出來的吧~

不過，我覺得這個Elastic Tag Maps還可以進一步改進，譬如說，根據user的興趣在tags加上不同的顏色或明暗度，如該tag是不是最近常被使用的熱門tags，或者根據不同主題將tags作分群(clustering)，又或者tags彼此間的相關程度等等。不過直覺跟我說這應該還是有人做過了XD。

Funny Videos to Introduce Social Network

你還不知道什麼是"Social Network"嗎？以下這兩個可愛的小短片，用最簡單的方式配合上生動的例子，為你介紹當紅的Social Network，並說明了Social Network隱含的價值(Value)。雖然並沒有講到它的精隨，但挺適合入門的人看喔！

Social networking in plain English

順便介紹dot Sub這個網站，它提供為影片加上字幕的服務，拿上面那個Social Network的例子，經dot Sub加工後，可以在下面看到。我覺得它可以拿來做聽力訓練或教學，彌補了YouTube多數影片沒有字幕的小缺點，挺適合我這種英聽超爛的人XD。

Tagging from System View

再來，整理一些關於目前網路上現有tagging應用的類別。大致上，tagging systems可以依據以下兩類來分析：(1)系統設計上的特色，以及(2)個人使用tag的動機與目的。此二者對於最後所有被annotated的tags可以傳達的意義、資訊如何在使用者間流動與互動、後來使用者tag的意願等都有舉足輕重的影響。這裡主要著重在系統設計上的一些介紹，從使用者的觀點下一篇再寫。

A. Tagging Rights
這或許是影響整個tagging system最大的部份，可再細分為三類：
self tagging: 使用者能夠tag他自己所製造的source，如Technorati。
free-for-all tagging: 任何人都可以tag任何source，如Yahoo! Podcasts。
permission-based tagging: 系統允許不同層級的tagging權限，如系統指定source給使用者tagging(如ESP Game)、使用者具體指明哪些人能夠做tagging(如Flickr: friends, family, contact distinctions)。相對地，系統也可以決定讓哪些人能刪除已標註的tags：任何人都可以刪除tags(如Odeo)，只有創造該tag的人能夠刪除它(如Last.fm)，或者只有source的擁有者能夠刪除(如Flickr)。
由此看來，selg tagging明顯是較能夠採集到更廣泛的tags，也就是同樣一個tag所代表的涵義可能會隨著下tag的人的族群或類型而不同。

B. Tagging Support
tagging的機制對整個tagging系統所呈現的行為也有影響很大。大致可分為三類：
blind tagging: 使用者無法看到其他人對相同source下了哪些tags，如del.icio.us。
viewable tagging: 針對同一source，使用者看得到已經被下過的tags，如Yahoo! Podcasts, mybloglog。不過，此種tagging方式將可能使特定的source被overweighting。
suggestive tagging: 使用這下tags時，系統會自動建議相關的tags，如Yahoo! MyWeb2.0, del.icio.us。
其中suggestive tagging的方式有助於使tagging system趨向於folksonomy，也就是協助整合(或收斂)針對特定source的tags usage。

Folksonomy「群眾分類法」是Thomas Vander Wal所創，由folks與taxonomy所組成，指個人運用自由定義關鍵字的協同分類，其形成通常必須滿足以下幾個特性:

a. 資料量龐大時: 在使用者沒有training任何依據來分類的情況下，下關鍵字或定義必定存在盲點或發生錯誤，但若資料量龐大且具重複性時，相同內容可能被許多不同關鍵字標註，其搜尋結果反而能趨近涵蓋各個面向。

b. 適用非學術/非精確/非嚴謹的領域: 若是特定的專門領域，肯定會存在許多相當嚴謹且精確的術語來對某一概念或事件做描述，但對普羅大眾而言這是難以達到的。

c. 配合indexing使用: 不管用哪一種index方法所做成的系統都得結合關鍵字，以達到關聯分析，譬如某些關鍵字與哪些關鍵字時常同時被標註，如此才能提供使用者較為完整的資訊。

其實社會科學領域早已對"Folk Classifications"(非專業人員如何進行分類)，做了相當程度的研究。可以參考Harold Conklin的《Folk Classification: A Topically Arranged Bibliography of Contemporary and Background References Through 1971》(1972, Amazon)。
而且Folksonomy與圖書資訊學中的「分面分類法」(Faceted Classification)是沒有直接關係的。

C. Aggregation
所指的是對同一source，其tags使用的重複性(multiplicity)，即是否允許不同使用者下相同的tags。
bag model: 允許不同使用者對特定source下相同的tags，如del.icio.us。
set model: 針對同一source，即使是不同使用者下tags，也不允許重複的tags出現，系統會自動將相同的tags識別為單一tags，或要求使用者不能下已標註的tags，如YouTube, Flickr。
對於使用bag model的tagging systems，必須要有能力以統計的方式將特定source、不同使用者集體下的tags呈現出來，如del.icio.us的popular link。甚至要進而能夠從這些被不同使用者下的相同tags中找出sources, tags, users間彼此的關係。

D. Type of Source
被tagged的source的類型也是tagging system所必須考量的，而廣泛來說，目前tagged source不外乎webpages(del.icio.us), bibliographic material(CiteULike), blog posts(Technorati, LiveJournal), images(Flickr, ESP Game), users(LiveJournal), Video(YouTube), audio objects such as songs(Last.fm), podcasts(Yahoo! Podcasts, Odeo), physical locations or events(Upcoming).
當然，針對不同類型的sources，被下的tags的用語與意義也就大不相同了，不過因此也衍生出multimodality correlation的研究議題，也就是能否針對同一tags名稱找出不同type的source彼此間的關係，譬如替multimedia analysis提供了許多現成的training data。

E. Source of Material
Source的來源是由誰來提供呢？是普羅users嗎(如Flickr, YouTube, Technorati, Upcoming)？還是系統提供呢(如ESP Game, Last.fm, Yahoo Podcasts)？甚至，來源是整個web的任何東西哩(如del.icio.us, Yahoo! MyWeb2.0)！

F. Resource Connectivity
在tagging system中sources彼此間是否存在隱含的關係呢？答案是肯定的。在此先不談理所當然地由tags建立起的sources的關係。Sources可以由直接的hyperlinks建立關聯(如webpage)、根據系統區分或使用者指定的group來串聯、藉由相同或接近的時間、地點、立場來建立事件的關連(如Upcoming)。這些不同關聯方式的背後隱含的是，相同關連下的sources，他們的tags很有可能類似，甚至相同，尤其在suggestive tagging與viewable的系統中。

G. Social Connectivity
上面講的關連是針對sources，那麼users彼此間的關係又如何呢？在有些提供social network service(SNS)的tagging system中，會根據使用者的興趣、所在地、教育背景、職業等等來協助建立彼此的關連、或以對稱(symmetric, know each other)或非對稱(asymmetric, A know B, B doesn't know A)的方式(如Flickr就未必是symmetric的)，讓使用者間有機會形成社群，或者說是localized folksonomies。

後記：挫賽... 明天要MMAI期中考，我竟然還在寫這個 = =+

Tag Visualization and TagOrbitals

Web2.0當紅，social tagging也是其中一環。在目前許多tagging system，一個source可以以一個以上的關鍵字來當作它的tag，也就是這個source可以從許多不同的面向來替它分類。然而，當我們的source種類很多、或者數量很大時，tag的數目隨之成長，甚至類別可能變得相當繁雜。Tag visualization的議題正是由此誕生的，目的是嘗試找出較為人性化的indexing呈現方式，協助個人化管理與搜尋。

傳統呈現關鍵字或類別的方式是階層式的(hierachical)，而web2.0打破這種固定結構化的呈現方式，轉為比較自由的形式。最廣為人知的標籤視覺化有兩種，一種是以graph，或者稱做network的方式，如下圖所示；

另一種是"TagCloud"(標籤雲)，Tag Cloud將使用者所標註的tag以特定的方式排序（通常為字母順序），同時每個tag會根據被使用的頻率而有字體大小的差別，如下圖所示。目前許多Social media網站都使用了Tag Cloud，如Technorati, Flickr, del.icio.us。使用Tag Cloud的好處是輕巧簡潔，然而，這種優點卻是犧牲了一些重要的資訊而換得的，也就是它忽略了tag與tag之間隱含的關係。

最近在survey關於tagging的研究時，發現了一種新的tag visualization方式—TagOrbitals。它是IBM Research的Bernard Kerr在SIGGRAPH 2006 Sketches提出來的。TagOrbitals與TagCloud的呈現概念背道而馳，它犧牲了簡潔輕巧來換取tags之間關係的資訊。TagOrbitals的視覺化呈現如下圖。

由上圖可以很清楚地看到它的結構，是將每個tag放在一個類似原子的中心（也就是原子核的位置），原子核的外面有許多能階軌道(obrits or bands)，跟中心tag相關的所有tags會依據和中心tag共同被標註的頻率來分配所在的軌道，共同出現的次數愈高，愈有可能被放在接近中心tag的軌道，如此便可看出那些tag較常被標註在同一群，tag在語意上的階層種類也一目了然。另一方面，被標註的source的title也同時秀在這個原子結構中，如下圖所示，title會被垂直地放在由內而外所屬的標籤旁，因此有哪些sources是被相同tags所標註的也就得知了。

最後，每一個tag都會有自己的原子結構，tag名稱放在原子中心，而各原子tag的名稱大小也根據出現次數多寡來決定，同時所有tags都是由左下角如泡泡般地生長出來的，如下圖所示。

The Wisdom of Crowds

The Wisdom of Crowds: Why the Many Are Smarter Than the Few and How Collective Wisdom Shapes Business, Economies, Societies and Nations 是 James Surowiecki 在 2004 所寫的，主要在探討是否三個臭皮匠能勝過一個諸葛亮，並告訴我們群體的決策思考是比一小群菁英還要正確聰明的，透過群眾的力量，更能蘊釀出創新，解決難題，甚至能準確地預測未來。我整理了以下構成群體智慧的四個重要元素。

1. Cognitive Diversity (多樣性)
Increases range of solutions, Reduces Groupthink

如果一個群體的成員全由菁英組成，即使成員來自各個領域，所做的決策很有可能侷限於他們類似的思考的模式，但若成員在思考層面較為多元，白話來說就是龍蛇混雜，如此群體思考的能見度與廣度將可大為提升，決策也較不容易有盲點，並能趨進各種情況都被涵蓋的程度。此外，多樣性能降低判斷中各種邏輯上出現謬誤的機率，增加正確資訊的選項。從另一個角度來看，一旦成員構成複雜，就較容易避免從眾的現象產生，任何人的想法都會受到挑戰，群體也就能激發出更多的創意了。

2. Independence (獨立性)
Relatively rare on current web, Reduces Groupthink

每個個體是否具有獨立思考的能力在群體智慧中扮演著關鍵的角色，最主要的原因是它能使錯誤不會綿延地在個體上發生，部分切斷了錯誤訊息傳遞關連性，因而群體的判斷不容易受到誤導。此外，獨立性具有另一種涵義：個體能夠保有演化資訊、產生新想法的能力。

舉兩個例子來說明或許會更容易理解。著名生物現象-蟻群的 circular mill 正是因欠缺獨立性導致群體危機的最佳例子。Circular mill 指的是螞蟻在找不到路時，會循著同伴所留下來的氣味前進，而不會去思考新方向。另一個是 1:100 vs. 1000:100000：一百個人裡面有一個人抬頭看天空，可能只有身旁的幾個人會受影響跟著抬頭；但十萬個人裡面有一千個人抬頭看時，雖然同為1:100，卻有可能大部分的人都受到影響。

若群體的成員純粹以旁人的行為作為自己決策的依據，當資訊流量超過某一 threshold 時，自己所有擁有的資訊將會很合理地被隱藏了，或者變得只接受來自外界的資訊。這就是缺乏群體智慧獨立性的一種典型。

3. Decentralization (分權化)
Better decision making

簡單來說，就是讓決策在最接近問題的地方形成，鼓勵竭盡局部知識做到專業化，或者根據週遭情況來做出最適切的反應，或者藉由自身過去經驗使得解決方案能最貼近問題的核心。最簡單的例子就是大型軟體設計的分工，設計流程的各個 components 分屬不同人員來負責。然而，此分權化的概念必須在群體內部具有一種能整合 (aggregation) 溝通各個子集資訊的管道或機制，才能做成一個較好的群體決策。

4. Easy Aggregation (整合機制)
Allows collective decision making

一種將個別資訊轉換成群體決策的機制。白話來說，就是「我覺得你會怎麼做（或者猜想你可能怎麼做），然後決定我怎樣做」的意境，也就是個體們透過內在的文化跟習俗、外在的規範法律或者該種群體的共通經驗等等默契，而自然的整合起來。例如公共場所人群的移動，看似各人按照自己的意識行走、毫無規則可循，但潛在的統合力使得群體能夠自然地找到移動的節奏與方向。排隊、先到先排也同樣是一個例子。

此外，James Surowiecki 提出了，五種造成群體智慧失敗的元素：

1. 同質性太高(Too homogenous)：群體組合愈多元，群體智慧愈能展現。
2. 核心性太強(Too centralized)：決策模式過度集中於金字塔頂，忽視下層意見。
3. 隔離性太大(Too divided)：群眾應該多元，但不能被隔離；隔離使意見無法自由交流。
4. 模仿性太高(Too imitative)：楬櫫少數意見，讓群眾不思考就模仿。
5. 情緒性太強(Too emotional)：情緒因素（例如：族群、宗教、階級等）都很容易造成同儕壓力、群體情緒失序等。

Bipartite Graph and Stable Marriage Problem

Bipartite graph 的定義，是一個 graph 中的所有 nodes，依據問題的性質分為兩類型的 disjoint set（即任一個 node 不可以同時出現在此二類 sets），並且 edges 只建立於此二 set 彼此間，而同一 set 中的 node 不會建立 edges。

以一個不太好的例子來說明。假定 bipartite graph 的兩類 nodes 為 human 與 event，edge 在某人參與此 event 時，會被建立。在此，human 包含男人與女人，event 則為 like（不同形式的喜歡，或好感），一個男人或女人可能同時喜歡多個異性（這是不好的..），那麼這個 graph 可表示如下圖左方（矩形代表喜歡或好感，圓形代表 human）。這樣的表示方式看起來似乎男女之間彼此沒有 edge 存在，但其實他們彼此的複雜關係是呈現在 event 的，如果我們將左邊的 bipartite graph 轉為右邊的 graph，男女的關係就顯而易見了。右邊 graph 的 edge 是在男女雙方相互喜歡時，才被建立。

其實，若要以 bipartite graph 來描述男女配對關係，比較合適的表示方式為，graph 的一邊是男人，另一邊是女人，每個男人或女人會有一個自己對於異性的喜歡程度列表（preference order list）（假定一般情況下，異性互相喜歡），因此 set 之內不會有連結，之間有連結。這種表示方式即為著名的穩定婚姻問題（Stable Marriage Problem，SMP）。SMP 問題的定義是，在上述的男女表示方式下，如何達到穩定（stable）也就是如何兼顧使得最多人能被配對到，並且都對配對的對方能有較高的喜歡程度（即在 preference order list 中排名較前面）。如下圖，右圖就是達到最大配對的結果。通常這種問題被轉為 Maximum-flow problem，並以 Ford-Fulkerson Algorithm 解之。

Types of Networks

一般來說，最簡單的網路（network, 這裡泛指所謂的 "graph"）是由一些 nodes 以 edges 相互連結所組成；然而，在許多關於 network 的研究議題上，對於 nework 的表示其實是比最初的型態還要複雜許多的。以下大略將 network 分為四種基本的型態，應用在許多領域或問題上的變化大多由此四類型所衍生的，如圖所示。

(a)
An Undirected network with only a single type of node and a single type of edge。傳統的 graph mining 欲解決的問題多為此類型的 network，最經典的論文為 Diane J. Cook 於 IEEE Intelligent Systems 2000 所發表的 Graph-based Data Mining。然而，目前所謂 Social Network 所著重的並非此類型，但許多傳統 graph 上的研究議題，如 graph classification, partition, motif discovery, subgraph discovery 等，卻重新被拿出來在 social network 上討論。

(b)
A network with multiple types of discrete nodes and multiple types of edges。也就是根據 domain knowledge 或者問題的定義，賦予 node 或 edge 各種不同的性質。以一個以人為主體的 social network 來說，nodes 表示的可以是男人或女人、不同國籍、居住地等，而 edge 可表示朋友、敵對、親人、學術、工作、或地理上的接近程度等。這是最常見的 social network 類型，也是 social network 根本的結構。

(c)
A network with varying weight of nodes and edges。直接舉例，node's weight 可以是一個人在 network 中的重要程度、收入、階級高低等；而 edge's weight 可以是兩個人有多熟、來往密切程度、居住距離、共同參與事件的次數等。

(d)
A directed network in which each edge has a direction。一個由 directed edges 所組成的 graph 通常被稱為 directed graph 或 digraph。最顯而易見的例子為 telephone calls, msn messages，訊息的交流是 "你來我往" 的。此外，digraph 允許存在 cycle，也就是連結許多 edge 可以形成一個具方向性的 loop，食物鏈（food web）就是最好的例子。

除了以上四種基本類型外，其他還有兩種比較有名的 network 表示方式：

hypergraph：簡單來說，它是由一種特殊的 edge（稱為 hyperedge）所組成，而 hyperedge 是指一個 edge 可連結 2 個以上的node，更準確地來說，n 個個體以某種關係相互連結，此時 edge 有 C(n,2) 個，但是用一個 hyperedge 就可以將這原本的 edges 都包含。hypergraph 較常用於生物資訊中，蛋白質與化學分子的關係表示上。hyperedge 的一個簡單的圖例。

bipartite graph：這就比較常見了。此種 graph 的 nodes 有兩種不同的類型，而 edge 只建立在不同類型的 nodes 之間。所謂的 "affiliation network" 正是此類型的一個代表，它指的是共同參與事件的關係，graph 的一種 node type 為 people，另一種 node type 為 events，共同參與某一事件的人都會與該事件的 node 建立連結，但這些人彼此間並沒有 edges 存在。

Eight Properties of Social Network (5~8)

5. Mixing Patterns
When we explored the networks to the details, one question was arisen: which nodes pair up with others? Recall in most networks, there exists a some different types of nodes, the probability of connection between nodes just have tight relation with the nodes' type. Take Internet as an example, the structure of the network reflects the existence of three broad categories of nodes: high-level connectivity providers who run the Internet backbone and trunk lines, consumers who are end users of Internet service, and ISPs who join the two. Again there are many links between end users and ISPs, while few between ISPs and other ISPs, or between backbone operators and end users.

In terms of social network, this kind of selective linking is called assortative mixing, or homophily. A typical example of assortative mixing in social networks is mixing by race. The following table can illustrate it, which is the results from study of 1958 couples in the city of San Francisco, California. We can observe that people prefer to choose their spouses from their own race. More examples can be raised, such as mixing by age, mixing by incoming, and mixing by culture. Hence, it could say that the association would be created preferentially from those with homogeneous characters.


6. Degree correlations
In addition to that the links could be connected depend on the types of nodes, the degree is also highly correlated with the mixing. Does high-degree nodes in a network often associate with other high-degree nodes? or to low-degree ones? Needless to say, assortative mixing by degree plays a important roles networks, especially for the consideration of graph topology. Degree correlation can give rise to some interesting network structure effects.

Newman investigated assortative mixing by degree by calculating the correlation coefficient of the degrees of nodes at each end of links, as shown the following tables. It could be observed that for so-called social network, it is positive for assortatively mixed network by degree, while for information networks, technological networks, and biological networks, it appears to be disassortative. However, it is not clear to explain the result.


7. Community Structure
It is widely observed that most social network show the property of community structure, which means that groups of nodes that have a high density of links within them, with a lower density of links between groups. It could be used to explain the phenomenon that people usually cluster by their interest, education, age, and so on. What follows illustrates the community structure by visualization of two examples: the first is the friendship network of children in a US school taken from a study by Moody, and the second is the science citation network taken from Eigenfactor.org. It is very obvious to see the effect of community.



8. Centrality
a) Degree centrality: nodes with high degree.
b) Closeness centrality: nodes that have low distance to all other nodes.
c) Betweenness centrality: nodes that occur on more shortest-paths.
It can be illustrated via the following picture.

Eight Properties of Social Network (1~4)

這幾天 survey 關於 social network 相關研究後，從 M. E. J. Newman 以及 Christos Faloutsos 的論文中歸納了以下八項 social network 或者說是 complex system 的特性（我用英文寫，感覺比較有學問 XD）：

Recently, during my survey for social network and complex system from papers of M. E. J. Newman, I think it could be briefly summed up to eight properties, as follows:

1. Network diameter
The diameter of a network is the length (edges) of the longest path between any two nodes. Generally, the diameter is small, like 6 of small-world phenomenon, and it is independent of network size. The small-world effect imply the dynamics of processes taking place on networks. e.g. fast spread of information for the network, like rumor. This effect also underlies some well-known parlor games, particularly the calculation of Erdős number and Bacon Number.

2. Network Transitivity or Clustering
The concept was derived from the behavior of random graph. The most comprehensible instance is that the friend of your friend is likely to be your friend. In terms of graph topology, transitivity means the presence of a heightened number of triangles in the network - sets of three nodes each of which is connected to each of the others. It can be measured through the definition of clustering coefficient C (with an example):


3. Degree distribution
The degree of a node in a network is the number of links connected to that node. We can define a probability pk to be the fraction of nodes in the network that have degree k. Meanwhile, the pk could be considered as an uniform probability for choosing nodes with degree k at random. Plot pk (vertical axis) with degree k (horizontal axis) for some networks can form a histogram of degree distribution of nodes, as follows.

It is observed that the degrees of nodes are highly right-skewed. In other words, the distribution has a long right tail, or heavy-tailed distribution, it might be the well-known long tail effect. Alternatively, this distribution can be plotted in a logarithmic method, as follows. Marvellously, it is nearly conformed with Power law, which is the primary property of scale-free network. In contrast to the Poisson distribution of random graph (Erdős-Rényi model).


4. Network resilience
The resilience of network means the removal of its nodes, which is related to the concept of degree distributions. The function and structure of a network usually rely on its connectivity. Once some nodes are removed, the length of paths could be increase, even the network becomes disconnected. However, there are a different ways to remove the nodes. One way to remove the nodes in a network is to random removal. This approach wouldn't affect the distances between nodes almost since most nodes in a network have low degree and therefore lie on few paths between others. The other way to remove nodes from networks is targeted at high-degree nodes. Needless to say, it will have tremendous effects on the structure of a network. And the distance would increase acutely with the fraction of nodes removed. The following picture can explan it! (Note blue for random removal and red for high-degree removal.)

M. E. J. Newman

我是在 NCCU Summer School on Computational Social Sciences 2007 上準教授 Martin Rosvall 的 Lecture 中得知這號人物的。這幾天拜讀了他的代表著作之一: The structure and function of complex networks，之後到 google 上搜尋他，才知道這個人不簡單！在複雜網路的研究領域中頗具貢獻。M. E. J. Newman 的網頁上是寫他叫做 Mark Newman，我也不知道為什麼許多論文上他都被稱為 "M. E. J. Newman" ...

Newman 是 University of Michigan 物理系的教授，同時是 University of Michigan 複雜系統研究中心（Center for Study of Complex System）的主要成員之一，這個研究中心是由學校中許多領域的教授所組成，目的在於從 nonlinear, dynamical, adaptive 的角度切入研究 complex system。更值得一提的是，Newman 竟然也是 Santa Fe Institute 的成員之一，可以他對於 complex system 具有相當程度的研究！

Newman 對複雜網路的研究主要著重於分析 network 的結構與功能，尤其針對 social network 與 information network，研究方式藉由結合經驗分析法（empirical analysis）與電腦模擬（computer simulation）。以下為他的代表著作 (都是跟該領域中其他大師級人物的coauthorship @@)：

• Random graphs with arbitrary degree distributions and their applications, M. E. J. Newman, S. H. Strogatz, and D. J. Watts, Phys. Rev. E 64, 026118 (2001).
• The structure and function of complex networks, M. E. J. Newman, SIAM Review 45, 167-256 (2003).
• The Structure and Dynamics of Networks, M. E. J. Newman, A.-L. Barabási, and D. J. Watts, Princeton University Press (2006).
• Identity and search in social networks, D. J. Watts, P. S. Dodds, and M. E. J. Newman, Science 296, 1302-1305 (2002).

Networks in The Real World

Complex network 研究之所以被發掘而且迅速地廣為被研究，最重要的時間點在 1998 年，Watts D. J. and Strogatz S. H. 在 Nature 雜誌上發表一篇名為 "Collective dynamics of 'small-world' networks" (Nature 393, 440-442)，該篇論文著重於分析複雜網路的特性，並嘗試將它以數學模型來解釋。

2003 年，Mark Newman 進一步將真實世界的 Complex network 歸納為四大類：
(M. E. J. Newman, The structure and function of complex networks, SIAM Review 2003)

1. Social Network
2. Information Network
3. Technological Network
4. Biological Network

[Social Network]
以人，或者由人所組成團體，為基本單位，藉由特定基本單位間各種互動關係建立彼此的連結，所形成的網路，稱之。典型的幾個例子：film actors, co-authorship, sexual contacts, email messages, blogosphere。Social Network 最為著名的體現是 Stanley Milgram 的 small-world experiments，得出世界上任何兩個人之間，至多存在五個人，便可建立關連，即"六度分離" (Six degree of separation)。在 Stanley Milgram 的實驗後，科學家發現傳統 social network analysis 的 sample size 都很小，加上資料來源可能受到人為主觀意識的影響，鑒於此，又時逢 WWW 迅速發展，因此資料來源轉為 affiliation network，也就是透過眾人的力量所組織成的 knowledge base。舉兩個social network的例子來說明：

Science coauthorship (Node: author; Link: write paper together)



Blogosphere (Node: blog (color means host); Link: (a-)reciprocal link (thickness)



[Information Network]
Also called "Knowledge Network"，典型的幾個例子為：citation network, WWW, word co-occurrence, preference network (bipartite graph)

World Wide Web (Node: webpage; Link: hyperlink)



[Technological Network]
Man-made networks designed for distribution of some commodities or resources. 典型的幾個例子為：Internet, power grid, train routes, P2P network, electronic circuits

Power grid (Node: generator, substations; Link: high-voltage power transmission lines [Note: Line thickness and color indicate the voltage level])



Internet (Node: computer, router; Link: physical lines)



[Biological Network]
Biological System，典型的幾個例子為：metabolic network, protein interactions, food web, neural network

Food web (Node: trophic species; Link: trophic interactions)



metabolic network, protein interactions