Juliaでスケールフリー・ネットワークの生成と可視化

前々回Juliaでランダムネットワークを生成しましたが、今回はスケールフリー・ネットワークを生成してみます。

otepipi.hatenablog.com

スケールフリーネットワークとは

ノードの次数分布がべき則で近似できるネットワークのことです。一方、以前紹介したランダム・ネットワークの次数分布はポアソン分布で近似されます。

ランダム・ネットワークとスケールフリー・ネットワークについて、たとえばノードの数をNとするネットワークについて以下の性質が知られています。

性質	ランダム・ネットワーク	スケールフリー・ネットワーク
最大次数	≒ $\ln{N}$	≒ $N^{1/(\gamma-1)}$
N→∞の次数の標準偏差	一定値	無限大に発散

つまりスケールフリー・ネットワークはノードの最大次数が大きく（≒巨大なハブが存在する）、また標準偏差がとても大きいので平均値が意味をなさない≒典型的な値を持たない≒「スケールフリー」ということでですね。

WWW（ワールド・ワイド・ウェブ）やタンパク質の相互作用などのネットワークはスケールフリーの性質を持つようです。

スケールフリー・ネットワーク生成のアルゴリズム

今回はスケールフリー・ネットワークの著名なモデルであるバラバシ・アルバートモデルを実装します。このモデルのアルゴリズムは以下になります。

各時間ステップで毎回、新たなノードを１つ加え、すでに存在するm個のノードとの間にリンクを貼る

各ノードiの次数を $k_i$ とすると、新しいノードのリンクがノードiに接続する確率は $\frac{k_i}{\Sigma{k_j}}$

このアルゴリズム自体はまだ解釈の余地がありますので、今回の実装は私なりの実装になります。私が解釈で追加した点は以下になります。

初期状態はノード数mの完全グラフとした
m個のリンク先を選ぶ際、リンクの重複は認めないとした
m個のリンクは同時に張られるとした

このバラバシ・アルバートモデルはJuliaのネットワーク関係のパッケージLightGraphs.jlに関数として存在していますので、手早く生成されたい場合はそちらを使用すれば良いと思います。

実装

##バラバシ・アルバートモデル

using LinearAlgebra
using LightGraphs
using GraphPlot
using Statistics

function barabasialbert(N,m);

    #N ノード数
    #m １ステップで追加されるリンクの数
    A=zeros(N,N);

    #初期条件：ノード数mの完全グラフ
    A[1:m,1:m] = ones(m,m);
    A = A - Diagonal(A);
    
    for i = m+1 : N;

        AR = sum(A,dims=2)';　#Aの各行の和
        L = sum(A); #Aの要素の和＝リンクの数/2
        P = AR ./ L; #リンクが点に来る確率
       
        line = zeros(1,N) ; #リンクができるノード番号を格納する配列
     
        j = 0

        while j <= m
        
            ran=rand(1);
            sumP = cumsum(P,dims=2);#Pの累積和
            
            ##乱数未満の数字を2に置き換えたsumPの最小値インデックスを取得
            underp =findall(x-> x < ran[1,1] , sumP);
            underpc = count(x-> x < ran[1,1], sumP);
            sumP[underp] =  2 .* ones(1,underpc);
            minin =argmin(sumP); #インデックスを格納
            
            if line[minin]== 0;
                 j = j + 1;
                 line[minin] = 1 ;          
            end   

            if j == m
                break;
            end
           
        end
        
        A[i,:] = line; #リンクの追加
        A[:,i] = line'; #リンクの追加
    end

    return A;
end

matrix = barabasialbert(100,2);　#N=100,m=2

deg = sum(matrix,dims=2);#各ノードの次数
siguma = std(deg);#次数の標準偏差
ave = mean(deg);#次数の平均値
kmax = maximum(deg);#次数の最大値

G = Graph(matrix);

gplot(G)#グラフの描画