单社区检测算法

Question

以下是我的数据集演示：

• 由非常大的相关帐户的Twitter帐户追随者、该追随者的追随者以及这些追随者的追随者组成的大型社交网络，在每次迭代中清理机器人帐户、私人帐户等。
• 总节点：约500,000
• 总连接：95百万
• 4个节点有超过300万个连接
• 567个节点有超过100,000个连接
• 一半的数据集有3个或更少的连接

也就是说，我想清理这个网络，以便在进一步聚集子社区之前，从原始的初始图中获得“最佳”单个社区。请记住以下几个事实：

• 由于收集数据的方式，我知道大多数节点都有一个大型社区，它比整个网络更为优化

我曾使用过诸如louvain或模块化优化之类的社区检测算法（在计算量过大的第二个样本中使用较小的子样本），但这些算法的目标是获得最佳分割，而我的目标在某些方面是获得最佳合并。

主要问题可以用这个想法来概括：我在考虑使用以下算法。从大型网络开始；在每次迭代中删除“最弱”的节点；而整体的模块化有所提高。但这将导致最终一个非常小的社区。

你有什么方向可以找吗？一种改变现有算法方法的方法？或者甚至是一篇与这个问题相关的论文，即使非常不同？

非常感谢。

Answer 1

在这里，您可以尝试几种方法。您的网络规模很有挑战性，并非所有社区检测方法都能够在如此大的网络上在合理的时间内运行。您可以尝试那些具有可调参数的方法，并根据经验找出这些参数如何影响其分辨率。在某些值下，您可以预期一个集群所覆盖的核心网络。例如，igraph中有walktrap和spinglass方法。如果更改walktrap的步数，可以观察到最大社区大小的变化：

g <- barabasi.game(n = 10000, m = 2)

steps <- seq(1, 10, 1)
steps <- c(steps, seq(11, 200, 10))
w <- list()
ccount <- NULL
clargest <- NULL

for(s in steps){
    cat(paste('Running walktrap with steps =', s, '\n'))
    w0 <- walktrap.community(g, steps = s)
    ccount <- c(ccount, length(levels(as.factor(w0$membership))))
    clargest <- c(clargest, max(tapply(w0$membership, w0$membership, length)))
    w[[s]] <- w0
}

plot(ccount ~ steps,
    xlab = 'Number of steps',
    ylab = 'Number of communities',
    main = 'Walktrap with increasing number of steps')
plot(clargest ~ steps,
    xlab = 'Number of steps',
    ylab = 'Size of largest community',
    main = 'Walktrap with increasing number of steps')

同样，更改spinglass的gamma参数：

gamma <- c(0.05, 0.1, 0.2, 0.5, 0.7, 0.85, 1.0, 1.2, 1.5, 1.8, 2.0, 2.5, 3.0, 3.5, 5.0, 10.0, 20.0, 50.0, 100.0, 500.0)
sg <- list()
sgsize <- NULL

for(gm in gamma){
    cat(paste('Running spinglass with gamma =', gm, '\n'))
    sg0 <- spinglass.community(g, vertex = 1, gamma = gm)
    sgsize <- c(sgsize, length(sg0$community))
    sg[[as.character(gm)]] <- sg0
    }

plot(sgsize ~ log10(gamma),
    xlab = 'Gamma (log)',
    ylab = 'Size of the community',
    main = 'Spinglass with increasing value of gamma',
    xaxt = 'n'
    )

根据其描述，另一种方法infomap正是针对您这样的问题而设计的。您可能不想使用igraph实现，而是使用原始实现，因为后者在设置参数方面提供了更多的自由。有更多的Python实现，但我不知道它们有多灵活。

您也可以尝试模块化方法系列。在这里，您可以选择四种景观构建方法：nodeland、link land、perturland和edgeright；和两种山丘检测方法：total_hill和proportional_hill；此外，在perturland，您可以设置参数x。请阅读论文以获取更多信息。正如我在评论中提到的，您可以检查亲和性并设置一个阈值来选择您的核心网络。这些方法没有Python接口，但您可以简单地导出一个文本文件并通过子进程调用二进制文件，并将其输出读回Python。

有关大量其他方法的概述，请参阅第52页——这已经不是最新的，但很全面。

另一个想法是，您可以运行许多方法，并比较它们的结果，发现核心网络是一个大分区，由不同方法之间的集群边界常量acc分隔。这也是一个你需要多精确的解决方案的问题。考虑到您的数据非常嘈杂，可能会有数千个节点被任何方法错误分类。为了比较不同的集群，可以使用一些规范化的互信息，这是在igraph中实现的（请参阅此处的更多内容）。