本文将讨论实现 3D 版本可探索 OpenGalaxy 的一些技术和算法细节，用于之后进一步优化的基础。

OpenGalaxy 回顾

在「加权 PageRank 下的 GitHub 全域项目活跃度分析」 和 「OpenRank 和 OpenGalaxy」两篇博客中，我介绍了关于构建 OpenGalaxy 的算法和一些可改进的方向，主要是记述了如何使用协作网络数据来评判一个开源项目的中心度以及聚类效果，关于算法方面还会有后续的文章进一步展开讨论。

但在可视化部分只是给出了 OpenGalaxy 2019 的结果，而没有具体说明如何实现大规模网络的可视化效果，以及在可视化层面可以进一步做出的改进。本文将就这部分进行讨论，并最终给出一些优化方向和进一步的工作。

回望过去一段时间的工作，对于开源数据的工作基本可以认为都是围绕 OpenGalaxy 展开的，大概包含了如下一些内容：

• 数据采集与结构化：这部分内容之前主要是 GitHub 全域日志数据的实时集成，现在已经非常稳定的在线上运行，可做到最多一天延迟的全域日志数据的持续集成。另外已经开始采集一些其他的数据，如制品库元数据等，关于数据采集部分的情况，可以通过 X-lab 数据采集服务大屏来进行监控和了解。
• 数学模型与图构建：这部分是基于采集到的数据做进一步的分析，通过构建数学模型、图模型的方式希望可以得到一些洞察，也是之前两篇博客的主要内容。
• 网络图可视化与交互：这部分是对于通过数学模型和图构建得到的结果进行进一步展示，使更多人可以更好的理解这些结果，之前主要是 OpenGalaxy 2019/2020 的这种静态二维展示方式。本文会对这部分做出更多的讨论。

Software Galaxies

在进入 OpenGalaxy 2019 的具体实现路径之前，先引入一个导致本文出现的重要项目，即 Software Galaxies。

该开源项目基于 GitHub 开发者 Anvaka 的研究工作展开，也是该项目名为 pm 的原因所在，即 Package manager，因此该项目的主要样例均为各语言包管理器的依赖关系网络，如 npm、PyPI 等等，其中作者为了展示其项目的渲染能力，同时也提供了一个 GitHub 用户社交网络示例，可在三维空间中实时渲染百万级节点。

事实上我一直希望可以以三维的方式展示可交互、可探索的 OpenGalaxy，否则只能像上图一样给出一个较宏观的效果，并且对于周边小项目群的探索也仅限于我本人的日常消遣，并没有办法让更多的人可以真正领会沉浸在开源星系中带来的震撼与愉悦，但受限于我本人前端和可视化方面的经验较少，一直也没有找到合适的项目可以做百万级节点的实时渲染，虽然知道 d3 等类库可以用于 WebGL 的渲染，但受限于技术能力，一直没有可行的方案。

感谢唐烨男同学的介绍了解到了这个开源项目，感到震撼的同时也意识到找到了一个非常适合用于展示开源世界数据的开源项目，因此展开了对于这个项目的一系列探索。

该开源项目群实现了一整套关于使用 Node 操作图数据并进行可视化的工具集，包括：

• ngraph.graph：作为底层的图数据结构，成为所有相关图项目的基础
• ngraph.tobinary, ngraph.tojson, ngraph.todot, ngraph.toprotobuf, ngraph.fromjson, ngraph.fromdot：用于对上述数据结构进行序列化和反序列的相关类库
• ngraph.forcelayout, ngraph.forcelayout3d, ngraph.offline.layout, ngraph.native：用于进行图可视化布局计算的类库，其中 offline 用于对较大的图进行离线运算，而 native 则为布局算法的 C++ 实现，用于超大规模图的布局计算
• pm：也就是 Software Galaxies 项目，作为示例展示各类的前端可视化项目

当然除了上述当我们使用 ngraph 相关项目会直接使用到的项目外，还有很多其他的依赖项目，包括：

