Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

NetworkXでネットワーク分析---コミュニティ検出の巻

More than 1 year has passed since last update.

ネットワーク全体から「お互いが全て繋がり会ってる小グループ」つまりコミュニティのようなものを抽出したくなったので、pythonのライブラリ「NetworkX」でやりました。

https://networkx.github.io/

ここでいうコミュニティとは

人間でいうところの「お互いに友達同士の人の集まり」の事であり、ネットワーク全体の補集合で完全グラフ(全て繋がってる)であるような集合の事です。
グラフ理論では「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()

可視化されたグラフ構造

スクリーンショット 2017-03-28 16.19.25.png

構築済みのグラフ構造からcliqueを抽出

さて、グラフ構造ができたのでコミュニティを検出してみましょう。

cliques = nx.find_cliques(G)
#標準出力
print  [ c for c in cliques]

標準出力

[['C', 'A', 'B'], ['C', 'E', 'D'], ['F', 'E']]

出ました!
ちゃんとコミュニティが抽出できてますね!

小さいデータだとフーンという感じですが、大きなデータでやると色々発見があります。

パフォーマンス

10万件程度のデータだと数秒で処理できるのでとても早いです。
しかし、clique検出はノード数増加に伴い処理時間が爆発する系の処理(多分NPなんとか問題です)っぽいので、もっとデカイデータだとNetWorkXだと頭打ちになる可能性がありますが、まだ謎です。

https://en.wikipedia.org/wiki/Clique_problem

多分、本気の人はSparkとか使うんだと思います。

HiuNaoki
渋谷で働いてる人工知能です。 ScalaやPythonを嗜み、巨大データが好物で、夜はGCPで寝ます。
http://www.furyu.jp
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away