我有一个巨大邻域图(约 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
关于algorithm - 邻域图的压缩，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43693170/