PhD Life 週記2

許多事情接踵而至，尤其備課Social Network的內容，看了許多Physical Review的論文，多了一些sense，但也感到自己數學真的很差，數學底子的sense一點也沒有。自從上大學後，就不在與數學當朋友了，倒是與「感覺」跟比較熟，這樣研究是不容易做穩的吧！「書到用時方恨少」，深深感到線性代數與離散數學的重要性，該像唸英文一樣，一天補一點點了。

「慢慢來，比較快。」

東西扎實學，記得比較久；關係淡淡繫，得細水長流。仔細想想，對於一些人事物，或許我們會多繞了幾圈、多磨了幾下，但只要最終能找到自己真正的方向，放大到人生的尺度，這些其實算不了什麼。趁著熱情消退之前，或跑或衝或跳，可能有時會迷惘，縱使不留意地弄傷了，終究還是在那我們應該前往的路上..

然後，還想告訴自己，有時候別太在意眼前的得失而認為它就是一切，那些可能和自己真正想要的沒有什麼關連。為了小東西(?)計較或寢食難安、磨損了長期的鬥志，甚至迷了路，不值得。共勉之。

PhD Life週記1

週五晚上，隔壁寢室放著音樂，藉由隔音極差的牆壁穿透過來，雖然不知道是什麼曲子，但節奏明亮而輕快，不知為何心裡就跟著共鳴起來？這是住到水源宿舍以來第一次覺得隔壁的吵雜聲不是噪音。

「路漫漫其修遠兮，吾將上下而求索」

我想，是那踏實的節奏在扣人。開學對研究生來說，毫無感覺，特別是博士生吧，尤其待在同一間實驗室，沒有結束，只有繼續，或者說是一種看著夥伴們結束學生生涯，自己卻走向一條漫漫長路的對比，好像踏著和之前碩士生活一般的步調又不是，又尚未找到生活的節奏。所以，我嘗試著清空過去，放空現在的自己（到有點孤僻？）（連宿舍寢室都是空的XD），重新開始找尋屬於自己PhD之路所需具備的氣氛。但鄰居這一個星期來的吵雜聲，把空空的自己裝進的讓人敏感的噪音，不時繚繞... 從一開始覺得敲隔壁的門不好意思，到現在一聽到聲音就馬上過去問好了...

研究上，一開始倒沒什麼強烈的幹勁，就穩穩地把跟老闆提的idea做了做，希望特殊結構特徵之摘要這邊可以順利在這月底完成。另外，重拾幾篇論文來看，轉了轉僵掉的腦袋，看能不能激發一些特別的想法。

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

觀音山．硬漢嶺．占山連峰

開學前最後一個假日、爬雪山的前夕、有人不服輸XD，眾多因素之下，今天的爬山成行！而且是11個單身的人一起以爬山作為近日行程XD。每次前往大屯山及淡水地區，都會見到淡水河另一岸矗立著的觀音山之姿，想著將來有機會一定要站在它上面，俯瞰關渡平原以及台北盆地那令人嚮往的景色～然而今天天氣不甚理想，觀音山地區整個雲霧繚繞，讓人無法一賭絕佳展望... 不過倒是見識到了淡水八景之一－－沉吟低迴欲雨時之「觀音吐霧」奇景 :p 另外，占山連峰的傳統山徑也挺有趣的！上上下下可說是「小筆架連峰」~

從捷運關渡站搭乘紅22公車在龍形站下車，循龍形三街，轉頂寮一街，接田埔巷，經過一大片墓園，到觀音社區涼亭旁的占山登山口。一路上還好有熱心的阿伯阿姨們指點方向，沒有迷路 :p

霧鎖觀音山區啊~ 漫步於霧中，身形飄邈如神仙 XD

登山占山，什麼也沒看見 :( 原本這邊可以展望淡水河口的，相當可惜..

我們走傳統山徑來爬占山連峰，一路拉繩上下，比旁邊一連串階梯有趣多了~

大夥兒有說有笑，愜意而行~

越過占山前五峰後，今日重頭戲小峭壁！80度拉繩陡上20公尺，相當過癮呢！嘻笑聲中大家順利通過，Fish爬到一半還講起電話哩！:p

觀音山地圖。占山連峰告一段落了！轉入硬漢嶺「階梯」步道 :(

若隱若現的硬漢嶺步道，一路延續到山頂。

「硬漢嶺」牌樓：「走路要找難路走，挑擔要揀重擔挑；為學硬漢而來，為做硬漢而去。」今天大家都很有硬漢精神唷！

哈哈... 像不像在拍鬼片 XD

雖然沒能見到硬漢嶺上壯闊的眺望視野，但「觀音吐霧」別具一番風情～P.S. 關渡是台北盆地主要的缺口，為海陸風交會要衝，因此「隔江相望，山巔雲霧鬱蒸、聚散馳逐、變幻焦窮、蔚為奇觀」由此場景得名。

只好用這張圖也代替展望了 XD

硬漢碑前來個大合照～

冬末春初之際，山櫻花已然盛開！

坐擁恢弘山勢與遼闊視野的「開山凌雲寺」！

烘爐地．南勢角山

這幾天一路好天氣就要在今天暫告段落了，和幾個朋友兒相約中和烘爐地拜拜兼小爬，遠離塵囂透透氣，也感受難得的午後悠閒光景～

上烘爐地前這九彎十八拐還真特別，而且是之字形陡上。不時可見單車客奮力的爬坡，真替他們感到辛苦... 不知道他們騎的時候在想些什麼麼？

全台灣最大尊的土地公像~

通往南山福德宮的階梯上，大夥兒成一列擺出pose~

這裡有著相當棒的展望，中永和一帶今收眼底！

大家很開心！:)

下了南勢角山後，自動倒數合照~

這裡的視野更讚！台北市就這麼大~

山櫻綻放~