Hubs And Authorities

deniz.n.rezai — Sun, 01 Dec 2019 23:56:51 +0330

Hyperlink Induced Topic Search (HITS) Algorithm is a Link Analysis Algorithm that rates webpages, developed by Jon Kleinberg. This algorithm is used to the web link-structures to discover and rank the webpages relevant for a particular search.HITS uses hubs and authorities to define a recursive relationship between webpages. Before understanding the HITS Algorithm, we first need to know about Hubs and Authorities.Given a query to a Search Engine, the set of highly relevant web pages are called Roots. They are potential Authorities.Pages which are not very relevant but point to pages in the Root are called Hubs. Thus, an Authority is a page that many hubs link to whereas a Hub is a page that links to many authorities.for example, we want to calculate hubs and authorities score for this adjacency matrix by using hits algorithm for k=3.Matrix A is:And adjacency matrix with nodes is:Then, we design a graph with nodes:After that, showing ranks by using hubs and authorities:Now, we calculate AT matrix:In this step, we assume that the initial hub weight vector, u, is 1. So, we calculatev = AT * uNext, hub weight vector updated. u = A * vNow, we create the graph again for k=1:Then, calculate new authority from k = 1: v1= 12 + 12 + 22 + 42 = 22 v1 = 1/√22 + 1/√22 + 2/√22 + 4/√22 v1 = 0.213 + 0.213 + 0.426 + 0.853similarly calculate new hub from k = 1: u1= 72 + 62 + 52 + 42 = 126 u1= 7/√126 + 6/√126 + 5/√126 + 4/√126 u1 = 0.623 + 0.535 + 0.445 + 0.356The diagram for k = 2, will be:Then, calculate new authority from k = 2: v2= 0.2132 + 0.2132 + 0.4262 + 0.8532 = 0.999 v2 = 0.213/√0.999 + 0.213/√0.999 + 0.426/√0.999 + 0.853/√0.999 v2 = 0.213 + 0.213 + 0.426 + 0.853similarly calculate new hub from k = 2: u2= 0.6232 + 0.5352 + 0.4452 + 0.3562 = 0.999 u2= 0.623/√0.999 + 0.535/√0.999 + 0.445/√0.999 + 0.356/√0.999 u2 = 0.623 + 0.535 + 0.445 + 0.356The diagram for k = 3, will be:So, k = 2 ≈ k = 3Hub and authority scores have come to a consistent value.And when we reached to this statement, it is FINISHED!!!The library for hits that you can use in python is Networkx. And the library code is:#!/usr/bin/env python# Copyright (C) 2008 by# Aric Hagberg # Dan Schult # Pieter Swart # All rights reserved.# BSD license.# NetworkX:http://networkx.lanl.gov/__author__ = """Aric Hagberg (hagberg@lanl.gov)"""import networkxfrom networkx.exception import NetworkXError__all__ = ['hits','hits_numpy','hits_scipy','authority_matrix','hub_matrix']def hits(G,max_iter=100,tol=1.0e-8,nstart=None):"""Return HITS hubs and authorities values for nodes.Parameters-----------G : graphA networkx graphmax_iter : interger, optionalMaximum number of iterations in power method.tol : float, optionalError tolerance used to check convergence in power method iteration.nstart : dictionary, optionalStarting value of each node for power method iteration.Returns-------(hubs,authorities) : two-tuple of dictionariesTwo dictionaries keyed by node containing the hub and authorityvalues.Examples-------->>> G=nx.path_graph(4)>>> h,a=nx.hits(G)Notes-----The eigenvector calculation is done by the power iteration methodand has no guarantee of convergence. The iteration will stopafter max_iter iterations or an error tolerance ofnumber_of_nodes(G)*tol has been reached.The HITS algorithm was designed for directed graphs but thisalgorithm does not check if the input graph is directed and willexecute on undirected graphs.For an overview see:A. Langville and C. Meyer, "A survey of eigenvector methods of webinformation retrieval." http://citeseer.ist.psu.edu/713792.html"""import networkxif type(G) == networkx.MultiGraph or type(G) == networkx.MultiDiGraph:raise Exception("hits() not defined for graphs with multiedges.")# if not G.weighted:# raise Exception("hits(): input graph must be weighted")# choose fixed starting vector if not givenif nstart is None:h=dict.fromkeys(G,1.0/G.number_of_nodes())else:h=nstart# normalize starting vectors=1.0/sum(h.values())for k in x: h[k]*=snnodes=G.number_of_nodes()# power iteration: make up to max_iter iterationsfor i in range(max_iter):hlast=hh=dict.fromkeys(hlast.keys(),0)a=dict.fromkeys(hlast.keys(),0)# this "matrix multiply" looks odd because it is# doing a left multiply a^T=hlast^T*Gfor n in h:for nbr in G[n]:a[nbr]+=hlast[n]*G[n][nbr].get('weight',1)# now multiply h=Gafor n in h:for nbr in G[n]:h[n]+=a[nbr]*G[n][nbr].get('weight',1)# normalize vectors=1.0/sum(h.values())for n in h: h[n]*=s# normalize vectors=1.0/sum(a.values())for n in a: a[n]*=s# check convergence, l1 normerr=sum([abs(h[n]-hlast[n]) for n in h])if err < tol:return h,araise NetworkXError("HITS: power iteration failed to converge in %d iterations."%(i+1))def authority_matrix(G,nodelist=None):"""Return the HITS authority matrix."""import networkxM=networkx.to_numpy_matrix(G,nodelist=nodelist)return M.T*Mdef hub_matrix(G,nodelist=None):"""Return the HITS hub matrix."""import networkxM=networkx.to_numpy_matrix(G,nodelist=nodelist)return M*M.Tdef hits_numpy(G,max_iter=100,tol=1.0e-6,nodelist=None):"""Return a NumPy array of the hubs and authorities."""import numpyimport networkxM=networkx.to_numpy_matrix(G,nodelist=nodelist)(n,m)=M.shape # should be squareA=M.T*M # authority matrixx=numpy.ones((n,1))/n# power iteration on authority matrixfor i in range(max_iter):xlast=xx=numpy.dot(A,x)x=x/x.sum()# check convergence, l1 normerr=numpy.abs(x-xlast).sum()if err < n*tol:a=numpy.asarray(x).flatten()# h=M*ah=numpy.asarray(numpy.dot(M,a)).flatten()h/=h.sum()return h,araise NetworkXError("page_rank: power iteration failed to converge in %d iterations."%(i+1))def hits_scipy(G,max_iter=100,tol=1.0e-6,nodelist=None):"""Return a SciPy sparse array of the hubs and authorities."""import numpyimport scipy.sparseimport networkxM=networkx.to_scipy_sparse_matrix(G,nodelist=nodelist)(n,m)=M.shape # should be squareA=M.T*M # authority matrixx=scipy.ones((n,1))/n # initial guess# power iteration on authority matrixfor i in range(max_iter):xlast=xx=A*xx=x/x.sum()# check convergence, l1 normerr=scipy.absolute(x-xlast).sum()if err < n*tol:a=numpy.asarray(x).flatten()# h=M*ah=numpy.asarray(M*a).flatten()h/=h.sum()return h,araise NetworkXError("page_rank: power iteration failed to converge in %d iterations."%(i+1))

نوشته های deniz.n.rezai

Hubs And Authorities