基于社团检测的大型网络可视化研究
Research on Large-Scale Complex Network Visualization Based on Community Detection
近年来,复杂网络研究受到了不同学科研究人员的广泛关注,其发展极大的促进了人们对现实复杂网络系统的理解.复杂网络研究者普遍认为网络中存在社团结构,即整个网络是由若干个群或团构成的,在同一个群内节点之间的连接非常紧密,而各个群之间的连接却比较稀疏.揭示网络中的社团结构对于了解网络结构及分析网络特性具有极为重要的意义.目前,虽然复杂网络可视化能以直观的方式表达网络节点之间的关系且已日渐成为复杂网络分析必不可少的工具,但是对于复杂网络社团结构的可视化工具特别是针对层次化重叠社团结构的可视化工具却较少.针对该问题,本文从复杂网络的社团结构出发,对网络中普遍存在的层次化重叠社团结构进行了深入的研究,侧重点在于基于社团检测的大型网络可视化方法.本文首先尝试对现行国内外常用的复杂网络可视化工具进行了总结.其次,本文探讨了网络社团的层次性及重叠性,针对真实网络的社团结构一般同时具有层次性及重叠性的事实,本文尝试将社团的层次性及重叠性同时进行研究并提出了一种适用于稀疏网络的快速层次化重叠社团检测算法.最后,基于对社团结构及现行复杂网络可视化工具的深入了解,本文在基于社团检测算法的基础上,提出了一种层次化社团划分与骑墙节点显示的可视化方法,并用Java开发出了一套应用于大型复杂网络的可视化平台Visualizationbased on Community Detection (VCD).本论文所作的主要贡献如下:1.对比分析了复杂网络可视化领域比较有代表性的工具,鉴于目前学术界并没有对复杂网络可视化给出一个统一的标准,本文引进了CIShell框架,并对网络可视化工具的使用及开发进行了总结;2.提出了一种适用于稀疏网络的快速层次化重叠社团检测算法,该算法循环的把网络中连接较为紧密的节点进行合并,聚集向上直至得到最优的模块度并将原始网络划分为若干具有层次性的社团.与一般的层次化社团检测算法不同,该算法在每一次迭代过程中允许节点归属于一个或多个社团以此发掘网络的重叠社团结构;3.提出了一种层次化社团划分与骑墙节点显示的可视化方法,该方法在使用基于模块度指标优化的社团划分算法检测层次化重叠社团结构的同时,通过节点及连边的关系分别对网络社团与骑墙节点进行抽象显示,避免了大型网络可视化研究中经常面临的节点与边的重叠堆积问题;4.本文的可视化平台综合采用了圆形布局与聚类布局,能模拟网络层次化社团结构及骑墙节点结构的动态演化,并将移动平台上使用甚广的Cover Flow技术应用于可视化中,提供用户不同的可视化效果,其中,基于层次化社团划分的可视化效果充分展示了社团间的关系,而基于骑墙节点检测的可视化效果充分展示了节点的多维社团属性.该平台还提供了丰富的交互功能,帮组用户从不同层面查看网络结构信息.
- 作者：
- 梁润鹏
- 学位授予单位：
- 上海交通大学
- 专业名称：
- 控制理论与控制工程
- 授予学位：
- 硕士
- 学位年度：
- 2012年
- 导师姓名：
- 汪小帆
- 中图分类号：
- O157.5；TP391.41
- 关键词：
- 可视化；复杂网络；社团；骑墙节点；层次化；重叠社团
- visualization； complex network； community； fence-sittingnodes； hierarchy； overlapping community