我想在具有数百万条边和节点的巨大无向图中执行图聚类。图几乎是聚类的，不同的簇只由一些节点（一种可以与多个聚类相关的模糊节点）连接在一起。两个聚类之间的边很少或几乎没有。这个问题几乎类似于查找图形的顶点切割集，但有一个例外，即图形需要划分为许多组件（它们的数量未知）。（参考这张图片 https://docs.google.com/file/d/0B7_3zLD0XdtAd3ZwMFAwWDZuU00/edit?pli=1）
它几乎就像不同的强连接组件在它们之间共享几个节点，我应该删除这些节点以分离这些强连接组件。边是微微的，但这个问题更像是在图中寻找结构，所以边边魏没有相关性。（思考这个问题的另一种方法是可视化实体球体在某些点上相互接触，球体是那些强连接的组件，接触点是那些模糊的节点）
我正在制作一些原型，所以很安静，没有时间自己拿起图聚类算法并选择最好的。另外，我需要一个可以切割节点而不是边缘的解决方案，因为在我的情况下，不同的集群共享节点而不是边缘。
是否有任何研究论文，博客可以解决这个问题或有点相关的问题？或者任何人都可以想出解决这个问题的方法，无论多么肮脏。
由于涉及数百万个节点和边缘，我需要解决方案的MapReduce实现。任何输入，链接？
MapReduce中是否有任何当前可以直接使用的开源实现？
我认为这个问题类似于通过删除顶点在在线社交网络中查找社区。
你的问题不是那么简单。恐怕与 NP 完备的 clique 问题有关，所以除非你以某种方式量化"集群之间几乎没有边"这句话，否则你的问题可能仍然非常困难。但是，我要站在你的立场上，尝试一种肮脏、贪婪的方法，即将节点视为以下准神经网络：
我认为每个顶点都有输入、输出和一个 sigmoid 激活函数，它将输入值（输入总和）转换为输出值。输出值，我认为这很重要，不会被克隆并发送到所有邻居，而是在邻居之间平均分配。除此之外，我还将定义神经元中活动的对数衰减（自我抑制，与自身的抑制连接），由网络的全局衰减参数定义。
现在，我将开始模拟从活动 0.5（活动范围为 0 到 1）开始的所有神经元，具有非常高的衰减参数，这将导致所有神经元快速稳定在 0 状态。然后，我将逐渐减小衰减参数，直到稳态结果将产生具有非零稳定活性的第一个集团。
问题是下一步该怎么做。一种可能性是从图中减去找到的集团并再次运行相同的过程，直到找到所有集团。如果你的图确实像你说的那样表现良好（实际上几乎是聚类的），这种贪婪的方法可能会成功，否则可能会导致意想不到的结果。另一种可能性是给找到的集团一个独特的集团气味，这种气味对其他集团来说是排斥的（相互取代），重新运行算法，直到找到第二个集团，给它一个不同的集团气味排斥所有其他集团等等，直到每个节点都有自己分配的气味。
我认为这将是我对此的许多大想法。
关键是，由于在一般情况下可能无法解决此问题（可能是NP完全），因此您需要利用图形具有的任何特殊属性。这意味着您需要使用参数一段时间，直到算法解决您遇到的 99% 的情况。我认为如果不对遇到的实际数据集进行长时间的实验，就不可能为您的问题给出数字上精确的答案。
由于涉及数百万个节点和边缘，我需要解决方案的MapReduce实现。任何输入，链接？
根据我的经验，我怀疑在这里使用Map/Reduce是否真的有利。节点的前 10^6 个顺序并不是那么大[在非超连接图中也是如此，因为您正在考虑聚类]，并且使用 Map/Reduce 的开销 [除非您已经为它设置了硬件/软件] 来解决您的问题将不值得。
Map/Reduce将更好地工作，一旦您解决了聚类问题，然后希望使用类似的分析来处理每个聚类。基本上什么时候你可以把你的任务分解成相对孤立的子任务，这些子任务可以并行执行。当然，这可以级联到几层。
在一个相对类似的情况下，我个人首先将我的图建模到一个图数据库中（我使用了Neo4J，并且强烈推荐它），然后对它运行我的分析和查询。您会惊讶于此解决方案的白板友好性，甚至大规模加入和连接的查询也将近乎即时地执行，尤其是在只有几百万个节点的规模上。例如，您可以根据分离程度进行过滤分析，然后列出公共资源。