自己参照ループを含むネットワークの検出

はじめに

巨大なネットワークをサンプリングしながら、「自己参照ループ」を強く持つ部分ネットワークを検出したい。

実装

スノーボールサンプリングという手法を用いてサブグラフを探索します。
そのサブグラフの中で、自己ループが最も多いものを視覚的に描画し、評価しています。

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
import random


# ランダムジオメトリックグラフの生成
G = nx.random_geometric_graph(300, 0.1)

# テストデータに自己参照ループの追加
for node in G.nodes():
   if random.random() < 0.1:  # 10%の確率で自己ループを追加
       G.add_edge(node, node)


# 初期ノードの選択とスノーボールサンプリングの実行
def snowball_sampling(start_node, target_size=30):
   queue = [start_node]
   sampled_nodes = set()
   while len(sampled_nodes) < target_size and queue:
       current = queue.pop(0)
       if current not in sampled_nodes:
           sampled_nodes.add(current)
           neighbors = list(G.neighbors(current))
           random.shuffle(neighbors)
           queue.extend(neighbors)
   return sampled_nodes


# 複数回のスノーボールサンプリングを実行
best_sample = set()
best_loop_count = 0
trial_results = []
for i in range(20):  # 20回の試行
   initial_node = random.choice(list(G.nodes()))
   sample = snowball_sampling(initial_node)
   subgraph = G.subgraph(sample)
   loop_count = sum(1 for n in subgraph.nodes() if subgraph.has_edge(n, n))
   trial_results.append((sample, loop_count))
   # 各試行の結果を表示
   print(f"試行 {i+1}: 初期ノード {initial_node}, 自己ループ数 {loop_count}")
   if loop_count > best_loop_count:
       best_loop_count = loop_count
       best_sample = sample

# 最適なサブグラフの描画
best_subgraph = G.subgraph(best_sample)
plt.figure(figsize=(8, 8))
nx.draw(best_subgraph, with_labels=True, node_color='orange', edge_color='red')
plt.title(f'Best Sample with {best_loop_count} self-loops')
plt.show()

# 最終判定結果の表示
print(f"最終判定結果: 選択された最適なサンプリングは自己ループを {best_loop_count} 個含みます。")