【グラフ理論入門】SNSで理解する。 Pythonで友達の友達を発見するアルゴリズム。

SNS上の友達関係は、複雑で広がりのあるネットワークを形成しています。このネットワークを解析することで、友達の友達や共通の興味を持つ人々を見つけ出すことができます。本記事では、Pythonとグラフ理論を使って、このネットワークを探機し、近い友達を発見する方法を紹介します！

「Pythonでグラフを探索」
Pythonの力を借りれば、以下ネットワークを効率的に探機し、友達の友達や潜在的な新しい友達を見つけ出すことができます。本記事では、幅優先探索（BFS）を用いて、近い友達を発見するサンプルコードです。

from collections import deque
import networkx as nx
import matplotlib.pyplot as plt

# 幅優先探索
def bfs(graph, start):
    visited = set()
    queue = deque([start])
    friends = []
    
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            friends.append(vertex)
            queue.extend(graph[vertex] - visited)
    return friends

# グラフの定義（お友達の繋がり）
graph = {
    'Alice': {'Bob', 'Charlie'},
    'Bob': {'Alice', 'David', 'Eva'},
    'Charlie': {'Alice', 'Frank'},
    'David': {'Bob'},
    'Eva': {'Bob', 'Frank'},
    'Frank': {'Charlie', 'Eva'}
}

# グラフの描画
G = nx.Graph(graph)
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color='skyblue', node_size=2000, font_size=20, font_weight='bold', edge_color='gray')
plt.show()

# 幅優先探索の実行
start_user = 'Alice'
print(f"Friends close to {start_user}: {bfs(graph, start_user)}")

実行結果。

Friends close to Alice: ['Alice', 'Bob', 'Charlie', 'Eva', 'David', 'Frank']

グラフ理論入門(原書第4版)

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

こちらの記事も合わせてどうぞ！