网络可视化在线视频

正式到 到我们网络可视化

首先我们认识的网络是什么

就是本来跟（李军）老师

我们合作都是做计算机网络

就是原来在（刘兵）老师的

这个实验室

这个比如说我们的一些个人机器

连到这个一些（01：20英文）

或者这个一些（英文）上去

最终连接

通过防护墙连接到外网

然后有路由器什么的

这是我们原来理解的计算机网络

然后我后代到微软实习

我跟那个（英文）做了一个

我们叫（英文）

提出一种结构很复杂

但是这种结构可能比这个

普通计算机网络复杂一些

都是这个数据中心之间的连接

这也是我们原来认识的网络

然后另外所谓的互联网自置系统

就是AS系统的网络

但是这个网络因为实在太大

所以只能画成这样

这个可能是我们原来认识的

在 比如说我们网络所

或者说我们新研院的

这个做网络的人

通常认识这种网络

OK 当然有更多的

我这儿不举例

但是实际上我们所说的

网络可视化

我现在在做的

更多的是这种叫

我们叫信息网络

当然为了表达和刚才

计算机网络的区别

我加了一个新型信息网络

实际上它不是特别新

做了很多年了

这种网络包括什么呢

最容易理解的社会网络

比如说我们用微信用微博

有好友关系

这个关注的关系

那这些形成一个网络

叫社会网络

那如果我是李开复

可能我网络就会变成这样

这就很多

这是更大的社会网络

另外看去年的时候

好像是去年吧

就是百度做了一个叫百度迁徙

然后这个新闻联播都报道了

就是中国人民

可能春节的时候都回家

一个迁移网络

但是美国迁徙网络

大概长这样

这是其中一个例子吧

然后迁移网络也是我们

所谓的信息网络一种

然后也是我们可视化的一个对象

另外文本网络

大家有没有想过文本

怎么形成网络

这是圣经的一个网络

当然一说就很简单

就是我们把这个《圣经》里的

每个词拿出来

然后我们看哪两个词

在一句话里面

然后这一句话里面加一个（边）

最后形成一个大网络

这是文本网络

当然我们也可以看

比如说（02：22英文）

就是用and连接的这种关系

是长什么样

然后用of连接的是什么样

通过这个谓语连接的是什么样

通过宾语连接的是什么

这个通过不同选择

可以得到文本网络

其中的不同的层面

另外在我们的这个个人脑部

甚至是全身

这个神经也是一个网络

所以这些

其实都是我们研究的目标

这个还有很多

有一个网站叫这个（02：47英文）

它这还是

这是一个2011年的时候（英文）

就是截图

当时就已经有777个项目在上面

后来它没有再更新了

他出了一本书

对 感兴趣大家可以去看一看

这个书卖的很便宜

我买了一本只有20多块钱

当然这本书实际上在讲

精选的这个777个项目里的一些

100多个项目吧

哪个项目有一些图片

都很好看

它这个所谓（英文）

意思是说复杂网络的一个可视化

我们来看一下这么多项目

艺术网络 生物网络 商业网络

计算机网络 食物网络

就是食物链

比如那个老虎吃什么山羊什么

这种网络

然后internet 当然了

然后知识网络

我们现在所谓的知识图谱

然后音乐网络

比如音乐家的网络

然后这些（政治）网络

这儿有很多很多

这个 这个列表会很长很长

所以我们想说的是

新型的信息网络

真是简直是无所不在

所以有些网络我们需要理解它

就更需要我们可视化的方法

去把这些网络能够很

有效的展示出来

看这些例子以后

我先想从回到原点

先说一下什么是网络数据

以及什么是网络数据可视化

当然这些网络数据可能

我的角度不是从我们

网络安全的角度来讲

而是从可视化角度讲

网络数据是什么

从可视化的角度来讲

网络数据非常简单

就有两个主要是两个元素

第一个元素是结点

英文是（04：33英文）

或者（英文）

结点表示的一些实体

我们这里举例

是一些社会网络里面

可以是一些用户

比如说（英文）

这个一个人就是一个点

第二个元素就是边

（英文）

所以这里用来表示关系的数据

在我们这个例子里

是（英文）有一个关联

实际上它可以是一个好友关联

它们互相认识

在微博上互相关注

或者是这个（英文）写了一个

（英文）这个（英文）转发了

也是一个关系

