아래 튜토리얼은 graph-tool 라이브러리에서 제공하는 similarity() 함수를 이용해, 두 그래프의 인접관계(또는 가중치 포함) 유사도를 측정하는 방법을 자세히 설명합니다. 특히, Jaccard 유사도를 기반으로 하여 두 그래프가 얼마나 “비슷한 간선 구조”를 갖는지 정량화할 수 있습니다. 초보자를 위해 파이썬 코드 예시, 자세한 한글 주석, 추가 팁 등을 친절하고 정성스럽게 안내합니다.

---

1. similarity() 함수 개요

similarity(
    g1,
    g2,
    eweight1=None,
    eweight2=None,
    label1=None,
    label2=None,
    norm=True,
    p=1.0,
    distance=False,
    asymmetric=False
)

• 인자 설명:

  1. g1, g2: 비교하고자 하는 두 개의 Graph 객체
     • 주의: 기본적으로 두 그래프가 같은 수의 정점을 갖는다고 가정하지 않습니다. 다만, label1, label2를 통해 매칭시킬 수 있음
     • 만약 undirected 그래프여도, 내부적으로는 양방향 간선을 가진 것으로 처리합니다.
  2. eweight1, eweight2: (옵션) 각 그래프의 간선 가중치 EdgePropertyMap
     • 없으면, 단순히 간선 유무(또는 중복 간선 수)를 비교
     • 있으면, 인접 행렬 항목이 해당 가중치 값이 됨
  3. label1, label2: (옵션) 정점 라벨(=인덱스)을 매핑하기 위한 VertexPropertyMap
     • 지정 안 하면, 각각 g1, g2의 내부 정점 인덱스를 그대로 사용
     • 서로 다른 그래프에서 “동일 라벨” 정점을 매칭시키고 싶다면, 명시해야 함
  4. norm=True: 결과값을 전체 간선(혹은 가중치 합)으로 정규화할지 여부
     • True면 [0..1] 범위 유사도 (Jaccard 계수와 유사), False면 분모 없이 단순합
  5. p=1.0: (옵션$\ell_p$-distance/유사도에서 p의 값
     • 기본 1.0 → Jaccard-L1 기반
     • p>1이면 $\ell_p$ 노름
  6. distance=False: True면 유사도가 아니라, “거리”($1 - similarity$)를 반환(원문에서는 “complement”)
  7. asymmetric=False: True면 비대칭(asymmetric) 유사도 계산
     • 비대칭일 경우, g1의 “간선 중 g2에도 있는” 부분만 카운팅 등

• 반환: float 스칼라 값

  • norm=True & distance=False & asymmetric=False 시 → [0..1] 사이의 유사도
  • norm=True & distance=True 시 → [0..1] 사이의 거리 (1 - 유사도 개념)
  • norm=False 시 → 분모 없이 raw 비교값

---

2. Jaccard 기반 유사도 개념

• $\text{기본 Jaccard 유사도}$무가중, norm=True, distance=False):
  $\text{similarity} = \frac{|E_{1} \cap E_{2}|}{|E_{1} \cup E_{2}|}$
  여기서 $E_1, E_2$는 각각 그래프 $g1, g2$의 간선 집합.
  • $|E_1 \cap E_2|$: 두 그래프 모두에 존재하는 동일 (source→target) 간선의 수
  • $|E_1 \cup E_2|$: 양쪽 그래프 간선을 모두 합친 것(중복 없이)
• 가중치 있는 경우, edge multiplicity(혹은 가중치)로 인접행렬 $A_1, A_2$ 항목을 대체

2.1 distance=True 인 경우

• distance=True → 실제 반환값 = $1 - \text{similarity}$정규화했을 때)
  • 즉, 그래프가 얼마나 다른가?

2.2 asymmetric=True 인 경우

• 비대칭: “$g1$이 $g2$에 비해 얼마나 포함되어 있는가?” 처럼 한쪽 방향만 본다
  • 수식 예: $\sum \theta( A_1(i,j) > 0 \text{ and } A_2(i,j) > 0 $ / “조건부 분모”
  • 용도: 부분 그래프(subgraph) 여부를 평가할 때 등

---

3. 예시 코드: 간단한 무가중 그래프 비교

아래는 두 개의 무방향 그래프를 생성하고, similarity()로 유사도를 계산해보는 예제입니다.

import graph_tool.all as gt
import numpy as np

def example_similarity_unweighted():
    # 1) 그래프 g1, g2 생성: 무작위 100노드, 평균 차수 3
    g1 = gt.random_graph(100, lambda: (3,3), directed=False)
    g2 = gt.random_graph(100, lambda: (3,3), directed=False)

    # 2) 기본 similarity(=Jaccard), norm=True, distance=False
    sim_val = gt.similarity(g1, g2, norm=True, distance=False)
    print("Similarity (Jaccard, unweighted) g1 vs g2:", sim_val)

    # 3) distance=True 시
    dist_val = gt.similarity(g1, g2, norm=True, distance=True)
    print("Distance (1 - similarity):", dist_val)

if __name__=="__main__":
    example_similarity_unweighted()

3.1 코드 해설

1. 그래프 생성: random_graph(100, (3,3), directed=False)
2. similarity(g1, g2, norm=True, distance=False)
   • $|E_1 \cap E_2|$와 $|E_1 \cup E_2|$ 기반의 Jaccard 유사도
3. distance=True 하면 1 - sim 형태
4. 출력 예)

   Similarity (Jaccard, unweighted): 0.03
   Distance (1 - similarity): 0.97

---

4. 예시: 가중치 포함 그래프 비교

아래 예시는 간단한 5개 정점의 방향성 그래프 두 개를 만들고, 임의 가중치로 similarity를 계산해 봅니다.

def example_similarity_weighted():
    # 1) 첫 번째 그래프 g1
    g1 = gt.Graph(directed=True)
    v1 = [g1.add_vertex() for _ in range(5)]
    e1a = g1.add_edge(v1[0], v1[1])
    e1b = g1.add_edge(v1[1], v1[2])
    e1c = g1.add_edge(v1[3], v1[4])
    
    w1 = g1.new_edge_property("double")
    w1[e1a] = 1.0
    w1[e1b] = 2.5
    w1[e1c] = 0.5

    # 2) 두 번째 그래프 g2
    g2 = gt.Graph(directed=True)
    v2 = [g2.add_vertex() for _ in range(5)]
    e2a = g2.add_edge(v2[0], v2[1])
    e2b = g2.add_edge(v2[2], v2[4])
    e2c = g2.add_edge(v2[3], v2[4])

    w2 = g2.new_edge_property("double")
    w2[e2a] = 1.5
    w2[e2b] = 2.5
    w2[e2c] = 0.5

    # 3) similarity with weights
    sim_val = gt.similarity(g1, g2, eweight1=w1, eweight2=w2,
                            norm=True, distance=False)
    print("Weighted similarity(g1 vs g2, norm=True):", sim_val)

    # distance = True -> 1 - sim
    dist_val = gt.similarity(g1, g2, eweight1=w1, eweight2=w2,
                             norm=True, distance=True)
    print("Weighted distance:", dist_val)

4.1 메커니즘

