ネットワーク全体から「お互いが全て繋がり会ってる小グループ」つまりコミュニティのようなものを抽出したくなったので、pythonのライブラリ「NetworkX」でやりました。
ここでいうコミュニティとは
人間でいうところの「お互いに友達同士の人の集まり」の事であり、ネットワーク全体の補集合で完全グラフ(全て繋がってる)であるような集合の事です。
グラフ理論では「Clique」というらしいです。
グラフ構造を作る
6ノードから成る小さい集合で実験します。
from networkx import *
import matplotlib.pyplot as plt
#元データ
data = [["A","B"],["A","C"],["C","B"],["D","C"],["D","E"],["C","E"],["E","F"]]
#ノードの構築
G = nx.Graph()
for p in list(set([r[0] for r in data] + [r[1] for r in data])):
G.add_node(p)
#エッジの構築
for d in data:
G.add_edge(d[0],d[1])
#描画
pos = nx.spring_layout(G)
nx.draw_networkx_nodes(G, pos, node_size=1200,node_color="white")
nx.draw_networkx_edges(G, pos)
nx.draw_networkx_labels(G, pos)
plt.show()
可視化されたグラフ構造
構築済みのグラフ構造からcliqueを抽出
さて、グラフ構造ができたのでコミュニティを検出してみましょう。
cliques = nx.find_cliques(G)
#標準出力
print [ c for c in cliques]
標準出力
[['C', 'A', 'B'], ['C', 'E', 'D'], ['F', 'E']]
出ました!
ちゃんとコミュニティが抽出できてますね!
小さいデータだとフーンという感じですが、大きなデータでやると色々発見があります。
パフォーマンス
10万件程度のデータだと数秒で処理できるのでとても早いです。
しかし、clique検出はノード数増加に伴い処理時間が爆発する系の処理(多分NPなんとか問題です)っぽいので、もっとデカイデータだとNetWorkXだと頭打ちになる可能性がありますが、まだ謎です。
多分、本気の人はSparkとか使うんだと思います。