甚至是可以敌人关系

OK 然后这是网络数据

就是结点和边组成一个

大的一个

这是典型的社会网络

然后所谓网络可视化很简单

就是这儿就是网络可视化

这也是一个基本的网络可视化

然后网络可视化比较核心的

或者说经典可视化

网络可视化研究

都得研究的是

我们所谓的布局算法

也就是布局

如何把结点摆放到合适的位置

使得这个图好看

这就叫图布局算法

或者叫（英文）或者叫（英文）

所以实际上都在研究的

网络可视化里研究的

第一个是怎么把这个图布局好

长的好看

第二个是怎么把这个图

画的好看

然后去展示更多信息

然后我分开来讲

这个在过一下就是

刚才是一个基本的网络数据

都是（无像图）

可以邻接表和邻接矩阵来表示

虽然有的时候也是（有像图）

比如说这个微博里

我可以关注你

你不关注我就是有像图

然后我给你发短信

我给你发两条 你给我发一条

这就是有权图

有一个权重

我先演示一个这个例子

给大家一个直观的印象

这是一个基本的一个

网络可视化的一个应用

OK

这是最简单的一个

基本的网络可视化

这里表示的一个社会网络

这里面有一些可视的表达

比如说这个人

人的这个（填充）越深的

表示他连接的人越多

然后有些交互

比如我可以选定一个人

只看这个人的子网

然后可以有更多的交互

比如说这个我们讲（06：54英文）

然后（英文）

这是拖动

当然你也可以是人的拖动

还有可以是一些基本的过滤

比如说我只想看一些重要的人

我可以根据他的结点的度

这是结点连接的人数来过滤

这是最重要的人有这么多

OK

你还可以根据一些边来过滤

中间有一些交互

OK 这是最简单的

只是给大家一个直观的印象

什么是真正做出软件的

这个网络可视化

然后我通过流水

就是刚才的可视化流水线

大概介绍一下

网络可视化的流水线

首先第一个阶段是多数据源

也就是说我网络可视化

不光是抽取出来那些

比如说我们微博上的好友关系

这个图而已

它还可以包括

比如在传统数据库里存储的

比如说阿里巴巴存储的

这个某个用户他买了多少商品

他通过这些信息

可以给你推荐更多的商品

再比如说你发的微博

它是文档结合

以及其他的社交媒体数据

比如说你的一些（08：08英文）

然后一些时时的一些其他数据

这些数据

把它集成起来

我们叫多元异构的数据

把它进行获取 清洗和融合

最后得到这个结构化的一个

我们叫一个多维的

可能是动态的一个网络

这里面所谓这个多元（异构）

另外一个角度是说

你可以把比如说（08：33英文）

是一个职业关系的网络

和你的在这个朋友圈

比如微信朋友圈的网络

能够融合起来

这是另外一种异构的概念

OK

那到第二阶段

我们把这些网络融合起来

把它进行标准化存储

这是我举几个例子

这是我原来用到的一个

三角数据格式

这是（英文）

这是我用的最基本的

就是（英文）

它是讲这样

主要是三个表

是结点 边和属性

结点属性

这个是结点有很多

这个ID呀 什么这个其他的属性

然后边是有（英文）和（英文）

就是从哪个点到哪个点

它有 权重是多少

然后这个是一个（英文）表示

然后这个是（09：22）的表示

长成这样

（说回来）最简单的是

最轻量级可以用（英文）表示

表示成这样 对

意思是说

实际上是把这个多个数据源

可能是非结构化

也可能半结构化

也可能结构化的数据

把它融合起来

形成我们可以去

用来展示的一个数据基础

有一些标准的数据格式

第三个这很简单

就是通过映射

这是其中一种

就是映射成那个结点边的

一种形式

这是所谓的可视化元素

是一些边和结点

然后最后一步示意图是

我通过把刚才得到的边和结点

怎么给它画出来

这个最核心的是

怎么找一个合适的布局

它布局不仅仅是长的好看

我们这里还有不同的布局的一个

或者叫流派

或者叫这个方法

比如这个是基于（树状）布局

就是如果数据一棵树

我可以把它按照一个

典型的树型结构来表现

然后如果它是

比如说我们视图来布这个电路图

我们就有一些要求

是它一个直角

就是直角交叉的

我们叫（10：28英文）

然后如果是我希望展示

比方它一个转发关系

