邻域图的压缩

Question

我有一个 巨大的 邻域图（~100M 个顶点），其中 "near" 彼此的顶点有一条边。显然相邻的顶点有很多共同的邻居。

为什么没有空间索引？

你可以把它想象成一个几何问题。但实际上有些边可能不存在，因为必须检查比仅几何体更多的标准才能满足 "neighour" 条件。另一种情况的检查成本非常高。但是可以保证几何上相距很远的顶点一定不会是邻居。几何邻近度是相邻边的必要条件。

因此，这不是社交图谱。该图仅局部密集。它有密集的子图。

有没有办法利用这些知识来压缩图形？目前它太大了，无法放入内存。

例子

在此示例中，所有邻域边都绘制为实线，而虚线边仅显示彼此 "near" 的顶点，而不是没有邻居（不满足其他条件）。虚线边不存在。只有关于实体边的信息是相关的。

问题

如何压缩邻边信息？

查询将是：给我特定顶点的所有相邻顶点。

Answer 1

似乎可以使用简单的压缩方案 -
选择任意节点
以几个级别的深度进行面包优先搜索
检查具有相似邻接列表的邻居
将它们标记为次要
为他们写基础节点和差异
当遇到邻接列表太远的节点时，用完整列表组织新的基节点。

但是这张图是用来做什么的？任何压缩都会使操作变慢...

 Node: 
     Base node (for base node: null, for secondary: base node (number or address)
     List: True adj. list for base node
           RemoveList, AddList for secondary node

当 RemoveList + AddList 的大小与 base 列表的大小相当时，创建新的 base

一些close ideas found

邻域图的压缩

Compression of neighborhood graph

compression

algorithm

geometry

nearest-neighbor

graph-algorithm

为什么没有空间索引？

例子

问题