单社区检测算法

Question

以下是我的数据集的演示：

• 由Twitter账户组成的大型社交网络，非常大的相关账户的追随者，这些粉丝的追随者，以及这些粉丝的追随者，每次迭代都会为机器人账户，私人账户等进行清理。
• 总节点：约500,000
• 总连接数：95百万
• 4个节点有超过3百万个连接
• 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实现，而是使用original，因为后者在设置参数时提供了更多自由。有更多的Python实现，但我不知道它们有多灵活。

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

有关see here from page 52的大量其他方法的概述---这已经不是最新的，而是全面的。

另一个想法是你可以运行许多方法，并比较它们的结果，找到核心网络作为由不同方法的簇边界限定的大分区。这也是一个问题，你需要多么精确的解决方案。考虑到您的数据非常嘈杂，您可能会发现数千个节点被任何方法错误分类。对于不同聚类的比较，您可以使用标准化的互信息，这是在igraph（see more here。