0

我想在具有数百万条边和节点的巨大无向图中进行图聚类。图几乎是由不同的集群组成的，仅由一些节点（一种可以与多个集群相关的模糊节点）连接在一起。两个集群之间将有很少或几乎没有边。这个问题几乎类似于找到一个图的顶点切割集，除了一个例外，图需要被划分成许多组件（它们的数量是未知的）。（参考这张图片https://docs.google.com/file/d /0B7_3zLD0X​​dtAd3ZwMFAwWDZuU00/edit?pli=1 )

它几乎就像不同的强连接组件在它们之间共享几个节点，我应该删除这些节点以分离那些强连接组件。边是加权的，但这个问题更像是在图中寻找结构，所以边权重不相关。（考虑这个问题的另一种方法是可视化实体球体在某些点相互接触，球体是那些强连接的组件，接触点是那些模棱两可的节点）

我正在做一些原型设计，所以我没有时间自己学习图聚类算法并选择最好的。另外，我需要一个解决方案来切割节点而不是边缘，因为在我的情况下，不同的集群共享节点而不是边缘。

是否有任何研究论文、博客可以解决这个或一些相关的问题？或者任何人都可以想出一个解决这个问题的方法，无论多么肮脏。

由于涉及数百万个节点和边缘，我需要解决方案的MapReduce实现。任何输入，链接呢？

我可以直接使用 MapReduce 中的任何当前开源实现吗？

我认为这个问题类似于通过删除顶点来寻找在线社交网络中的社区。

4

2 回答 2

1

你的问题没那么简单。恐怕它与NP完全的集团问题有关，所以除非你以某种方式量化“集群之间几乎没有边”的陈述，否则你的问题可能仍然非常困难。但在你的情况下，我会尝试一种肮脏、贪婪的方法，即将节点视为以下类型的准神经网络：

我认为每个顶点都有输入、输出和一个 sigmoid 激活函数，它将输入值（输入的总和）转换为输出值。输出值，我认为这很重要，不会被克隆并发送给所有邻居，而是在邻居之间平均分配。除此之外，我将定义神经元中活动的对数衰减（自我抑制，与自身的抑制连接），由网络的全局衰减参数定义。

现在，我将从活动 0.5（活动范围为 0 到 1）开始的所有神经元开始模拟，具有非常高的衰减参数，这将导致所有神经元快速稳定在 0 状态。然后我会逐渐减小衰减参数，直到稳态结果产生第一个非零稳定活动的团。

问题是下一步该怎么做。一种可能性是从图中减去找到的集团并再次运行相同的过程，直到我们找到所有集团。如果您的图表确实像您所说的那样表现良好（实际上几乎是集群的），这种贪婪的方法可能会成功，但否则可能会导致意外结果。另一种可能性是给找到的派系一个独特的派系气味，这种气味会排斥其他派系（相互抑制），然后重新运行算法，直到找到第二个派系，给它一个不同的派系气味，对所有其他派系都排斥等等，直到每个节点有自己指定的气味。

我认为这将是我对此的许多重要想法。

关键是，由于在一般情况下可能无法解决此问题（可能是 NP 完全问题），因此您需要使用图形具有的任何特殊属性。这意味着您需要使用参数一段时间，直到算法解决您遇到的 99% 的情况。我认为，如果不对您遇到的实际数据集进行长时间的实验，就不可能对您的问题给出精确的数字答案。

于 2012-05-26T09:05:52.383 回答
0

由于涉及数百万个节点和边缘，我需要解决方案的 MapReduce 实现。任何输入，链接呢？

以我的经验，我怀疑在这里使用 Map/Reduce 是否真的有优势。前 10^6 个节点的顺序并没有那么大 [在非超连接图中也是如此，因为您正在考虑集群]，并且使用 Map/Reduce 的开销 [除非您已经设置了硬件/软件对于它] 你的问题将不值得。

Map/Reduce 会工作得更好，一旦你解决了聚类问题，然后想用类似的分析处理每个聚类。基本上，当您可以将您的任务分解为相对独立的子任务时，这些子任务可以并行执行。这当然可以级联到几层。

在一个相对相似的情况下，我个人首先将我的图建模成一个图数据库（我使用了 Neo4J，并强烈推荐它），然后对其进行分析和查询。您会惊讶于该解决方案对白板的友好程度，即使是大规模连接和连接的查询也将几乎立即执行，尤其是在只有几百万个节点的规模下。例如，您可以根据分离程度进行过滤分析，然后列出公地。

于 2012-05-26T16:42:22.190 回答