如何通过邻接矩阵快速计算任意节点对的共享邻居数量矩阵

你提到的通过邻接矩阵乘法计算共享邻居矩阵的方法完全正确，底层逻辑和矩阵乘法的规则天然匹配：

• 你示例中生成的是无向图的邻接矩阵，满足对称、对角线为0的特征，元素为1代表对应两个节点直接相连。对于无向图来说，邻接矩阵adjm和它的转置完全相等，因此 t(adjm) %*% adjm和adjm %*% adjm的计算结果完全一致。
• 矩阵乘法的规则下，结果矩阵第i行第j列的取值为sum(adjm[i,k] * adjm[k,j])，遍历所有节点k：只有当节点k同时和i、j都相连时，两项乘积为1才会被计入总和，最终的求和结果恰好就是节点i和j的共享邻居总数。
• 结果矩阵的对角线元素(i,i)对应的是节点i的度（即节点i本身的邻居总数），如果不需要这部分信息可以手动将对角线置0。

简单验证示例：3节点全连接无向图的邻接矩阵为

0 1 1
1 0 1
1 1 0

计算得到的共享邻居矩阵（对角线置0后）结果为

0 1 1
1 0 1
1 1 0

每对节点的公共邻居计数完全符合预期。

基于你给出的示例扩展的完整实现如下：

# 生成邻接矩阵
adjm <- matrix(sample(0:1, 100, replace=TRUE, prob=c(0.6,0.4)), nc=10)
# 对角线置0，无自环
diag(adjm) <- 0
# 转为对称矩阵，适配无向图特征
adjm[lower.tri(adjm)] = t(adjm)[lower.tri(adjm)]

# 计算共享邻居矩阵
common_neighbor_mat <- t(adjm) %*% adjm
# 可选：将对角线置0，去掉每个节点自身的度统计
diag(common_neighbor_mat) <- 0

• 该方法的效率远高于循环遍历每对节点统计共享邻居，节点数量越大，矩阵乘法的性能优势越明显。
• 如果是有向图场景：如果要统计同时被i和j指向的公共邻居，仍然可以用t(adjm) %*% adjm计算；如果要统计同时指向i和j的公共邻居，改用adjm %*% t(adjm)即可。

内容的提问来源于stack exchange，提问作者Chris T.