• ngraph.quadtreehd, ngraph.quadtreehd3d：用于布局算法空间索引的四叉树与八叉树数据结构
• ngraph.centrality, ngraph.path, ngraph.louvain, ngraph.pagerank, ngraph.kruskal, ngraph.hits, ngraph.jaccard 等：各类图相关算法的实现
• ngraph.physics.*：用于图布局算法的物理模拟引擎
• ngraph.pixel, ngraph.fabric, ngraph.svg, unrender 等：用于进行 Web 图渲染的类库，可以进行大规模图的实时渲染

可以说，作者 Anvaka 通过对各个类库的深度解耦，实现了从图构建、图分析、图布局计算到图渲染的一整套工具集，并且对于不同类别的类库，开发者可以自己实现相关的接口并插入到整个系统中替换默认的实现，实现了高可配和灵活组合。

Force-Directed Graph

由于之前的 OpenGalaxy 直接使用了 Neo4j 做图的存储运算，故对 ngraph 系列的使用仅限于布局计算和渲染，故仅涉及了 graph, forcelayout3d, pm 等几个项目。

其中 forcelayout3d 为主要的布局运算项目，由 offline.layout 调用来离线计算三维布局。提到布局算法，ngraph 的布局算法为经典的 Force-Directed Graph 算法，即力引导布局算法。

力引导布局算法采用对图数据结构引入物理系统的力学模型的方式来计算图中节点的布局，主要引入的是库伦斥力和胡克弹力，并包含了一个阻尼衰减用于在拉动节点后节点可以快速复原。而对于我们在 OpenGalaxy 中使用无法拖拽的这种情况，就只需要考虑斥力和弹力。

库伦斥力

在力引导布局算法中，图中的每个节点被看做是带电粒子，那么点和点之间就会因为电荷而产生互斥的电磁力，且这种斥力的大小和点的距离满足库仑定律，即 $ |F|=k_e\frac{|{q_1}{q_2}|}{r^2} $，也就是说两个点的之间的斥力与他们所带的电荷数量成正比，与他们之间距离的平方成反比。

在通用的图模型中，可以人工指定每个点的“电荷数”，对于更通用的情况，一般会直接使用节点的度作为其“电荷数”，即度越大的节点会尽可能排斥其他度较大的节点。这也是 ngraph 中的实现方式，具体实现可参考 quadtreehd3d 的实现。该库使用八叉树对空间进行索引，从而可以形成 POI 检索，由于斥力会随距离增加而快速降低，所以对于距离较远的节点，在计算时可以忽略它们之间的斥力从而减少运算量，否则对于任意节点$ n $，都需要$ N - 1 $次斥力计算，对于算力是极大的消耗，通过每次计算时仅索引自己周围一定范围内的节点计算斥力，可以大幅节省算力。

在 OpenGalaxy 中，可以通过节点度或 PageRank 值作为节点的“电荷数”，对视觉呈现的影响并不大。

胡克弹力

斥力表达的是所有节点之间的排斥作用，而对于图中的边，则遵循胡克定律，即 $ F_s=kx $，也就是好比两个相邻的节点之间存在一个弹簧，弹簧的对两个节点的弹力（也就是引力）与两个节点之间的距离成正比，即节点距离越远，则他们之间的引力越大，且引力和距离是线性正比关系。

在通用的图模型中，也就是无权图中，一般认为边的长度是一个常数。但在加权图中，需要自己指定边长来覆盖默认的统一边长设置。

ngraph 实现

通过引入上述两种简单的物理定律，就可以快速计算一个图的空间布局了，可以是二维空间也可以是高维空间。

初始时对所有节点在 N 维空间中初始化一个随机位置，之后进行多次迭代计算。每次迭代时对于每个节点计算它与其他节点之间的斥力，然后遍历其所有邻接边，计算相关的弹力，最终将所有的力向量进行合并，计算本次迭代中该节点受到的合力大小和方向，就可以判断在下次迭代前该节点的位移情况。在多次迭代后，所有节点将进入一个平衡态，此时就得到了一个图布局。

Gephi & Force Atlas 2

在初始的 OpenGalaxy 2019 中，我使用了 Gephi 对图进行布局计算和渲染，最终的效果为二维平面布局。使用的算法为 Gephi 内置的 Force Atlas 2 布局算法，该算法下的总体布局效果较好，故也对该算法进行了一些深入探究，可参考相关论文，该算法为 Gephi 研发小组针对社交网络进行优化的算法。

