グラフ構造の諸指標

2. グラフ構造の諸指標#

Hide code cell source 
import numpy as np
import networkx as nx

%matplotlib inline
Hide code cell source 
DRAW_CONFIG = {
    'node_color': 'white',
    'edgecolors': 'black', # line color of nodes
    'with_labels': True,
    'node_size': 600,
    'font_size': 14,
    'font_family': 'Arial',
}

2.1. グラフの大きさ#

2.1.1. グラフに含まれるノード数#

グラフの大きさを示す最も単純な指標はノード数である． グラフ\(G\)のノード集合\(V\)のとき，ノード数は\(|V|\)と表記する．

../_images/28fb653fe2fab0db26b425c8a62bb1782e38751e336500ddbb60fb4d97c3dcf9.png

上記グラフ\(G_{barbell}\)のノード数は6である． これをNetworkXで求めるには以下のように書く．

# 上記グラフを定義
G_barbell = nx.barbell_graph(3, 0)

# ノード数
V = G_barbell.nodes() # ノードを求める
len(V) # ノード集合の大きさ

# 以下でもOK
# G_barbell.number_of_nodes()

6

2.1.2. 直径#

グラフに属するノード間の距離の最大値をグラフの直径（diameter） と呼ぶ． グラフの直径とは，最も離れているノード同士の距離である．

例えば，上図のグラフ\(G_{barbell}\)の直径は3となる． それに対して，下図のグラフ\(G_{complete}\)の直径は1となる．

../_images/87b7707f4d7919649817cba96006bf09aff2cd1ecb422b7714f9d9d6b797cb78.png

グラフの直径を求めるにはNetworkXのdiameter関数を用いる． 以下は，上のグラフ\(G_{complete}\)の直径を求めるコードである．

# 上記グラフを定義
G_complete = nx.complete_graph(6)

# 直径
nx.diameter(G_complete)

1

以下のグラフ\(G_{cycle}\)の直径はいくつだろうか． 直径は3である． コードを書いたらすぐに求まるが，頭の中でなぜ直径が3になるか確認してみよう．

../_images/5be2b0927ec29c45a384b763e6980311b33f95aea5acada66eddd5fc1106e47c.png

2.1.3. （ノードの）離心数#

離心数（eccentricity） とはノードに定義される指標で，グラフ\(G\)に属するノード\(n\)に着目した際，\(n\)から\(G\)中の他のノードへの距離の最大値を表す． 例えば，以下のグラフにおいて

  • ノード0の離心数は3

  • ノード2の離心数は2

となる． ちなみに，グラフの直径は「グラフに属するノードの離心数の最大値」と言い換えることができる．

../_images/7ac22774d129bda31190cec7e6c4a8d63000667ecad0cc8330bc2a1dd47d79ec.png

NetworkXで離心数を求めるにはeccentricity関数を用いる． 以下は，上のグラフ\(G_{barbell}\)の全ノードの離心数を求めるコードである．

nx.eccentricity(G_barbell)

{0: 3, 1: 3, 2: 2, 3: 2, 4: 3, 5: 3}

2.1.4. 半径#

グラフの半径（radius） とは，グラフに属するノードの離心数の最小値を表す． 直径は離心数の「最大値」に着目しているのに注意しよう．

../_images/7e65e5fef0c36d6b1989ac9c3f5915ca8c989fcb929c7487378be46044f1227c.png

上のグラフ\(G_{barbell}\)の半径を考えてみよう． 離心数の分布を調べると分かるように，ノード2からノード4への経路の距離が2となり，この値がグラフ\(G_{barbell}\)における最小の離心数となる． よって，\(G_{barbell}\)の半径は2である（直径は3）．

グラフの半径をNetworkXで求めるにはradius関数を用いる． 以下，上のグラフ\(G_{barbell}\)の半径を求めるコードである．

nx.radius(G_barbell)

2
../_images/87b7707f4d7919649817cba96006bf09aff2cd1ecb422b7714f9d9d6b797cb78.png

上記グラフ\(G_{complete}\)の半径はいくつだろうか？答えは1である（直径は1）． グラフによって直径と半径が異なるものもあれば，同じものもあるので注意しよう．

2.2. 密度#

グラフ中の各ノードが他のノードとどの程度密に繋がっているかを定量化するには，密度を使う． グラフの密度（density） とは，グラフ中のノード間に張ることのできるすべての辺に対する，実際の辺の数の割合である．

グラフ\(G\)のノード集合を\(V\)，エッジの集合を\(E\)とする． 仮に\(G\)中のすべてのノード同士が接続されていれば，エッジの総数は\({}_{|V|} C_2\)通りになるので，グラフ\(G\)の密度は以下で計算できる．

