【グラフ理論入門】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']
こちらの記事も合わせてどうぞ！