graph_tool.spectral Operator objects

Sylen·2025년 1월 4일

아래 튜토리얼은 graph-tool 라이브러리의 AdjacencyOperator 클래스를 활용하여, 그래프의 인접 행렬(Adjacency matrix)을 직접 메모리에 구성하지 않고도 효율적으로 스펙트럴 연산(예: 고윳값 계산, 행렬-벡터 곱 등)을 수행하는 방법을 소개합니다. 초보자도 쉽게 이해할 수 있도록 단계별 파이썬 코드 예시와 친절한 한글 주석을 포함했습니다.

1. `AdjacencyOperator`란?

1.1 의의와 개념

AdjacencyOperator는 scipy.sparse.linalg.LinearOperator를 상속받아, 그래프의 인접행렬 (A)에 해당하는 선형 연산을 “구체 행렬 없이” 정의해주는 클래스입니다.

전통적으로 인접행렬 (A)를 (|V|\times |V|)로 만들어서 메모리에 저장 → 큰 그래프에서는 매우 비효율 (메모리 소모가 큼).
AdjacencyOperator는 “가상 행렬”: 행렬 곱 등에 필요한 연산(matvec, matmat)만 정의 → 실제 행렬을 생성하지 않고도 곱셈 가능.
희소 선형대수(특히 부분 고윳값 계산) 시, 메모리/성능 이점이 크며, 병렬화(OpenMP)로 속도 향상 가능.

1.2 주요 메소드

dot(x): (A x) (행렬-벡터/행렬 곱)
matvec(x): 벡터 × 연산(1D 배열)
matmat(X): 행렬 × 연산(2D 배열)
rmatvec(x): 수반(Adjoint) 곱 → (A^\top x) (인접행렬이 대칭이면 사실 동일)
transpose(), adjoint(): 전치, 에르미트 수반 반환

2. 기초 예시: `adjacency` vs `AdjacencyOperator`

2.1 `adjacency()`와의 관계

graph_tool.spectral.adjacency(...) 함수:

희소행렬(csr_matrix) 혹은 AdjacencyOperator(operator=True 시)로 반환.
내부적으로 AdjacencyOperator 클래스를 통해 operator를 만든다고 생각하면 됨.

즉,

op = gt.adjacency(g, operator=True)

이런 식으로 쓰면, 반환객체가 사실상 AdjacencyOperator의 인스턴스.

2.2 실제 코드 예제 (소규모 그래프)

# adjacency_operator_tutorial.py

import graph_tool.all as gt
import numpy as np
import scipy.sparse.linalg as spla
import matplotlib.pyplot as plt

def main():
    # 1) 그래프 생성 (간단 예시)
    g = gt.Graph(directed=False)
    vlist = [g.add_vertex() for _ in range(5)]
    # 에지 추가
    g.add_edge(vlist[0], vlist[1])
    g.add_edge(vlist[1], vlist[2])
    g.add_edge(vlist[2], vlist[3])
    g.add_edge(vlist[3], vlist[4])
    g.add_edge(vlist[4], vlist[0])
    # => 5개 노드를 연결해 "오각형" 구조를 만듦

    # 2) AdjacencyOperator 생성
    #    - adjacency(g, operator=True)가 내부적으로 AdjacencyOperator를 반환
    A_op = gt.adjacency(g, operator=True)
    
    # 3) 크기 확인 (오각형이므로 5x5)
    print("Shape of the operator:", A_op.shape)
    
    # 4) 임의 벡터 x와 곱해보기
    x = np.array([1, 2, 3, 4, 5], dtype=np.float64)
    y = A_op.matvec(x)  # = A * x
    print("Result of A*x:", y)
    
    # 5) 부분 고윳값 계산: largest real (LR) + smallest real (SR)
    #    인접행렬은 대칭 => 고윳값이 모두 실수
    #    n=5 전체이므로 그냥 전부 구해도 됨(k=5)
    #    하지만 예시로 LR, SR로 나눠서 해보자
    ew_lr = spla.eigs(A_op, k=2, which="LR", return_eigenvectors=False)
    ew_sr = spla.eigs(A_op, k=3, which="SR", return_eigenvectors=False)
    ew = np.concatenate((ew_lr, ew_sr))
    
    print("Eigenvalues (approx):", ew)
    
    # 6) 시각화(실수부 vs 허수부)
    plt.figure()
    plt.scatter(np.real(ew), np.imag(ew), c="blue", alpha=0.7)
    plt.xlabel("Re(λ)")
    plt.ylabel("Im(λ)")
    plt.title("Approx. eigenvalues from AdjacencyOperator")
    plt.grid(True)
    plt.show()

if __name__=="__main__":
    main()

코드 해설

그래프 구성: 5노드, 오각형 형태.
A_op = gt.adjacency(g, operator=True) → (\text{AdjacencyOperator}) 객체 반환
.shape → (5,5) (노드 수 × 노드 수)
matvec(x): np.array로 만든 벡터와 곱. 실제로는 A * x (오각형 인접행렬 × x).
고윳값(eigs): “LR” (largest real) 2개 + “SR” (smallest real) 3개 → 총5개
간단 시각화(실수부 vs 허수부). 인접행렬이 대칭이므로, 허수부=0 근처일 것.

3. `AdjacencyOperator` 직접 사용하기

위 예제는 사실 adjacency() 함수를 통해 AdjacencyOperator를 받았지만, 더 직접적으로 AdjacencyOperator를 다루려면(예: 생성자 인수), 문서상 아래와 같은 방식을 활용할 수 있습니다:

class graph_tool.spectral.AdjacencyOperator(*args, **kwargs)

일반 사용자는 보통 adjacency(g, operator=True)를 쓰면 되고, AdjacencyOperator를 명시적으로 인스턴스화할 일은 드뭅니다. 하지만, operator 객체가 가진 메소드들(dot, matvec 등)은 동일하게 제공.

4. 주요 메소드 상세 설명

4.1 `matvec(x)` 와 `matmat(X)`

matvec(x): x가 1D numpy array(길이 N)일 때, 결과는 (\in \mathbb{R}^N).
matmat(X): X가 (N,K) 크기의 2D 배열(행렬)일 때, 결과 (N,K).

