您的特定示例建议在网络中找到社区中的节点之间具有更多连接且不同社区中的节点之间的边相对较少的社区。这与寻找孤立的社区不同，其中有完全断开的子图。

这是使用igraph包和Clauset 等人描述的算法在 R 中进行社区检测的示例。（2004 年）。要使用此算法，我将您的“跳数”转换为没有自循环的二进制邻接矩阵。该算法需要一个无向矩阵，它与您的手写图表和您提供的数据一致（边缘是对称的）。

library(igraph)
mymatrix <- rbind(
     c(1,1,2,3,3,3,2,1,1,1),
     c(1,1,1,2,2,2,1,1,1,1),
     c(2,1,1,1,1,1,1,1,2,2),
     c(3,2,1,1,1,1,1,2,3,3),
     c(3,2,1,1,1,1,1,2,3,3),
     c(3,2,1,1,1,1,1,2,2,2),
     c(2,1,1,1,1,1,1,1,2,2),
     c(1,1,1,2,2,2,1,1,1,1),
     c(1,1,2,3,3,2,2,1,1,1),
     c(1,1,2,3,3,2,2,1,1,1))

#turn this into an adjacency matrix
adjMat <- mymatrix == 1
diag(adjMat) <- 0 #no self loops

g  <- graph.adjacency(adjMat)
plot(g)

#only works for undirected graphs, which this example is fine since symetric
fc <- fastgreedy.community(as.undirected(g))

#make colors for different communities
V(g)$color <- ifelse(membership(fc)==1,"red","blue")
plot(g)

我无法评论折叠此类节点以进行进一步分析的适当性，但此类社区检测对于探索网络绝对有用。还有许多其他社区检测算法（以及 R 中用于网络分析的其他库）。这只是恰好为这个玩具问题产生所需输出的一个示例。

对于未来的读者，

这是 igraph 包中的一组函数，最后一个来自 MCL：

print("LABEL PROPAGATION")
w<-cluster_label_prop(g)

print("Leading Eigen")
w<-cluster_leading_eigen(g)

print("SpinGlass")
w<-cluster_spinglass(g, stop.temp = 0.05)

print("walktrap")
w<-cluster_walktrap(g, steps=4)

print("MCL")
adj<-get.adjacency(g)
w<-mcl(adj,addLoops=TRUE)

您可以在此处找到文档http://igraph.org/r/doc/和此处https://cran.r-project.org/web/packages/MCL/MCL.pdf

我发现 walktrap 特别有用

如果您还没有绑定到节点和连接数据的存储库，您可能会查看 Rneo4j 包。但这意味着使用 neo4j（图形数据库，而不是 RDBMS）来存储您的数据。我不是这里的专家，但我确实认为这种方法可能特别有效，如果 a) 如 Anony-Mousse 所建议的那样，您无法将其形式化，或者 b) 节点和连接的数量特别大，或者 c) 你会发疯有关于您的网络的其他问题。