PageRank in Julia
Using iterators and the linear map data structure to implement PageRank.
function pagerank(A, alpha=0.85, p = fill(1/size(A,2),size(A,2));
details=false, args...)
S = 1.0 ./ (A * ones(Float64,size(A,2)))
D = find(isinf,S) # S[i] = Inf if node i has no outlinks
S[D] = 0.0
p = p./norm(p,1)
L = LinearMap{Float64}((y,x) -> begin
At_mul_B!(y, A, S .* x)
y .= alpha .* y .+ (alpha * sum(x[D]) + 1.0 - alpha) .* p
y
end, size(A,1), size(A,2))
x = copy(p)
res = powermethod!(L, x; args...)
if details x, res, L else x end
end
function powermethod!(A, x, Ax=similar(x);
maxiter=15, tol=eps(Float64) * size(A,2),
log=true, verbose=true)
T = eltype(A)
x ./= norm(x,1)
verbose && println("Running power method, maxiter = $maxiter, tol = $tol")
history = Tuple{Int,T,T}[]
iter = 0
radius = zero(T)
err = Inf
while iter <= maxiter
A_mul_B!(Ax, A, x)
radius = norm(Ax,1)
Ax ./= radius # want |x|_1 = 1
err = norm(Ax-x,1)
verbose && @show iter,err,radius
log && push!(history,(iter,err,radius))
copy!(x, Ax)
err < tol && break
iter += 1
end
isconverged = err < tol
if log radius,x,history,isconverged else radius,x end
endVipin Vijayan. Aug 28, 2022 (u: Aug 31, 2022)