ネットワークシステム (2024 年度後期)

ネットワークの平均次数を求めなさい。

ネットワークの次数分布を求めなさい。

ネットワークの平均経路長と直径をそれぞれ求めなさい。

クラスタ係数が最大となるノードを答えなさい。

8 / 3

p(1) = 1 / 6, p(2) = 1 / 6, p(3) = 1 / 2, p(4) = 1 / 6

• 平均経路長: 8 / 5
• 直径: 3

ノード 3

以下のア.〜ウ. は、次数中心性・近接中心性・媒介中心性のいずれかを説明 している。ア.〜ウ. の説明に対応する中心性指標の名称を回答しなさい。

• ア. 当該ノードを通過する最短経路の数がどの程度であるかを表す
• イ. 当該ノードから他ノードへの平均距離が短いほど、そのノードが重要である、ということを表す
• ウ. 当該ノードの次数に相当する

各ノードの近接中心性を求めなさい。

ノード 4 とノード 5 の媒介中心性を求めなさい。 ただし、値を正規化する必要はない。

• ア. 媒介中心性
• イ. 近接中心性
• ウ. 次数中心性

C(1) = 5 / 8, C(2) = 5 / 7, C(3) = 5 / 9, C(4) = 5 / 6, C(5) = 5 / 7, C(6) = 5 / 11

B(4) = 7, B(5) = 8

ER モデルに従って、 N = 5, p = 1 / 2 のランダムグラフを手作業で生成してみなさい。

以下の文章は、ランダムネットワークの次数分布 P(k) の導出を 説明している。この文章における空欄にあてはまる適切な数式や記号を答えなさい。

• あるノードに着目し、そのノードの次数が k である確率を考える。
• ノードの次数が k であるためには、(1) k 個のノードとつながり、 (2) 残りの N - 1 - k 個のノードとつながらない、ということを満たせばよい。
• あるノードが、k 個のノードと同時につながる確率は、[ ア ] である。 一方、残りの N - 1 - k 個のノードと同時につながらない確率は、 [ イ ] である。
• さらに、N -1 個のノードから k 個のノードを求める組み合わせが [ ウ ] であることを踏まえれば、 次数分布 P(k) は [ エ ] である。

スケールフリー性を表現するために、BA モデルが導入した二つの仕組みを答え、 それらを簡潔に説明しなさい。

以下に示すグラフに対して、 BA モデルに従って、 新たにノードを追加した時に、 優先的接続で各ノードにリンクが接続される確率を答えなさい。

1 ----- 2
| \     | \
|   \   |  5 --- 6
|     \ | /
3 ----- 4

(乱数に依るので) 省略

• ア: p^k
• イ: (1 - p)^(N - 1 - k)
• ウ: N - 1 C k
• エ N - 1 C k * p^k * (1 - p)^(N - 1 - k)

(講義資料を参照すればよいので) 省略

• ノード1: 3 / 16
• ノード2: 3 / 16
• ノード3: 2 / 16 (= 1 / 8)
• ノード4: 4 / 16 (= 1 / 4)
• ノード5: 3 / 16
• ノード6: 1 / 16

コミュニティ構造を有するネットワークの特徴を、「密」および「疎」という語句を用いながら、 説明しなさい。

以下に示す無向グラフにおいて 4-クリークは存在するかどうかを答えなさい。

1 ----- 2
| \     | \
|   \   |  5 --- 6
|     \ | /
3 ----- 4

演習 2 で対象としたグラフにおいて、 ノード v1, v2, v3, v4 がコミュニティを形成するものとしたときに、 このコミュニティは「強いコミュニティ」であるかどうかを理由とともに答えなさい。

ノード同士が密に接続されたコミュニティと、 疎に接続されたコミュニティから構成されたネットワーク。

存在しない。

「強いコミュニティ」の定義に基づいて、全てのノードに対して、 k^int_v > k^ext_v が成立しているかどうかを確認すると、

