原文地址:http://geekplux.com/2019/07/27/network-data-visualization

Why - 图分析的价值

首先,图是最能描述世界的结构。几乎所有事物都能抽象成图。有一门学科叫作“复杂网络”是专门用图这种数据结构来研究世界规律的。图一直是炙手可热的研究方向,国内复杂网络的研究不仅热门,也颇有成就。在图分析领域,已经沉淀了很多分析方法、研究模式,我们光是把这些现成的算法筛选,进而应用到我们的业务中已经很有价值了,更别说我们可以根据我们的需求去拓展图分析的边界。

目前我能想到的一些场景:

  • 分析网络中的结构。哪些节点形成了“孤岛”,哪些节点的重要性、影响力巨大
  • 关键节点挖掘。关键节点就是那些能够在更大程度上影响网络的结构与功能的一些特殊节点。准确发掘出网络中的关键节点,可以帮助我们更好地控制信息的传播、精准投放商品广告、预测热门研究成果等等。
  • 链路分析,链路预测。分析用户跳转的路径,分析服务器、数据库请求的路径、故障分析。预测用户可能跳转的地方,行为预测,推荐系统。

具体的场景:

用户进入一个网站之后,不停的跳转,然后每个页面是一个节点,每次跳转是一条边。我能不能比较多个用户跳转图的相似性,先把他们分类,然后再比较他们的偏好不同。搞清楚用户到底是为什么点击到了这个产品,这个链路的特点是什么,等等。

计算 - 图数据结构类库

既然图可视化需求这么多,我觉得应该把数据作为核心,数据和视图分离,抽象出一个单独的模块用来维护、处理、计算图数据结构。比如基本的节点查找、路径查找、最小生成树算法等等。

这个库的作用只用来计算,输出统一结构的图数据,我们甚至可以将图数据定义标准化,这样在其他图可视化或应用到图数据结构的场景中就能通用。

类似的轮子已经有了,我所用过最强大的是 networkx https://github.com/networkx/networkx ,但它是一个 python 库。我调研了一下发现目前前端可用的库要不是太简单(只能加减数据,查找节点),要不就太复杂(https://github.com/fkling/JSNetworkX ,是 networkx 的 JS 版,功能很多)。

定义了标准化的数据结构之后,就能将库设计为插件化的,主体只实现基本算法,插件实现特殊需求算法。

目前我想到的一些计算:

  • 密度。图实际边数与最大可能边数的比例。可以根据密度将图分层、分组、筛选、区分出小世界网络。
  • 度。节点的度是很重要的指标,度又分很多种:平均度、最大度、中心度。中心度(中心性)即该图中最重要的节点。
  • 路径。平均路径长度,可以算出该图中,一个点到另一个点必须经过的平均边数,比如从一个页面到另一个页面必须跳转多少次
  • 群聚指数。用于聚类分析等。
  • 邻居。最近邻居、共同邻居、bring neighbours 等
  • 相似性计算、相似子图:wl kernel、edit distance、graphlet kernel、reducing snapshots to points、向量化等

布局 - 图可视化布局

  • 邻接矩阵
  • 节点链接图(Node-Link)
    • 力引导布局(Force-Layout)
    • 弧长链接图
    • 弦图(Chord)
    • 桑基图(Sankey)
  • 混合布局(变种)
    • 恒星图
    • 弦图变种
    • 矩阵与节点链接图结合
    • 与玫瑰图结合

交互 - 图交互与分析

交互是数据可视分析中必不可少的步骤。通过各种交互,我们可以探索数据的模式。

典型的几个交互:

  • 过滤(filter)
  • 分组(group),分层
  • 路径展示(关键节点、路径分析)
  • 缩放(zoom)
  • 拖动(pan + drag)
  • Overview + detail (缩略图)
  • Fish eye (鱼眼效果)
  • Brush (圈选)
  • 切换布局(如从矩阵切换到节点-链接图)
  • 导出子图