社群網路之訊息工程-子計畫六:動態社群網路之視覺與競爭性分析( I )
摘要
一般而言,社群網路分析包含三項任務:判斷群體、判斷中心行為者、及分析行為者
的角色。這些任務能提供有用的社群資訊來解決社群網路問題且引發許多行動網路的
應用。然而,因為社群網路會隨著使用者的改變而有節點行動性與鏈結不穩定性的動
態演變,且當中群體數目通常是未知的,所以實際的動態社群網路是相當難以分析的。
因此,本計畫規劃將分別用視覺分析與競爭性分析來研究動態社群網路。計畫第一年
將著重於視覺分析,就我們所知的,過去社群網路視覺化技術均只著重於個別群體的
視覺化,鮮少關心社群網路分析中重要的重疊體群、中心行為者、與扮演特殊角色行
為者的視覺化呈現。因此我們將開發同時包含上述考量之社群網路視覺化技術及其應
用,並進一步考慮網路語意與結構來設計視覺分析演算法,以取得社群網路的各種可
能應用的有用且有意義的資訊。計畫第二年將著重於設計動態社群網路中群體結構偵
測問題之線上演算法,並且使用理論計算機科學中的競爭性分析來推導線上演算法的
嚴謹的理論結果。藉由競爭性分析,可從理論層面來推導出線上演算法之解與最佳離
線演算法解的比率是有界的。我們的構想是去參考用在類似於社群網路的叢集圖形之
線上演算法來推導出我們的線上演算法的完整的競爭性分析與計算複雜度。
的角色。這些任務能提供有用的社群資訊來解決社群網路問題且引發許多行動網路的
應用。然而,因為社群網路會隨著使用者的改變而有節點行動性與鏈結不穩定性的動
態演變,且當中群體數目通常是未知的,所以實際的動態社群網路是相當難以分析的。
因此,本計畫規劃將分別用視覺分析與競爭性分析來研究動態社群網路。計畫第一年
將著重於視覺分析,就我們所知的,過去社群網路視覺化技術均只著重於個別群體的
視覺化,鮮少關心社群網路分析中重要的重疊體群、中心行為者、與扮演特殊角色行
為者的視覺化呈現。因此我們將開發同時包含上述考量之社群網路視覺化技術及其應
用,並進一步考慮網路語意與結構來設計視覺分析演算法,以取得社群網路的各種可
能應用的有用且有意義的資訊。計畫第二年將著重於設計動態社群網路中群體結構偵
測問題之線上演算法,並且使用理論計算機科學中的競爭性分析來推導線上演算法的
嚴謹的理論結果。藉由競爭性分析,可從理論層面來推導出線上演算法之解與最佳離
線演算法解的比率是有界的。我們的構想是去參考用在類似於社群網路的叢集圖形之
線上演算法來推導出我們的線上演算法的完整的競爭性分析與計算複雜度。