書記が数学やるだけ#849 次数相関，中心性，コミュニティ構造

次数相関，中心性，コミュニティ構造について簡単に見ておく。

問題

データセットは，アメリカの大学の空手クラブのメンバーの友人関係について示したもので，対立構造の事例として用いられる。

Zachary, Wayne W. “An Information Flow Model for Conflict and Fission in Small Groups.” Journal of Anthropological Research, 33, 452–473, (1977).

説明

次数相関について，正であればあるほどハブ同士の繋がりが強く，負であればあるほどハブと末端ノードとの繋がりが強い。一般に，ソーシャルネットワークは正の次数相関，インターネットは負の次数相関を持つ傾向がある。

中心性について，次数中心性のほかに近接中心性，媒介中心性，固有ベクトル中心性といった指標がある。

ネットワークはしばしば複数のコミュニティからなる。これを計算する方法にはGirvan-Newman法やLouvain法などがある。

解答

karate_club_graphを可視化すると，2つのハブとその他末端ノードからなることがわかる。

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns

# グラフを作成または読み込み
G = nx.karate_club_graph()

# ノードの次数に基づいて色を設定
node_color = [G.degree(v) for v in G]

# ノードのサイズに基づいてサイズを設定
node_size = [G.degree(v) * 100 for v in G]

# ネットワークを可視化
plt.figure(figsize=(12, 12))
pos = nx.spring_layout(G, seed=42)  # スプリングレイアウトでノードを配置
nx.draw_networkx_nodes(G, pos, node_size=node_size, node_color=node_color, cmap='coolwarm', alpha=0.8)
nx.draw_networkx_edges(G, pos, alpha=0.5)
plt.title('Network Visualization with Degree-based Node Colors and Sizes')
plt.show()

次数相関係数は負の値である，これはハブに末端ノードが多く繋がっていることと整合性がある。

# 次数相関を計算
assortativity_coefficient = nx.degree_assortativity_coefficient(G)

# 結果を表示
print("次数相関係数:", assortativity_coefficient)
#次数相関係数: -0.47561309768461413

次数相関行列をヒートマップで可視化する。

# 次数を取得
degree_sequence = np.array([G.degree(n) for n in G.nodes()])

# 次数相関行列を作成
correlation_matrix = np.outer(degree_sequence, degree_sequence)

# ヒートマップで可視化
plt.figure(figsize=(10, 8))
sns.heatmap(correlation_matrix, cmap='Blues', square=True)
plt.title('Degree Correlation Matrix')
plt.xlabel('Node Index')
plt.ylabel('Node Index')
plt.show()

次数と平均次数の関係からも，次数相関が負であることが言える。

# 各ノードの次数を取得
degrees = np.array([G.degree(n) for n in G.nodes()])

# 隣接ノードの平均次数を計算
avg_neighbor_degrees = np.array([np.mean([G.degree(neighbor) for neighbor in G.neighbors(n)]) for n in G.nodes()])

# 次数と隣接ノードの平均次数を散布図で表示
plt.figure(figsize=(8, 6))
plt.scatter(degrees, avg_neighbor_degrees, alpha=0.7, color='b')

# 散布図のタイトルとラベル
plt.title('Degree vs. Average Neighbor Degree')
plt.xlabel('Degree of Node')
plt.ylabel('Average Neighbor Degree')
plt.grid(True)

# 相関係数を計算して表示
correlation_coefficient = np.corrcoef(degrees, avg_neighbor_degrees)[0, 1]
plt.text(max(degrees)*0.7, max(avg_neighbor_degrees)*0.9, f'Correlation: {correlation_coefficient:.2f}', fontsize=12, color='r')

plt.show()

次数中心性が最も高いノードについて，近接中心性，媒介中心性，固有ベクトル中心性を計算する。

import networkx as nx

# グラフを作成または読み込む
G = nx.karate_club_graph()  # 例として空手クラブのネットワークを使用

# 各中心性を計算
degree_centrality = nx.degree_centrality(G)
betweenness_centrality = nx.betweenness_centrality(G)
closeness_centrality = nx.closeness_centrality(G)
eigenvector_centrality = nx.eigenvector_centrality(G)

# 次数中心性が最も高いノードを取得
max_node = max(degree_centrality, key=degree_centrality.get)

# そのノードの他の中心性の値を取得
max_node_betweenness = betweenness_centrality[max_node]
max_node_closeness = closeness_centrality[max_node]
max_node_eigenvector = eigenvector_centrality[max_node]

# 結果を出力
print(f"ノード {max_node} が最も高い次数中心性を持っています。")
print(f"そのノードの媒介中心性: {max_node_betweenness}")
print(f"そのノードの接近中心性: {max_node_closeness}")
print(f"そのノードの固有ベクトル中心性: {max_node_eigenvector}")

#ノード 33 が最も高い次数中心性を持っています。
#そのノードの媒介中心性: 0.30407497594997596
#そのノードの接近中心性: 0.55
#そのノードの固有ベクトル中心性: 0.37337121301323506

最後に，Girvan-Newman法を用いて2つのコミュニティに分割してみる。

from networkx.algorithms.community import girvan_newman

# グラフを作成または読み込む
G = nx.karate_club_graph()  # 例として空手クラブのネットワークを使用

# Girvan-Newman法を使ってコミュニティを検出
communities = girvan_newman(G)

# 2つのコミュニティに分割されるまでエッジを削除し続ける
# ここで最初の分割を取得します
for community in communities:
    if len(community) == 2:
        first_level_communities = community
        break

# コミュニティリストを作成
community_list = [list(community) for community in first_level_communities]

# コミュニティごとのノードカラーを設定
node_colors = []
for node in G.nodes():
    for i, community in enumerate(community_list):
        if node in community:
            node_colors.append(i)
            break

# グラフのレイアウトを設定 (例: spring_layout)
pos = nx.spring_layout(G)

# ノードを色付きで描画
nx.draw_networkx_nodes(G, pos, node_color=node_colors, cmap=plt.cm.Set1, node_size=300)
nx.draw_networkx_edges(G, pos, alpha=0.5)
nx.draw_networkx_labels(G, pos, font_size=10, font_color="black")

# グラフを表示
plt.title("Girvan-Newman")
plt.show()

本記事のもくじはこちら：