둘 다 내부적으로 _matvec, _matmat를 호출 → AdjacencyOperator의 구현에서는 “간선을 순회하며” 곱 계산.

4.2 `rmatvec(x)` 등 수반/전치

rmatvec(x): (A^\top x) (adjoint mul). 인접행렬이 무방향이면 (A^\top=A).
transpose() or T: 전치. 무방향 그래프의 인접행렬이면 사실 동일.
adjoint() or H: 에르미트 수반(복소 그래프에서).

5. 추가 팁 / 주의점

Large graph에서 유용: AdjacencyOperator는 실제 (|V|\times |V|) 행렬을 만들지 않음 → 메모리 절약 + 부분 고윳값 계산 가능.
대칭 여부: 무방향 그래프면 실제로 행렬이 대칭이지만, operator는 일반화된 형태.
Complex 그래프? graph-tool은 일반적으로 실수 중심이지만, 이론적으로 복소형 AdjacencyOperator도 가능(조건).

6. 요약

AdjacencyOperator 는 graph-tool의 인접행렬을 “LinearOperator”로 구현해, 희소 선형대수 작업에 최적화된 객체.
실제 사용 시 보통:
```
op = gt.adjacency(g, operator=True)
```
로 얻고, op.matvec(...), op.matmat(...), op.dot(...) 등을 통해 행렬 곱 연산.
대규모 그래프에서 스펙트럴 메서드(고윳값 추출) 시 메모리·성능 큰 이점.

이상으로 AdjacencyOperator 클래스의 사용법, 메소드, 예시 코드를 살펴보았습니다. 희소 네트워크(도시·교통 빅데이터 등)에서 “인접행렬 전체를 메모리에 올리지 않고도” 부분 고윳값을 구하는 데 매우 유용하니, 참고하시기 바랍니다.

아래 튜토리얼은 graph-tool 라이브러리의 LaplacianOperator 클래스를 사용하여, 그래프 라플라시안(Laplacian) 행렬을 효율적으로 다루는 방법을 단계별로 설명합니다. LaplacianOperator는 실제 (|V|\times|V|) 라플라시안 행렬을 생성·저장하지 않고도, 행렬-벡터 곱이나 고윳값 계산 등에 활용할 수 있도록 해주는 scipy.sparse.linalg.LinearOperator 기반의 객체입니다. 초보자도 쉽게 따라 할 수 있도록, 친절한 한글 주석과 함께 예시 코드를 준비했습니다.

1. 라플라시안(Laplacian) 행렬이란?

1.1 정의와 배경

그래프 (G)가 있을 때,

(D) = 노드의 차수(degree)를 대각에 배치한 행렬 (정방 (n\times n), (D_{ii} = \deg(v_i))),
(A) = 인접행렬(adjacency matrix).

일반적인 (비정규화) 라플라시안은
[
L \;=\; D \;-\; A.
]

그래프 이론에서 라플라시안의 고윳값·고유벡터는 연결성, 군집 구조, 스펙트럴 임베딩 등 다양한 분석에 쓰입니다. 예를 들어,

가장 작은 고윳값(=0)의 중복도 = 연결성분 수
두 번째로 작은 고윳값(Fiedler value) = 그래프의 ‘분할 용이성’ 등.

1.2 왜 `LaplacianOperator`?

큰 그래프에서 (|V|)가 매우 크면, (L) 전체 (|V|\times|V|)를 메모리에 올리는 것은 비효율적(또는 불가능).
LaplacianOperator는 실제 행렬 없이 “선형 연산자”만 정의.
- 예: 부분 고윳값 계산 시 scipy의 eigs 등에서 matvec(x) => Lx 연산만 구체적으로 구현.
- 메모리 절약, 연산 병렬화에 유리.

2. graph-tool의 `laplacian` vs. `LaplacianOperator`

graph-tool에서 라플라시안 행렬을 얻는 두 가지:

laplacian(g, ...): 라플라시안 희소행렬(csr_matrix나 coo_matrix) 반환, 또는 operator=True로 LaplacianOperator 반환.
LaplacianOperator 클래스 직접 사용.

일반 사용자에게는

op = gt.laplacian(g, operator=True)

가 가장 간단합니다. 내부적으로 LaplacianOperator 인스턴스를 생성해 반환합니다.

3. 간단 예시 코드

아래 예시는 작은 그래프를 만든 뒤, LaplacianOperator로 라플라시안 곱 연산과 간단한 부분 고윳값 계산을 시연합니다.

# laplacian_operator_tutorial.py

import graph_tool.all as gt
import numpy as np
import scipy.sparse.linalg as spla
import matplotlib.pyplot as plt

def main():
    # 1) 예시 그래프 생성 (소규모)
    g = gt.Graph(directed=False)
    v_list = [g.add_vertex() for _ in range(5)]
    # 에지 추가: (0-1, 1-2, 2-3, 3-4, 4-0) => 5개 노드로 오각형
    g.add_edge(v_list[0], v_list[1])
    g.add_edge(v_list[1], v_list[2])
    g.add_edge(v_list[2], v_list[3])
    g.add_edge(v_list[3], v_list[4])
    g.add_edge(v_list[4], v_list[0])
    
    # 2) LaplacianOperator 생성
    #    - laplacian(..., operator=True) => LaplacianOperator 리턴
    L_op = gt.laplacian(g, deg="total", norm=False, operator=True)
    # deg="total": 무방향 그래프에서 모든 차수
    # norm=False: 비정규화 라플라시안 L = D - A
    
    # 3) 크기 확인
    print("Laplacian operator shape:", L_op.shape)  # (5,5)
    
    # 4) matvec 테스트: Lx
    x = np.array([1, 2, 3, 4, 5], dtype=np.float64)
    y = L_op.matvec(x)  
    print("L*x =", y)
    
    # 5) 부분 고윳값(전체) 계산
    #    - n=5 -> 굳이 부분 구할 필요 없으나, 예시로 "SR"+"LR" 분리
    ew_lr = spla.eigs(L_op, k=2, which="LR", return_eigenvectors=False)
    ew_sr = spla.eigs(L_op, k=3, which="SR", return_eigenvectors=False)
    ew = np.concatenate([ew_lr, ew_sr])
    
    print("Eigenvalues (approx):", ew)
    
    # 6) 시각화: 실수부 vs 허수부 (사실 라플라시안은 대칭 => 허수부 거의 0)
    plt.figure()
    plt.scatter(np.real(ew), np.imag(ew), c="red", alpha=0.7)
    plt.xlabel("Re(λ)")
    plt.ylabel("Im(λ)")
    plt.title("Eigenvalues from LaplacianOperator")
    plt.grid(True)
    plt.show()