\[ density = \frac{|E|}{{}_{|v|} \mathrm{C}_k} =\frac{2 |E|}{|V|(|V|-1)} \]
../_images/650edb0b78cd69d98ada438aec8a48d857ac336d3b129d50b7a961fc78909a8b.png

上のグラフ\(G_{barbell}\)の密度を計算してみよう． グラフ\(G_{barbell}\)のノード数は6，エッジ数は7である． よって\(G_{barbell}\)の密度は\(\frac{7}{{}_6 C_2}\)となる．

グラフの密度をNetworkXで求めるにはdensity関数を用いる． 以下は，\(G_{barbell}\)の密度を求めるコードである．

nx.density(G_barbell)

0.4666666666666667
../_images/87b7707f4d7919649817cba96006bf09aff2cd1ecb422b7714f9d9d6b797cb78.png

上記グラフ\(G_{complete}\)の密度はいくつだろうか？ このグラフはすべてのノード同士が接続されている． よって，グラフ\(G_{complete}\)の密度は1となる．

このように，すべてのノード同士が接続されているグラフ（つまり密度が1）のグラフは完全グラフ（complete graph） と呼ばれる．

2.3. 連結性#

グラフ中の任意のノード間に経路が存在するとき，つまりどのノードの間にも経路が存在するとき，そのグラフを連結グラフ（connected graph） と呼ぶ． 例えば，以下のグラフは連結グラフである．

../_images/aada295a05ddeb2d37ca661d137b6c1aed507e0241e48c870a8160520523ddc4.png

一方，グラフ内に特定のノード間に経路が存在しない場合，そのグラフを非連結グラフと呼ぶ． 例えば，以下のグラフはノード1とノード2の間には経路が存在するものの，ノード0，3，4，5からノード1とノード2にたどり着く経路が存在しない． よって，以下のグラフは非連結グラフである．

../_images/f48690ecbc6a49e41a614198042e1249a62dd51959d084f4080c238244c24348.png

NetworkXでグラフが連結グラフであるか否かを調べるには，is_conncected関数を用いる． 以下は，上記グラフが連結グラフかどうかを調べるコードである．

# グラフを定義しておく
G_disconnected = nx.Graph()
G_disconnected.add_nodes_from([0, 1, 2, 3, 4, 5])
G_disconnected.add_edges_from(
    [(1, 2), (0, 3), (0, 5), (3, 5), (4, 5), (0, 4)]
)

# 連結グラフであればTrue，そうでなければFalseが返ってくる
nx.is_connected(G_disconnected)

False

グラフが有向グラフの場合，より厳密な連結性を定義できる． 以下のグラフ\(G_wc\)を見てみよう． このグラフは無向グラフならば連結グラフであるが，有向グラフとしてみるとノード0からノード1にたどり着ける経路が存在しない． このようなグラフを弱連結グラフ（weakly-connected graph） と呼ぶ．

../_images/6dcf4ea5f51cd187ef200a0876602dd27419e19b83d6695f239ea26870a2203c.png

次に以下のグラフ\(G_sc\)を見てみよう． このグラフは先のグラフ\(G_wc\)とは異なり，ノード0からノード1にたどり着ける経路が存在する． また，どのノードからも他のノードにたどり着くことができる． このように，有向グラフ中の任意のノード間に有効経路が存在するとき，そのグラフを強連結グラフ（strongly-connected graph） と呼ぶ．

../_images/01fc624c87dfdbf4b18008e2b6df3686d0c7f9fe698473f440cc2c65aef5ddad.png

NetworkXでグラフが強連結グラフであるかを調べるにはis_strongly_connected関数を使う． 以下は，上のグラフ\(G_{sc}\)が強連結グラフであるかを調べるコードである．

# グラフを定義しておく
G_sc = nx.DiGraph()
G_sc.add_nodes_from([0, 1, 2, 3, 4, 5])
G_sc.add_edges_from(
    [(1, 0), (0, 2), (1, 4), (4, 1),
     (2, 3), (2, 4), (3, 5), (4, 5), (5, 2)]
)

# 強連結グラフであればTrue，そうでなければFalseが返ってくる
nx.is_strongly_connected(G_sc)

True

2.4. 次数分布#

ノードに接続しているエッジの数は次数（degree） と呼ばれる． 例えば，以下のグラフにおけるノード2の次数は3である． また，ノード3の次数は2であり，ノード4の次数は1である．

G = nx.Graph()
G.add_edges_from([(0, 1), (0, 2), (1, 2), (2, 3), (3, 4)])
nx.draw(G, **DRAW_CONFIG)
../_images/78924464bd210e2e1005180b50fad13a74c35ddae46837f02ac4396f00210835.png

ちなみに，NetworkXを用いてノードの次数を調べるにはdegreeメソッドを用いる． 以下は，上記グラフ\(G\)におけるノード3の次数を調べるコードである．