我希望用一个辐射状的

从中心向四周散发的

一个树状辐射状布局

再比如说我不想用这个结点边

我用一种（英文）

这是这个邻接矩阵的表示

当然你还可以用更多

我这里演示一个挺有意思

它就是不光是

它可以把这个结点边

和这个矩阵表示结合起来

这个没有声音

这是原始的结点边的表示

它可以通过选择

选择一些结点

把它变成一个矩阵

它所谓选择的规律是

如果尽量比较密的

我们叫（11：06英文）的

这个…

它可以用一个（英文）来表示

然后这个（英文）之间

也可以通过边来连接

所以这是一个

我们叫（英文）

就是一个混杂的一个展示形式

OK 这只是给大家一个概念

就不展示很多了

那么我们回到一个PPT

最终我们这个视图是要给人看的

人我刚才讲到可视化

一定是（英文）

就是说人不光看一个视图

他也可以通过切换一些视角

可以看到这个网络的

不同的结构

不同位置的结构

尤其是网络很大的时候

我这里还要展示一个

不是水平的一个交互展示

OK

这是一个我们叫双曲线浏览器

可以 像在一个球上转动似的

然后这个数据首先是

（IBM）的年代了

所以这个数据也没什么意思

因为很小

如果我们看IBM的产品

它就更大一些

这有三大产品线

然后产品线下面还有子产品线

对 然后可以通过一个

这个我们叫双曲线浏览器

在球面上的一个旋转

推动这个交互手段来看到

更大的一个网络结构

当然这个还不算大

这个是最终这个

（12：20英文）是

实际（IBM）是员工的一个页面

这实际上展示的

员工的一个管理结构

比如这个实际上管理结构

又非常深

OK

所以这是通过交互

能够看到很大的一个网络

这个网络虽然是

我还在公司时候的一个数据

它有两万多人

然后你在每一个视图

可能只看到几百个

但是你可以通过一些（英文）

就是每一级的一些管理人员

你可以看到下一级

像这样你可以找到每一个人

然后每一个人附近的结构

OK

这是非常经典的一个展示

OK 好 就到这儿

刚才大概总结了一下

整个网络可视化的流水线

从多数据源到结构化数据

再到可视结构的一个元素的

一个设计

以及最终的展示出来的视图

以及用户如何跟视图去交互

用来做分析

那下面我涉及到

更深入一点的内容就是

刚刚讲到网络可视化核心是

如何把这个布局做好

就是什么样的

画什么样的图

就是把哪个结点放在哪儿

这就显然很核心的一个事儿

当然这个图布局的算法

早在三四十年前已经开始研究

可以说到现在已经基本完善了

所以我们大概有一套理论

来说怎么布局是好的

然后我们告诉大家

这个布局是好的

这个布局是差的

所以大家肯定是认可的我觉得

是不是认可

如果喜欢这种布局的可能是

适合去做艺术

OK 就是我们做工程

可能更喜欢看这种

比较简洁明快的布局

OK

但是为什么这个好 这个差

我们又做（14：01）

一定要寻求一些标准

然后能够判断哪个好哪个差

否认我们没法去设计算法

对吧

所以这里确实经过这么多研究

已经有很稳定的

公认的一些判别标准

当然最核心的标准是这个

就是我们叫边交叉数目

叫（英文）

我这里这个PPT

介绍一个实验的结果

用来说明为什么边交叉的结果对于布局的好坏有影响

它的实验是这么做的

就是首先找一些用户

然后我再做三组图

三组图数据是一样的

但是我画的结果不一样

就是这个图它的交叉

就是边的交叉会少

这个图边交叉多一些

这个图就非常交叉根本看不懂

然后让用户去做一些实验

就是我告诉你

哪两个点

问你这个两个点

是否有连接

然后让你找A点到B点的一个路径

然后看你的结果是否正确

我把这个正确率画在一张图上

最后发现这个红线是

用户平均在这三个不同的图上的

正确率的一个变化

可以看到随着这个边交叉

越来越多

用户的错误率是直线上升的

所以通过用户实验证明了

而且做了大量的实验

更多的边交叉会导致

用户完成图分析的任务

出现更多错误

所以像公认的边交叉是这个

影响图布局质量的一个

首要的标准

OK 当然第二个标准

第二 第三还有很多标准

我现在只讲 再讲一个吧