v1: 3 > 0
v2: 2 > 1
v3: 2 > 0
v4: 3 > 1

である。よって、全てのノードに対して、 k^int_v > k^ext_v が成立しているため、 ノード v1, v2, v3, v4 から成るコミュニティは「強いコミュニティ」である。

本演習では、以下に示す無向グラフを対象とする。このときに、次の ア.〜エ. のコミュニティ集合が、講義資料の p.7 における定義を満たしているかどう かを検証し、満たいしていないものを列挙しなさい。その理由も述べること。

1 ----- 2
| \     | \
|   \   |  5 --- 6
|     \ | /
3 ----- 4

• ア. C = {{1, 3, 4}, {2, 4, 5, 6}}
• イ. C = {{1, 3, 4}, {2, 5}}
• ウ. C = {{1, 2, 3}, {4, 5, 6}}
• エ. C = {{1, 2, 4}, {3, 5, 6}}

講義資料の p.12 における、 右半分の例 (講義ビデオ内で解説していない方の例) に対して、 モジュラリティを計算しなさい。

1 ----- 2
| \     | \
|   \   |  5 --- 6
|     \ | /
3 ----- 4

• ア. ノード 4 が複数のコミュニティで重複しているから
• イ. ノード 6 がいずれのコミュニティにも属していないから
• エ. c2 において、ノード 3 とノード 5 との間で、路が存在しないから

省略

講義資料の p.8 で紹介した数値計算に従って、 \(S(1)\) 、 \(I(1)\) 、 \(R(1)\) を手計算しなさい。 パラメータおよび初期値は次の通りとする; \(S(0)\) =9,990、 \(I(0)\) =10、\(R(0)\) =0、 \(\beta\) =0.4、\(\gamma\) =0.2

講義資料の p.8 で紹介した数値計算を行うプログラムを、 何らかのプログラミング言語で実装し、 講義資料の p.9 で掲載しているグラフを求めてみなさい。

• \(S(1)\) = 9,990 - (0.4 * 9,990 * 10) / 10,000 = 9986.004
• \(I(1)\) = 10 + (0.4 * 9,990 * 10) / 10,000 - 0.2 * 10 = 11.996
• \(R(1)\) = 0 + 0.2 * 10 = 2

• Python 言語の場合:

Google Colab
https://colab.research.google.com/drive/1fzc0MdkKuTWvXas-4-rYNOIl67oQ_s98?usp=sharing#scrollTo=e8jzirdi8mot

• C 言語の場合:

#include <stdio.h>

#define ARRAY_SIZE 1024
#define MAX_TIME 100

int N = 10000;
double BETA = 0.4;
double GAMMA = 0.2;
double DELTA = 1;

int
main()
{
  int k = 0;
  double S[ARRAY_SIZE], I[ARRAY_SIZE], R[ARRAY_SIZE];
  double T[ARRAY_SIZE];
  S[0] = 9990; I[0] = 10; R[0] = 0;
  T[0] = 0;

  for (k = 0; k < MAX_TIME / DELTA; k++) {
    T[k + 1] = T[k] + DELTA;
    // first-order approximation
    S[k + 1] = S[k] - BETA / N * S[k] * I[k] * DELTA;
    I[k + 1] = I[k] + (BETA / N * S[k] * I[k] - GAMMA * I[k]) * DELTA;
    R[k + 1] = R[k] + GAMMA * I[k] * DELTA;
  }

  for (k = 0; k < MAX_TIME / DELTA; k++) {
    printf("%.2f S %.4f\n", T[k], S[k]);
    printf("%.2f I %.4f\n", T[k], I[k]);
    printf("%.2f R %.4f\n", T[k], R[k]);
  }
}

SIR モデルにおける基本再生産数の定義を、 記号を用いながら、 答えなさい。

ネットワーク上の情報拡散を抑制するための方策を、 ネットワークを構成するグラフの観点から、 答えなさい。

(講義資料に記述されているので) 省略

例: ネットワークからノード/リンクを取り除く。