单社区检测算法-Java 学习之路

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

由Twitter帐户组成的大型社交网络，包括非常大的相关帐户的关注者，这些关注者的关注者以及这些关注者的关注者，每次迭代都会为机器人帐户，私人帐户等进行清理 .
总节点数：约500,000
总连接数：95百万
4个节点有超过3百万个连接
567个节点有超过100,000个连接
一半的数据集有3个或更少的连接

这说，在子社区进一步聚类之前， I want to clean this network in order to get the "best" single-community coming out of the raw initial 图 . 请记住这几个事实：

由于收集数据的方式，我知道大多数节点都有一个大型社区，它比整个网络更优化 .
我想获得初始网络的最佳单个子网，摆脱不属于最大可能共同社区的所有节点 .
根据一般的社区检测文献，进一步的研究将构成在几个社区中分裂这个社区，但这不是我想在这里做的 .

我已经使用了社区检测算法，例如louvain或模块化优化（在一个较小的子样本中用于计算太多的第二个），但这些算法的目标是获得最好的分裂，而我在某些方面的目标是拥有最佳合并 .

The main problema can be summarized by this idea: 我正在考虑使用以下算法 . 从大型网络开始;在每次迭代时删除"weakest"节点;而整体的模块化提高了 . 但这最终会导致一个非常小的社区 .

你有找路的地方吗？一种改变现有算法方法的方法？甚至是一篇与这个问题有关的论文即使有很大的不同？

谢谢 .

1 回答

0
在这里你可以尝试几种方法 . 您的网络规模具有挑战性，并非所有社区检测方法都能够在如此大的网络上合理地运行 . 您可以尝试那些具有可调参数的方法，并凭经验找出这些参数如何影响其分辨率 . 在某些值，您可以期望一个群集覆盖核心网络 . 例如，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 .
回复于 2024-05-05T20:06:35+08:00

单社区检测算法

1 回答

相关问题