• 각 그래프의 인접행렬 $A_1(i,j$, $A_2(i,j$ = 간선 가중치 (없으면 0)
• similarity ≈ $\sum \min(A_1(i,j), A_2(i,j)$정규화 시, 이를 $\sum \max(A_1(i,j), A_2(i,j)$로 나눔)
• distance=True 시 → $1 - similarity$

---

5. label(정점 라벨) 사용하기

두 그래프의 노드 수, 인덱스 체계가 다를 때, 동일한 라벨을 갖는 노드를 서로 매칭하고 싶다면 label1, label2를 활용할 수 있습니다.

def example_similarity_with_labels():
    # 예: g1, g2가 서로 다른 인덱스지만 "이름"이 같은 노드들을 매칭해보자
    g1 = gt.Graph(directed=False)
    g2 = gt.Graph(directed=False)

    # g1: "A,B,C" 노드
    v1A = g1.add_vertex(); g1.vertex_properties["name"] = g1.new_vertex_property("string")
    g1.vp.name[v1A] = "NodeA"
    v1B = g1.add_vertex(); g1.vp.name[v1B] = "NodeB"
    v1C = g1.add_vertex(); g1.vp.name[v1C] = "NodeC"
    g1.add_edge(v1A, v1B)
    g1.add_edge(v1B, v1C)

    # g2: "NodeA, NodeB, NodeC" - 순서 달라도 라벨만 일치하면 됨
    v2X = g2.add_vertex(); g2.vertex_properties["lab"] = g2.new_vertex_property("string")
    g2.vp.lab[v2X] = "NodeB"  # index 0 => name=NodeB
    v2Y = g2.add_vertex(); g2.vp.lab[v2Y] = "NodeA"  # index 1 => name=NodeA
    v2Z = g2.add_vertex(); g2.vp.lab[v2Z] = "NodeC"  # index 2 => name=NodeC
    g2.add_edge(v2X, v2Y)  # B->A
    g2.add_edge(v2X, v2Z)  # B->C

    # similarity(g1, g2) with label1=g1.vp.name, label2=g2.vp.lab
    sim_val = gt.similarity(
        g1, g2,
        label1=g1.vp.name,
        label2=g2.vp.lab,
        norm=True
    )
    print("Similarity with vertex label matching:", sim_val)

위 예시에서 “NodeA”, “NodeB”, “NodeC”가 서로 매핑되며, 인덱스가 달라도 라벨이 같다면 동일 노드로 간주.

---

6. 매개변수 정리

1. norm=True/False:
   • True → $\sum \min(A_1, A_2$ / $\sum \max(A_1, A_2$ 식 (0~1 범위)
   • False → $\sum \min(A_1, A_2$ 등 분모 없는 값
2. p: $\ell_p$-distance/유사도에서 p (기본 1)
3. distance=False/True:
   • False: 유사도(similarity), True: 1 - similarity(거리)
4. asymmetric=False/True:
   • False: 교집합 관점, True: 한쪽 그래프가 다른 한쪽에 포함되는 정도(부분집합) 관점
5. label1, label2: 노드 라벨 매칭(없으면 인덱스로 대응)
6. eweight1, eweight2: 간선 가중치 (없으면 무가중)

---

7. 시간 복잡도

• $\mathrm{O}((V+E) \log(V)$소스 문서상 $\mathrm{O}((n+e)\log(n)$ 언급)
  • 내부적으로 정점 매칭(label mapping) + 간선 테이블 비교
  • 병렬(OpenMP) 지원 시, 규모가 큰 그래프에도 효율적

---

8. 종합 예시

아래는 가중치 포함, 라벨도 매핑하며, distance(거리) 모드로 비교하는 완성 예제:

import graph_tool.all as gt

def example_similarity_full():
    # 그래프 g1 (5노드, 방향성, 라벨)
    g1 = gt.Graph(directed=True)
    g1.vp.label = g1.new_vertex_property("string")
    v1 = [g1.add_vertex() for _ in range(5)]
    # 라벨 설정
    labels1 = ["A", "B", "C", "D", "E"]
    for i, v in enumerate(v1):
        g1.vp.label[v] = labels1[i]

    # 간선
    e1 = g1.add_edge(v1[0], v1[1])  # A->B
    e2 = g1.add_edge(v1[1], v1[2])  # B->C
    e3 = g1.add_edge(v1[2], v1[3])  # C->D

    # 가중치
    w1 = g1.new_edge_property("double")
    w1[e1], w1[e2], w1[e3] = 1.2, 2.0, 0.5

    # 그래프 g2 (5노드, 방향성, 라벨)
    g2 = gt.Graph(directed=True)
    g2.vp.lab = g2.new_vertex_property("string")
    v2 = [g2.add_vertex() for _ in range(5)]
    labels2 = ["E", "C", "A", "D", "B"]  # 일부 순서 뒤섞음
    for i, v in enumerate(v2):
        g2.vp.lab[v] = labels2[i]

    # 간선
    e4 = g2.add_edge(v2[0], v2[3])  # E->D
    e5 = g2.add_edge(v2[2], v2[1])  # A->C
    e6 = g2.add_edge(v2[4], v2[1])  # B->C

    # 가중치
    w2 = g2.new_edge_property("double")
    w2[e4], w2[e5], w2[e6] = 0.5, 2.0, 2.0

    # similarity: distance=True => (1 - similarity)
    dist_val = gt.similarity(
        g1, g2,
        eweight1=w1, eweight2=w2,
        label1=g1.vp.label, label2=g2.vp.lab,
        norm=True,
        distance=True  # => 거리(1 - sim)
    )
    print("Distance (1-sim) between g1,g2 with label & weight:", dist_val)

if __name__=="__main__":
    example_similarity_full()

---

9. 마무리

similarity() 함수를 통해, 두 그래프가 간선 구조(또는 가중치 포함) 관점에서 얼마나 유사한지 편리하게 계산할 수 있습니다.

• Jaccard 유사도(교집합/합집합) 혹은 $\ell_p$-노름 기반
• distance 모드로 그래프 간 “차이” 정도 판단 가능
• 라벨(label)을 통한 서로 다른 노드 인덱스 매핑 지원
• 가중치(edge weight) 지원 (비교 시 인접행렬 항목을 실수값으로 취급)
• 대규모 그래프도 병렬 처리 가능

따라서, 네트워크의 유사성 비교나, 리와이어링 전후 차이 또는 여러 버전의 그래프가 얼마나 변했는지 측정할 때 유용합니다.

아래 튜토리얼은 graph-tool 라이브러리의 random_graph() 함수를 이용해 무작위 그래프를 생성하는 과정을 보여줍니다. 특히, 오류 없이 제대로 동작하기 위해서 정점의 차수(degree)를 생성하는 방법(파라미터)과 주의사항을 자세히 설명합니다. 초보자를 위해 파이썬 코드 예시, 상세한 한글 주석 등을 포함했습니다.

---

1. random_graph() 함수 개요

graph_tool.generation.random_graph(n, deg_sampler, ..., directed=False)는

• 정점 수: n
• 차수(=간선 개수) 분포를 정하는 함수: deg_sampler
  • 예: lambda: np.random.poisson(lambda_value)
  • 혹은 유향 그래프의 경우 (in_degree, out_degree) 형태를 반환하는 함수

를 인자로 받아, 무작위로 그래프를 생성합니다.

그러나 유향 그래프 생성 시에는 deg_sampler가 lambda: (in_deg, out_deg) 형태의 튜플을 반환해야 하고,
무향 그래프 생성 시에는 deg_sampler가 lambda: deg 형태의 단일 정수를 반환해야 합니다.

중요: 무향(directed=False) 그래프에서는 deg_sampler()가 단일 int(or float로 변환가능)를 반환해야 하며, (3,3)와 같이 튜플을 반환하면 에러가 발생합니다.

---

2. 왜 lambda: (3,3)에서 오류가 나는가?

• lambda: (3,3)는 매번 (3,3)라는 튜플을 반환
• directed=False인 그래프에서 random_graph()는 단일 차수 값을 예상
• 따라서 (3,3) 형태로 두 개의 값(=유향 그래프처럼 in/out degrees)을 반환 → 무향 그래프 코드에서는 예상치 못한 형식 → 에러 발생

---

3. 예시 코드 1: 무작위 무향 그래프, 포아송 분포 차수

import graph_tool.all as gt
import numpy as np

def example_random_graph_undirected():
    """
    무향 그래프를 random_graph()로 생성:
    deg_sampler는 단일 정수를 반환해야 한다.
    아래에서는 np.random.poisson(λ)를 사용.
    """
    n = 50  # 정점 수
    # deg_sampler: np.random.poisson(2)를 반환 (평균 차수가 2인 Poisson분포)
    # --> 무향이므로 단일 int여야 함!
    deg_sampler = lambda: np.random.poisson(2)

    # 무작위 무향 그래프 생성
    g = gt.random_graph(
        n,
        deg_sampler,
        directed=False
    )
    print("Undirected random graph created with", g.num_vertices(), "vertices and", g.num_edges(), "edges.")

    # 임의의 정보 출력
    print("Degree of first vertex:", g.vertex(0).out_degree())

if __name__=="__main__":
    example_random_graph_undirected()

3.1 코드 해설

• deg_sampler = lambda: np.random.poisson(2)
  • 호출 시, e.g. deg_sampler() → 3 (확률적으로 2 주변 정수)
  • 단일 정수 반환, 무향 그래프에서 문제 없음
• random_graph(50, deg_sampler, directed=False)
  • 50개 정점
  • 각 정점의 목표 차수를 Poisson(λ=2) 근사
• 실행 결과 예시:

  Undirected random graph created with 50 vertices and 40 edges.
  Degree of first vertex: 3

  (값은 무작위)

---

4. 예시 코드 2: 유향 그래프에서 (in,out) 형태의 정수 튜플

만약 유향 그래프(directed=True)를 생성하려면, deg_sampler()는 두 개의 정수(또는 float) (in_deg, out_deg)를 반환해야 합니다.

def example_random_graph_directed():
    """
    유향 그래프 random_graph() 예시:
    deg_sampler -> (in_degree, out_degree) 형태 튜플.
    """
    n = 30
    # in_degree, out_degree 각각 Poisson(2)로
    deg_sampler = lambda: (np.random.poisson(2), np.random.poisson(2))

    # 유향 그래프
    g = gt.random_graph(
        n,
        deg_sampler,
        directed=True
    )
    print("Directed random graph created with", g.num_vertices(), "vertices and", g.num_edges(), "edges.")

    # 임의 정보
    v0 = g.vertex(0)
    print("Vertex 0 in-degree:", v0.in_degree(), "out-degree:", v0.out_degree())

if __name__=="__main__":
    example_random_graph_directed()

4.1 코드 해설

• deg_sampler = lambda: (np.random.poisson(2), np.random.poisson(2))
  • in_deg ~ Poisson(2), out_deg ~ Poisson(2)
• directed=True → 내부적으로 유향간선 구성

---

5. (3,3)로 하면 왜 안 되나?

• lambda: (3,3)는 매번 (3,3)라는 고정 튜플을 반환
  • 이것 자체는 유향 그래프 생성용으로는 문제 없음 (in=3, out=3).
  • 하지만 directed=False인 무향 그래프 모드에서 (3,3)은 "단일 정수"가 아니므로 에러
• 따라서 무향이면 → lambda: 3 처럼 단일 값
• 유향이면 → lambda: (3,3) 가능(단, directed=True로 해야 함)

---

6. 결론 및 요약

• 무향 그래프를 random_graph()로 생성할 때:

  g = gt.random_graph(n, lambda: np.random.poisson(λ), directed=False)

  여기서 deg_sampler()는 단일 정수(혹은 float) 반환해야 함
• 유향 그래프에서는 (in_deg, out_deg) 형태의 튜플 반환 가능:

  g = gt.random_graph(n, lambda: (in_deg, out_deg), directed=True)

• (3,3)처럼 튜플을 고정으로 반환할 경우, 반드시 directed=True인지 확인해야 하며, 무향 그래프에서는 오류 발생

---

7. 종합 예시 + 오류 재현/해결

7.1 잘못된 코드 (오류 발생)

def bad_example():
    # 의도: 무향 그래프(50개 노드) & 차수 ~3
    # 근데 deg_sampler가 (3,3) 튜플을 반환
    g = gt.random_graph(
        50,
        lambda: (3,3),  # WRONG for undirected => error
        directed=False
    )
    # => 에러 발생!

7.2 올바른 코드 (오류 없이)

def good_example():
    # 1) 무향
    g_undirected = gt.random_graph(
        50,
        lambda: 3,   # 단일 int => 문제 없음
        directed=False
    )
    print("Undirected Graph:", g_undirected.num_vertices(), "vertices,", g_undirected.num_edges(), "edges")

    # 2) 유향, (in,out)
    g_directed = gt.random_graph(
        50,
        lambda: (3,3),  # (in=3, out=3)
        directed=True
    )
    print("Directed Graph:", g_directed.num_vertices(), "vertices,", g_directed.num_edges(), "edges")

---

최종 요약 튜토리얼

아래는 무작위 그래프를 만드는 올바른 예시 튜토리얼입니다.

• 무향 그래프엔 단일 차수
• 유향 그래프엔 (in_degree, out_degree) 튜플

import graph_tool.all as gt
import numpy as np

def tutorial_random_graph():
    """
    graph_tool의 random_graph() 함수를 이용해 무작위 그래프를 생성하는 예시.
    1) 무향 그래프 (단일 정수 반환)
    2) 유향 그래프 ((in,out) 튜플 반환)
    """

    # 1) 무향 그래프 -> deg_sampler(): 단일 정수
    def undirected_deg_sampler():
        # Poisson(λ=2)로 무작위 차수
        return np.random.poisson(2)

    g_undirected = gt.random_graph(
        50,
        undirected_deg_sampler,
        directed=False  # 무향
    )
    print("[Undirected] #V:", g_undirected.num_vertices(), "#E:", g_undirected.num_edges())

    # 2) 유향 그래프 -> deg_sampler(): (in,out) 형태
    def directed_deg_sampler():
        # in_deg, out_deg를 각각 2 평균의 포아송
        return (np.random.poisson(2), np.random.poisson(2))

    g_directed = gt.random_graph(
        50,
        directed_deg_sampler,
        directed=True   # 유향
    )
    print("[Directed]   #V:", g_directed.num_vertices(), "#E:", g_directed.num_edges())

if __name__=="__main__":
    tutorial_random_graph()

• 만약 (3,3)처럼 고정된 튜플을 반환하려면 반드시 directed=True를 사용해야 함.
• lambda: (3,3) + directed=False → 오류 발생 (무향에서는 단일 차수를 요구).

이렇게 하면 오류 없이 무작위 그래프를 생성할 수 있습니다.

아래 튜토리얼은 graph-tool 라이브러리의 vertex_similarity() 함수를 이용하여 정점 간 유사도(similarity) 값을 계산하고, 이를 활용하는 방법을 다룹니다. 초보자를 위해 파이썬 코드 예시, 친절한 한글 주석, 추가 활용 팁 등을 포함해 자세히 설명합니다.

---

1. 함수 개요

similarities = graph_tool.topology.vertex_similarity(
    g,
    sim_type="jaccard",         # "dice", "salton", "hub-promoted", ...
    vertex_pairs=None,          # 특정 정점 쌍에 대해서만 유사도 계산 (iterable)
    eweight=None,               # (옵션) 간선 가중치
    sim_map=None                # (옵션) 결과 저장할 vertex property map
)

• 입력

  • g: 사용될 그래프 (Graph 객체).
  • sim_type: 유사도 종류 (기본값: "jaccard"). 아래 표 참고.
  • vertex_pairs: 특정 정점 쌍만 대상. 생략 시 그래프의 모든 정점 쌍에 대해 계산.
  • eweight: (선택) EdgePropertyMap 형태의 간선 가중치.
  • sim_map: (선택) 만약 vertex_pairs=None일 때(즉 모든 쌍) 계산 결과를 저장할 vertex_property_map(vector type).

• 출력

  • similarities:
    1) 만약 vertex_pairs가 주어졌다면, 해당 쌍들에 대한 유사도를 담은 numpy.ndarray.
    2) vertex_pairs=None(모든 정점 쌍)일 경우, 유사도 행렬(혹은 2D정보)을 가진 vector-valued vertex_property_map.

1.1 지원되는 유사도 지표

sim_type	설명	공식 (G=무가중/단순그래프 기준)
"jaccard"	Jaccard 유사도	$\displaystyle \frac{
"dice"	Sørensen–Dice 계수	$\displaystyle \frac{2\,
"salton"	Salton (cosine) 유사도	$\displaystyle \frac{
"hub-promoted"	Hub-promoted similarity	$\displaystyle \frac{
"hub-suppressed"	Hub-suppressed similarity	$\displaystyle \frac{
"inv-log-weight"	Inverse log weighted similarity (Adamic-Adar 등)	$\displaystyle \sum_{x\in N(u)\cap N(v)} \frac{1}{\ln
"resource-allocation"	Resource allocation similarity	$\displaystyle \sum_{x\in N(u)\cap N(v)} \frac{1}{
"leicht-holme-newman"	Leicht-Holme-Newman similarity	$\displaystyle \frac{

$*$ leicht-holme-newman의 공식은 원문 참조.

무가중 그래프 기준 공식만 제시했으며, 가중/멀티그래프 시 A[u,v] (가중치/중복) 합산에 맞추어 수정 적용.

---

2. 예시: 모든 정점 쌍의 "jaccard" 유사도 계산

import graph_tool.all as gt
import numpy as np
import matplotlib.cm as cm

def example_vertex_similarity_jaccard():
    # 1) 무작위 그래프 생성(무방향)
    g = gt.random_graph(
        30,
        lambda: np.random.poisson(3),
        directed=False
    )

    # 2) "jaccard" 유사도로 모든 정점 쌍(sim_map에 저장)
    sim_map = gt.vertex_similarity(
        g,
        sim_type="jaccard",
        vertex_pairs=None,  # => 모든 정점 쌍
        eweight=None,       # 가중치 없다고 가정
        sim_map=None        # 새 property map 자동 생성
    )

    # sim_map: vector-valued VertexPropertyMap
    # sim_map[v][u] => v와 u 사이 jaccard 유사도 (float)
    
    # 3) 예: vertex 0과 나머지들의 유사도
    similarities_to_0 = sim_map[g.vertex(0)].a  # numpy array
    print("Jaccard similarity to vertex 0:", similarities_to_0)

    # 4) 시각화 or 분석
    # 예) 정점 컬러를 "vertex 0과의 jaccard 유사도"로 설정
    colorprop = g.new_vp("double")
    colorprop.a = similarities_to_0
    # graph_draw 등으로 시각화 가능 (생략)

if __name__=="__main__":
    example_vertex_similarity_jaccard()

2.1 실행 결과 예시

Jaccard similarity to vertex 0: [0.         0.33333333 0.2        0.25 ... ]

(길이는 30, 값은 무작위 그래프 구조에 따라 달라짐)

---

3. 예시: 특정 정점 쌍만 계산하기

vertex_pairs에 (u, v) 쌍 목록을 주면, 해당 쌍들만 계산하여 numpy 배열을 반환한다.

def example_vertex_similarity_pairs():
    g = gt.random_graph(20, lambda: np.random.poisson(2), directed=False)

    pairs = [
        (0,1), (0,5), (2,6), (3,7)
    ]
    # Salton similarity (cosine)
    result = gt.vertex_similarity(
        g,
        sim_type="salton",
        vertex_pairs=pairs
    )
    # => numpy.ndarray, shape=(len(pairs), )

    for p, val in zip(pairs, result):
        print(f"Salton sim between {p} = {val:.4f}")

실행 결과 예시:

Salton sim between (0,1) = 0.5164
Salton sim between (0,5) = 0.0000
Salton sim between (2,6) = 0.2582
Salton sim between (3,7) = 0.7746

---

4. 가중치 있는 그래프

가중치(EdgePropertyMap)가 있으면, 유사도 계산 시 A[u,v] (가중치) 기반으로 수정된 공식을 사용.
예시:

def example_vertex_similarity_weighted():
    # 유향 그래프
    g = gt.Graph(directed=True)
    vlist = [g.add_vertex() for _ in range(5)]
    # 간선
    e1 = g.add_edge(vlist[0], vlist[1])
    e2 = g.add_edge(vlist[0], vlist[2])
    e3 = g.add_edge(vlist[1], vlist[3])
    e4 = g.add_edge(vlist[2], vlist[3])
    e5 = g.add_edge(vlist[3], vlist[4])

    # 가중치 property
    wprop = g.new_edge_property("double")
    wprop[e1] = 1.5
    wprop[e2] = 2.0
    wprop[e3] = 0.5
    wprop[e4] = 0.8
    wprop[e5] = 2.5

    # "hub-promoted" similarity를 계산, 가중치 사용
    sim_map = gt.vertex_similarity(
        g,
        sim_type="hub-promoted",
        eweight=wprop,
        vertex_pairs=None
    )
    
    # vertex 0과의 similarity
    sim0 = sim_map[vlist[0]].a
    print("Hub-promoted similarity to v0:", sim0)

유향 그래프인 경우, "이웃"은 out-neighbors를 가정. in-neighbor 유사도를 원하면 GraphView(g, reversed=True)로 바꿔서 사용.

---

5. distance(=False) & asymmetric(=False) 옵션?

• distance=True → 유사도 대신 "그래프 간 거리" (1 - similarity 등)를 반환
• asymmetric=True → 비대칭 유사도( 예: set difference ) 적용
• 대부분 "jaccard" 등에서는 distance=False, asymmetric=False가 기본.

---

6. 복잡도

• vertex_pairs=None(전체 정점쌍) → $O(n^2$ 시간
• vertex_pairs 길이가 $m$ → $O(m$
• 병렬화(OpenMP) 지원 → 큰 그래프에서도 성능 개선 가능

---

7. 정리

vertex_similarity()는 그래프 내 각 정점쌍 사이의 이웃관계 (또는 가중치) 기반으로 여러 가지 well-known local similarity 지표( Jaccard, Dice, Salton 등 )를 간단히 계산할 수 있는 강력한 함수입니다.

• 모든 쌍 vs 특정 쌍
• 무향 vs 유향 (out-neighbor 기반, 필요 시 reversed GraphView)
• 무가중 vs 가중/멀티그래프

결과물인 similarity(혹은 distance)를 통해 링크 예측이나 그래프 분석 등에 활용 가능합니다.

아래 튜토리얼은 그래프 서브그래프 동형성(Subgraph Isomorphism) 문제를 다루고, 특히 Boost.Graph의 vf2_subgraph_iso(C++ API)에 대응하거나, graph-tool 등 파이썬 라이브러리를 통해 서브그래프 동형성을 판별하는 과정을 자세히 설명합니다.
이 튜토리얼은 서브그래프 동형성이 무엇인지, 왜 NP-완전인지, 어떤 알고리즘(예: VF2)들이 있는지, 그리고 파이썬 예제 코드(graph-tool 또는 유사)를 통해 실용적으로 문제에 접근하는 방안을 구체적으로 설명합니다.
(도시·교통 빅데이터, 네트워크 분석 전문가 시점에서, 초보자가 이해하기 쉽도록 한글 주석도 풍부히 담았습니다.)

---

1. 서브그래프 동형성(Subgraph Isomorphism)이란?

서브그래프 동형성이란, 두 그래프 $G$와 $H$가 주어졌을 때, $G$ 내부에 $H$와 ‘정확히 같은 구조’를 가진 부분 그래프가 존재하는지 판별하는 문제입니다.

• 즉 $H$가 $G$에 “포함(subgraph)”되어 있고, 동시에 간선 연결관계를 완벽히 일치시킬 수 있는 매핑(1:1대응)이 존재하는지를 묻습니다.
• 대표적으로, 클릭(clique), 해밀턴 사이클(Hamiltonian cycle) 등이 서브그래프 동형성의 특수 사례로 귀결되어, NP-완전임이 잘 알려져 있습니다.

1.1 예시 그림

• 그래프 $G$의 일부분을 보면(빨간색 서브그래프), 그래프 $H$와 정점/간선 구조가 완전히 같은 경우.

1.2 서브그래프 동형성 vs 그래프 동형성

• 그래프 동형성(Graph Isomorphism)은 전체 그래프가 동일 구조인지 판별.
• 서브그래프 동형성은 $G$의 부분만 보아도 $H$와 같은지.

---

2. 왜 NP-완전 문제인가?

• 서브그래프 동형성은 클릭 문제(NP-완전)의 일반화. 예: $H$를 $K_k$k개 정점의 완전그래프)로 잡으면, $G$에 $K_k$ 서브그래프 있는지 → 클릭 문제와 동일.
• 따라서 폴리노미얼 시간 안에(일반적인 경우) 해결 불가능이라 추정 (P=NP 미해결).
• 단, 특정한 그래프 클래스 (예: 트리, 외부플래너 그래프, 상수 크기 $H$) 에서는 다항시간 알고리즘이 존재.

---

3. 알고리즘 개요

서브그래프 동형성은 대표적으로 백트래킹(Backtracking) 기반 접근:
1. DFS/백트래킹으로 $H$의 각 정점을 $G$ 내부 정점에 매핑 시도
2. 매핑 중간에 정점/간선 호환성(Equivalence predicate) 어긋나면 백트래킹
3. 모든 정점 매핑 완료 → 성공 시 subgraph isomorphism 성립

3.1 VF2 알고리즘

• Cordella 등(2001, 2004)에 의해 제안된 VF2 알고리즘이 유명
• 정점 순서 선정 + 수색 공간 압축 + 프루닝(Pruning)
• Boost.Graph의 vf2_subgraph_iso 함수가 이를 구현.

3.2 Ullmann, VF2, VF3 …

• Ullmann(1976)의 초기 알고리즘
• VF2(2004년) → 메모리 절감, 휴리스틱 개선
• VF3(2018년) → 더욱 대규모 그래프도 빠르게 처리

---

4. 파이썬 graph-tool 예시 (유사)

graph-tool에서 현재(2024년) 직접적인 subgraph_isomorphism() 함수는 공식 문서에 없을 수 있습니다. 그러나 유사하게, 탐색 알고리즘이나 topology 하위 모듈에서 subgraph_isomorphism(Beta/테스트 버전) 시도할 수 있습니다. (또는 Boost.Python 바인딩으로 직접 VF2를 호출하는 방식.)

아래 예시는 “개념적” 예제 코드로, 실제 graph_tool.topology 내 (가칭) subgraph_isomorphism 함수를 가정:

import graph_tool.all as gt

def subgraph_iso_example():
    # 1) 작은 그래프 g_small
    g_small = gt.Graph(directed=False)
    vs_small = [g_small.add_vertex() for _ in range(4)]
    # 간선 (사각형)
    g_small.add_edge(vs_small[0], vs_small[1])
    g_small.add_edge(vs_small[1], vs_small[2])
    g_small.add_edge(vs_small[2], vs_small[3])
    g_small.add_edge(vs_small[3], vs_small[0])

    # 2) 큰 그래프 g_large
    g_large = gt.Graph(directed=False)
    vs_large = [g_large.add_vertex() for _ in range(6)]
    # 간선: (0--1--2--3), (4--5) + (2--4), (1--5) ...
    g_large.add_edge(vs_large[0], vs_large[1])
    g_large.add_edge(vs_large[1], vs_large[2])
    g_large.add_edge(vs_large[2], vs_large[3])
    g_large.add_edge(vs_large[2], vs_large[4])
    g_large.add_edge(vs_large[4], vs_large[5])
    g_large.add_edge(vs_large[1], vs_large[5])  # 임의로 추가

    # 3) (가정) subgraph_isomorphism 호출
    # return 형식: iterator or list of dict-like mapping
    # !! 실제 graph-tool에는 정식 API가 아닐 수 있으니 가상의 예시임.
    iso_mappings = subgraph_isomorphism(g_small, g_large)

    if not iso_mappings:
        print("No subgraph isomorphic to g_small found in g_large.")
        return

    print("Found subgraph isomorphisms:")
    for mapping in iso_mappings:
        # mapping: g_small 정점 -> g_large 정점
        # 예) {0:2, 1:1, 2:5, 3:4}
        print(mapping)

if __name__=="__main__":
    subgraph_iso_example()

주의: 이 코드는 실제로 graph_tool 최신 버전에서 동작하지 않을 수 있습니다(공식 subgraph_isomorphism가 없거나, 별도 브랜치에 있을 가능성).
그러나 개념적으로 VF2 또는 유사 알고리즘을 Python 레벨에서 호출해, “g_small가 g_large 내부 어느 부분과 구조 일치?”를 찾을 수 있음을 보여주는 예시입니다.

---

5. Boost Graph Library (C++): vf2_subgraph_iso

Boost C++ 라이브러리에서는:

bool vf2_subgraph_iso(
  const GraphSmall& graph_small,
  const GraphLarge& graph_large,
  SubGraphIsoMapCallback user_callback
  /* 기타 파라미터... */
);

• user_callback: 서브그래프 동형성을 만족하는 매핑이 발견될 때마다 콜백으로 호출
• 매핑 전체를 나열하거나, 하나만 찾고 종료 가능

예)

// pseudo-code for callback:
struct my_callback {
  template <typename MapSmallToLarge, typename MapLargeToSmall>
  bool operator()(MapSmallToLarge f, MapLargeToSmall g) {
    // f(v_s) = v_l
    // ... do something with mapping ...
    // return false => stop searching
    return true;
  }
};

---

6. 알고리즘적 상세

6.1 VF2 알고리즘 요약

1. 탐색 상태(state) = 현재까지 매핑된 정점 쌍(부분 매핑)
2. 후보 정점(next vertex in graph_small)을 pick
3. graph_large의 어떤 정점이 이와 호환되는지(간선 eq/ 정점 eq) 체크
4. 매핑 확장 → 백트래킹

시간복잡도: 최악에선 $O(V!$, 하지만 실제로는 많은 pruning 덕에 빨라질 수 있음.

6.2 Equivalence Predicate

• 정점/간선에 대한 “동등함” 기준을 정의
  • 예) 라벨이 동일해야 한다
  • 예) 가중치 ± 일정 범위여야 한다

---

7. 활용 예

1. 화학물질 분자 구조: 부분구조 검색 (SMARTS vs SMILES)
2. 사회·교통망: 특정 패턴(서브그래프) 존재 여부
3. 패턴 마이닝(graph mining)
4. 전자회로: 부분회로 매칭

---

8. 결론

• 서브그래프 동형성: NP-완전하지만, 실제로는 VF2, VF3 등으로 중간 규모 그래프에 대해 빠른 해법 가능
• graph-tool에는(공식) subgraph_isomorphism API가 완비되지 않았을 수 있음, 그러나 원리상 C++ Boost Graph vf2_subgraph_iso에 대응 가능.
• 정점·간선 특성(invariant, equivalence predicate)을 잘 활용하면 pruning↑, 성능↑

정리:

• 서브그래프 동형성 문제는 응용분야가 매우 넓고, NP-완전이지만 효율적 휴리스틱/알고리즘(VF2 등) 활용 시 충분히 유용.
• graph-tool(Python) 혹은 Boost.Graph(C++)에서 VF2 기반 함수를 호출 → 원하는 서브그래프 매핑을 찾거나, 존재 여부를 판별.

이로써, 서브그래프 동형성 문제와 관련된 개념, NP-완전성, 대표 알고리즘(VF2) 구조, 간단한 Python 예시 등을 모두 살펴보았습니다.

아래 튜토리얼은 “(Sub)Graph Isomorphism Algorithm for Matching Large Graphs” (Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, and Mario Vento) 논문의 주요 내용을 중심으로, 서브그래프 동형성(Subgraph Isomorphism) 문제와 해당 알고리즘(VF, VF2)을 도시·교통 빅데이터(분산처리), 네트워크 분석에 적용할 수 있는 관점에서, 개념, 수식, 원리, 구현 순으로 최대한 자세히 설명합니다.
본 튜토리얼은 초보자가 이해하기 쉽게 한글 주석과 파이썬 예시 등을 포함합니다.

---

1. 서브그래프 동형성(Subgraph Isomorphism)이란?

• 정의
  서브그래프 동형성 문제는 두 그래프 $ G_1 = (V_1, E_1와 $ G_2 = (V_2, E_2가 주어졌을 때, $ G_1 $ 내부에 $ G_2 $와 ‘정확히 동일한 구조’를 가진 부분 그래프가 존재하는지를 판별하는 문제입니다.

  • 만약 $ G_2 $가 $ G_1 $의 부분그래프로서 모든 간선 연결 관계가 1:1 대응으로 일치한다면, 서브그래프 동형성 성립.
  • 서브그래프 동형성은 그래프 동형성(Graph Isomorphism), 클릭 문제(Clique), 해밀턴 경로 문제 등과 밀접하며, NP-완전임이 알려져 있습니다.

• 왜 중요한가?

  • 도시·교통망에서 특정한 패턴이 실제 네트워크에 존재하는지 (예: 특정 형태의 교통 흐름, 특정 서브패턴)
  • 화학 분자 구조(그래프)에서 부분 구조 검색(기능기 반)
  • 이미지나 도면(기술 도면)의 부품 검색
  • 해당 문제는 일반적으로 지수 시간이 걸릴 수 있으나, 휴리스틱/알고리즘 최적화(VF2, Ullmann, Nauty 등)로 실제 중간 크기 그래프까지는 해결 가능.

---

2. 논문 요약: Cordella 등 (VF, VF2 알고리즘)

Cordella 등은 2001년, 2004년에 걸쳐 VF(VF2) 라 불리는 (Sub)Graph Isomorphism 알고리즘을 제안했습니다.

• 특징
  1. State Space Representation (SSR) : 매핑을 구성하면서, “현재까지 매핑된 정점 쌍”을 하나의 상태(state)로 보며, 깊이 우선 탐색(DFS)과 백트래킹으로 해결.
  2. Feasibility Rules : 부분 매핑을 확장할 때마다, 구조적/속성적 제약을 빠르게 검사해 불필요한 백트래킹 가지를 줄임.
  3. Attributed Graph(속성 그래프)도 처리 가능: 정점·간선의 속성(길이, 라벨 등)을 일치 검사(semantic feasibility)로 조합해 pruning.
  4. 메모리 절감: 큰 그래프에서 백트래킹 시, 이전 상태들을 복사하지 않고, 필요한 정보만 갱신/복원.

이 논문의 기여
1. VF 알고리즘을 개선(VF2) → 메모리 사용량이 줄고, 대형 그래프에서 더욱 효율적.
2. 랜덤 그래프·실제 어플리케이션(기술 도면 등)에서 Ullmann(1976)보다 상당히 빠른 성능 시연.

---

3. 수식·원리: 상태 공간(SSR)과 Feasibility

3.1 상태 공간 (State Space Representation)

1. 매핑 $ M(s) = {(n_1, m_1), (n_2, m_2), \dots} $ : 그래프 $ G_1 $의 정점 $ n_i $을 $ G_2 $의 정점 $ m_i $로 대응시킨 집합.
2. 부분그래프 $ G_1(s), G_2(s$ : 매핑에 의해 매칭된 정점/간선만 모아놓은 그래프.
3. 서브그래프 동형성을 만족하려면, 각 단계에서 확장되는 매핑 $ M(s이 “여전히 유효”해야 함 → Feasibility function $ F(s; n, m 이용.

3.2 Feasibility Rules

논문에서는 5가지 룰(Rpred, Rsucc, Rin, Rout, Rnew)을 제안하여, 부분 매핑이 더 확장될 수 있는지 판단:

1. Rpred, Rsucc : 매핑된 정점 간 선행/후행(Predecessor/Successor) 관계가 양 그래프에서 호환되는지 검사

   • $ R\mathrm{pred}(s,n,m) \land R\mathrm{succ}(s,n,m$

2. Rin, Rout : 1-단계 look-ahead.

   • $ R_\mathrm{in} $은 새로 매핑된 정점이 가져야 할 “들어오는 간선” 개수가 적절히 대응되는지.
   • $ R_\mathrm{out} $은 “나가는 간선” 개수 대응 확인.

3. Rnew : 2-단계 look-ahead(좀더 넓은 정점 후보군).

   • 매핑되지 않은 인접 정점 개수 등을 비교.

만약 이들 규칙 중 하나라도 만족 안 하면, 가지치기(백트래킹)하여 탐색 중단.

3.3 Syntactic + Semantic Feasibility

1. Syntactic 부분($ F_\mathrm{syn} $) : 위 5가지 규칙 (구조적 일치)
2. Semantic($ F_\mathrm{sem} $) : 정점·간선 속성이 일치하는지.
   • 예) 정점 라벨이 동일, 혹은 간선 길이/방향 차이가 임계값 이하 등.
   • $ F(s; n, m) = F\mathrm{syn}(s,n,m) \land F\mathrm{sem}(s,n,m$

---

4. 알고리즘 개요 (VF2)

![Pseudocode]

VF2_Match(G1, G2, state):
    if 모든 정점이 매핑되었다면:
        return SUCCESS (혹은 매핑을 callback)
    
    P = 후보 정점 쌍 집합 (SSR기반)
    for (n, m) in P:
        if F(s, n, m) == True:   # feasibility check
            state.push(n, m)
            VF2_Match(G1, G2, state)
            state.pop(n, m)
    return

• 후보 쌍 $ P(s$ 계산: “이미 매핑된 정점”에 인접한 정점(둘 다)에 대해, 가능한 쌍만 나열.
• Feasibility: 앞서 말한 규칙 + 속성 체크.
• DFS + Backtracking: 더 이상 유효한 확장 없으면 백트래킹.

---

5. 구현 및 Python 예시

graph-tool에는 공식 subgraph_isomorphism()가 없지만, 논문 방식(VF2)을 Python으로 예시해볼 수 있습니다.
아래 코드는 개념적이며, 실제 대규모 그래프 시 최적화·C++ 연동 등 필요.

import sys

class VF2State:
    def __init__(self, G1, G2):
        self.G1 = G1
        self.G2 = G2
        # core_1[v] = 매핑된 G2 정점 (or None)
        self.core_1 = [None]*G1.num_vertices()
        # core_2[u] = 매핑된 G1 정점 (or None)
        self.core_2 = [None]*G2.num_vertices()
        
        # in_1, out_1, in_2, out_2 → terminal set membership
        self.in_1 = [0]*G1.num_vertices()
        self.out_1= [0]*G1.num_vertices()
        self.in_2 = [0]*G2.num_vertices()
        self.out_2= [0]*G2.num_vertices()
        
        self.depth = 0  # 현재 매핑된 정점 수(혹은 탐색 depth)

    def match(self, solution_callback):
        # 만약 모든 정점(혹은 subgraph 조건)이 만족되면 성공
        if self.depth == self.G1.num_vertices():
            # => G1 전체가 G2의 부분그래프로 매칭됨(=이건 Isomorphism case)
            # Subgraph Isomorphism시, 원하는 개수만큼 매핑할 수도.
            solution_callback(self.core_1)  # or pass mapping
            return
        
        # 1) 후보 P(s) 계산
        P = self.compute_candidate_pairs()
        
        for (n, m) in P:
            if self.feasibility(n, m):
                # 매핑 확장
                self.core_1[n] = m
                self.core_2[m] = n
                self.depth += 1

                # in/out update, skip

                # 재귀
                self.match(solution_callback)

                # backtrack
                self.core_1[n] = None
                self.core_2[m] = None
                self.depth -= 1
    
    def compute_candidate_pairs(self):
        # SSR기반으로 Tin, Tout 집합 등 계산
        # 간단히: 아직 매핑 안된 정점들 중
        #         한쪽 그래프 정점 n, 다른쪽 그래프 정점 m
        #         => yield (n, m)
        candidates = []
        # (실제론 in_1/out_1/in_2/out_2를 사용)
        # 여기선 간단하게 모든 미매핑 정점 쌍
        for n in range(self.G1.num_vertices()):
            if self.core_1[n] is None:
                for m in range(self.G2.num_vertices()):
                    if self.core_2[m] is None:
                        candidates.append((n,m))
        return candidates
    
    def feasibility(self, n, m):
        # 1) 구조적(Rpred, Rsucc, etc)
        # 2) 속성(semantic)
        # (실제로는 check edges, in/out등)
        # 여기서는 간단히 pass
        return True


def subgraph_isomorphism(G1, G2, callback=print):
    """
    G1, G2: 그래프(임의)
    callback: 매핑 발견 시 호출
    """
    state = VF2State(G1, G2)
    state.match(callback)

• 위 코드는 동작 원리만 보여주며, Feasibility 구현이 간소화됨. 실제 구현은 Cordella/VF2 논문에 나온 5가지 규칙(Rpred, Rsucc, Rin, Rout, Rnew) + attribute check(semantic) 추가 필요.
• 또한, “매핑이 G2의 부분그래프로 제한되는지(=subgraph), 또는 G1 전체 = G2 전체인지(=isomorphism)”에 따라 depth 조건/규칙이 조금 달라짐.

---

6. 복잡도 & 성능

1. 시간 복잡도

   • 최악 $ O(V!$V는 정점 수).
   • 실제로는 pruning 효과로 대부분 예시에서 훨씬 빠름.
   • Cordella 등은 large graph(수천 노드)에서도 효율적임을 시연.

2. 메모리

   • VF2는 Core vectors($ \mathrm{core_1}, \mathrm{core_2}, \mathrm{in_1}, \mathrm{out_1}, \dots $)를 재사용하여, 백트래킹 시 값을 복원 → **$ O(V$**로 억제.

3. 실험 결과(논문):

   • Ullmann(1976)과 비교시, 대형 그래프(수백~수천 노드)에서 VF2가 훨씬 빠름.
   • Nauty와 비교: Nauty는 Graph Isomorphism 한정, VF2는 Subgraph Isomorphism 전용 시나리오에선 VF2가 유리.

---

7. 실제 예시: 기술 도면(부품 서브그래프 매칭)

논문에 따르면, 기술 도면(라인 드로잉)을 그래프로 변환하여 부품 서브그래프를 찾는 문제에서 VF2가 강력한 성능을 보임:

• 정점: 코너/교차점
• 간선: 선분 (속성: 길이, 방향)
• 부분 패턴(부품)을 그래프로 표현 → 대형 도면 그래프에서 VF2로 검색 → 성능이 Ullmann 대비 수백~수천 배 개선 (논문 Fig. 3 등).

---

8. 정리 및 결론

• VF2 알고리즘은 서브그래프(혹은 그래프) 동형성 문제를 속성 그래프에서도 처리하며, 대형 그래프에서도 메모리·시간 성능을 상당히 개선함.
• 논문 기여:
  1. Feasibility Rules (SSR)
  2. 메모리 효율적 자료구조
  3. 실제 대형 이미지/도면 데이터셋에서 효과 입증
• 파이썬/graph-tool에서 공식 Subgraph Isomorphism는 미완비일 수 있으나, VF2 개념을 응용한 코드(혹은 Boost.Python 연동)로 구현 가능.
• 도시·교통 빅데이터 관점: 특정 교차·도로 구조(“sub-patten”)가 실제 지도그래프에 존재하는지 여부, 분산처리로 확장 시도 가능(하지만 NP-완전).
• 결론: Cordella 등(2004)의 VF2 알고리즘은 서브그래프 동형성 문제 해결의 핵심적 접근이며, 다양한 실전 응용에서 유용.

---

참고 문헌

1. Cordella, L. P., Foggia, P., Sansone, C., & Vento, M. (2004). A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs. IEEE Trans. PAMI, 26(10), 1367-1372.
2. Ullmann, J. R. (1976). An algorithm for subgraph isomorphism. J. of the ACM, 23(1):31-42.
3. Nauty: B. D. McKay, http://cs.anu.edu.au/~bdm/nauty
4. M. Burge, W. Kropatsch, “Minimal line property preserving representation for line images,” Computing, (1999).

(끝)

아래 설명은 Tomita, Tanaka, Takahashi (2006) 논문("The worst-case time complexity for generating all maximal cliques and computational experiments" / Theoretical Computer Science 363, pp. 28–42)을 기반으로, 무방향 그래프에서 모든 최대 클리크(Maximal Clique) 목록을 생성하는 알고리즘과 해당 알고리즘의 최악 사례 시간 복잡도를 자세히 살펴봅니다. 특히 수학적 개념과 원리에 중점을 두어 최대한 정성스럽게 정리합니다.

---

1. 문제 개요: 최대 클리크 열거

• 클리크(clique): 무방향 그래프 $ G=(V,E$에서, 임의의 두 정점이 모두 인접하는 완전 부분 그래프.
• 최대 클리크(maximal clique): 더 이상 확장할 수 없는(즉, 다른 클리크의 ‘진부분그래프’가 아닌) 클리크.
• 목표: 그래프 $ G $ 안의 모든 최대 클리크를 중복 없이 열거(생성)하는 알고리즘을 설계하고, 그 최악 시간 복잡도를 분석.

1.1 관련성

• 최대 독립집합(maximal independent set) 열거와 동등: 그래프 $ G $의 여 그래프(보완그래프, complement graph)를 생각하면 최대 클리크는 $ G $의 최대 독립집합과 일대일 대응.
• 브론-커보쉬(Bron-Kerbosch) 알고리즘(1973)이 깊이우선탐색 기반으로 최대 클리크를 열거하는 대표적 방법. 하지만 본 논문에서는 별도의 출력 형식 최적화를 통해 이론적 최악 시간 복잡도 $O(3^{n/3}$를 증명.
• Moon & Moser (1965)에 따르면, $ n $개의 정점을 가진 그래프가 가질 수 있는 최대 클리크의 개수는 최악의 경우 $3^{n/3}$ 정도로 클 수 있음 → 이 수치가 열거 알고리즘 관점에서 ‘이론적 하한’ 역할.

---

2. 그래프 및 표기

• 그래프: 무방향 $ G = (V,E$, 다중 간선이나 루프 없음(simple graph).
• 인접(Adjacent): 두 정점 $v, w$가 $v,w) \in E $이면 인접.
• $\Gamma(v$: 정점 $ v $와 인접한 정점들의 집합.
• 유도 부분그래프 $ G(W$: $ W \subseteq V $에 대한 부분그래프로, $ W $ 내에서 가능한 모든 간선을 포함.
• $ |W| $는 집합 $ W $의 원소 개수.

---

3. 알고리즘 개요 (CLIQUES)

3.1 깊이 우선 탐색(DFS) 구조

1. 전역 변수 $ Q $: 현재까지 확장된 클리크(아직 최대인지 불분명).

2. SUBG $ = \bigcap_{p_i \in Q} \Gamma(p_i$또는 $ V $에서 $ Q $ 모든 정점과 공통으로 인접한 부분).

   • 처음에는 $ Q=\emptyset$, $ SUBG = V $.
   • $ SUBG = \emptyset 이면 $ Q $는 더 확장 불가 → 이 시점에서 $Q가 최대 클리크이면 출력.

3. 재귀함수 $ \text{EXPAND}(SUBG, CAND$:

   • $CAND$는 “아직 탐색해야 할 후보(candidates)” 정점 집합.
   • $FINI$는 “이미 탐색 끝난(finished)” 정점 집합. 즉, $ SUBG = FINI \cup CAND, \, FINI \cap CAND = \emptyset $.
   • DFS로 $CAND$ 내부의 정점을 하나씩 선택해 $ Q $에 추가하고, 그와 동시 인접하는 후보들로 SUBGq 갱신 → 재귀.
   • 이때 가지치기(Pruning) 두 가지 사용 (아래 3.2 참조).

3.2 주요 가지치기 원리

1. 이미 탐색 완료한 FINI 정점은 재확장 X
   • 이유: FINI 소속 어떤 정점을 사용해 클리크를 확장했다면, 그 정점에 대한 모든 최대 클리크 이미 생성됨.
2. 피벗 정점(pivot$u$ 선택 후 $SUBG - \Gamma(u)$쪽만 탐색
   • $ u \in SUBG $ 중, $ CAND \cap \Gamma(u$가 최대가 되도록 $ u $ 선택. (Heuristic)
   • $ SUBG - \Gamma(u$에 속하는 정점으로 확장해도, “$ Q \cup {u} $”가 아닌 새로운 최대 클리크를 찾을 수 있다고 보장.
   • 이런 방식으로, 재귀 깊이를 줄이거나 중복 탐색 감소.

3.3 출력 형식 최적화

• Bron–Kerbosch 등 기존 방법: 각 최대 클리크를 정점 리스트로 직접 출력 → 최악 경우 $ n \cdot 3^{n/3} $ 시간.
• 이 논문(CLIQUES) 방식:
  • “clique,” 라는 문자열만 출력(클리크 자체는 한꺼번에 전체 정점을 나열X).
  • 재귀 진행할 때 정점 추가마다 “q,”, 재귀 빠져나올 때 “back,”를 출력.
  • 이렇게 하면, 최악 시간 복잡도를 $ O(3^{n/3}$로 증명 가능(출력 문자열 길이를 일정 수준 억제).

---

4. 시간 복잡도 증명 (최악 경우 $ O(3^{n/3}$)

4.1 정의

• $ T(n: $ |SUBG| = n $일 때, $ \text{EXPAND}(SUBG, CAND의 최악 실행 시간.
• $ P(n: 재귀 대신 “더 이상 자식 호출 없이” 처리한다고 가정하는 비재귀판 `EXPAND0`의 시간. 대략 $ O(n^2 가정 → $P(n) = p_1 n^2$.
• $ T_k(n: (일부 상황에서) 첫 번째 pivot에서 $k개의 재귀가 발생할 때의 실행 시간.

4.2 핵심 보조정리 (Lemma 2)

• 첫 pivot $u$를 골라, CAND - \Gamma(u)) = \{v_1,\dots, v_k\} $크기 $k).
• 각 $v_i$ 선택 후, $ SUBG_{v_i} = SUBG \cap \Gamma(v_i$로 재귀.
• $ Tk(n) \le \sum{i=1}^{k} T( | SUBG_{v_i} | ) \;+\; P(n). $
• 또한 $| SUBG_{v_i} | \le n-1$이 성립 (가지치기 적용 후).

4.3 본론 증명 (Theorem 3)

1. 수식
   $T(n) \;\le\; C \cdot 3^{n/3} \;-\; Q(n),$
   • 여기서 $ Q(n) = q_1 n^2 + q_2 n + q_3 $ 는 다항 항,
   • $ C = \max{C_1, C_2, C_3} $는 적절한 상수($p_1$ 등과 연관).
2. 증명 스케치
   • $ n=1 $일 때, $ T(1) = P(1) = p_1 $이므로 성립.
   • 가정: $ T(m) \le C\,3^{m/3} - Q(m$ 가 $ m \le N $에서 성립.
   • $ n = N+1 $에 대해서, Lemma 2(i)를 이용해$
     Tk(n) \;\le\; \sum T(|SUBG{vi}|) \;+\; P(n).
     $$
     \le \sum \bigl[C\,3^{|SUBG{vi}|/3} - Q(|SUBG{v_i}|)\bigr] + P(n).
     $
   • $ |SUBG{v_i}| \le n-1 $ 이므로, $ C\,3^{|SUBG{v_i}|/3} \le C\,3^{(n-1)/3} = 3^{-1/3}\,C\,3^{n/3} $.
   • 세부 인수 분해와 부등호 처리로, 최종 $ T(n) \le C 3^{n/3} - Q(n$ 유도.
   • 이는 곧 $ T(n) = O(3^{n/3}$.

4.4 의미

• Moon–Moser(1965): $n$-정점 그래프에서 최대 클리크의 개수가 최악 $ 3^{n/3}$개 가능.
• 본 논문 알고리즘은 $ O(3^{n/3}$ 시간에 모든 최대 클리크를 열거 → 정점 개수 기준으로 최적(tight bound).

4.5 만약 각 최대 클리크를 정점 리스트로 직접 출력하면?

• 출력 자체에 $O(n$ 시간이 걸리므로, 결과적으로 $n \cdot 3^{n/3}$이 됨 → 여전히 지수적.

---

5. 실험 및 비교

• 논문에서는 CLIQUES(본 알고리즘) vs. 다른 열거 알고리즘(예: Tsukiyama et al., Makino & Uno, Chiba & Nishizeki 등) 수행 시간을 Pentium4 등 환경에서 비교 실험.
• 결과:
  • 무작위 그래프, Moon–Moser 그래프, DIMACS 벤치마크 등에서 CLIQUES 알고리즘이 여러 경우 빠른 성능.
  • 매우 희소(sparse)하거나, 최대 클리크 개수가 극도로 적은 특수 그래프에서는 다른 방법(Makino & Uno의 변형)도 빠를 수 있지만, 전반적으로 CLIQUES가 우수.

---

6. 결론 및 의의

1. 깊이우선탐색(DFS) + 가지치기로 모든 최대 클리크를 생성.
2. 출력 형식을 최적화(각 클리크 자체를 전부 출력하지 않고, “clique,”/“back,” 등으로 트리 구조로 표현)함으로써, 이론적 최악 시간 $O(3^{n/3}$ 증명.
3. 문헌상 Moon–Moser 그래프의 최대 클리크 수가 $3^{n/3}$까지 가능 → 본 알고리즘이 사실상 가능한 최적(Order-Optimal).
4. 실험적으로도 타 알고리즘 대비 빠른 수행시간 관찰.

후속:

• 최대 극값 문제 vs. 열거 문제: Tarjan & Trojanowski (1977), Robson (1986) 등은 하나의 최대 독립집합(클리크)만 찾는 알고리즘이 $O(2^{n/3}$ 등 다소 빠르다. 하지만 “모든” 최대 클리크를 찾을 때는 $3^{n/3}$이 근본적 한계.
• 추가 적용: 이 DFS 열거 방식은 최대 클리크 문제(혹은 최대 독립집합) 외에도 생물정보학, 화학구조 비교, 소셜네트워크 분석에서 유용.

---

부록: 주요 증명 스케치

(A) Theorem 1 (Correctness)

• 알고리즘이 모든 최대 클리크를 중복 없이 찾음을 증명.
• 핵심 아이디어: 재귀적으로, 이미 처리된 FINI와 새 후보 CAND로 분할해서 중복 없는 열거가 가능.
• 이 과정을 귀납(Induction)과정으로 살펴보면, 각 단계에서 새로운 클리크가 나오거나 이미 처리된 정점을 포함하는 클리크는 이전에 다 열거됨을 보장.

(B) Theorem 3 (Worst-case $ O(3^{n/3}$)

• Lemma 2를 기반으로 귀납적(unrolling) 계수를 정밀 계산.
• 최종적으로 $ T(n) \leq C \cdot 3^{n/3} - Q(n$ 형태로 귀결 → 빅오표기 $ O(3^{n/3}$ 획득.
• Moon–Moser 그래프 예시에서 최대 $3^{n/3}$개의 최대 클리크 존재 → matching upper bound.

---

마무리

• 본 논문은 모든 최대 클리크 열거에 대해, 이론적으로 최적($O(3^{n/3}$)임을 최초로 엄밀히 증명했다는 점이 핵심.
• 알고리즘 CLIQUES는 심플하고 구현 용이하며, 실제 실험에서도 효율성이 좋음을 보였다.
• 더 세부 증명(귀납, 부등식 처리)과 구현 세부는 원문을 참조할 것.

아래 설명은 Cazals, Karande (2008)의 논문("A note on the problem of reporting maximal cliques") 내용을 토대로, 모든 최대 클리크를 찾는 문제(Maximal Clique Enumeration)와 관련한 알고리즘들의 핵심 개념과 원리를 정리한 것입니다. 특히, Bron–Kerbosch (1973) 알고리즘과 그 변형들, Koch (2001), 그리고 Tomita et al. (2006) 알고리즘 간의 연관성과 차이점을 수식과 함께 상세히 다룹니다.

---

1. 문제 배경

1.1 최대 클리크 문제

• 최대 클리크(Maximal Clique): 무방향 그래프 $ G = (V,E에서, 부분집합 $R \subseteq V가 모든 정점 쌍이 인접(완전 그래프)이고, 추가로 더 이상 확장할 수 없는(진부분 집합으로 더 큰 완전 그래프가 없는) 클리크를 말한다.
• 최대 클리크 열거(모든 maximal clique 나열)는 사회망 분석, 생물정보학, 패턴인식 등 다양한 분야에서 중요하게 쓰인다.

1.2 최대 클리크 vs. 최대가중치 클리크

• 최대 가중치 클리크 문제(Maximum Weight Clique): 주어진 그래프에서 가중치 합이 최대인 클리크를 하나 찾는 문제.
• 모든 최대 클리크 열거: 그래프 안에 가능한 모든 maximal clique를 중복 없이 찾는 문제.
  • 이 문제는 최악의 경우 출력 크기(모든 최대 클리크 수)가 지수적($3^{n/3}$ 수준)일 수 있으므로, 일반적으로 입력 크기만으로 다룰 수 없는 출력민감(즉, output-sensitive) 문제이다.

1.3 문헌 배경

• Bron–Kerbosch (1973): 깊이 우선 탐색(DFS) 기반으로 최대 클리크를 열거하는 고전적인 알고리즘 두 버전(Version 1, Version 2)을 제안.
• Koch (2001): Bron–Kerbosch 기반 변형(“IK"로 불리는 알고리즘들)을 정교화. 특히, 피벗(pivot)을 어떻게 선택하는지에 따라 성능이 달라짐을 체계적으로 분석.
• Tomita et al. (2006): 피벗을 $P \cup X\ 중에서 선택하는 방법으로, 최악 사례에서 $O(3^{n/3}$ 시간이 걸린다는 점을 이론적으로 증명함.

본 논문(Cazals & Karande, 2008)은 위 세 접근을 서로 비교·정리하여, 결국 (1) Koch가 언급하였으나 활용하지 않았던 “$P \cup X\에서 피벗을 고르는” 아이디어가, (2) Tomita 등 알고리즘과 사실상 동일함을 보임.

---

2. Bron–Kerbosch 알고리즘 계열 정리

2.1 Bron–Kerbosch 기본(Version 1)

다음과 같은 세 집합을 사용:

• $ R $: 현재 구성 중인 클리크(또는 그 후보)
• $ P $: 확장할 가능성이 있는 정점들(candidates)
• $ X $: 이미 처리된 정점들(finished), 즉 이전 단계에서 이미 고려되어 최대 클리크가 생성된 정점

Bron–Kerbosch(Version 1) 의 핵심 아이디어(그림 1 참조):
1. $ R 을 클리크 후보로 유지하며, $ P $에 있는 정점을 하나씩 추가(R \cup {v})해 재귀적으로 탐색. 2. 만약 $ P = \emptyset $이고 $ X = \emptyset $이면, $ R $은 최대 클리크로 출력(왜냐하면 더 이상 확장할 정점 없음 + 이미 처리된 정점도 없음). 3. 한편, $X에 속한 정점들은 이미 처리되었으므로, 중복 생성을 막기 위해 이들을 다시 선택하지 않음.

이 알고리즘은 최악의 경우 시간 복잡도가 매우 크며, 특히 “비최대 클리크”를 모두 한 번씩 탐색(완성된 뒤에야 비최대임을 알게 됨)한다는 점에서 지수적 중복이 발생할 수 있다.

---

2.2 Bron–Kerbosch Version 2와 Koch의 피벗 선택

Version 2 (Bron–Kerbosch 원 논문 내)에서는 “피벗(pivot)” 개념을 도입해 중복/불필요 탐색을 줄인다. 아이디어:

• 임의의 피벗 정점 $u$를 $ P 또는 $P \cup X)에서 선택.
• $P$을 두 부분집합으로 나눔:
  1. $P^- = P \cap \Gamma(u$: 피벗 $u$와 인접한 정점들
  2. $P^+ = P - P^-$: 피벗 $u$와 인접하지 않은 정점들

이유: $P^-$ 내 정점들을 단독으로 $R$에 추가해서는, $u$로 더 확장 가능한 여지가 있기 때문에 그것만으로 최대 클리크가 되지 않는다. 따라서 maximal clique를 만들려면 반드시 $P^+\ 중 적어도 하나를 골라야 한다. (이걸 “건너뛰기(pruning)”로 활용)

Koch(2001)은 피벗 선택 전략을 다양히 실험:

• IK_RP: 피벗을 $P$ 안에서 무작위(R) 선택
• IK_GP: 피벗을 $P$ 안에서 차수가 가장 큰 것(G) 선택
• IK_*$P \cup X$: 피벗을 $P \cup X$ 안에서 선택 (논문 내 이론적 가능성은 언급했지만 실제 구현은 안함)

Koch의 문제점:

• 예: 그래프 $K_1, n \cup K_n$즉, 점 1개와 n개가 완전연결된 구조 + 또다른 n정점 완전그래프). 이 때 피벗을 $P$에서만 고르려 하면, 재귀 호출의 가지치기가 크게 줄지 않아 $O(n^2$ 정도로 느려짐.

여기서 Koch 자신이 “피벗을 $P \cup X$에서 고르면 된다”고 언급하였으나, 실제로 활용하지는 않았다고 본 논문은 지적. (이 방법을 쓰면 위 문제 사례가 $O(n$으로 해결)

---

2.3 Tomita et al. (2006) 알고리즘

Tomita 등은 Koch가 “가능”이라 언급한 “피벗을 $P \cup X$에서 고른다”를 실제로 구현(알고리즘 Cliques).

• 재귀함수 EXPAND(SUBG, CAND)에서, $ \text{pivot } u \in (P \cup X을 고른 뒤, $P - \Gamma(u) 정점들만 재귀적으로 확장.
• 이렇게 하면 $K_1, n \cup K_n$ 같은 경우도 $O(n$에 처리가능.

결론: Tomita 알고리즘은 Bron–Kerbosch Version 2의 자연스러운 확장판으로서, Koch가 제안했으나 구현하지 않은 “피벗을 $P \cup X$에서 선택” 방식을 사용한다.

---

3. 최악 사례 최적성과 남은 과제

3.1 최악 사례 $ O(3^{n/3}$

• Tomita 등(2006)은 Moon–Moser 그래프에서 최대 클리크가 최대 $3^{n/3}$개까지 생길 수 있음을 이용, 자기 알고리즘이 실제 그 경우에 $O(3^{n/3}$ 시간에 모든 최대 클리크를 나열함을 증명.
• 이는 가능한 최악 사례와 대응하여, Bron–Kerbosch 계열 알고리즘 중 최적의 복잡도 달성.

3.2 출력 민감성(Output-sensitivity)

• 이 문제는 출력 개수가 최악 $3^{n/3}$개일 수 있으므로, “입력 크기만”으로는 다루기 힘들다.
• 일반적으로, “출력 delay” (새로운 최대 클리크가 하나 나올 때마다 소요되는 평균 시간)을 줄이는 연구가 추가로 존재(예: Tsukiyama et al., Makino & Uno 등). 하지만 실험적으로는 “Bron–Kerbosch 계열 + 피벗 최적화”가 더 빠른 경우가 많다.
• Cazals & Karande(2008) 주장: Tomita 알고리즘이 Koch의 관찰(‘피벗을 $P \cup X$에서’)을 구현함으로써 그리디 접근이 더욱 안정적으로 빨라짐.

---

4. 결론

• Bron–Kerbosch Version 2 → Koch(2001)가 피벗 선택을 $P$뿐 아니라 $X$도 포함 가능함을 이론 언급 → Tomita(2006)가 이를 실질 구현하여 최악 사례에서 $O(3^{n/3}$ 시간 복잡도를 달성.
• 본 논문(Cazals & Karande, 2008)은 이 점을 정리·해명하여, Bron–Kerbosch→Koch→Tomita 간의 연결고리를 명확히 보여준다.
• 향후 연구:
  • 특정 그래프 클래스에 대한 출력민감적(output-sensitive) 복잡도 분석 미완.
  • Tomita 알고리즘보다 더 좋은 평균 성능이나 추가의 이론적 보장을 갖는 방법 모색도 가능성.

---

주요 참조

• Bron, Kerbosch, Algorithm 457: Finding all cliques of an undirected graph, Comm. ACM, 1973.
• Koch, Enumerating all connected maximal common subgraphs, TCS, 2001.
• Tomita, Tanaka, Takahashi, Worst-case time complexity for generating all maximal cliques, TCS, 2006.
• Cazals, Karande, A note on the problem of reporting maximal cliques, TCS, 2008.

수식이나 코드로 표현하면, Tomita 알고리즘(Cliques)의 핵심은 다음과 같이 요약할 수 있다:

$\begin{aligned} & \textbf{함수 } \mathrm{EXPAND}(SUBG,\, CAND): \\ & \quad \text{(1) 만약 }CAND=\emptyset \text{이고 }SUBG=\emptyset \text{이면, 현재 }Q\text{(전역 저장된 클리크 후보)는 최대클리크}\\ & \qquad \;\;\text{이므로 “clique” 출력;}\\ & \quad \text{(2) 그렇지 않으면, 피벗 } u \text{를 }(CAND \cup SUBG)\text{ 중에서 골라} \\ & \quad \qquad \text{ (예: } u = \arg\max_{v \in (CAND \cup SUBG)} |\Gamma(v)\cap CAND|\text{ ).}\\ & \quad \text{(3) } \text{for } q \in (CAND - \Gamma(u)) :\\ & \quad \qquad Q := Q \cup \{q\}; \\ & \quad \qquad \mathrm{EXPAND}(SUBG \cap \Gamma(q),\; CAND \cap \Gamma(q)); \\ & \quad \qquad Q := Q - \{q\}; \\ & \quad \qquad CAND := CAND - \{q\}; \quad \text{// 중복 방지}\\ \end{aligned}$

이 알고리즘이 최악 사례 $O(3^{n/3}$임을 Tomita 등(2006)이 증명하였고, 이는 Moon–Moser 그래프에서 최대 클리크가 $3^{n/3}$개 나타날 수 있다는 사실과 일치한다.

끝으로, Cazals & Karande(2008)은 다음과 같이 결론짓는다:

“Tomita 등 (2006)은 Koch(2001)가 언급한 '피벗을 $P \cup X\에서 고르는' 아이디어를 완전히 구현하여, 실제로도 여러 그래프에서 뛰어난 성능을 보여준다. 이로써 Bron–Kerbosch 알고리즘의 변종들이 서로 밀접하게 연결되어 있음을 알 수 있다.”

以上.