复杂网络可视化方法研究

VIP免费

3.0 侯斌 2024-11-19 4 4 1.98MB 47 页 15积分

侵权投诉

摘要

随着复杂网络的小世界特征和无标度特征被揭示，人们对复杂网络的研究日

益深入，如何直观地有效地认识复杂网络的结构，辅助人们挖掘复杂网络中隐藏

的信息，一个很好的方法是将复杂网络可视化。复杂网络可视化的基础是关系图

的可视化及其相关作图算法，但无论是经典的基于能量系统模型的作图算法还是

基于数值优化工具的图可视化方法，在处理大规模网络时都会面临性能和可阅读

性的问题。本文提出了一种多层次聚类抽象的网络可视化方法，该方法适用于大

规模关系图、复杂网络的可视化。

本文全面地综述了图的可视化方法以及复杂网络可视化的相关技术和思想，

在这些理论方法和思想的基础上，本文完成了这些工作：

（1）定义了“边强度”，提出了基于“边强度”的分裂算法，该算法用于

对大规模网络的聚类分析；

（2）根据复杂网络中“社团网络”的结构特征，量化了社团结构，定义了

“社团网络”的两个重要属性，用于对网络分割质量的评价；

（3）在（1）和（2）的理论基础上，提出了网络分割算法；

（4）提出了一种“多级抽象”的思想来降低大规模网络的可视化规模，该

过程尽可能地保留原始网络的关键属性；

（5）最后本文应用经典的“力导引”模型作图算法对不同抽象层次的网络

可视化呈现，并提供交互性视图，用户可以自由地浏览整个网络或局部细节。

关键词：可视化复杂网络可视化画图算法社团发现网络抽象

ABSTRACT

The reveal of characteristics of small world and scale-free in complex network increase

the deeper research on complex network. A better manner to understand the structure of

complex network obviously and effectively so as to help to mine the hidden information

behind the network is to visualize complex network. The base of visualization of

complex network is graph visualization and its corresponding graph drawing algorithms.

However, neither energy system model based classical graph drawing algorithm nor

optimization based graph visualization technique can overcome the bottleneck of

performance and readability when process large-scale graphs. This paper proposes a

new technique called hierarchical clustering and abstraction visualization of network.

This technique is able to visualize large-scale graph or complex network.

This paper thoroughly researches into graph visualization techniques and both

technologies and thoughts on visualization of complex network. Based on these theory,

methods and thoughts, those related work was done:

(1) We define Edge Strength and propose a divisive algorithm based on Edge

Strength. This algorithm is applied to clustering analysis of large-scale network.

(2) According to the characteristics of community structure in complex network, we

quantitate the community structure and define two important properties of

community network, which is used to evaluate the quality of network

partitioning.

(3) A network partitioning algorithm is proposed based on the (1) and (2).

(4) We propose a method called hierarchical abstraction to decrease the scale of

large-scale network. This process will keep the key properties of the original

network.

(5) We apply the classical force-directed graph drawing algorithm to visualize

graphs on different abstraction level. Interactive view is provided which allow

users to navigate freely through whole network or local details.

Key Word: Visualization, Visualization of Complex Network, Graph

Drawing Algorithm, Community discovering, Network Abstraction

中文摘要

ABSTRACT

第一章绪论 .......................................................... 1

§1.1 复杂网络及其可视化 ........................................... 1

§1.2 国内外研究现状 ............................................... 2

§1.3 本文相关研究 ................................................. 4

第二章图的可视化及其算法 ............................................5

§2.1 图的可视化问题 ............................................... 5

§2.2 经典布局算法 ................................................. 6

§2.2.1 “弹性模型”算法 ......................................... 6

§2.2.2 “力导引”算法 ........................................... 8

§2.3 约束优化作图算法 ............................................ 10

§2.3.1 模拟退火算法作图 ........................................ 10

§2.3.2 遗传算法作图 ............................................ 11

第三章复杂网络可视化技术 ...........................................14

§3.1 图分层 ...................................................... 14

§3.2 网络聚类与分割 .............................................. 15

§3.2.1 层次聚类 ................................................ 15

§3.2.2 图形分割算法 ............................................ 18

§3.3 多尺度缩放 .................................................. 20

§3.4 网络可视化工具 .............................................. 21

§3.4.1 通用型 API 类库 .......................................... 21

§3.4.2 网络可视化工具 .......................................... 22

§3.4.3 可视化网络分析工具 ...................................... 23

第四章多级聚类抽象的复杂网络可视化 .................................24

§4.1 网络结构描述 ................................................ 25

§4.2 边强度 ...................................................... 25

§4.3 社团网络 .................................................... 27

