Connecting Nearest Neighborモデルを用いたグラフの生成
Connecting Nearest Neighborモデルとは，スケールフリー性，クラスタ性，スモールワールド性を満たすソーシャルネットワーク的なグラフを生成するアルゴリズムの一つです．何かしらのシミュレーションなどに使えるのではないかと思います．
アルゴリズムは以下を繰り返すだけとなります．
- 1-pの確率で新たなvertexを作成．ランダムに既存のvertexを一つ選ぶ．新たなvertexと選ばれた既存のvertexを結びつける．
- pの確率で，ランダムに選んだpotential edge一つを本物のedgeへと変換する．
ちなみに，potential edgeとは次のような，潜在的なedgeです．
例えば，以下のようなグラフがあった場合のpotential edgeは，1と3を結ぶedgeとなります．
2 / \ 1 3
また，以下のようなグラフであった場合は，1-5，1-3，5-3，2-4を結ぶedgeがpotential edgeとなります．
4
|
1-2-3
|
52hopを1hopに変えるようなedgeがpotential edgeであるとも言えます．
pythonでのプログラムは以下のようになります．
#!/usr/bin/env python # this program generates social netwrok graphs by connecting nearest-neighbor # # see Alexei Vazquez, "Growing network with local rules: Preferential # attachment, clustering hierarchy, and degree correlations", Physics Review # E 67, 2003. import random class node: def __init__(self, id): self.link = [] self.id = id class cnn: def _initialize(self): random.seed() self.nodes = {} self.nodes[0] = node(0) self.nodes[1] = node(1) self.nodes[2] = node(2) self.nodes[0].link = [self.nodes[2]] self.nodes[1].link = [self.nodes[2]] self.nodes[2].link = [self.nodes[0]] self.nodes[2].link = [self.nodes[1]] self.neighbor = [(0, 1)] self.n = 2 def generate(self, step, p): self._initialize() for var in range(step): rnd = random.random() if rnd < p: self._addLink() else: self._addNode() def _addNode(self): self.n += 1 self.nodes[self.n] = node(self.n) rnd = int(random.uniform(0, self.n - 1)) self.neighbor += [(link.id, self.n) for link in self.nodes[rnd].link] self.nodes[self.n].link += [self.nodes[rnd]] self.nodes[rnd].link += [self.nodes[self.n]] def _addLink(self): if len(self.neighbor) == 0: return rnd = int(random.uniform(0, len(self.neighbor))) id1, id2 = self.neighbor[rnd] del self.neighbor[rnd] self.nodes[id1].link += [self.nodes[id2]] self.nodes[id2].link += [self.nodes[id1]] def printLink(self): for n in range(self.n): if len(self.nodes[n].link) == 0: continue for link in self.nodes[n].link: if n < link.id: print '(%d, %d)' % (n, link.id) # draw with NodeBox # see http://nodebox.net/code/index.php/Graph def draw(self, width, height): try: graph = ximport("graph") except ImportError: graph = ximport("__init__") reload(graph) size(width, height) g = graph.create() for n in range(self.n): if len(self.nodes[n].link) == 0: continue for link in self.nodes[n].link: if n < link.id: g.add_edge(n, link.id) g.solve() g.styles.apply() g.draw(directed = False, traffic = 1) if __name__ == "__main__": graph = cnn() graph.generate(1000, 0.666) graph.printLink() """ graph = cnn() graph.generate(1000, 0.666) graph.printLink() graph.draw(1440, 900) """
NodeBox（http://nodebox.net/code/index.php/Graph）を用いてvisualizeしてみたところ，以下のようになりました．
ちなみに，100回ループでp = 0.666とした場合の出力は以下のようになります．
(0, 2) (0, 1) (0, 3) (0, 5) (0, 9) (0, 10) (0, 11) (0, 7) (0, 12) (0, 18) (1, 2) (1, 3) (1, 5) (1, 6) (1, 7) (1, 12) (1, 11) (1, 8) (1, 10) (1, 4) (1, 16) (1, 20) (1, 17) (1, 9) (1, 34) (2, 4) (2, 3) (2, 10) (2, 12) (2, 7) (2, 16) (2, 5) (2, 20) (2, 11) (2, 25) (2, 26) (3, 6) (3, 11) (3, 12) (3, 7) (3, 5) (3, 10) (3, 14) (3, 19) (3, 22) (3, 26) (3, 34) (3, 20) (3, 37) (4, 17) (4, 20) (5, 8) (5, 9) (5, 13) (5, 7) (5, 10) (5, 26) (6, 12) (6, 11) (6, 14) (6, 7) (7, 22) (7, 16) (8, 9) (8, 33) (9, 13) (9, 18) (9, 15) (9, 10) (9, 26) (10, 16) (10, 20) (10, 26) (10, 31) (11, 12) (11, 14) (11, 19) (12, 14) (12, 16) (13, 15) (13, 21) (13, 28) (14, 19) (14, 27) (15, 23) (15, 24) (15, 28) (16, 25) (16, 20) (19, 27) (20, 25) (20, 31) (20, 30) (23, 24) (23, 35) (24, 29) (24, 28) (25, 30) (27, 32) (31, 38) (34, 36)
