社群網路之訊息工程-子計畫六：動態社群網路之視覺與競爭性分析( I )

Abstract

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

In general, social network analysis includes three tasks: identify communities; identify central actors; analyze actors’ roles. Those tasks are capable of offering useful information to develop more social-aware approaches to social network problems and inspire a variety of applications for mobile networking. However, it is very hard to analyze real dynamic social networks because they dynamically evolve with node mobility and unstable links as the number of their users is changed, and the number of communities is typically unknown. As a result, this project will use visual analysis and competitive analysis to investigate dynamic social networks, respectively. The first year of this project will focus on visual analysis. To our understanding, previous visualization techniques for social networks focus only on the visualization of individual communities, without much concern about display of overlapping communities, central actors, and actors with special roles, which are very crucial in social network analysis. Hence, we will develop a social network visualization technique with the above concerns, and further take the network semantics and structures into account to design visual analysis algorithms for retrieving meaningful information for various possible applications of social networks. The second year of this project will focus on designing an online algorithm for the problem of detecting community structure in dynamic social networks. We will use the competitive analysis from theoretical computer science to derive the precise theoretical results of our online algorithm. By competitive analysis, a bound for the ratio of the online algorithm solutions from the optimal offline solutions can be derived from theoretical aspect. Our idea is to take the analogy from the online algorithms for clustered graphs to conduct a comprehensive competitive analysis and derive computational complexity of our online algorithm.