§4.3.1 社团网络结构量化 ........................................ 27

§4.3.2 社团网络属性 ............................................ 28

§4.4 网络分割 .................................................... 29

§4.5 多级抽象 .................................................... 29

§4.5.1 孤立节点过滤 ............................................ 29

§4.5.2 网络抽象 ................................................ 30

§4.4 可视化算法 .................................................. 30

§4.5 交互视图 .................................................... 32

第五章应用与展望 ...................................................35

§5.1 网络可视化应用 .............................................. 35

§5.1.1 可视化信息检索 .......................................... 35

§5.1.2 可视化网络拓扑 .......................................... 37

§5.1.3 社会关系网络可视化 ...................................... 38

§5.1.4 其他领域的应用 .......................................... 39

§5.2 总结与进一步研究 ............................................ 39

参考文献 ............................................................ 41

在读期间公开发表的论文 ..............................................44

致谢 ................................................................ 45

第一章绪论

§1.1 复杂网络及其可视化

近年来，随着计算机数据处理和运算能力的飞速发展，研究人员通过对 web

网络、社会关系网络、生物网络等的研究中发现，大量的真实网络既不是规则网

络，也不是随机网络，但是这些网络都具有某些共同的特征：（1）整体稀疏，

局部密集，低平均最短路径；（2）顶点度数服从幂率分布。1998 年Watts 和

Strogatz 在Nature 上发表题为《“小世界”网络的集体动力学》（Collective

Dynamics of ‘Small World’ Networks）的文章[1]，揭示了复杂网络的小世界（Small

World）特征，小世界网络既具有与规则网络类似的聚类特征，又具有与随机网

络类似的较小平均路径长度。1999 年Barabasi 和Albert 在Science 上发表了题为

《随机网络中标度的涌现》（Emergency of Scaling in Random Networks）的文章

[2]，提出许多实际复杂网络的连接度分布具有幂率形式，揭示了复杂网络的无标

度特征，同时具有小世界特征和无标度特征的网络被称为复杂网络。

数据可视化（Data Visualization）是利用计算机图形学和图像处理技术，将

数据转化为图形或者图像呈现出来，并可以进行交互操作[3]。数据可视化是可视

化技术在非空间数据领域的应用，它改变了传统的通过关系数据来观察和分析数

据信息的方式，使得人们能够更直观地看到数据及其结构，发现数据中的信息。

复杂网络可视化是利用数据可视化技术，将复杂网络中的关系数据转化为图形呈

现出来。复杂网络可视化一方面通过直观的图形帮助人们认识网络的内部结构，

另一方面还可以帮助挖掘隐藏在网络内部的有价值的信息。

人们对大规模关系图可视化的研究，尤其是对大规模复杂网络可视化的研究

才刚刚开始，随着对复杂网络研究的兴起，复杂网络可视化技术有着重要的研究

价值和广泛的应用前景，作为信息可视化的一个重要分支，复杂网络可视化的研

究从 20 世纪 90 年代中期开始，在 Graph Drawing，InfoVis (IEEE Symposium on

Information Visualization )，IV (International Conference on Information Visualization)

等重要国际会议中都成为一个备受关注的议题，引起了各国学者的高度重视[4]。

在大规模关系图可视化之前，人们对一般有向图或无向图的可视化的研究已

经有了相当长的历史，期间产生了很多优秀的平面图作图算法。传统的二维平面

图作图算法又称为布点算法，其中最著名的算法是由 P.Eades 提出的“弹性模型

（Spring-Embedded Model）”算法[5]，之后很多学者基于这个模型进行算法优

化，产生了一些这个分支下的类似算法。随着关系图规模的不断增大，特别是具

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

摘要随着复杂网络的小世界特征和无标度特征被揭示，人们对复杂网络的研究日益深入，如何直观地有效地认识复杂网络的结构，辅助人们挖掘复杂网络中隐藏的信息，一个很好的方法是将复杂网络可视化。复杂网络可视化的基础是关系图的可视化及其相关作图算法，但无论是经典的基于能量系统模型的作图算法还是基于数值优化工具的图可视化方法，在处理大规模网络时都会面临性能和可阅读性的问题。本文提出了一种多层次聚类抽象的网络可视化方法，该方法适用于大规模关系图、复杂网络的可视化。本文全面地综述了图的可视化方法以及复杂网络可视化的相关技术和思想，在这些理论方法和思想的基础上，本文完成了这些工作：（1）定义了“边强度”，提出了基于...

展开>> 收起<<

复杂网络可视化方法研究.pdf

共47页,预览5页

还剩页未读，继续阅读

复杂网络可视化方法研究

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: