三角関係の特定
クリークについて学んだところで、その知識を使ってネットワーク内の構造を見つけてみましょう。最初の目標は「三角形」です。三角形は、最も単純な複雑クリークであるため、しばしば注目されます。ここではいくつかの関数を書き、この章の演習を通じてネットワークアルゴリズムの基本的な考え方を身につけます。
Twitter のネットワークでは、各ノードにユーザーの職業を示す 'occupation' ラベルが付いており、celebrity、politician、scientist に分類されています。三角形検出アルゴリズムの応用の一つは、似た職業を持つユーザー同士が、互いにクリークを形成しやすいかどうかを調べることです。
この演習はコースの一部です
Pythonで学ぶネットワーク分析入門
演習の手順
itertoolsからcombinationsをインポートします。- 2 つの引数
Gとnを受け取り、指定したノードが三角関係にあるかどうかをチェックする関数is_in_triangle()を作成します。combinations(iterable, n)は、iterableから大きさnの組合せを返します。ここでは、list(G.neighbors(n))から大きさ2の組合せが必要になるため有用です。- 2 つのノード間にエッジがあるかを確認するには、
.has_edge(node1, node2)メソッドを使います。エッジが存在する場合、そのノードは三角関係にあるので、Trueを返してください。
実践的なインタラクティブ演習
このサンプルコードを完成させて、この演習に挑戦してみましょう。
____
# Define is_in_triangle()
def is_in_triangle(G, n):
"""
Checks whether a node `n` in graph `G` is in a triangle relationship or not.
Returns a boolean.
"""
in_triangle = False
# Iterate over all possible triangle relationship combinations
for n1, n2 in ____:
# Check if an edge exists between n1 and n2
if ____:
in_triangle = ____
break
return in_triangle