kuso random-walk program

kuso_walk.jl

using LightGraphs
using GraphPlot
using Colors
using Cairo
using Compose
using Plots
using StatsBase
gr()

# plot example
k = 10
m = 2
Gk = complete_graph(k)

# m人のキーパーソン
nodes = sample(1:nv(Gk), m, replace=false)
used = [false for j in 1:k]
used[nodes] .= true
nc = [colorant"white" for j in 1:k] # 色を作る
nc[nodes] .= colornat"tomato"

gg = gplot(Gk, nodelabel=1:nv(Gk), layout=circular_layout, nodefillc=nc)
draw(PNG("example.png", 8cm, 8cm), gg)
gg

# randomwalkのシミュレーションをiter回ぐらいやる

function simulation(;k=30, m=2, max_trial=100, depth=3)
    Gk = complete_graph(k)
    
    # 何人知っているかのログ
    log_used = Int[m]
    
    # 情報を知っている m 人
    selected = sample(1:nv(Gk), m, replace=false)
    used = [false for j in 1:k]
    used[selected] .= true
    known = Set{Int}(selected)
    
    # trial 回数の情報伝達
    for _trial in 1:trial
        # 全員伝わったら終わり
        all(used) && break
        
        # まだ知らない人が他の人に対して，深さ depth ぐらいで聞こうと頑張る
        k = sample(1:nv(Gk), Weights([used[j] ? 0 : 1 for j in 1:nv(Gk)]))
        rw_t = non_backtracking_randomwalk(Gk, k, depth)
            
        # 伝言ゲーム rw_t の中に知っている人がいるかどうか
        f_exist = false
        for j in rw_t
            if j in known
                f_exist = true
                break
            end
        end

        # 伝言ゲームした人は全員情報を知った
        f_exist && (used[rw_t] .= true)    
        push!(log_used, sum(used))
    end
    log_used
end

# グラフを描く
k = 50
log0 = simulation(k=k, depth=2);
log1 = simulation(k=k, depth=3);
log2 = simulation(k=k, depth=4);
log3 = simulation(k=k, depth=5);

f = plot(figsize=(5, 3), title="On complete graph K$k")
plot!(f, log0, marker=:square, color=:black, label="d=2")
plot!(f, log1, marker=:square, color=:tomato, label="d=3")
plot!(f, log2, marker=:square, color=:blue, label="d=4")
plot!(f, log3, marker=:square, color=:forestgreen, label="d=5")
savefig(f, "graph.png")