数据挖掘 - 算法或 JS 图形绘制库，可以生成 100,000+ 个节点和边的图形，同时最大限度地减少边交叉 - 吾爱随笔录

我正在尝试绘制节点和边的有向图（但不仅仅是一个循环）。最终，我需要能够共享交互式图表（缩放、平移、标签）。 $2^{16}$ $2^{16}$

Mathematica 以最小化边缘交叉的方式绘制了这个图：

您看到的是大量节点（蓝色）混合在一起，完全隐藏了所有边缘。这不是一个可行的解决方案，因为它 (1) 需要安装 Mathematica，(2) 需要几分钟才能生成，并且 (3) 无法保存 - 导出绘图时 SVG 崩溃了我尝试过的所有 SVG 查看器。

SigmaJS 具有随机初始位置，然后是 ForceAtlas2

似乎对于大型图形，使用 HTML5 Canvas 进行渲染是可行的方法，而SigmaJS是一种流行的选择。

SigmaJS 的第一个问题是它不会像 Mathematica 那样自动放置节点。因此，要应用任何力导向绘图算法，首先我必须为所有节点提供初始位置。

将 65,536 个节点随机分散在一个正方形中会造成如此绝望的边缘缠结，即使在运行 ForceAtlas2 几分钟后，我也只能看到：

SigmaJS 与环相邻放置，然后是 ForceAtlas2

嗯，没什么大不了的。我决定进行简单的深度优先搜索，而不是随机放置，并在找到节点时将它们放置在一个环中。这样，大多数节点将紧邻邻居开始。以下是 ForceAtlas2 在开始时、几分钟后、一小时后和几个小时后的演变情况：

但这使得力导向图形算法的结果在很大程度上取决于它们的初始状态非常明显。我可以看到每个径向“岛屿”都陷入局部最优，从未达到 Mathematica 所做的配置。

关于这个特定的图表，并研究 Mathematica 的算法

我正在研究的图表是形式的伪随机数生成器

x_{n e x t} = 5 x_{c u r r e n t} + 273 mod 65536

$x_{next} = 5x_{current}+273 \bmod 65536$

在大多数情况下。（实际汇编代码实现中的一个怪癖实际上会导致 65536 条边中的约 700 条边按 1 移位。）换句话说，我正在绘制的是由该公式生成的“随机”数字的连续性，例如

0 \to 273 \to 1365 \to 7098 \to 35763 \to 48016 \to \dots

$0 \rightarrow 273 \rightarrow 1365 \rightarrow 7098 \rightarrow 35763 \rightarrow 48016 \rightarrow \ldots$

最终，这种连续产生了一个我们已经看到的数字，关闭了循环并形成了该图的 3 个循环之一。我知道这并不是关于数据科学或“大数据”，但我正在寻找的技术肯定是为这些应用程序开发的，并且该解决方案将有助于可视化类似的大型、稀疏连接的图。

为了看看 Mathematica 做了什么，首先我只为前 1000 个整数绘制了一个连续的图，即

\begin{aligned} 0 & \to 273 \\ 1 & \to 279 \\ 2 & \to 285 \\ \dots \\ 999 & \to 5268 \end{aligned}

$\begin{align}0 &\rightarrow 273\\1 &\rightarrow 279\\2 &\rightarrow 285\\ &\ldots \\999 &\rightarrow 5268\end{align}$

（由于前面提到的怪癖，有一些 3 和 4 长度的链。）对于 10,000 个整数，这里是相同的：

显然，Mathematica 以某种顺序组织子图与每个子图的大小有关。

“生命”开始形成大约 40,000 个节点，并且随着边在不同的中点连接子图以产生越来越有趣的形状，我们会向我们开始的图收敛：

那么：是否有可以执行此操作的 Javascript 库，或者我可以尝试实现的已知算法？这显然不仅仅是一个强制导向的过程。初始布局会发生某种排序。

如果有人有兴趣玩它，这里是 Mathematica 实现。

  Hex[exp_] := FromDigits[exp, 16];
  LByte[exp_] := BitAnd[exp, Hex@"00ff"];
  HByte[exp_] := BitAnd[exp, Hex@"ff00"]~BitShiftRight~8;
  PRNG[v_] := Module[{L5, H5, v1, v2, carry},
    L5 = LByte@v*5;
    H5 = HByte@v*5;
    v1 = LByte@H5 + HByte@L5 + 1;
    carry = HByte@v1~BitGet~0;
    v2 = BitShiftLeft[LByte@v1, 8] + LByte@L5;
    Mod[v2 + Hex@"0011" + carry, Hex@"ffff" + 1]
    ];
  mappings = # -> PRNG@# & /@ Range[0, Hex@"ffff"];
  (* WARNING! GraphPlot takes a long time to generate. *)
  (* GraphPlot[mappings] *)