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分析上使用。

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

Principles of Information Visualization

關於Information Visualization，資訊視覺化設計，最高指導原則是Ben Shneiderman於1996年IEEE Symposium on Visual Languages所提出的"Visual Information Seeking Mantra": Overview first, zoom and filter, then details-on-demand.

1. Overview

如同讀論文，一開始必須先對資訊的輪廓有概括性的體認，這適應於各種資料型別，包含1-d,2-d,3-d,temporal,tree,network views。Overview的呈現通常會搭配局部輔助detail view，主要有兩種：一種是透過可移動式field-of-view box，透過bar control或overall sub-image selection，讓使用者能觀察特定範圍，或將對應的地方highlight起來，如下圖。

另一種是著名的Fisheye strategy(經常被用於network browsing)，畫面是秀出整體或局部的，而滑鼠如同放大鏡的效果，移動到哪裡(或觸發特定事件後)，該區域就放大，如下圖。

2. Zoom

針對使用者感興趣的區域(Region of Interest)或項目，系統必須提供一些方便瀏覽的功能，當使用者觸發感應區時，將該部分所在的位置(position)以及與鄰近地帶(context)的狀態一併呈現，可以搭配zoombar調整該區域之大小或時間範圍等等。

3. Filter

當資訊過量(information overload)時，系統自動將使用者不感興趣的項目過濾掉，在information visualization領域中，專門的術語叫做"dynamic query"，換句話說，當使用者與系統做關於呈現內容的互動時，系統要能夠即時依據使用者的設定來動態變化panel。因此，如何針對系統的目的來設計這些可過濾容的項目，是系統開發者必須先想好的。可以透過sliders, buttons, 或其他不同control widgets來達到。其實search也算是某種的filtering。

4. Details-on-demand

使用者選擇特定項目或群組(entity)後，系統必須將與該項目自身相關的資訊秀出來，當然，可以善用圖表等統計的方式當作個人資訊的分析與呈現。在網頁上，最常見的方式就是以一個pop-up window列出相關屬性了，在軟體上，通常也會透過HTML將資訊格式化秀出，如Spotfire。

5. Relate

除了individual entity本身，entities彼此間個關係(relationship)也是資訊視覺化重要的一環。當使用者點選details-on-demand window中特定屬性時，系統同時將相關(or共同興趣)的entities列出或在視覺化呈現上highlight起來，並顯示關聯強度。關於這個項目，在data mining領域興起後，一直是information visualization研究中重要的一支。

6. History

視覺化系統設計中，與一般文字或影像編輯軟體一樣，紀錄使用者操作過的動作，提供UNDO, REDO, 以及progressive refinement的功能是必備的，以允許使用者重新trace瀏覽出感興趣內容的過程。然而，這部份是目前大部分具Graphical User Interfaces(GUI)編寫的程式語言所沒有提供的？

7. Extract

當使用者透過某些動作或query找到或產生出自己想要的內容後，若能提供把這些視覺化資訊儲存成檔案、列印出來、甚至轉為其他常用軟體input的格式的功能，對使用者將是一大福音，而且最好是能夠提供客製化output的control widget。

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)逐層以同系列的視覺化效果顯示，而使用者可以調整想秀出幾層。如下圖。

Projects Week

在實驗室通宵達旦了兩天，爆肝了一個禮拜，這學期的Projects Week終於過去啦！雖然後續要完成的項目還不少，但至少這週末可以稍微喘口氣了！:D

先是MMAI，完全從無到有四天達成XD，雖然效果目前不是很好，但從動機到雛形大致像個樣子，也有不錯的理論基礎與方法support，讓presentation不流於太嘴砲XD。至於MD，趨勢分析支撐著我們理論的部份，然後用小小的DEMO轉移聽眾的注意力(下圖)，掩飾另一個還沒完成的部份XD。值得一提的是，MD present時，或許是東西稍微有趣，難得地讓台下聽眾笑了，那種感覺真是不錯:p