第二个是所谓的边的曲折性

或者叫直线性（15：50英文）

也是做类似的实验

第一个图长成这样

这一边基本都是直线的

OK

第二个图

A到B它可以不是直接画过来

它可以是有一个拐弯

第三个图它不但拐弯

而且拐了好几个弯

还拐了很多钝角弯

OK 做相同的实验后来发现

用户在从基本直线

这个图到少量曲线

或者折线图的时候

我的错误率还没有上升特别多

但是会上升一点

但是一旦你这个边的这个曲折性

折了好多弯以后

我这个分析的结果

或者我做任务的错误率上升很快

所以我很容易理解

因为人看这个线的时候

尤其看连接的时候

是（16：37英文）

是直线就看过去的

你有一个弯可能我还能转过来

你有好几个弯

可能我就看的非常慢

OK 所以这个结果也是容易理解的

所以刚才那两个标准

是我们最终想布局得到效果

就是首先我们能布局这个图

让它不交叉

边不交叉

再一个我这个边

也尽量能画成直线

基于这个目的有很多算法

在最早可能60年前

都是手工画图

是手工画的

但是你看有很多交叉

虽然是直线

但是因为人一般喜欢画直线

但是很难看懂 对吧

后面有一个开拓性进展是

1963年的时候五十年前了

终于有一个计算机算法

当然现在不用了

我不会仔细讲

后来终于分成两个流派

一个是叫基于（17：27英文）的

一个普及算法

一个基于（力导向）

但是这个

这块布局算法是最近常用的

那我会分别稍微介绍一下

所谓重心算法

这个大家感兴趣

也可以看这个PPT

我们可能有的网上

可以再学一学

但是实际上这个50年前用的

我们也不用仔细学

这是我直观说一下什么意思

很简单就是

我现在图里找几个点

我给定它的位置

比如一二三四五六

四五六七八

然后其它点

在它连接的这些点里头

平均重点把它放在这儿

然后不断迭代就好了

所以这很简单

虽然很简单

但是它是第一个算法

OK 后面两个流派

第一个流派是

是一个基本理论化的流派

它是基于这个叫（英文）

这个我很难翻译

所以我就没有翻译

这是什么意思

所以（英文）是说

如果一个图我画的完全没有交叉

它就叫（英文）

然后这个图就具有（英文）属性

所以基于（英文）的普及算法

基本它是首要准则是

最小化边交叉

对 当然这也涉及一个理论问题

是我怎么能测试一个图

到底能不能画成不交叉

而现在自由算法可以做到线性

然后当然有一个简单的算法

就是如果你这个图里存在K5

就是一个五个点全连接的图

或者一个三个点两两全连接的图

那你一定会存在交叉

也就是说存在这种子图

也就是一定是（18：59英文）

然后再区分一个概念是说

（英文）就是说

（英文）可以画成不交叉的图

但是（英文）是说

这是（英文）

就是可以画成不交叉

而且我画成了不交叉

就是（英文）

但是如果我可以画成不交叉

我故意画成交叉了

那就叫（英文）

当然这个有点绕

我就是大概提一下

当然对于这个它的理论

还是蛮重要的

然后我不会具体讲它的算法

因为这些算法又都非常复杂

但是现在也用的很少

因为它不够

扩展性不好

这种算法一般都根据

你数的一些类型

比如这是树状结构我怎么去做

然后层次状我怎么去做

然后如果我需要布局成正交

我怎么做

这是基于（英文）算法的

一些分支

但是现在当然它也有其他标准

比如说我尽量把这个

这个弯曲度我刚才说了

图画成对称的

一般这种对称

OK 这是实线边

比这个弯曲边会好

然后对称图一般认为

比这个不对称图好看

另外这个边的交

如果说 这是边交叉和角

就是我会尽量把这个角度

让它连接角度

让它最大化

也就是说尽量使得很钝角

而不是很尖锐的连接

OK 但是有的时候很难去优化

所有图布局

所以基于（20：25英文）的算法

扩展性比较差

最新的最近20年吧

在商业软件

或者说可视化会议上

用到的布局算法

基本都是机遇力导向的

或者我们叫（英文）

力导向布局算法非常容易理解

实际上就是我不具体讲模型

只给大家一个 一个直观概念

就是说一个图

可以想象成一个系统

系统是由小球和弹簧组成的

这个点就是球

