標題: 社群網路之訊息工程-子計畫六:動態社群網路之視覺與競爭性分析( I )
VI Sual and Competitive Analyses of Dynamic Social Networks( I )
作者: 林春成
Lin Chun-Cheng
國立交通大學工業工程與管理學系(所)
關鍵字: 社群網路分析;視覺分析;競爭性分析;群體偵測;資訊視覺化;圖形繪製;Social network analysis;visual analysis;competitive analysis;community
detection;information visualization;graph drawing
公開日期: 2012
摘要: 一般而言,社群網路分析包含三項任務:判斷群體、判斷中心行為者、及分析行為者
的角色。這些任務能提供有用的社群資訊來解決社群網路問題且引發許多行動網路的
應用。然而,因為社群網路會隨著使用者的改變而有節點行動性與鏈結不穩定性的動
態演變,且當中群體數目通常是未知的,所以實際的動態社群網路是相當難以分析的。
因此,本計畫規劃將分別用視覺分析與競爭性分析來研究動態社群網路。計畫第一年
將著重於視覺分析,就我們所知的,過去社群網路視覺化技術均只著重於個別群體的
視覺化,鮮少關心社群網路分析中重要的重疊體群、中心行為者、與扮演特殊角色行
為者的視覺化呈現。因此我們將開發同時包含上述考量之社群網路視覺化技術及其應
用,並進一步考慮網路語意與結構來設計視覺分析演算法,以取得社群網路的各種可
能應用的有用且有意義的資訊。計畫第二年將著重於設計動態社群網路中群體結構偵
測問題之線上演算法,並且使用理論計算機科學中的競爭性分析來推導線上演算法的
嚴謹的理論結果。藉由競爭性分析,可從理論層面來推導出線上演算法之解與最佳離
線演算法解的比率是有界的。我們的構想是去參考用在類似於社群網路的叢集圖形之
線上演算法來推導出我們的線上演算法的完整的競爭性分析與計算複雜度。
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.
官方說明文件#: NSC101-2219-E009-025
URI: http://hdl.handle.net/11536/98431
https://www.grb.gov.tw/search/planDetail?id=2581300&docId=388695
顯示於類別:研究計畫