使用NetworkX的社区检测算法

Question

我有一个网络是一个图形网络，它是Email-Eu网络，在这里可用。

该数据集具有实际数据集，这是一个由大约1005个节点组成的图，其边缘形成了这个巨大的图。它还具有节点及其相应社区（部门）的地面真相标签。这些节点中的每一个都属于42个部门中的一个。

我想在图上运行一个社区检测算法，为每个节点找到相应的部门。我的主要目标是找到最大社区中的节点。

因此，首先我需要找到前42个部门（社区），然后在其中最大的一个中找到节点。

我从Girvan Newman算法开始寻找社区。Girvan Newman的美妙之处在于，它很容易实现，因为每次我都需要找到中间值最高的边缘，并将其移除，直到找到我想要的42个部门（社区）。

我正在努力寻找其他社区检测算法，这些算法让我可以选择指定我需要将我的图分解成多少个社区/分区。

是否有任何社区检测功能/技术可供我使用，让我可以选择指定需要从图表中发现多少社区？非常感谢您的任何想法。

我正在使用Python和NetworkX。

Answer 1

我不完全确定我的答案，但也许你可以试试这个。您知道标签传播吗？主要思想是您在图中有一些节点被标记，即它们属于一个社区，并且您想为图中的其他未标记节点提供标签。LPA将在整个图中传播这些标签，并为您提供节点列表和它们所属的社区。这些社区将与您标记的节点集所属的社区相同。

因此，我认为您可以通过控制在开始时初始化的社区数量来控制要从图中提取的社区数量。但我认为，在LPA收敛后，由于图的结构和算法的随机性，您初始化的一些社区也可能从图中消失。但是有许多LPA变体可以控制这种随机性。我相信sklearn的这一页谈到了这一点。

你可以在这里和这里读到LPA

Answer 2

您可能想试试pysbm。它基于networkx，实现了随机块模型和推理方法的不同变体。

如果您考虑从networkx切换到不同的基于python的图形包，您可能需要考虑graph-tools，在那里您可以使用随机块模型来执行聚类任务。另一个值得注意的包是igraph，可能想看看如何使用python igraph对图形进行聚类。

networkx中直接可用的方法相当过时。如果您的目标是最先进的聚类方法，您可以考虑使用光谱聚类或Infomap。选择取决于所需的推断社区使用情况。从网络中推断地面真相的任务属于（近似）无免费午餐定理，即（大致）不存在任何算法，因此，如果我们对所有可能的结果进行平均，它会返回比任何其他算法都“更好”的社区。

Answer 3

对于您的问题，一个（非常）部分的答案（和解决方案）是使用Networkx作为asyn\u fluidc实现的Fluid Communities算法。

请注意，它适用于连接的、无向的、未加权的图，因此，如果您的图有n个连接的组件，则应该运行n次。事实上，这可能是一个重要的问题，因为您应该对每个组件有一些初步的了解，以选择相应的k。

无论如何，值得一试。