Duplication-divergence ModelをPythonで実装してみました

Duplication-Divegence Modelとは

遺伝子やタンパク質の重複（Duplication）とそれに続く異変（Divergence）が進化の基本的なメカニズムの1つであることを示すモデルです。
このモデルでは、ネットワーク内のノードの複製によって、最初は元のノードと同じである新しいノードが作られると仮定している。その後、新しいノードがランダムな突然変異を起こし、その特性や他のノードとの相互作用が変化するダイバージェンスプロセスを導入したモデルです。

"Duplication-divergence model of protein interaction network evolution"

この論文では、重複と分岐によるタンパク質間相互作用ネットワークの進化を記述するモデルを検討しており、著者らは、分岐時に重複したリンクを保持する確率という単一のパラメータに依存する豊かな挙動を示す非常に単純なモデルを提案しています。
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2092385/

作成にあたってのステップ

1. 既存のノードを複製して新しいノードを作成する
2. 一定の確率で、複製されたエッジを保持するか、新しいエッジを形成する

保持確率pについて

DDモデルには1つのパラメータpがあり、発散過程で重複したリンクが保持される確率を表します。pの値は、ネットワークの成長速度と構造的特性を決定します。pが大きい場合、ネットワークは急速に成長し、次数分布はべき乗則になリマス。べき乗則な次数分布は方、pの値が小さいと、ネットワークの成長は遅くなり、次数分布はほぼポアソン型になります。

つまり、pが大きい場合、新しいエッジが形成される可能性が低くなり、pが小さい場合、ランダムに新しいエッジが計施される可能性が高くなります。

作成したプログラムについて

作成したプログラムは2つあります。
1つは、NetworkXのduplication_divergence_graph()関数を使用して、duplication-divergence modelを作成し増田。この関数を使用すると、引数としてノード数nとリンク保持確率pを指定できます。
2つ目は、(こちらの論文)[https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2092385/]を実装したプログラムになります。

それでは早速コードを載せていきます。

import networkx as nx
import matplotlib.pyplot as plt

p=0

# n=100,保持確率0.5の重複-発散モデルを生成する
for graph_count in range(11):
  G = nx.duplication_divergence_graph(n=1000, p=0.1)

  # 次数を取得
  degrees = sorted([d for n, d in G.degree()], reverse=True)
  degree_counts = [(d, degrees.count(d)) for d in set(degrees)]

  # 次数分布の導出
  plt.loglog([d for d, count in degree_counts], [count for d, count in degree_counts], 'bo', markersize=3)
  plt.title("Degree Distribution, p={}".format(p))
  plt.xlabel("k")
  plt.ylabel("N_count")
  plt.show()

  p += 0.1

こちらのコードでは、networkXと呼ばれるライブラリを使用して、モデルを作っているので、とても簡単です。ノード数nと保持確率pを設定してあげれば良いだけなので、簡単に試すことができます。
また、今回は、次数分布の導出も行っています。
下の画像を見ればわかるように、次数分布はべき乗則になっているので、スケールフリーなネットワーク構造であることがわかります。

続いて、論文を実装した際のpythonのコードです！

import random
import matplotlib.pyplot as plt


n = 1000
p = 0
for graph_count in range(11):
  # 初期グラフを生成する
  graph = {0: {1}, 1: {0}}

  # ノード数がnに達するまでduplication-divergenceモデルに従ってノードを追加する
  for i in range(2, n):
      # ノードiを追加する
      graph[i] = set()
      # 各ノードjの次数をリストに格納
      probs = [len(graph[j]) for j in range(i)]
      # jの次数の合計を計算
      probs_sum = sum(probs)
      # 各jの次数を全体の確率の合計で正規化
      probs = [prob/probs_sum for prob in probs]
      # probsリストの重みで定義された確率でノードjを選ぶ
      j = random.choices(range(i), weights=probs)[0]
      # jと接続しているノードneighborsを取得する
      neighbors = graph[j]
      # 各ノードneighborに対して、確率pでiとneighborを接続する
      for neighbor in neighbors:
          if random.random() < p:
              graph[i].add(neighbor)
              graph[neighbor].add(i)
      # iとjを接続する
      graph[i].add(j)
      graph[j].add(i)


  # ノードの次数をカウントする
  degree_counts = {}
  for node in graph:
      degree = len(graph[node])
      if degree not in degree_counts:
          degree_counts[degree] = 1
      else:
          degree_counts[degree] += 1

  # 次数分布のグラフを描画する
  plt.loglog([d for d, count in degree_counts.items()], [count for d, count in degree_counts.items()], 'bo', markersize=3)
  plt.xlabel('k')
  plt.ylabel('N_count')
  plt.title('Degree Distribution, p={}'.format(p))
  plt.show()

  p += 0.1

こちらはコード内に細かく説明を記述しているので、解説する必要はあまりないと思います。
今回も次数分布を導出しました！

先ほどのモデルで実装した次数分布と比較してみると、少し誤差はあるものの、ネットワーク構造自体はあまり変わっていないように見えます。

ということで、今回はDuplication-divergence Modelの実装を行いました。
コメント・いいねお待ちしております！