可视化不确定网络的概率图布局方法

简介:

 

不确定网络,在本文表示顶点是确定的(certain),边的存在与否满足某种概率分布的网络。在图1中,左图是确定网络(certain graph),右图是不确定网络(uncertain graph)。

在不确定网络可视分析中,现有的方法往往直接在确定图(exact graph)中用视觉变量(visual variables)表示不确定信息。这些方法可以很好的将图的拓扑结构展示出来,但忽略了不确定信息的概率分布情况。

在这篇文章[1],作者们提出一个概率图(probabilistic graph)布局方法。这个方法可以同时展示图的拓扑结构和不确定信息的概率分布。它的基本思想是,依据蒙特卡洛方法(Monte Carlo process)对不确定图进行采样;将采样获得图根据力导向算法进行布局;之后,将所有采样图的力导向布局组合起来,获得最后概率图的布局(如图2所示)。

图1 左图是确定图;右图是不确定图

图2 文章提出的概率图布局方法流程图

文章分析的数据可以用G = (V, E, F)表示,其中V表示顶点集合。顶点是确定的元素;E表示边集合。边的存在与否满足F表示的概率密度函数。

在采样阶段,采用随机采样方法。

在力导向布局阶段,他们采用图3公式优化图布局。其中dij表示顶点i和顶点j之间的理想距离;wij表示边被选取的概率。

图3 力导向算法优化函数

在组合阶段,目标是将所有采样图的力导向布局整合成一个布局。文章提出的方法是构建一个参考布局(reference layout),然后将所有的采样图根据图4公式,重新布局。

图4 根据参考布局,重新布局的优化函数

在文中,参考布局一般是期望图(expected graph)。在期望图中,边的权重是该边概率分布的期望值。

在可视化阶段,为了更好的将每个顶点的位置分布情况和整体的图结构展示出来,他们对最后计算得到的整合布局进行了一系列的处理。

首先,他们对图中的顶点进行了滚雪球(splatting)处理。这样处理的目的是为了更好的将相同顶点的可能位置展示出来。在实际处理中,他们采用核密度估计函数计算每个顶点位置的概率密度分布函数,然后用ray-casting的方法,将顶点的位置分布展现出来(图5)。在核密度估计函数中,带宽h的值对结果的影响很大。图6展示了在不同h的情况,获取的结果。从左至右,布局从欠平滑状态过渡到过平滑状态。文章作者认为欠平滑的布局更利于用户进一步的分析,因为欠平滑的布局可以清晰展现顶点和边的关系。

图5

左图每个方块表示每个顶点位置的概率密度分布;右图是在左图基础上进行ray-casting后得到的布局

图6 从左至右,布局从欠平滑状态过渡到过平滑状态

接着,他们对最后计算得到的整合图中的边进行了处理。为了更好的描述边的分布和图的拓扑结构,他们对图中的边进行了层次聚类;接着采用贝赛尔曲线表示这些边,并采用滚雪球的方法对边进行可视化(图7)。

图7 左图,直接用直线展示边的布局;右图,对边进行一系列处理后的布局

最后,他们采用Welsh-Powell方法对图中的顶点进行着色。因为同个顶点的位置分布可能因为一些异常值,导致在空间上不能聚集在一起。为了帮助用户快速的识别同个顶点的位置分布,他们对图中的顶点进行了聚类处理。针对每个聚类,他们计算了群簇的边缘,并将表示同个顶点的群簇通过图8的方法,连接起来。

图8 对顶点进行聚类,添加边缘的结果

根据轮廓之间的空缺方向,用户可以将属于同个顶点的群簇链接起来。

接下来,我将介绍两个实例,验证这个方法的可用性。

第一个例子使用的是人造数据。在这个数据中,有五个顶点,8条边。每条边的概率分布如图9(c)第一行所示。图9(a)表示的是这个人造数据的期望图。我们可以发现,这个布局可以清晰的展示图的拓扑结构,但不能将边的不确定信息展示出来;图9(b)表示的是通过文章的方法计算得到的布局。

它清晰的展现了图的拓扑结构和顶点的位置分布;图9(c)表示的是边的统计信息。每一列表示一条边,第一行表示边存在与否的概率分布,第二行表示采样获得的边的概率分布,第三行表示边的欧拉距离分布。我们可以发现,同一列的三个分布都非常的相似。这说明,足够的采样是可以逼近真实概率分布的;也说明他们的方法可以很好的将图拓扑结构展现出来。

