Scale Free NetworkをMatlabで実装する

はじめに

RyosukeClaの急な発案によって明治大学総合数理Advent Calender 2017が始まってしまった。とりあえず初日は僕がその場のノリで請け負ってしまった責任もあるので、今やっている何がしかを書いていこう。

目標

Scale Free NetworkをMatlab(2017a)にて実装する。

Scale Free Network

Scale Free NetworkとはNetworkの一種で、Nodeの次数(Nodeから出ているエッジの数)がべき分布に従っているようなNetworkである。

なんのこっちゃ？となるので、平たく言うと「お金持ちがよりお金持ちになる」っていうことを表すNetworkである。次数がべき分布(裾が重い)に従うNetworkは現実に結構溢れていて、このScale Free Networkはそれをよく表しているとされている。

僕はNetworkの上にある「もの」がどうにかなったり、拡散したりする様子に興味があるので、これを実装していこうという算段である。

これからNetworkとGraphは同じ意味で使います。

Scale Free Networkのレシピ

BarabasiさんとAlbertさんというRandom Network界隈のお偉い方々が考えたレシピは以下の通り。
1. 適当な大きさの完全Graphを用意する。
2. Nodeを一つ付け加える
3. $m$個のNodeを選び、2にて付け加えたNodeから、選んだNodeへとその次数に比例する確率でEdgeを繋ぐ。
4. 2-3をお望みの大きさのGraphが得られるまで続ける。

実装

MatlabにはGraphを表現するpackageがあるので、存分に使っていく。
- startSize : レシピ1の完全Graphの大きさ
- m : レシピ3のやつ
- N : レシピ4の「お望みの大きさ」
を引数に取って、Scale Free Networkをgraphとしてreturnする。

scalefreenetwork.m

function g = scalefreenetwork(startSize, m, N)
    % create complete graph
    A = ones(startSize) - diag(ones(1, startSize));
    remain = N - startSize;
    g = graph(A);

    for r = 1 : remain
        r + startSize
        g = addnode(g, 1);

        % add m links
        deg = degree(g);
        prob = rand(m, 1) * sum(deg);
        randIndex = zeros(m, 1);

        A = adjacency(g);
        for i = 1 : m
            total = 0;

            for j = 1 : startSize + r - 1
                total = total + deg(j);
                if (total >= prob(i, 1))
                    randIndex(i) = j;
                    break;
                end
            end

            if (A(startSize + r, randIndex(i)) == 1) 
                continue;
            else
                g = addedge(g, [startSize + r], [randIndex(i)], [1]);
            end

            A = adjacency(g);
        end
    end

    [~, order] = sort(degree(g), 'descend');
    order
    [g, idx] = reordernodes(g, order);
end

完成品

Node数200のScale Free Networkはこんな感じ。中心に行くほど次数が高くなるように描画している。

ちなみにこんな感じで描画している。

startSize = 16;
m = 5;
N = 200;
g = scalefreenetwork(startSize, m, N);
plot(g, 'LineWidth', 0.2, 'EdgeAlpha', 0.4, 'MarkerSize', 8, 'Layout', 'force');

次数のヒストグラムを見るときちんと裾が重くなっている。

結論

Scale Free NetworkをMatlabにて実装できた。