# グラフを定義しておく
G = nx.Graph()
G.add_edges_from([(0, 1), (0, 2), (1, 2), (2, 3), (3, 4)])

# 次数の取得
G.degree[3]

2

グラフ中のノードの次数分布を調べることは，グラフの特徴を理解する上で有用である． グラフのノード数や密度が同じでも，次数の分布が異なることもありえる． 例えば，以下のグラフ\(G_a\)を見てみよう．

# 隣接行列データからグラフを読み込む
G_a = nx.read_adjlist("data/degree-distribution/graph_a.adjlist")
nx.draw(G_a, node_size=80, width=0.4, alpha=0.9)
../_images/f2202635ea9c31a72f2637b043b8325af86d8f3e6ea7f79d907a2d88791529b3.png

このグラフ\(G_a\)のノード数は50，密度は0.078である． では，\(G_a\)の次数の分布を見てみよう． 以下はグラフ\(G_a\)のすべてのノードの次数を調べて，その分布をヒストグラムとして可視化するコードである．

# 可視化のためのライブラリをインポート
import matplotlib.pyplot as plt

# 各次数の値をdegrees_G_aリストに格納する
degrees_G_a = []
for node, degree in G_a.degree:
    degrees_G_a.append(degree)

# 次数のヒストグラムを表示
plt.hist(degrees_G_a, range=(0, 30), bins=30);
../_images/8a96c8d0f197cebe4391ccc45b3083b455f1dcade855b2e197b55f504cb5676e.png

ヒストグラムを見ると，大半のノードはその次数が2〜3であるが，次数が10を超えるノードも数個あることが分かる．

続いて以下のグラフを見てみよう．

# 隣接行列データからグラフを読み込む
G_b = nx.read_adjlist("data/degree-distribution/graph_b.adjlist")
nx.draw(G_b, node_size=80, width=0.4, alpha=0.9)
../_images/c32cda79cabe7c101d238b4ac2f472ea3ed1a0f44645a57273e59d3b3527a2c7.png

\(G_a\)と同様に，このグラフ\(G_b\)のノード数は50，密度は0.078である． では，\(G_b\)の次数の分布を見てみよう．

# 各次数の値をdegrees_G_bリストに格納する
degrees_G_b = []
for node, degree in G_b.degree:
    degrees_G_b.append(degree)

# 次数のヒストグラムを表示
plt.hist(degrees_G_b, range=(0, 30), bins=30);
../_images/5f8072c2fc15bd3d99c5f716fd4d6774bbfad09a98b10cb5c522314f369093ab.png

ヒストグラムを見ると，グラフ\(G_b\)のほぼ全てのノードの次数が4であり，それより大きな次数を持つノードは存在しないことが分かる． このように，同じノード数，同じ密度を持つグラフでもグラフの性質がまったく異なることがある．

2.5. クイズ#

2.5.1. Q: 研究者のネットワーク#

科学研究費助成事業（略称「科研費」）は学術研究を格段に発展させることを目的とし，文部科学省および日本学術振興会が審査・交付を行っている競争的研究費である． 日本の大学研究者の多くは，科研費を獲得・活用して研究活動を行っている． 科研費に採択された研究プロジェクトについては科学研究費助成事業データベースに公開されており，プロジェクトの概要やプロジェクトに関わる研究者を確認することができる．

コチラからダウンロードできるファイルは，2025年4月1日の時点で科学研究費助成事業データベースから取得した一部のデータを圧縮したものである． 解凍後に得られる4つのファイルは，ある審査区分（研究分野）の採択プロジェクトに携わったことのある研究者同士の共同研究関係を（NetworkXの）隣接行列形式で保存したファイルとなっている． ファイルと対象としている審査区分の対応関係は以下の通り：

  • collaboration_eme.adjlist: 「電気電子材料工学関連」分野

  • collaboration_mb.adjlist: 「分子生物学関連」分野

  • collaboration_ps.adjlist: 「宇宙惑星科学関連」分野

  • collaboration_jh.adjlist: 「日本史関連」分野

上記ファイルをNetworkXライブラリを使って読み込み，各研究分野の共同研究者ネットワークを示すグラフを可視化しなさい． また，各グラフの

  • ノード数

  • 密度

  • 次数の平均値

  • 次数の分布

を比較しなさい．

なお，隣接行列形式のグラフデータが格納されたxxx.adjlistファイルからグラフを読み込むには，以下のようにNetworkXのread_adjlist関数を用いればよい．

import networkx as nx

# data/kakendbディレクトリに保存したcollaboration_eme.adjlistを読み込む
G_eme = nx.read_adjlist("data/kakendb/collaboration_eme.adjlist")
Contents