📂그래프이론

네트워크 이론에서의 허브 노드

정의 ¹

네트워크에서 다른 많은 노드와 연결된 노드를 허브^hub라 한다.

설명

네트워크 이론에서의 중심성이란 그 중에서 ‘중요한 노드가 무엇인가’에 대한 대답 중 하나다. 이러한 목적에서 차수 $\deg v$ 가 높은 노드 $v$, 즉 다른 노드와 연결이 많이 된 노드가 중요할 것이라는 직관은 상식적이라 할 수 있을 것이다.

위 그림은 바라바시-알버트 모델로 스케일-프리 네트워크를 만들고 $X$-축에 차수 $x$, $Y$-축에 빈도 $p(x)$ 를 점으로 찍고 두 축에 로그를 취한 로그-로그 히스토그램이다. $X := \log x$, $Y := \log p(x)$ 라 두면 $$ Y = \log p(x) \sim - \gamma \log x = -\gamma X $$ 과 같이 스케일-프리 네트워크다운 직선을 얻을 수 있으며, $X$-축의 오른쪽 극단에 가 있는 점들은 그만큼 차수가 큰 점들을 나타낸다.

정의에서 곧바로 알 수 있듯 사실 다른 많은 노드와 연결된 노드라는 건 엄밀한 수학적 정의와는 거리가 있다. 어떤 연구냐에 따라 특정 구심성이 어떤 임계치^threshold를 넘기는 노드를 허브라고 하거나, 다른 모든 노드와 연결되어야 노드라 부를 수도 있다.

시각화

다음은 바라바시-알버트 모델로 스케일-프리 네트워크를 만들고 그 허브를 그리는 줄리아코드다.

@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")