simrank use numpy

simrank.py

import numpy as np
# normalize 歸一化 sum(0)為每一點被連接點個數的陣列
def normalize(G):
    s = G.sum(0)
    return G/s
'''
simrank 公式:
S = C*(W^T ∙ S ∙ W)+(1-C) ∙ I
S 相似度陣列
C 阻尼係數
W normalize後的圖鄰接矩陣
I 單位矩陣

變數：
S 相似度陣列的初始值(單位矩陣)
I 單位矩陣,S相似度陣列的初始值(單位矩陣)
G 圖鄰接矩陣
n 陣列 row or column 長度
t 為避免無限遞迴(封閉圖形)之次數
'''
def simrank(G,C,n,t=10):
    S = np.identity(n)
    I = np.identity(n)
    G = normalize(G)
    i = 1
    for a in range(t):
        S = C * np.dot(np.dot(G.T,S),G) + (1-C) * I
    # S(a,b) 如果a=b S則為1   
    for j in range(n):
        S[j][j] = 1
    return S
    
C = 0.8

""" univ """
n = 5
G = np.zeros((n,n))
G[0][1] = 1
G[0][2] = 1
G[1][3] = 1
G[2][4] = 1
G[3][0] = 1
G[4][2] = 1

S = simrank(G,C,n)