HITS Algorithm Calculation Example

The equations for HITS algorithm are:

a = L'h (L' denoting transpose of adjacency matrix L)
h = La

a, h denoting the authority score and hub score respectively.

The following python code shall compute the hub score and authority score for this particular graph:

import numpy as np

adjacency_mtx = np.matrix([

  [0, 0, 0, 1, 0],
  [0, 0, 0, 1, 1],
  [0, 0, 0, 1, 0],
  [0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0]
 ])
hub_score = np.matrix([ #initial guess
  [2],
  [2],
  [2],
  [2],
  [2]
 ])
authority_score = np.matrix.transpose(adjacency_mtx)*hub_score
hub_score = adjacency_mtx*authority_score

print authority_score
print hub_score

#output:
[[0]
 [0]
 [0]
 [6]
 [2]]

[[6]
 [8]
 [6]
 [0]
 [0]]

This matches our intuition that, node 4 has a higher authority over node 5 and node 2 is a better hub than nodes 1 and 3.

Maximum Independent weight and traceback set in Graph

The following code shall find the maximum weight independent set and weight in a given graph:

def wis(arr):
 if(len(arr) == 0):
  return 0
 A = []
 B = {}
 for i in xrange(len(arr)+1):
  A.insert(i, 0)
 A[0] = 0
 A[1] = arr[0]
 B[arr[0]] = [arr[0]]
 for i in xrange(2, len(arr)+1): 
  A[i] = max(A[i-1], A[i-2]+arr[i-1])
  try:
   if(A[i-2]+arr[i-1] > A[i-1]):
    B[A[i]] = [B[A[i-2]], arr[i-1]]
  except KeyError:
   B[A[i-2]] = 0
   B[A[i]] = [B[A[i-2]], arr[i-1]]
 return A,B

res, trace = wis([5, 7, 100, -15, 3, 2])
print res[len(res)-1]
print trace[res[len(res)-1]]