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
end

#julia

Vipin Vijayan. Aug 28, 2022 (u: Aug 31, 2022)

#julia (1)