始める無料で始める

オープンな三角形を見つける

それでは、オープンな三角形を見つけていきましょう。これは友達推薦システムの基盤でしたね。「A」が「B」を知っていて、さらに「A」が「C」を知っているなら、「B」も「C」を知っている可能性が高い、という考え方です。

この演習はコースの一部です

Pythonで学ぶネットワーク分析入門

コースを見る

演習の手順

  • 2つのパラメータ G と n を取り、ノードが隣接ノードとのオープンな三角形に含まれるかを判定する関数 node_in_open_triangle() を作成します。
    • for ループでは、考えられるすべての三角関係の組み合わせを反復します。
    • ノード n1 と n2 の間にエッジが「ない」場合、in_open_triangle を True に設定し、if 文を抜けて in_open_triangle を返します。
  • この関数を使って、T に存在するオープンな三角形の数を数えます。
    • for ループでは、T のすべてのノードを反復します。
    • 現在のノード n がオープンな三角形に含まれていれば、num_open_triangles をインクリメントします。

実践的なインタラクティブ演習

このサンプルコードを完成させて、この演習に挑戦してみましょう。

from itertools import combinations

# Define node_in_open_triangle()
def node_in_open_triangle(G, n):
    """
    Checks whether pairs of neighbors of node `n` in graph `G` are in an 'open triangle' relationship with node `n`.
    """
    in_open_triangle = False

    # Iterate over all possible triangle relationship combinations
    for n1, n2 in ____:

        # Check if n1 and n2 do NOT have an edge between them
        if not ____:

            in_open_triangle = ____

            break

    return ____

# Compute the number of open triangles in T
num_open_triangles = 0

# Iterate over all the nodes in T
for n in ____:

    # Check if the current node is in an open triangle
    if ____:

        # Increment num_open_triangles
        ____ += 1

print(num_open_triangles)
コードを編集して実行