图9 (a)期望图;(b)根据文章的方法得到的布局;(c)边的统计信息分布图

在第二个例子中,他们尝试用这个方法分析城市之间的行程时间。该例子分析了8个城市之间的行程时间。在构图上,他们将每个城市看作顶点,在可到达的城市之间建立边。边的权重表示行程时间。为获取城市之间的行程时间,他们通过Google Direction API随机获取不同时间段,任意两个连接的城市之间的行程时间,并通过直方图处理,获取城市之间行程时间的概率分布图(如图10(a)所示)。

接着,他们根据不同的参考布局,得到了不同的概率图布局。图10(b)和(c)展示的布局,在其参考布局中,顶点的位置是不确定的,但顶点之间的理想距离是相应城市之间的真实距离。图10(d)和(e)展示的布局,在其参考布局中,顶点的位置就是相应城市的地理位置。我们可以发现,这两类参考布局得到的最后布局非常的相似,它们似乎只是旋转了不同的角度。

图10 (a)城市之间行程时间的概率分布图;(b)(c)和(d)(e)是两种参考布局得到的概率图布局

总的来说,这篇文章提出了一个新颖的不确定网络的可视化方法。他们的方法可以清晰的展现图的拓扑结构和图中不确定信息的概率分布。


本文作者:Lijing Lin

来源:51CTO

相关文章
|
9天前
|
弹性计算 安全 关系型数据库
带你读《从基础到应用云上安全航行指南》——来上课!一文掌握守住ECS网络安全的最佳方法(1)
带你读《从基础到应用云上安全航行指南》——来上课!一文掌握守住ECS网络安全的最佳方法(1)
142 0
|
9天前
|
弹性计算 运维 安全
带你读《从基础到应用云上安全航行指南》——来上课!一文掌握守住ECS网络安全的最佳方法(2)
带你读《从基础到应用云上安全航行指南》——来上课!一文掌握守住ECS网络安全的最佳方法(2)
30 2
|
9天前
|
云安全 弹性计算 监控
带你读《从基础到应用云上安全航行指南》——来上课!一文掌握守住ECS网络安全的最佳方法(3)
带你读《从基础到应用云上安全航行指南》——来上课!一文掌握守住ECS网络安全的最佳方法(3)
33 0
|
2月前
|
供应链 安全 网络协议
网络安全的行业黑话 ——攻击篇 之攻击方法(2)
网络安全的行业黑话 ——攻击篇 之攻击方法(2)
43 0
|
2月前
|
SQL 安全 网络安全
网络安全的行业黑话 ——攻击篇 之攻击方法
网络安全的行业黑话 ——攻击篇 之攻击方法
57 0
|
2月前
|
弹性计算 运维 监控
来上课!一文掌握守住ECS网络安全的最佳方法
本文整理自【弹性计算技术公开课——ECS安全季】系列课程中,阿里云弹性计算技术专家刘明带来了《如何守住ECS的第一道防线——网络安全》一节。
|
2月前
|
网络协议 网络架构 Windows
局域网网络故障判断常用方法
网络基础培训,整理了如下局域网常用的判断故障的方法,供大家参考学习。
84 2
|
2月前
|
网络协议 网络安全 区块链
常见网络延迟测量方法
常见网络延迟测量方法
179 0
|
2月前
|
搜索推荐 数据可视化 5G
从《三体》中的“降维打击”看网络世界,论维度升级的方法与实践
刘慈欣的《三体》为人们拉开一副天马行空的科幻画卷。在地球人类文明和三体文明的信息交流、生死搏杀历程中,“黑暗森林”推动星球文明间的关系发展,也通过一个毁灭性武器--二向箔,“降维打击”终结了人类文明。 在商业的暗黑森林中,无论是商业帝国还是创业公司,都面临着被“降维打击”的潜在风险,而防御风险的最高效模式,是通过维度的增值来引导发展,真正实现“发展+转型”,在业务主航道上拓展出新的领域。随着新领域,新方向、新业务的不断拓展,企业底层的ICT核心架构也需要随之升级增维,此时企业们该如何抓住破局关键呢?
|
2月前
|
机器学习/深度学习 自然语言处理 算法
【论文精读】COLING 2022 -带有对偶关系图注意力网络的事件检测模型
【论文精读】COLING 2022 -带有对偶关系图注意力网络的事件检测模型

热门文章

最新文章