無論是MMAI或MD，大家的創意或DEMO真讓人大開眼界啊！同時也發現，拿tag來bridge semantic gap似乎是個流行趨勢，而建構在Flickr上也有好多有趣的應用議題。MMAI印象最深刻的一組是PISAR(Progressive Image Search and Recommendation system)，有興趣的可以進去玩玩看。MD的話，Janet和Evelyn的個人化tag推薦，以及某組利用language model分析新聞來預測股市都挺具新意的~

聽過MMAI和MD的project present，最大的心得是：研究所與以前大學做project最大的不同在於以前著重技術的訓練，如何才做得出來，做的東西早就已經有人做過；現在則偏重研究導向，如何思考出有趣、有潛力的議題，一些假設前提、理論根據，著重方法與架構的設計，此外，要有contribution，如何評估，實驗要準確、合理、禁得起挑戰，做的可能是沒有人做過的東西。

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

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)：情緒因素（例如：族群、宗教、階級等）都很容易造成同儕壓力、群體情緒失序等。

Present and Read Papers

昨天去聽了李家同教授的演講，題目是"How to Perform a Good Presentation of a Paper and How to Read Difficult Papers"，雖然大部分 MK 都強調過好多次，不過我還是將演講的重點簡單摘要一下：

How to Perform a Good Presentation?

1. Always remember that no term can be mentioned without first defining it.

2. The definition of any term must be precise (嚴謹,精準). And the definition has to be accurate (正確).

3. Once a term is defined, this definition must be strictly followed.

4. Every statement must be precise.

5. Once a term is defined and mentioned, it must be mentioned later. If it is not used later, why should we have defined it in the first place?

6. The presentation must be smooth. Suppose you are now talking about subject A. Then you start talking about subject B while these two subjects are totally unrelated. This is not good. Something must be wrong. There are two possibilities. The first possibility is that something between A and B should be talked about. But you missed it. The second possibility is that B should not be presented after A at all. A good presentation is just opposite to a good detective story. (A good detective story always keeps the reader puzzled.)

7. Tell the whole story from the very beginning. In other words, give the top view of the paper first and give the technical details later. The worst case is to introduce individual trees before introducing the structure of the forest.

How to Read Difficult Papers?

1. Given a paper to read, we should always try to get the top view before getting into the technical details. If you fail to see the whole forest, knowing individual trees would never help you.

2. If this paper is an improvement of some old techniques and you do not know these old techniques. Give up this paper at once and go to read the old papers.

3. Never miss any critical point.

4. Never pay too much attention to abstract definitions. You must understand the physical meaning of these definitions. You must try to figure out why the researcher defined these terms. The worst case is that you learn advanced topics by rote learning. That is, you simply remember some terms without knowing what they really mean.

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 存在。

Music Search Engine - Musipedia

Musipedia - 一個以 midi 為主的音樂搜尋引擎。(簡體中文版)

Musicpedia 主要是搜尋它自已的資料庫，不過也可以對整個 web 做搜尋！它的搜尋技術平台是用 Alexa search platform。如果印象中有段旋律，但卻不是明確地記得是哪首音樂或歌的話，可以拿它來嘗試找看看。它提供了四種搜尋方式:

鍵盤輸入搜尋 (Keyboard search)
在上面的鍵盤一個一個音按好之後搜尋即可，網頁下方有使用方法

弦律輪廓搜尋 (contour search)
這部份它是使用一種叫做 Parsons Code 來當 Melodic Contours。簡單來講，就是利用連續音的起伏，當下個音比現在這個音還變高時，就 encode 成 U, 變低則為 D, 不變則為 R，當然，每首音樂的第一個音若拿來編碼，可能造成不準確，因此，在 Parsons Code 中，第一個音以星號 * 來表示。

哼唱搜尋 (Sing or Whistle)
可直接用錄音的, 或者要唱還是吹口哨都可以。

節奏搜尋 (Rhythm search)
按下 Start Tapping 後，就可以利用鍵盤敲出節奏來搜尋。

比較值得一提的是關於它如何比對 midi 的相似度，主要使用 Editing distance 與 Earth Mover's Distance。

Musipedia 的前身是 Melodyhound，由 Rainer Typke 從 1997 年開始規劃建置的，直到 Wikipedia 出現後，2006 年時，這個音樂搜尋引擎才改名為 Musipedia，並且也開始能夠搜尋 WWW 上的 midi 音樂。Melodyhound 目前還是可以使用的。

