📂グラフ理論

ネットワーク理論におけるハブノード

定義 ¹

ネットワークで多くの他のノードに接続されているノードをハブ^hubと言う。

説明

ネットワーク理論の中心性とは、「重要なノードが何か」という問いに対する答えの一つである。この目的のために、度$\deg v$が高いノード$v$、つまり他のノードと多く接続されているノードが重要であるという直感は常識的であると言えるだろう。

上の図は、度$x$を$X$-軸に、頻度$p(x)$を$Y$-軸にプロットし、両軸にログをとったバラバシ-アルバートモデルを使ってスケールフリーネットワークを作成したログ-ログヒストグラムである。$X := \log x$、$Y := \log p(x)$とすると、 $$ Y = \log p(x) \sim - \gamma \log x = -\gamma X $$ のようなスケールフリーネットワークらしい直線が得られ、$X$-軸の右端にある点は、その分度が大きい点を表している。

定義から直ちにわかるように、実際に多くの他のノードと接続されているノードというのは、厳密な数学的定義とはかけ離れている。研究によっては、特定の中心性がある閾値^thresholdを超えるノードをハブとしていたり、他のすべてのノードと接続されていなければならないとされる場合もある。

可視化

以下は、バラバシ-アルバートモデルを使ってスケールフリーネットワークを作成し、そのハブを描画するJuliaのコードだ。

@time using Graphs, Plots

function hiscatter(data; bin = 10,
    xaxis = :log10, yaxis = :log10, size = (600, 400), legend = :none,
    xlabel = "x", ylabel = "p(x)",
    color = :black)
    a, b = minimum(data), maximum(data)

    if typeof(bin) == Int
        if xaxis == :linear
            stat_class = collect((a:((b - a) / bin):b))
        elseif xaxis == :log
            stat_class = 10 .^ (range(log(a), log(b), length = bin+1))
        elseif xaxis == :log2
            stat_class = 10 .^ (range(log2(a), log2(b), length = bin+1))
        else
            stat_class = 10 .^ (range(log10(a), log10(b), length = bin+1))
        end
    else
        stat_class = bin
    end
    
    freq = zeros(Int64, bin)
    freq[1] = sum(data .≤ stat_class[2])
    for i = 2:bin
        freq[i] = sum(stat_class[i] .< data .≤ stat_class[i+1])
    end
    pop!(stat_class)
    
    if length(data) == sum(freq)
        well_defined = (freq .> 0)
        
        return scatter(stat_class[well_defined], freq[well_defined],
        xaxis = xaxis, yaxis = yaxis, size = size, legend = legend,
        xlabel = xlabel, ylabel = ylabel,
        color = color) # stat_class, freq
    else
        error("something")
    end
end

G = barabasi_albert(1000,3)
hiscatter(degree(G), bin = 100, size = (400,400)); png("logloghist")