Motive

約10年くらい前にscilabで簡単な複雑ネットワークモデルを作成したのですが、packageが豊富で学習コストが比較的低いpythonで実装してみました。

Algoryism

初期値は2つのノード（点 or dot）を用意してエッジ(線)でつなぐ

ノードが一つ増える。元からあるノードを一つ選び、新しくできたノードとつなぐ。

この時の選び方は各ノードが持つエッジの数(次数)に依存する。

例)

ノード	所有しているエッジ数	次の新しいノードにつながる確率
0	1	1/10　　　　　10%
1	2	2/10　　　　　20%
2	3	3/10　　　　　30%
3	2	2/10　　　　　20%
4	1	1/10　　　　　10%
5	1	1/10　　　　　10%

2をひたすら繰り返す

Development

パッケージを含めて10行です。

import random
__TRAINING_COUNT__ = 100
pile, edges= [1,1], [(0,1)]
for i in range(__TRAINING_COUNT__ ):
	board = sum([[i] * p for i,p in enumerate(pile)], [])
	node = random.choice(board)
	pile[node] = pile[node] + 1
	pile.append(1)
	edges.append((node, len(pile) - 1))
print("pile:{}, edge:{}".format(pile, edges))

新しくノードにつなぐ部分ですが単純に次数分のノードNoを配列に格納してランダムで取得しています。

sum([[i] * p for i,p in enumerate(pile)], [])

ものすごいnodeがあった場合は配列が崩壊しそうです。他にいい方法はないかと考え中です。

Conclusion

pile:[7, 12, 1, 2, 15, 9, 5, 9, 1, 4, 3, 2, 3, 3, 2, 1, 3, 2, 2, 2, 1, 1, 1, 5, 2, 5, 1, 3, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 5, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
edge:[(0, 1), (1, 2), (1, 3), (1, 4), (1, 5), (0, 6), (1, 7), (1, 8), (4, 9), (5, 10), (1, 11), (10, 12), (4, 13), (5, 14), (9, 15), (5, 16), (5, 17), (12, 18), (14, 19), (4, 20), (0, 21), (4, 22), (6, 23), (19, 24), (6, 25), (13, 26), (11, 27), (0, 28), (4, 29), (7, 30), (23, 31), (16, 32), (30, 33), (6, 34), (16, 35), (4, 36), (25, 37), (23, 38), (23, 39), (0, 40), (1, 41), (7, 42), (27, 43), (24, 44), (0, 45), (4, 46), (4, 47), (7, 48), (25, 49), (13, 50), (37, 51), (4, 52), (44, 53), (1, 54), (4, 55), (4, 56), (27, 57), (7, 58), (23, 59), (18, 60), (40, 61), (25, 62), (10, 63), (7, 64), (44, 65), (62, 66), (54, 67), (44, 68), (5, 69), (1, 70), (44, 71), (12, 72), (50, 73), (7, 74), (60, 75), (3, 76), (7, 77), (6, 78), (17, 79), (9, 80), (68, 81), (57, 82), (5, 83), (5, 84), (7, 85), (84, 86), (67, 87), (4, 88), (9, 89), (51, 90), (1, 91), (43, 92), (25, 93), (66, 94), (4, 95), (92, 96), (4, 97), (86, 98), (0, 99), (5, 100), (77, 101)]

Future

上記をもとにnetworkXで描画、分析でもしてみよう。
あとはこのモデルの亜流をいろいろと考えてみます。
非同期処理のサンプルモデルにも使えそうです。

SNSの普及とともに複雑ネットワークが流行し始めたのは2000年くらいですが、ネットワークの性質を求める方法としてノードの次数グラフや平均最短経路ノードの密度などがありますが、他に一般解・評価方法がまだありそうな気がします。さまざまなジャンルの実データを使って分析する必要がありそうです。

Reference

複雑ネットワーク
 Barabási–Albert model