标题: 社群网路之讯息工程-子计画六:动态社群网路之视觉与竞争性分析( 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
显示于类别:Research Plans