Color Harmonization

日常生活中，我們對於環境的感知時常是透過顏色來傳達的，雖然顏色可能會因為心境變化、不同文化而給人不同的感覺，但不同顏色彼此交織形成的和諧感通常對人們來說是一致的。所謂的和諧顏色（harmonic colors）指的是，在特定顏色的組合下，使人類視覺感官產生美感上愉悅的狀態。

在 ACM SIGGRAPH 2006 上，有一篇以 computer science 的角度來分析顏色和諧性的論文：Color Harmonization。它將顏色以色環（color wheel）表示，並在 color wheel 上歸納定義了八種類型的和諧（harmonic template），如下圖所示，其中灰色區域即為形成和諧的關連顏色，在和諧顏色彼此間的角度不變下，旋轉色環可得的各種和諧顏色的組合：

同時，作者定義了一個能夠將影像在 HSV color space 上，考慮 hue 維度以及 color histogram 上的距離關係，mapping 至 harmonic templates 的方法，並應用至視覺設計的配色上，可將原本的影像作和諧化處理、指定部分區域和諧化、harmonize by example，像網頁配色、衣服配色、室內設計配色等，都能有不錯的效果。它舉了幾個結果：

看過這篇論文後，我也在網路上搜尋看是不是已經有其他相關的應用，找到了以下幾個根據和諧性來配色的網站：

Adobe Kuler：Adobe 做的，提供各種不同風格的和諧配色，同時提供使用者自行根據不同 harmonic template 來進行配合，並推薦一些受歡迎的搭配。

I Like Your Colors：給定一個網址，它能夠幫你分析該網頁所採用的配色，可以用它來觀察一些配色不錯的網站。

COLOURlovers：挺棒的色彩分享網站，可以看到目前顏色流行的趨勢，大家推薦哪些不錯的配色，有做 ranking，並對不同的組合做有趣的評論。同時提供不同檔案類型的 color palette 下載的服務。

Color Palette Generator：使用者可上傳圖片，它會幫你分析該圖片所採用的配色，很適合用來做以照片為主的網頁配色設計。

Color Schemer：提供一些配色的色表，並有線上色彩選擇的功能，不過跟上面幾個比起來算是比較陽春的。

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.)

Christos Faloutsos

接下來介紹的這一位教授 Christos Faloutsos 算很久以前就知道了，不過一直都沒有詳細地去了解他的研究，只知道他在 multimedia 相關會議中發表過許多論文，直到最近在看一篇有關 social network mining 論文: Graph Mining: Laws, Generators, and Algorithms, ACM Comupting Surveys (CSUR), 2006，驚訝地發現他是其中一位作者...

Christos Faloutsos 是 Carnegie Mellon University Dept. of Computer Science 的教授，研究興趣主攻 data mining，尤其是 graph mining，可以說是 graph mining 的大師，應用在 Knowledge Discovery, Multimedia mining, Bioinformatcis, Social Network Analysis 等等。我就拜讀過他和他的博士班學生 Jia Yu (Tim) Pan 在 ACM SIGKDD 2004 年發表的論文: Automatic Multimedia Cross-modal Correlation Discovery，以及幾篇由這篇所延伸應用的論文，他們提出一種新的 graph - Mixed Media graph, MMG，並利用 random walk with restart 的方式探勘 multi-modal correlations。

值得一提的是，他是 ACM SIGKDD, SIGMOD conference, IEEE ICDM, PAKDD 的"非常"常客，看他今年 (2007) 竟然一次上了四篇 SIGKDD，實在嚇人（註：ACM SIGKDD 和 ACM SIGMOD 是 data mining 與 database management 領域中最頂尖的會議），此外，他也有好幾篇論文投上 ACM Multimedia，並在今年 ACM SIGGRAPH 2007 上受邀 Tutorials（註：ACM Multimedia 是多媒體領域中最頂尖的會議，ACM SIGGRAPH 是 graphics 電腦圖學與互動式技術最最最頂級的會議!），同時也是 SIGKDD, SIGMOD, MM 等。我個人覺得，未來幾年內，他應該很有機會拿到 ACM 或 IEEE Fellow。