如何计算Newman(2010)的正则等价Katz相似度及对应R包实现方法

可用包说明 #

目前CRAN收录的R包中没有直接实现Newman(2010:218)定义的带δ自相似度调整参数的Katz相似度专用函数，主流网络分析包（igraph、sna等）仅提供Katz中心性的计算接口，你可以通过以下两种方法自行实现该度量，也可直接拆分出Katz中心性对应的各相似度分项：

方法1：基于闭式解直接计算 #

根据Newman给出的定义，Katz相似度矩阵的闭式解为 σ = δ(I - αA)⁻¹，其中：

• A 为图的邻接矩阵
• α 为衰减参数，需小于邻接矩阵最大特征值的倒数以保证收敛
• δ 为对角元素自相似度提升系数
• I 为与A同维度的单位矩阵

最终得到的相似度矩阵中，第i行的所有元素就是顶点i对应的Katz中心性的各个组成分项，直接求和即可得到顶点i的Katz中心性，完全匹配Newman给出的定义。
实现代码示例：

# 加载依赖包
library(igraph)

# 构造测试网络，此处用经典的空手道俱乐部网络做示例
g <- make_graph("Zachary") 
A <- as_adjacency_matrix(g, sparse = FALSE)

# 设定参数
# 最大可行α可通过1/eigen(A)$values[1]计算，此处取0.05做演示
alpha <- 0.05 
delta <- 1
n <- nrow(A)
I_mat <- diag(n)

# 计算Katz相似度矩阵
katz_similarity <- delta * solve(I_mat - alpha * A)

# 验证与Katz中心性的对应关系
# 手动计算每行和（即对应顶点的Katz中心性）
calc_centrality <- rowSums(katz_similarity)
# 调用igraph自带Katz中心性函数对比结果
builtin_centrality <- katz_centrality(g, alpha = alpha, exo = rep(delta, n))
# 二者结果完全一致，符合Newman给出的结论
all.equal(calc_centrality, as.numeric(builtin_centrality))

方法2：大规模稀疏场景的迭代实现 #

如果处理的是大规模稀疏网络，直接求逆矩阵内存开销过大，可以通过迭代计数路径的方式计算：
Katz相似度本质是两个顶点之间所有长度的路径的加权和，路径长度为k时权重为α^k，对角元额外加δ。迭代到新增路径的贡献小于设定阈值时停止即可，无需整体求逆。

注意事项 #

• 衰减参数α的取值必须小于邻接矩阵最大特征值的倒数，否则矩阵不可逆，计算结果不会收敛
• 稀疏网络场景可替换Matrix包的稀疏矩阵运算函数，大幅降低内存占用

内容的提问来源于stack exchange，提问作者Dani Mohammed