SimRank in Python implementiert

Vorwort

SimRank ist eine Methode zur (rekursiven) Berechnung der Ähnlichkeit zwischen Knoten in einem Diagramm.

Es hat das Merkmal, dass die Ähnlichkeit berechnet werden kann, ohne einen gemeinsamen benachbarten Knoten zu haben.

Papier Leicht verständliche Erklärung auf Japanisch Wikipedia (Englisch)

Der zweite Autor des SimRank-Papiers ist übrigens ein sehr berühmter DB-Forscher.

Implementierung

In der Arbeit gab es eine Methode zur Berechnung des SimRank für das zweiteilige Diagramm, daher habe ich sie auch implementiert.

simrank.py

import numpy as np

def simrank(G,C,n,t=10):
    S = np.identity(n)
    I = np.identity(n)
    G = normalize(G)
    i = 1
    while True:
        S = C * np.dot(np.dot(G.T,S),G) + (1-C) * I
        for j in range(n):
            S[j][j] = 1
        if i >= t:
            break
        i += 1
    return S

def bipertite_simrank(G,C,n,m,diag_1=True,t=10):
    S1 = np.identity(n)
    S2 = np.identity(m)
    I1 = np.identity(n)
    I2 = np.identity(m)
    G_T = normalize(G.T)
    G = normalize(G)
    i = 1
    while True:
        S2 = C * np.dot(np.dot(G.T,S1),G) + (1-C) * I2
        for j in range(m):
            S2[j][j] = 1
        S1 = C * np.dot(np.dot(G_T.T,S2),G_T) + (1-C) * I1
        for j in range(n):
            S1[j][j] = 1
        if i >= t:
            break
        i += 1
    return (S1,S2)

def normalize(G):
    s = G.sum(0)
    return G/s

if __name__ == '__main__':
    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)
    print S

    print '=================='

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

    S1, S2 = bipertite_simrank(G,C,n,m)
    print S1
    print S2

Berechnen und aktualisieren Sie einfach das Matrixprodukt.

Der Wert von C soll in der Arbeit etwa 0,8 betragen, aber es scheint, dass etwa 0,6 in späteren Untersuchungen gut ist (Quelle ist Wikipedia).

Auch wenn die Anzahl der Iterationen in der Arbeit ausreicht, scheint es besser zu sein, in späteren Nachforschungen mehr zu tun (Quelle ist Wikipedia).

Ergebnis

>> python simrank.py
[[ 1.          0.          0.1321943   0.          0.032768  ]
 [ 0.          1.          0.4131072   0.          0.10575544]
 [ 0.1321943   0.4131072   1.          0.04096     0.08687124]
 [ 0.          0.          0.04096     1.          0.33048576]
 [ 0.032768    0.10575544  0.08687124  0.33048576  1.        ]]
==================
[[ 1.          0.54658196]
 [ 0.54658196  1.        ]]
[[ 1.          0.61863088  0.61863088  0.43726175]
 [ 0.61863088  1.          0.61863088  0.61863088]
 [ 0.61863088  0.61863088  1.          0.61863088]
 [ 0.43726175  0.61863088  0.61863088  1.        ]]

Es stimmt mit den Ergebnissen im Papier überein (Abbildung 1, Abbildung 2), also bin ich sicher, dass es übereinstimmt!