Skip to content

Instantly share code, notes, and snippets.

Avatar
💻
computing

Austin Benson arbenson

💻
computing
View GitHub Profile
@arbenson
arbenson / triangles.jl
Last active Apr 15, 2020
Simple triangle enumeration julia
View triangles.jl
using SparseArrays
function find_triangles(A::SparseMatrixCSC{Int64,Int64})
n = size(A, 1) # number of nodes
d = vec(sum(A, dims=2)) # degree vector
deg_order = zeros(Int64, n)
deg_order[sortperm(d)] = 1:n
triangles = []
for i = 1:n
N_i = findnz(A[:, i])[1] # neighbors of node i
@arbenson
arbenson / UMVC.jl
Created Oct 25, 2018
Union of minimum vertex covers algorithm.
View UMVC.jl
using SparseArrays, Random
function UMVC(A::SparseMatrixCSC{Int64,Int64},
ncovers::Int64=300)
edges = filter(e->e[1] < e[2],
collect(zip(findnz(A)[1:2]...)))
umvc = zeros(Int64,size(A,1))
for _ in 1:ncovers
# Run 2-approximation with random edge ordering
vc = zeros(Int64, size(A,1))
for (i, j) in shuffle(edges)
View parse_sx.jl
using LightXML
function parse_tags(filename::AbstractString)
tag_map = Dict{String, Int64}()
function get_tag_key(tag::AbstractString)
if !haskey(tag_map, tag)
n = length(tag_map) + 1
tag_map[tag] = n
return n
end
@arbenson
arbenson / tensor_dynsys_alg.jl
Last active Nov 20, 2018
Tensor dynamical system for Z-eigenvector computation
View tensor_dynsys_alg.jl
using LinearAlgebra
function tensor_apply(T::Array{Float64,3}, x::Vector{Float64})
n = length(x)
y = zeros(Float64, n)
for k in 1:n; y += T[:, :, k] * x * x[k]; end
return y
end
function tensor_collapse(T::Array{Float64,3}, x::Vector{Float64})
n = length(x)
Y = zeros(Float64, n, n)
@arbenson
arbenson / UMVC.jl
Last active Mar 14, 2018
Union of minimum vertex covers.
View UMVC.jl
function UMVC(A::SparseMatrixCSC{Int64,Int64}, ncovers=300)
edgevec = filter(e -> e[1] < e[2],
collect(zip(findnz(A)[1:2]...)))
umvc = zeros(Int64, size(A,1))
for _ in 1:ncovers
# Run 2-approximation with random edge ordering
cover = zeros(Int64, size(A,1))
edge_queue = shuffle(edgevec)
while length(edge_queue) > 0
i, j = pop!(edge_queue)
@arbenson
arbenson / parse_timestamp.jl
Created Feb 28, 2018
Parse W3C email dataset timestamps in Julia
View parse_timestamp.jl
using TimeZones
function parse_timestamp(timestamp::String)
ts = strip(timestamp)
if length(ts) < 10; return -1; end
if ts[1] == '"' && ts[end] == '"'; ts = ts[2:(end - 1)]; end
try @show ts; catch; return -1; end
# Truly terrible cases that we give up on
if contains(ts, "???"); return -1; end
@arbenson
arbenson / motif_spectral.jl
Created May 28, 2017
Julia implementation of the motif-based clustering algorithm
View motif_spectral.jl
# Find a motif-based cluster for any directed triangle motif.
function MotifSpectralClust(A::SparseMatrixCSC{Int64,Int64}, motif::AbstractString)
# Form motif adjacency matrix
B = min.(A, A') # bidirectional links
U = A - B # unidirectional links
if motif == "M1"
C = (U * U) .* U'
W = C + C'
elseif motif == "M2"
C = (B * U) .* U' + (U * B) .* U' + (U * U) .* B
@arbenson
arbenson / motif_spectral.jl
Created May 7, 2017
Julia implementation of the motif-based clustering algorithm
View motif_spectral.jl
# Find a motif-based cluster for any directed triangle motif.
function MotifSpectralClust(A::SparseMatrixCSC{Int64,Int64}, motif::AbstractString)
# Form motif adjacency matrix
B = min.(A, A') # bidirectional links
U = A - B # unidirectional links
if motif == "M1"
C = (U * U) .* U'
W = C + C'
elseif motif == "M2"
C = (B * U) .* U' + (U * B) .* U' + (U * U) .* B