if __name__=="__main__":
    main()

코드 해설

그래프 구성: 5노드, 오각형 구조(무방향).
L_op = gt.laplacian(g, deg="total", norm=False, operator=True) → 라플라시안 연산자(LaplacianOperator) 획득
.matvec(x)로 (Lx) 계산 테스트
부분 고윳값(eigs) 시연. 라플라시안은 대칭 → 고윳값이 실수.
시각화(실수부 vs 허수부) → 허수부=0 근처.

4. 클래스 `LaplacianOperator`의 주요 메소드

LaplacianOperator는 LinearOperator를 상속 → 아래 메소드들이 주로 사용됨:

matvec(x): (L \times x) 계산(벡터)
matmat(X): (L \times X) 계산(행렬)
rmatvec(x): 수반((L^\top) 또는 에르미트) 곱. 무방향 그래프면 동일.
transpose(), adjoint(): 전치, 에르미트 수반 연산자.
dot(x): matvec와 동일 기능.

대칭 그래프 라플라시안인 경우, L^\top = L, L^\mathrm{H} = L (복소가 아니라면).

5. 라플라시안 정규화, 옵션

laplacian(g, norm=True, ...) 하면 정규화(normalized) 라플라시안:
[
L_{\text{norm}} = I - D^{-1/2} A D^{-1/2}.
]
다만, operator=True일 때도 비슷한 방식으로 내부 계산. 사용법 동일.

6. 실제 활용: 스펙트럴 군집, 연결성 분석

라플라시안의 작은 고윳값 → 그래프 연결성, 군집 등.
연결 성분 수: “0” 고윳값 중복도 = 컴포넌트 개수.
Fiedler vector(두 번째 최소 고윳값 벡터)로 2-way 분할.

대규모 그래프에서, 행렬 전체를 메모리에 저장하지 않고도, LaplacianOperator로 부분 고윳값(예: 가장 작은 2~3개)을 구할 수 있어 효율적.

7. 결론

LaplacianOperator는 그래프 라플라시안을 메모리 효율적으로 다룰 수 있는 scipy.sparse.linalg.LinearOperator 구현.
사용 방법: 보통
```
op = gt.laplacian(g, operator=True)
```
로 얻음 → .matvec(x), spla.eigs(...) 등.
장점: 대규모 그래프 스펙트럴 분석 시, 불필요한 행렬 생성 없이 부분 고윳값 계산 가능.

이상으로 LaplacianOperator에 대한 소개와 예시 코드를 마칩니다. 도시·교통 네트워크 등 규모가 큰 그래프에서 라플라시안을 스펙트럴 분석할 때, 이 방식을 이용하면 메모리, 속도 측면에서 큰 이점을 얻을 수 있습니다.

