如何调整邻接矩阵值，使其每行每列的和均为1？

我有个5×5的邻接矩阵，行和列都是用户ID，元素0或1：1代表用户互相认识，0代表不认识。

我想把矩阵改成这样：如果用户i认识用户j，那Matrix[i][j] = 1/d[j]（d[j]是用户j认识的总人数），最终要让每行每列的和都是1。

现在我只做到了列和为1，代码如下：

import numpy as np

matrix = [[0, 1, 0 ,1, 0],
          [1, 0, 0, 1, 0],
          [0, 0, 0, 1, 1],
          [1, 1, 1, 0, 1],
          [0, 0, 1, 1, 0]]

d = np.sum(matrix, axis = 0) # 算每列里1的总数

for i in range(len(matrix)):
    for j in range(len(matrix)):
        if matrix[i][j] == 1:
            matrix[i][j] = 1 / d[j]
        else:
            matrix[i][j] = 0

现在每列的和是1，但每行的和没法保证是1，求指导。

为啥当前代码只能满足列和为1？ #

你现在的操作只是列归一化：对每列j，原来邻接关系为1的元素都设成了1/d[j]，那列j的和自然是1（毕竟d[j]个1/d[j]加起来就是1）。但每行的和要看该行有多少个非零元素，每个元素是对应列的1/d[j]，这些值加起来大概率不等于1，所以行和没法达标。

要实现行列和都为1？试试Sinkhorn-Knopp算法 #

要保留原邻接矩阵的0/1结构（原来不认识的用户还是0），同时让行列和全为1，你可以用Sinkhorn-Knopp算法。这个算法就是通过迭代地对行和列做归一化，把非负矩阵转成双随机矩阵（行列和都为1），而且原矩阵的零元素一直是0。

代码实现 #

import numpy as np

# 初始邻接矩阵
adj_matrix = np.array([[0, 1, 0 ,1, 0],
                       [1, 0, 0, 1, 0],
                       [0, 0, 0, 1, 1],
                       [1, 1, 1, 0, 1],
                       [0, 0, 1, 1, 0]], dtype=np.float64)

def sinkhorn_knopp(matrix, max_iter=1000, tol=1e-6):
    n = matrix.shape[0]
    
    for _ in range(max_iter):
        # 先把每行归一化，让行和为1
        row_sums = matrix.sum(axis=1, keepdims=True)
        matrix = matrix / row_sums
        
        # 再把每列归一化，让列和为1
        col_sums = matrix.sum(axis=0, keepdims=True)
        matrix = matrix / col_sums
        
        # 检查是否收敛：行和列和都接近1就停
        row_diff = np.abs(row_sums - 1).max()
        col_diff = np.abs(col_sums - 1).max()
        if row_diff < tol and col_diff < tol:
            break
    return matrix

# 生成双随机矩阵
double_stochastic_matrix = sinkhorn_knopp(adj_matrix)

print("处理后的矩阵：")
print(double_stochastic_matrix)

# 验证下结果
print("\n每行和：", double_stochastic_matrix.sum(axis=1))
print("每列和：", double_stochastic_matrix.sum(axis=0))

额外说明 #

1. 如果你想基于你之前的列归一化结果当初始值，直接替换初始矩阵就行：

# 先用你的方法做列归一化
initial_matrix = np.array([[0, 1, 0 ,1, 0],
                           [1, 0, 0, 1, 0],
                           [0, 0, 0, 1, 1],
                           [1, 1, 1, 0, 1],
                           [0, 0, 1, 1, 0]], dtype=np.float64)
d = initial_matrix.sum(axis=0)
initial_matrix[initial_matrix > 0] = 1 / d[initial_matrix > 0]

# 再跑Sinkhorn-Knopp算法
double_stochastic_matrix = sinkhorn_knopp(initial_matrix)

2. 你的邻接矩阵是连通的（任意两个用户之间都有间接认识的路径），所以这个算法肯定能收敛到符合要求的双随机矩阵。

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