【Python】ネットワークからコミュニティを抽出したい

・お題：ネットワークを描いたところ、なんだがゴチャっとしている。どのノード同士がまとまった集団を形成しているのか、コミュニティを抽出してみたい。

・ネットワークの中にある局所的に繋がりが密な集団をコミュニティと呼ぶらしく、ネットワークの中からこれを抽出することで、解釈がちょっと進むらしい。正直全然わからないので、理屈はおいおい勉強していくとして、とりあえずそれっぽく様子を見てみたい。

・とりあえずデータセットを作成する。データセットの作り方のイメージがわかなかったので、以下のサイトを参考にさせて頂いた。きちんとしたことは元サイトをご確認いただきたい。

towardsdatascience.com

・データセットを作成する。

import networkx as nx

import matplotlib.pyplot as plt
community_sizes = [20, 30, 20]
community_probs = [[0.5, 0.01, 0.01],
[0.01, 0.5, 0.01],
[0.01, 0.01, 0.5]]

g = nx.stochastic_block_model(community_sizes, community_probs, seed=42)

・これだけだとどんなデータが生成されたのかイメージできない。とりあえず図示する。データの作り方的に当然なのだけれど、明らかに3つの塊にぼんやりと分かれていそう。

pos = nx.spring_layout(g, k=0.5)
nx.draw_networkx_nodes(g,pos,node_size=20, node_color="lightblue",edgecolors="gray")
nx.draw_networkx_edges(g, pos,alpha=0.1)

・次に、コミュニティに分割してみる。公式サイトを見てみると、たくさんの手法がある。とりあえず、girvan_newmanでいってみる。今回は理解が追い付いていないが、将来的には原理を確認して使い分けられるようにしていきたい。。

networkx.org

from networkx.algorithms import community
communities_generator = community.girvan_newman(g)
level_1_communities = next(communities_generator)
level_2_communities = next(communities_generator)
level_3_communities = next(communities_generator)

・例えば、level_2_communitiesには以下のようなタプルが入っている。各コミュニティに含まれるノードの集合のタプルみたい。

({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19},
{20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49},
{50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69})
・各レベルのCommunityで、例えばlevel_1であれば2つのコミュニティに、level_2であれば3つのコミュニティに、分けてみたことになるらしい。それぞれ色付けしてみたい。

level_1

colors1=[(n,"red") for n in range(70) if n in level_1_communities[0]]
colors1.extend([(n,"yellow") for n in range(70) if n in level_1_communities[1]])

nx.draw_networkx_nodes(g,pos,node_size=20,node_color=[dict(colors1)[n] for n in range(70)],edgecolors="gray")
nx.draw_networkx_edges(g, pos,alpha=0.1)

level_2

colors2=[(n,"red") for n in range(70) if n in level_2_communities[0]]
colors2.extend([(n,"yellow") for n in range(70) if n in level_2_communities[1]])
colors2.extend([(n,"green") for n in range(70) if n in level_2_communities[2]])

nx.draw_networkx_nodes(g,pos,node_size=20,node_color=[dict(colors2)[n] for n in range(70)],edgecolors="gray")
nx.draw_networkx_edges(g, pos,alpha=0.1)

level_3

colors3=[(n,"red") for n in range(70) if n in level_3_communities[0]]
colors3.extend([(n,"yellow") for n in range(70) if n in level_3_communities[1]])
colors3.extend([(n,"green") for n in range(70) if n in level_3_communities[2]])
colors3.extend([(n,"blue") for n in range(70) if n in level_3_communities[3]])

nx.draw_networkx_nodes(g,pos,node_size=20,node_color=[dict(colors3)[n] for n in range(70)],edgecolors="gray")
nx.draw_networkx_edges(g, pos,alpha=0.1)