Force Atlas 2 布局算法同样基于力引导布局算法，并在其基础上进行了一些优化，除了基于节点度的库伦斥力和胡克弹力外，还包括：

非线性弹力

在胡克弹力中，两相邻节点之间的引力与两节点之间的距离成正比，但在 Force Atlas 2 中，采用了 LinLog 算法对引力进行修正，即 $ F_s=log(1+x) $，也就是引力不与距离成正比，而是成对数关系，最终的图的局部聚集效果会更紧致。

重力

在传统的力引导布局算法中，没有重力，所以与大部分节点没有连接的节点会互相排斥到布局的边缘，所以 Force Atlas 2 增加了一个重力，即所有节点都受到图中心的一个引力影响，该引力会因为节点的质量大小而异，与节点的质量大小和节点与中心的距离成正比。该重力的影响，会使得图布局整体更加紧致，并且质量较大的节点会更靠近整个布局的中心位置。

以上是我认为对传统力引导布局算法主要改进点，事实上论文中还有很多其他的改进，有一些改进在 ngraph 的布局算法中也已经实现，故不再在这里列举赘述。

需关注的点

边权支持

ngraph 的布局算法在计算弹力时事实上支持了边权，但在其 ngraph.graph 的基本数据结构中却没有在接口层面支持，因此可通过强制类型转换置入边权。需要注意的是在 ngraph 中可用于布局计算的事实上不是边权（weight），而是边长（length），所以在置入 length 时需要处理一下，不要将权重直接置入，而应该是边权越大，则边长越小才对。

节点质量

在 ngraph 的布局计算中，节点的质量用于斥力计算，默认会使用节点度的 $ 1/3 + 1 $ 为节点的默认质量，即度越高的节点质量越高。如果需要自定义质量，例如在 OpenGalaxy 中用 PageRank 值作为节点质量，则需要在初始化物理模拟引擎时，通过 nodeMass 函数置入质量计算函数。

参数配置

从上述分析中可以看到，不同的力最终会形成一个合力，在每次迭代时对节点进行位置调整。所以即便采用了不同的模型，还是需要精细的调整不同力模型下的参数，因为这些力需要在同一个度量体系下合并使用。在默认的 ngraph 力引导布局计算中，默认的参数配置为：

1
2
3
4

springLength = 10;
springCoefficient = 0.8;
gravity = -12;
theta = 0.8;

即对于无权图，边长（springLength）默认为 10，胡克系数（springCoefficient）为 0.8，即弹力为常数 8。库伦系数（gravity）为 -12，默认节点质量为 $ 1 + \frac{dg(n)}{3} $，即对于度为 3 的点，其质量大小为 2，两个度为 3、距离为 4 的节点，其斥力为 -12。theta 为斥力优化参数，使用的是 Barnes Hut 模拟算法。

故若对于边长和节点质量进行自定义，则需要调整相关的系数，使得整体的力系统相对平衡，即斥力和引力在相对合理的区间，否则会导致图过于紧致或过于分散。

可视化参数

即便对布局算法和参数做出调整和优化，使其达到较合理的布局，但最终的可视化效果同样重要。因为布局算法仅确定了每个节点所在的位置，但最终渲染时除了位置外，还需要考虑节点的大小、颜色、材质、边的颜色等因素，对于整体视觉感受会有较大的影响。

即便在 OpenGalaxy 2019 中通过 WPR 计算了每个节点的中心度，但在最终可视化时，事实上对于节点的大小采用了非线性的样条曲线，效果为 PageRank 较小的节点尽量显示大小偏小，从而防止绝大多数长尾节点因大小偏大而导致整体的显示效果偏凌乱。而 PageRank 达到中等偏上后节点大小迅速变大，从而防止中上游的节点因大小偏小而使图中的大节点数量过少。这其实也是因为总体的分布满足幂律分布的原因，PageRank 值较大的节点数量远小于值较小的节点数量。

而对于颜色、材质、边的渲染等，可进一步根据个人喜好进行调整，从而得到一个比较好的体感效果。目前调整的体感效果如下图，后续还会持续进行调整和优化。