📂Graph Theory

Hub Nodes in Network Theory

Definition ¹

A node that is connected to many other nodes in a network is called a hub.

Description

In network theory centrality, one of the answers to the question, “What constitutes an important node?” could be a node with a higher degree $\deg v$, i.e., a node that is connected to many other nodes. This intuition is considered to be commonsensical.

The above picture is a log-log histogram plotting the degree $x$ on the $X$-axis and frequency $p(x)$ on the $Y$-axis, creating a scale-free network using the Barabási-Albert model. If we label them as $X := \log x$ and $Y := \log p(x)$, $$ Y = \log p(x) \sim - \gamma \log x = -\gamma X $$ we can obtain a straight line characteristic of a scale-free network, and the points on the extreme right of the $X$-axis represent nodes with high degrees.

As can be immediately understood from its definition, the concept of a node being connected to many other nodes is somewhat distant from a strict mathematical definition. Depending on the study, a hub can be a node that exceeds a certain centrality threshold, or it might be described as a node that needs to be connected to every other node.

Visualization

Below is the Julia code for creating a scale-free network with the Barabási-Albert model and drawing its hubs.

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