gistfile1.py

#!/usr/bin/env python
# HITS (on memory)
# von Neumann kernel vs. regularized Laplacian kernel

from numpy import *
from numpy.linalg import *

STEP = 500

class Relatedness():
    def __init__(self, adj_matrix):
        self._adj = adj_matrix

    def __laplacian(self, adj):
        sz = size(adj[0])
        d = zeros( (sz,sz) )
        for i in range(sz):
            d[i][i] = sum(adj[i])
        return d - adj

    # regularized laplacian kernel
    def calc_rl(self):
        cit_matrix = dot(self._adj.T, self._adj)
        sz = size(cit_matrix[0])
        beta = 1. / sorted( eigvals( cit_matrix ), reverse=True )[0] -0.001
        lap = self.__laplacian(cit_matrix)
        mul_tmp = beta * (- lap)
        tmp = mul_tmp
        ret = ones( (sz,sz) ) + tmp
        for i in range(STEP):
            tmp = dot(tmp, mul_tmp)
            ret += tmp
        return ret

    # von Neumann kernel
    def calc_vnk(self):
        cit_matrix = dot(self._adj.T, self._adj)
        sz = size(cit_matrix[0])
        beta = 1. / sorted( eigvals( cit_matrix ), reverse=True )[0] -0.001
        mul_tmp = beta * cit_matrix
        tmp = mul_tmp
        ret = ones( (sz,sz) ) + mul_tmp
        for i in range(STEP):
            tmp = dot(tmp, mul_tmp)
            ret += tmp
        return dot(cit_matrix, ret)


adj = array( ((0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
              (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
              (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
              (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
              (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
              (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
              (1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0),
              (0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0),
              (0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0),
              (0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0),
              (0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0)))

relation = Relatedness(adj)
# use von Neumann kernel
matrix = relation.calc_vnk()
print "#### von Neuman kernel ####"
print "vNK(1,2)=", matrix[0,1], " <"
print "vNK(3,2)=", matrix[2,1]

# use regularized laplacian kernel
matrix = relation.calc_rl() 
print "#### regularized laplacian kernel ####"
print "RL(1,2)=", matrix[0,1]," >"
print "RL(3,2)=", matrix[2,1]