边就是弹簧

然后弹簧

每个弹簧有个圆长

这个圆长可以根据

你想让这个两个点距离有多大来决定

然后你把它摆在一个任意位置

弹簧都安好

然后把它在一个真空条件下

往那儿一扔

然后它会不断振动

达到一个平衡

虽然没有理论证明

但是经过多年的实践

这种达到的平衡状态

一般是在对称性和交叉性上

都是相当好的

我们可以大致有一个

这个直观的概念

说你想 弹簧嘛它不断弹

尽量使得这个弹簧不交叉

对吧

但是这个没有理论

特别多的理论证明

然后力导向模型也分两类

这里就不细解释了

就是一个是原有的弹簧电荷模型

再一个是基于图理论距离

用最优化理论去解的一个

我们叫MDS的一个模型

或者叫（21：53英文）

以及（英文）

然后这个我就不具体讲了

因为都是涉及算法

然后更多的就是

现在要布局很大的图

所以抽10的5次方结点

这些图的复杂度 都是n平方

它会用一些优化算法

比如多尺度和多层的算法

这是算法的

感兴趣也可以来看这个PPT了

这个也是模型

最近都是用一个M

叫MDS的一个数学方法来解

然后只想提一点就是

网络可视化在可视化里非常重要

是信息可视化基本一个核心的

题目之一

为什么这么说

有人做过统计

在这是我们的一个可视化的

三大会议

信息可视化

这个欧洲可视化

和（亚太）可视化

这里的论文20%以上

都用到了图布局算法

也就是说五分之一的论文

都跟这个有关系

这是改进的力导向模型

在大图上的应用的结果

当然感兴趣的同学

可以查一些论文

这是一些不用力导向模型

用刚才讲的

（23：00英文）的方法

得到这些其他的布局结果

好 这是还有人尝试用

基于力导向模型来布局地铁图

当然这个

后来我跟这个作者聊过

这个基本是（英文）

就是用这个力导向模型

想画成这样的图很难

刚才讲的是

基本是比较算法

就是怎么去布局图

它有什么限制条件

想达到什么效果

用什么算法

然后第二个也蛮重要的是说

我把结点位置画好了

我怎么表达信息

当然首先结点位置

首先就是一个信息

表达的（23：35英文）

但是结点上也有很多信息

可以通过什么手段来表达

当然这也非常简单

我们看可以通过各种可视通道

所谓可视通道结点

结点也可以有形状

比如圆圈用代表学生

方块代表老师

然后可以有这个颜色

可以有这个大小

可以表示重要不重要

然后边可以用

边的方向边的颜色

以及边的 我们叫（24：01英文）

就是它的粗度

或者更多的可以用这个

我们叫（英文）

就是来表示方向

就是同时用粗度

就不用箭头来表示它的方向

然后举个例子

最典型的数据网络

我这里面可以用结点

这个人来表示用户

这个人之间的边

用来表现对外关系

然后可以用结点（填充）

用来表示谁重要

然后用边的粗细

来表示人之间的联系的密切度

同时我可以用一些高级的

一些我们叫（隐域）

就是可以用一些填充

或者叫阴影轮廓线

用来表示社区

这是一个典型的

我布局好了图以后

网络以后怎么去展示

展示更多信息

然后你也可以不用图

这是一个结点边的图

这是一个矩阵

基于邻接矩阵的一个展示

当然还可以用

这个信息可视化很著名的

一个叫（24：56英文）

就是（英文）发明的

它是把一棵树画成一个

面积填充的一个形式

是有点像（英文）

先切横的 再切竖的

用来表示这个树状结构

然后这里面不光用这个

横切竖切来表示树状结构

一个（英文）

同时也可以用这里的颜色

以及内容来表示

它的更多信息

比如（考虑）这可以是淘宝

所有的分类的一个

销售的一个情况

然后可以是 这是股市行情

用这个绿表示

美国是绿表示涨 红比较跌

跟中国反着

所以这也是一个很混杂

可能这个涨的很好

这是不同块是不同的分区吧

或者这么说

我也不炒股不太懂

然后这可能看到这个图

心情很好都涨了

然后这个就是股栽了

就只有这个涨

然后这一个（树图）

然后树图我可以

也可以画成从中心往外辐射

它可能

我们叫有两种

一个（25：57英文）

这个叫（英文）

类似的这种方法