サイズ "n" の極大クリークをすべて見つける
三角形（と開いた三角形）を確認できたところで、次は極大クリークの概念に進みましょう。極大クリークは、隣接する辺を追加してもそれ以上拡張できないクリークのことで、コミュニティを見つける際に有用なグラフの性質です。NetworkX には、グラフ内の各極大クリークに含まれるノードを特定できる関数 nx.find_cliques(G) があります。IPython Shell で T に対してこの関数を試し、そのあとで演習に取り組んでください。
この演習はコースの一部です
Pythonで学ぶネットワーク分析入門
演習の手順
- 2つの引数
Gとsizeを取り、サイズnの極大クリークをすべて見つける関数maximal_cliques()を作成します。forループでは、nx.find_cliques()関数を使ってG内のすべてのクリークを反復処理します。- 現在のクリークのサイズが
sizeなら、リストmcsに追加します。
assert文と作成したmaximal_cliques()関数を使って、グラフTにサイズ3の極大クリークが33個あることを確認します。
実践的なインタラクティブ演習
このサンプルコードを完成させて、この演習に挑戦してみましょう。
# Define maximal_cliques()
def ____:
"""
Finds all maximal cliques in graph `G` that are of size `size`.
"""
mcs = []
for clique in ____:
if ____ == ____:
____
return mcs
# Check that there are 33 maximal cliques of size 3 in the graph T
assert ____ == ____