아래 튜토리얼은 graph-tool 라이브러리의 IncidenceOperator 클래스를 이용해서 그래프의 인시던스 행렬을 효율적으로 다루는 방법을 단계별로 설명합니다. 실제 ((#V) \times (#E)) 또는 ((#E) \times (#V)) 인시던스 행렬을 메모리에 올리지 않고도, 행렬-벡터 곱이나 고윳값 등의 선형대수 연산을 수행할 수 있게 해주는 scipy.sparse.linalg.LinearOperator 형태의 객체입니다.

1. 인시던스(Incidence) 행렬이란?

1.1 기본 개념

인시던스(Incidence) 행렬은 그래프에서 “정점(vertex)와 간선(edge) 간의 연결 관계”를 행렬 형태로 나타낸 것입니다.

무방향 그래프일 때, 인시던스 행렬 (B)는 ((#V) \times (#E)) 크기이고,
- 행은 그래프의 정점,
- 열은 그래프의 간선.
- 예) (B_{v,e} = 1) (정점 (v)가 간선 (e)에 incident이면), 아니면 0.
방향 그래프인 경우에는, “유향 간선”에서 정점과의 연결(들어오는 방향인지, 나가는 방향인지)에 따라 (\pm 1)의 값으로 확장하기도 함.

이 인시던스 행렬을 통해, 네트워크의 “유량(flow)”나 “사이클(cycle)” 분석(예: (\mathrm{cycle} \sim \mathrm{ker}(B^\top)))에 유용하게 쓰입니다.

graph-tool에서 incidence() 함수로 인시던스 행렬(또는 연산자)를 생성할 수 있으며, 이 중 IncidenceOperator는 실제 행렬 없이도 연산을 제공하므로, 큰 그래프에서 메모리 절약과 효율적인 연산이 가능해집니다.

2. `IncidenceOperator`와 graph-tool

2.1 `incidence()` 함수 vs. `IncidenceOperator`

graph_tool.spectral.incidence(g, ..., operator=True) 를 호출하면 IncidenceOperator가 반환됨. (operator=False 면 csr_matrix 등 희소행렬이 반환)
IncidenceOperator는 scipy.sparse.linalg.LinearOperator 를 상속 → .matvec(), .rmatvec(), .dot() 등으로 인시던스 행렬 곱을 수행.

3. 예시: `incidence(...)`로 인시던스 연산자 만들기

아래 코드는 작은 그래프를 구성하고, 인시던스 연산자를 얻어, 벡터 곱을 시연해 봅니다.

# incidence_operator_tutorial.py

import graph_tool.all as gt
import numpy as np
import scipy.sparse.linalg as spla
import matplotlib.pyplot as plt

def main():
    # 1) 간단한 예시 그래프 생성
    #   - 4개 노드, 3개 에지
    g = gt.Graph(directed=False)
    v0 = g.add_vertex()
    v1 = g.add_vertex()
    v2 = g.add_vertex()
    v3 = g.add_vertex()
    g.add_edge(v0, v1)
    g.add_edge(v1, v2)
    g.add_edge(v2, v3)
    # => 선형으로 연결된 4노드 (v0 - v1 - v2 - v3)

    print("Number of vertices:", g.num_vertices())  # 4
    print("Number of edges:", g.num_edges())        # 3

    # 2) 인시던스 연산자 생성
    #    - incidence(g, operator=True)는 IncidenceOperator 반환
    B_op = gt.incidence(g, operator=True, eindex=None)
    # eindex=None => 내부 edge 인덱스 사용
    # (vindex도 없음 => 내부 vertex index 사용)

    # 인시던스 행렬 크기: (#V x #E)
    print("Shape of Incidence operator:", B_op.shape)  # (4,3)

    # 3) matvec: (V x E) "행렬" * 벡터
    #    - 여기서 x dimension = #E => x 길이는 3
    x = np.array([10, 20, 30], dtype=np.float64)
    y = B_op.matvec(x)
    print("y = B * x =", y)
    # y의 길이는 #V=4

    # 4) rmatvec: (B^T x)
    #    - 결과 길이는 #E=3
    z = B_op.rmatvec(y)
    print("z = B^T * y =", z)

    # 5) 부분 고윳값 (사실 incidence는 직사각형이라 보통 '특이값'이 적절)
    #    - 여기서는 operator=False 로 matrix 받고 svds 써도 됨
    #    - 또는 크기가 작으니 직접 transform 가능
    # * 여기서는 예시로 matvec만 시연

    # 6) 그래프 시각화(간단)
    gt.graph_draw(g, vertex_text=g.vertex_index, output="incidence_example.png")

if __name__ == "__main__":
    main()

코드 해설

그래프 구성:
- 노드 4개(v0, v1, v2, v3)
- 에지 3개: (v0–v1), (v1–v2), (v2–v3)
B_op = gt.incidence(g, operator=True) → “인시던스 연산자(사이즈=4×3)”
matvec(x): 벡터 x 길이는 3(에지 수), 결과 y 길이는 4(노드 수).
rmatvec(y): adjoint 곱((B^\top y)) → 길이 3으로 돌아옴.
인시던스 행렬은 직사각형 → 고윳값(eigenvalue) 대신 일반적으로 “특이값(SVD)”을 더 많이 씁니다.

4. `IncidenceOperator` 주요 메소드

4.1 matvec(x), matmat(X)

matvec(x): ((#V\times #E)) 연산자 × “(#E) 길이 벡터” → “(#V) 길이 결과”
matmat(X): ((#V\times #E)) × “(#E\times k) 행렬” → “(#V\times k) 결과”

4.2 rmatvec(x), rmatmat(X)

인시던스의 수반(Transpose/Adjoint):
- ((#E\times #V))로 해석.
- rmatvec(x): ((#V))→(#E) 변환
무방향 그래프에서는 단순 전치((B^T))지만, 방향 그래프라면 +1/-1 구분( “in” vs “out”).

5. 인시던스 행렬 활용: 흐름, 사이클 등

인시던스 행렬로 “유량(flow) 조건” = (B^\top f=0) 형태.
“사이클(cycle) 조건” = (\mathrm{Ker}(B)) 등.
graph-tool의 IncidenceOperator는 이런 연산(곱, kernel 찾기)에 직접 사용 가능.

6. 정리와 결론

IncidenceOperator 는 그래프 인시던스 행렬을 “LinearOperator” 형태로 구현하여, 큰 그래프에서 희소 선형 연산 시 효율적.

사용:

B_op = gt.incidence(g, operator=True)
y = B_op.matvec(x)     # B * x
z = B_op.rmatvec(y)    # B^T * y

실제 직사각 행렬(#V x #E)을 만들지 않고도 연산 가능 → 메모리·속도 장점.
흐름문제(커트, cycle, spanning tree) 등에서 매우 유용.

추가 아이디어:

operator=False → 실제 희소행렬(csr_matrix) 반환 후, svds(특이값 분해)로 cycle space, cut space 분석.
대규모 그래프 → operator=True로 부분특이값/커널만 계산.

이상으로 IncidenceOperator 활용 튜토리얼을 마칩니다. 도시·교통·네트워크 분석에서, 인시던스 행렬 기반 기법(유량, 사이클, 커트) 등에 큰 도움을 줄 수 있으니 참고하시기 바랍니다.

아래 튜토리얼은 graph-tool 라이브러리에서 제공하는 TransitionOperator 클래스를 활용하여, 그래프의 전이(Transition) 행렬을 메모리 효율적으로 다루고, 이를 이용해 랜덤워크나 마코프 체인 해석 등을 수행하는 방법을 설명합니다. 실제로 (|V|\times|V|) 전이행렬 전체를 만들지 않고도, 부분 고윳값 계산이나 벡터곱 연산을 할 수 있으므로 대규모 그래프에서도 활용하기 좋습니다.

1. 전이(Transition) 행렬이란?

1.1 개념 및 목적

전이(Transition) 행렬이란, 확률 행렬(stochastic matrix) 형태로, 각 노드에서 이웃 노드로 이동할 확률을 기록한 것.
무방향·가중치 없는 그래프라면, 노드 (i)의 차수가 (di)일 때,
[
T{i,j} =
\begin{cases}
\frac{1}{d_i}, &\text{if }(i,j)\in E,\
0, &\text{otherwise}.
\end{cases}
]
랜덤워크 해석: 한 노드에서 임의 이웃 노드로 이동할 때 이 확률행렬로 한 스텝 전이.
TransitionOperator: 이 전이 행렬을 실제로 (|V|\times|V|) 희소행렬로 만들지 않고도, ‘선형 연산자’로 곱만 정의해둔 것.

2. `transition()`와 `TransitionOperator`

2.1 graph-tool 함수

graph_tool.spectral.transition(g, weight=None, vindex=None, operator=False, csr=True):
- operator=True → TransitionOperator 리턴
- operator=False → 희소행렬(csr_matrix나 coo_matrix) 리턴
보통 전이 확률을 구하기 위해선 노드별 차수(or 가중치 합)로 나눈 값 활용.

2.2 `TransitionOperator` 특징

scipy.sparse.linalg.LinearOperator 기반 → .matvec(), .rmatvec(), .dot() 등으로 (\mathbf{T}\times \mathbf{x}) 연산 가능.
메모리 절약. 수천~수백만 노드도 가능(단, 그래프-tool 컴파일 옵션, RAM은 제한).
향후 “PageRank”나 “임의워크(random walk)” 분석 시 효율적.

3. 예시 코드: 전이 행렬 연산자 사용

다음은 작은 그래프로 전이 연산자를 생성하고, 벡터 곱을 시연한 예입니다.

# transition_operator_tutorial.py

import graph_tool.all as gt
import numpy as np
import scipy.sparse.linalg as spla
import matplotlib.pyplot as plt

def main():
    # 1) 예시 그래프 생성(무방향, 5노드 오각형)
    g = gt.Graph(directed=False)
    v_list = [g.add_vertex() for _ in range(5)]
    g.add_edge(v_list[0], v_list[1])
    g.add_edge(v_list[1], v_list[2])
    g.add_edge(v_list[2], v_list[3])
    g.add_edge(v_list[3], v_list[4])
    g.add_edge(v_list[4], v_list[0])

    print("Num vertices:", g.num_vertices())  # 5
    print("Num edges:", g.num_edges())       # 5

    # 2) 전이 행렬 연산자 생성
    #    - operator=True => TransitionOperator
    T_op = gt.transition(g, operator=True)  # weight=None => unweighted
    print("Shape of Transition operator:", T_op.shape)  # (5,5)

    # 3) matvec 연산: T*x
    #    - x는 노드 수 길이=5
    x = np.array([1, 2, 3, 4, 5], dtype=np.float64)
    y = T_op.matvec(x)
    print("y = T*x:", y)

    # 4) rmatvec 연산: T^H * y
    #    - 전이 행렬은 일반적으로 대칭 아님 => T^T != T
    z = T_op.rmatvec(y)
    print("z = T^H * y:", z)

    # 5) 고윳값(eigs) 시연
    #    전이 행렬은 확률행렬 => 최대 고윳값=1
    #    (LR: largest real, SR: smallest real)
    ew_lr = spla.eigs(T_op, k=2, which="LR", return_eigenvectors=False)
    ew_sr = spla.eigs(T_op, k=3, which="SR", return_eigenvectors=False)
    ew = np.concatenate([ew_lr, ew_sr])
    
    print("Approx eigenvals:", ew)

    # 6) 시각화
    plt.figure()
    plt.scatter(np.real(ew), np.imag(ew), c='blue', alpha=0.7)
    plt.title("Eigenvalues of TransitionOperator (approx)")
    plt.xlabel("Re(λ)")
    plt.ylabel("Im(λ)")
    plt.grid(True)
    plt.show()

if __name__=="__main__":
    main()

코드 해설

오각형 그래프(5개 정점, 5개 간선) 생성.
T_op = gt.transition(g, operator=True) → TransitionOperator 객체 획득
.matvec(x): 전이연산 × 벡터. 각 노드로부터 이웃 노드로 1/degree 확률.
.rmatvec(y): 수반(에르미트Transpose) 곱 → “(T^\top y)” 같은 연산.
부분 고윳값: 전이행렬은 확률행렬 → 1이 최대 고윳값.
시각화(실수부, 허수부)

4. `TransitionOperator` 메소드 요약

matvec(x): (\mathbf{T}\cdot\mathbf{x}).
matmat(X): (\mathbf{T}\cdot\mathbf{X}) (행렬 곱).
rmatvec(x): 수반. (\mathbf{T}^\mathrm{H}\cdot\mathbf{x}).
transpose(), adjoint(): 전치, 에르미트 수반 연산자 반환.
dot(x): matvec와 유사.

전이행렬 (\mathbf{T})는 일반적으로 대칭이 아님 → (\mathbf{T}^\top \neq \mathbf{T}).

5. 전이 연산자의 사용 사례

임의워크(Random walk) 시뮬: (\pi_{t+1} = \pi_t \cdot T). 한 번의 matvec() 연산으로 스텝 업데이트.
스테디 스테이트(Stationary distribution): 고윳값=1 대응 벡터.
- spla.eigs(T_op, which="LR") 통해 1 근처 고윳값, 고유벡터 찾기.
PageRank(유사) → damping factor만 적용한 변형 필요.

6. 결론

TransitionOperator 는 그래프의 확률적 전이행렬을 scipy.sparse.linalg.LinearOperator 형태로 제공 → 실제 (|V|\times|V|) 생성 없이 행렬-벡터 곱 등 가능.
희소 그래프에서 대규모 노드로 랜덤워크, stationary distribution, 스펙트럴 분석 시 메모리·성능 이점이 큼.
일반 사용 패턴:
```
T_op = gt.transition(g, weight=None, operator=True)
v_new = T_op.matvec(v_old)
```
이런 식으로 확률 분포 업데이트 or 고윳값 계산에 활용.

이상으로 TransitionOperator 클래스의 소개와 예시 코드를 마칩니다. 대규모 그래프의 확률적 이동(랜덤서퍼, 교통수요 분산 등)을 효율적으로 처리하고자 할 때 매우 유용하니, 실무에서도 적극 활용할 수 있습니다.

아래 튜토리얼은 graph-tool 라이브러리에서 제공하는 HashimotoOperator 클래스를 활용하여, Hashimoto(=Non-backtracking) 행렬을 효율적으로 다루는 방법을 단계별로 설명합니다. 이는 Ihara–Hashimoto, non-backtracking, edge adjacency operator 등 여러 이름으로 불리며, 그래프의 스펙트럴 분석(특히 희소 그래프에서 군집 검출 등)에 큰 이점을 주는 중요한 도구입니다.

1. Hashimoto(Non-backtracking) 행렬이란?

1.1 배경과 개념

전통적인 인접행렬 (A)는 ((#V)\times(#V)) 형태로, 간선이 있으면 1(무방향일 때)로 표시.
반면 Hashimoto(=non-backtracking) 행렬은 ((2|E|)\times (2|E|)) 형태(무방향 그래프 기준, 각 간선의 양방향을 별도 인덱스로 처리).
행렬 (\mathbf{B})에서, 행·열은 “유향 edge”를 의미. 만약 row=(u→v)이고, col=(x→y)라면, (\mathbf{B}_{(u\to v),(x\to y)}=1) 이 되려면:
1. (v=x) (즉, 연속해서 이동하려면 끝점이 일치해야 함)
2. (u \neq y) (방금 온 방향으로 바로 되돌아가지 않음)

이렇게 즉시 역추적(backtracking)을 금지한 “non-backtracking walk”를 표현. 따라서 고차수 노드에서 역추적 잡음이 줄어들어, 희소 그래프에서 스펙트럼이 더 선명하게 군집 구조나 고유모드 등을 반영합니다.

1.2 `HashimotoOperator`의 의의

실제 ((2|E|)\times (2|E|)) 행렬을 만들면, 간선이 많을 때 메모리 부담이 큼.
HashimotoOperator는 scipy.sparse.linalg.LinearOperator를 상속 → 행렬 없이 matvec 등 곱셈 연산만 정의하여 희소 선형대수(예: 부분 고윳값)를 효율적으로 지원.

2. graph-tool에서의 생성: `hashimoto(g, operator=True)`

일반적으로 graph_tool.spectral.hashimoto(g, ...) 함수를 사용해 HashimotoOperator를 얻습니다:

H_op = gt.hashimoto(g, operator=True, compact=False)

operator=True를 지정해야 실제 희소행렬 대신 HashimotoOperator 객체로 반환.
compact=False면 전형적인 non-backtracking 행렬((2|E|\times 2|E|)) 형태(“full mode”).
(참고) compact=True일 경우, Krzakala 등에서 소개한 “compact”한 변형이지만, 일반적으로 bipartite 변환 등에 쓰임.

3. 예시 코드

아래는 작은 그래프(5노드로 형성된 오각형)에서 HashimotoOperator를 사용해 행렬–벡터 곱, 부분 고윳값 등을 시연합니다.

# hashimoto_operator_tutorial.py

import graph_tool.all as gt
import numpy as np
import scipy.sparse.linalg as spla
import matplotlib.pyplot as plt

def main():
    # 1) 예시: 무방향 그래프 (오각형)
    g = gt.Graph(directed=False)
    v_list = [g.add_vertex() for _ in range(5)]
    g.add_edge(v_list[0], v_list[1])
    g.add_edge(v_list[1], v_list[2])
    g.add_edge(v_list[2], v_list[3])
    g.add_edge(v_list[3], v_list[4])
    g.add_edge(v_list[4], v_list[0])
    # => 5개 노드를 순환 연결 (오각형)

    print("Number of vertices:", g.num_vertices())  # 5
    print("Number of edges:", g.num_edges())       # 5 (무방향 간선)

    # 2) Hashimoto Operator 생성
    #    - operator=True => HashimotoOperator
    H_op = gt.hashimoto(g, operator=True, compact=False)
    # compact=False => (2|E| x 2|E|) = (10 x 10)

    print("Shape of Hashimoto operator:", H_op.shape)
    # (10, 10), 무방향이라 유향간선은 2*5=10

    # 3) matvec: H*x 시연
    #    - x의 길이는 2*|E|=10
    x = np.arange(10, dtype=np.float64)  # ex) [0,1,2,3,4,5,6,7,8,9]
    y = H_op.matvec(x)
    print("y = H*x:", y)

    # 4) rmatvec: H^H * y (수반 곱)
    z = H_op.rmatvec(y)
    print("z = H^H * y:", z)

    # 5) 부분 고윳값 계산
    #    - 해시모토 행렬은 비대칭 => 고윳값이 복소 가능
    #    - "LR": 실수부 큰 쪽, "SR": 실수부 작은 쪽
    #    - 10x10 전체를 다 구해도 되지만, 예시로 3개 + 2개 등 시연
    ew_lr = spla.eigs(H_op, k=3, which="LR", return_eigenvectors=False)
    ew_sr = spla.eigs(H_op, k=2, which="SR", return_eigenvectors=False)
    ew = np.concatenate((ew_lr, ew_sr))
    
    print("Approx eigenvalues (subset):", ew)

    # 6) 시각화(복소평면)
    plt.figure()
    plt.scatter(np.real(ew), np.imag(ew), c="blue", alpha=0.7)
    plt.title("Eigenvalues from HashimotoOperator (sample subset)")
    plt.xlabel("Re(λ)")
    plt.ylabel("Im(λ)")
    plt.grid(True)
    plt.show()

if __name__=="__main__":
    main()

코드 해설

오각형 그래프를 구성(5노드, 5간선).
gt.hashimoto(g, operator=True) → HashimotoOperator 객체 (compact=False).
.matvec(x) : ((2|E|))-dim 벡터 x 곱, 결과도 ((2|E|))-dim.
.rmatvec(y) : 수반곱((H^\top)), (2|E|)-dim -> (2|E|)-dim.
고윳값: 해시모토 행렬은 비대칭(복소 가능). “LR”(largest real part), “SR”(smallest real part).

4. HashimotoOperator 주요 메소드

matvec(x): (\mathbf{H}\cdot x) (행렬–벡터 곱)
matmat(X): 행렬–행렬 곱
rmatvec(x): 수반(Adjoint) 곱 → (\mathbf{H}^\mathrm{H} x)
transpose(), adjoint(): 전치/에르미트 수반 연산자를 담은 LinearOperator 리턴
dot(x): matvec(x)와 유사

5. 해시모토 행렬의 활용

5.1 희소 그래프 스펙트럴 군집

non-backtracking 특성 → 역추적 잡음이 줄어들고, 고윳값 분포가 좀 더 “명확”.
Krzakala et al.(2013) “Spectral redemption in clustering sparse networks”: SBM(sparse) 그래프에서 이 해시모토 행렬 사용 시 성능이 크게 향상.

5.2 스펙트럼 bulk와 유의미한 고윳값

해시모토 행렬은 일반적으로 bulk가 (|\lambda| \le \sqrt{d-1}), 또는 (\sqrt{c}) 등 범위에 몰림.
밖에 있는 실제 고윳값이 군집 구조 / 주파수 모드 등을 반영.

6. 정리

HashimotoOperator = 해시모토(non-backtracking) 행렬을 “행렬 없이” 정의한 LinearOperator.
생성:
```
H_op = gt.hashimoto(g, operator=True)
```
사용:
- .matvec(x) → 곱
- spla.eigs(H_op, ...) → 부분 고윳값
- .rmatvec(...) 등 → 수반 연산
장점: 대규모 그래프에서 희소행렬을 전부 보관하지 않고도 고윳값·벡터 연산 가능. 희소 그래프 군집, 페이지랭크 유사 문제, 비반환 랜덤워크 해석 등에 유리.

이상으로 HashimotoOperator 활용 튜토리얼을 마칩니다. 특히 희소 네트워크에서 스펙트럴 군집 효율과 정확도를 높이는 핵심 연산자로 쓰이니, 도시·교통·소셜·생물 네트워크 등에서 폭넓게 응용할 수 있습니다.

아래 튜토리얼은 graph-tool 라이브러리에서 제공하는 CompactHashimotoOperator 클래스를 이용해, Compact Hashimoto(=non-backtracking) 행렬을 효과적으로 다루는 방법을 단계별로 설명합니다. 이는 일반적인 Hashimoto(=non-backtracking) 행렬을 더 간략화한 형태로, 특정한 스펙트럴 분석(특히 양단성(bipartite) 그래프) 등에 유리하게 쓰일 수 있습니다.

1. Compact Hashimoto(Non-backtracking) 행렬이란?

1.1 일반 Hashimoto 행렬 복습

일반 Hashimoto(=non-backtracking) 행렬은 무방향 그래프 (G=(V,E))에서 ((2|E|)\times(2|E|)) 크기의 행렬로, “유향 edge”를 행·열 인덱스로 삼으며, 즉시 역추적(backtracking)을 금지하는 전이(transition)를 1로 표현합니다.
희소(sparse) 네트워크에서 이 연산자 고윳값·고유벡터가 기존 인접행렬보다 더 명확히 군집 구조 등을 드러낸다(Krzakala 등 ‘Spectral redemption’ 논문).

1.2 Compact(압축) 버전 동기

Krzakala 등에서 소개된 Compact Hashimoto는 정규(regular) 그래프나 bipartite 그래프 등에서 보다 간단히 다룰 수 있도록, 실제 ((2|E|)\times(2|E|)) 대신 (|V|\times |V|) 크기로 압축한 연산자를 정의하는 기법입니다.
graph-tool의 hashimoto(g, compact=True) 옵션을 통해, 이 압축 버전 행렬을 만들 수 있으며, CompactHashimotoOperator로 바로 사용할 수 있습니다.
특히 “semi-regular bipartite graph”(ex. ((q_1+1, q_2+1))-valent) 등에서, 컴팩트 형태가 더 직접적으로 스펙트럼 해석(예: ((q_1q_2))-eigenvalue) 가능.

2. `CompactHashimotoOperator`와 graph-tool

2.1 생성 방법

보통 다음 함수를 사용:
```
op = gt.hashimoto(g, compact=True, operator=True)
```
→ CompactHashimotoOperator 반환.
compact=False로 호출 시 일반 HashimotoOperator, operator=False 시 희소행렬(csr_matrix 등) 반환.

2.2 어떤 상황에서 쓸까?

bipartite 혹은 semi-regular 그래프에서 해시모토 행렬을 좀 더 작게(노드 수 (|V|\times|V|))로 다루고 싶을 때.
더 일반 그래프에서도 사용 가능하나, 보통은 bipartite 그래프 관련 연구에서 자주 언급.

3. 파이썬 예시 코드: Compact Hashimoto 연산자 사용

아래는 6노드 bipartite 그래프(예: 3개의 노드 그룹1, 3개의 노드 그룹2, 서로 간 간선 연결)에서 CompactHashimotoOperator를 생성하고, 연산·고윳값을 시연하는 예입니다.

# compact_hashimoto_operator_tutorial.py

import graph_tool.all as gt
import numpy as np
import scipy.sparse.linalg as spla
import matplotlib.pyplot as plt

def main():
    # 1) bipartite 예시 그래프 구성
    g = gt.Graph(directed=False)
    # V1={v0, v1, v2}, V2={v3, v4, v5}
    vlist = [g.add_vertex() for _ in range(6)]
    # 간단히, 각 v_i(0..2)와 v_j(3..5) 간에 간선 연결
    for i in range(3):
        for j in range(3, 6):
            g.add_edge(vlist[i], vlist[j])
    # => 3x3 bipartite 완전연결(K(3,3)) -> 총 9개 간선

    print("Vertices:", g.num_vertices())  # 6
    print("Edges:", g.num_edges())       # 9

    # 2) Compact Hashimoto Operator 생성
    #    - compact=True, operator=True
    H_cop = gt.hashimoto(g, compact=True, operator=True)
    # => CompactHashimotoOperator
    print("Shape of compact Hashimoto operator:", H_cop.shape)
    # (6,6), bipartite일 때 유용

    # 3) matvec 연산
    x = np.array([1,2,3,4,5,6], dtype=np.float64)
    y = H_cop.matvec(x)
    print("y = H_compact * x:", y)

    # 4) rmatvec: 수반 곱
    z = H_cop.rmatvec(y)
    print("z = H_compact^H * y:", z)

    # 5) 부분 고윳값 계산
    #    - shape=(6,6)이므로 k<6
    ew_lr = spla.eigs(H_cop, k=2, which="LR", return_eigenvectors=False)
    ew_sr = spla.eigs(H_cop, k=2, which="SR", return_eigenvectors=False)
    ew = np.concatenate((ew_lr, ew_sr))
    print("Eigenvalues approx:", ew)

    # 6) 시각화
    plt.figure()
    plt.scatter(np.real(ew), np.imag(ew), c='red', alpha=0.7)
    plt.title("Eigenvalues of Compact Hashimoto Operator (sample)")
    plt.xlabel("Re(λ)")
    plt.ylabel("Im(λ)")
    plt.grid(True)
    plt.show()

if __name__=="__main__":
    main()

코드 해설

이분(Bipartite) 그래프: (3,3) 완전이분그래프(K(3,3)) 예시(노드6, 간선9).
gt.hashimoto(g, compact=True, operator=True) → CompactHashimotoOperator 객체 획득.
.matvec(x) : 인덱스는 (6,6) → “노드별” (compact)로 곱 실행.
.rmatvec(...): 수반 곱(에르미트).
고윳값: ((6\times 6)) → 정방행렬. bipartite 정규 특성상, (\pm\sqrt{q_1 q_2}) 등 eigenvalue 가능성.
시각화(복소평면), bipartite 일 경우 보통은 실수부로 나타날 수도 있음.

4. `CompactHashimotoOperator` 메소드

CompactHashimotoOperator는 LinearOperator를 상속하므로, 주요 메소드는 다음과 같습니다:

matvec(x): (\mathbf{H_{compact}}\times x) (벡터 곱)
matmat(X): 행렬–행렬 곱
rmatvec(x): 수반 곱
transpose(), adjoint(): 전치, 에르미트 수반
dot(x): matvec(x) 유사

주의: 일반 해시모토((2|E|\times 2|E|))와 달리, compact는 (|V|\times |V|). bipartite일 때 유용(정규성, 이분성 등 가정).

5. Compact Hashimoto와 일반 Hashimoto의 비교

크기: 일반은 (2|E|\times 2|E|), compact는 (|V|\times |V|).
적용: bipartite나 semi-regular 그래프에서 compact가 스펙트럼 해석이 간단, 메모리 절약.
스펙트럴 군집: bipartite 구조 파악 시 compact가 직접적.
일반 그래프: compact 모드도 동작은 하지만, 해석이 쉬운 건 bipartite 등.

6. 활용 시 주의점

bipartite or semi-regular일 때, compact 버전이 장점 큼.
일반 그래프에서도 가능하나, 해석상 이점 제한적.
복소 고윳값 → non-symmetric, eigenvectors complex 가능.

7. 결론

CompactHashimotoOperator는 해시모토(non-backtracking) 행렬을 “(|V|\times |V|) 크기로 압축”한 LinearOperator**.

생성:

cop = hashimoto(g, compact=True, operator=True)

bipartite 그래프나 정규/반정규 세팅에서 스펙트럴 분석에 큰 장점.
.matvec(), .rmatvec(), .dot() 등으로 곱, spla.eigs(...)로 고윳값 추출.
대규모 그래프, 메모리 절약, 희소 선형대수 시 유용.

이상으로 CompactHashimotoOperator 튜토리얼을 마칩니다. 도시·교통·네트워크 분석에서, 특히 이분(bipartite) 구조가 있을 때, 효율적인 스펙트럴 군집이나 라플라시안-like 해석에 활용할 수 있습니다.

Sylen

AI가 재밌는 걸

이전 포스트

graph_tool.spectral hashimoto

다음 포스트

graph_tool.spectral Operator objects

1. AdjacencyOperator란?

1.1 의의와 개념

1.2 주요 메소드

2. 기초 예시: adjacency vs AdjacencyOperator

2.1 adjacency()와의 관계

2.2 실제 코드 예제 (소규모 그래프)

코드 해설

3. AdjacencyOperator 직접 사용하기

4. 주요 메소드 상세 설명

4.1 matvec(x) 와 matmat(X)

4.2 rmatvec(x) 등 수반/전치

5. 추가 팁 / 주의점

6. 요약

1. 라플라시안(Laplacian) 행렬이란?

1.1 정의와 배경

1.2 왜 LaplacianOperator?

2. graph-tool의 laplacian vs. LaplacianOperator

3. 간단 예시 코드

코드 해설

4. 클래스 LaplacianOperator의 주요 메소드

5. 라플라시안 정규화, 옵션

6. 실제 활용: 스펙트럴 군집, 연결성 분석

7. 결론

1. 인시던스(Incidence) 행렬이란?

1.1 기본 개념

2. IncidenceOperator와 graph-tool

2.1 incidence() 함수 vs. IncidenceOperator

3. 예시: incidence(...)로 인시던스 연산자 만들기

코드 해설

4. IncidenceOperator 주요 메소드

4.1 matvec(x), matmat(X)

4.2 rmatvec(x), rmatmat(X)

5. 인시던스 행렬 활용: 흐름, 사이클 등

6. 정리와 결론

1. 전이(Transition) 행렬이란?

1.1 개념 및 목적

2. transition()와 TransitionOperator

2.1 graph-tool 함수

2.2 TransitionOperator 특징

3. 예시 코드: 전이 행렬 연산자 사용

코드 해설

4. TransitionOperator 메소드 요약

5. 전이 연산자의 사용 사례

6. 결론

1. Hashimoto(Non-backtracking) 행렬이란?

1.1 배경과 개념

1.2 HashimotoOperator의 의의

2. graph-tool에서의 생성: hashimoto(g, operator=True)

3. 예시 코드

코드 해설

4. HashimotoOperator 주요 메소드

5. 해시모토 행렬의 활용

5.1 희소 그래프 스펙트럴 군집

5.2 스펙트럼 bulk와 유의미한 고윳값

6. 정리

1. Compact Hashimoto(Non-backtracking) 행렬이란?

1.1 일반 Hashimoto 행렬 복습

1.2 Compact(압축) 버전 동기

2. CompactHashimotoOperator와 graph-tool

2.1 생성 방법

2.2 어떤 상황에서 쓸까?

3. 파이썬 예시 코드: Compact Hashimoto 연산자 사용

코드 해설

4. CompactHashimotoOperator 메소드

5. Compact Hashimoto와 일반 Hashimoto의 비교

6. 활용 시 주의점

7. 결론

graph_tool.spectral hashimoto

graph_tool.stats

0개의 댓글

1. `AdjacencyOperator`란?

2. 기초 예시: `adjacency` vs `AdjacencyOperator`

2.1 `adjacency()`와의 관계

3. `AdjacencyOperator` 직접 사용하기

4.1 `matvec(x)` 와 `matmat(X)`

4.2 `rmatvec(x)` 등 수반/전치

1.2 왜 `LaplacianOperator`?

2. graph-tool의 `laplacian` vs. `LaplacianOperator`

4. 클래스 `LaplacianOperator`의 주요 메소드

2. `IncidenceOperator`와 graph-tool

2.1 `incidence()` 함수 vs. `IncidenceOperator`

3. 예시: `incidence(...)`로 인시던스 연산자 만들기

4. `IncidenceOperator` 주요 메소드

2. `transition()`와 `TransitionOperator`

2.2 `TransitionOperator` 특징

4. `TransitionOperator` 메소드 요약

1.2 `HashimotoOperator`의 의의

2. graph-tool에서의 생성: `hashimoto(g, operator=True)`

2. `CompactHashimotoOperator`와 graph-tool

4. `CompactHashimotoOperator` 메소드