graph_tool.spectral

Sylen·2025년 1월 4일

아래 답변은 중학생도 이해할 수 있도록 쉽고 친절하게 “라플라시안(Laplacian) 행렬”이라는 개념을 차근차근 설명한 것입니다. 네트워크(그래프)에서 흔히 쓰이는 라플라시안의 기본 아이디어와 정의, 그리고 왜 중요한지를 알아보겠습니다.

1. 그래프(네트워크)란?

우선, 그래프 또는 네트워크라는 것은 “점과 선으로 이루어진 구조”라고 생각하면 됩니다:

점(노드): 예를 들어, 도시나 교차로, 사람 등을 나타낼 수 있음.
선(간선): 노드와 노드를 연결하는 길, 관계, 통로 등을 의미.

이렇게 점과 선으로 이루어진 구조를 그래프(네트워크)라고 부릅니다.

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

2.1 개념 한 줄 요약

라플라시안 행렬은 그래프(네트워크)에서 “내 노드가 가진 연결 정보”와 “이웃 노드와 연결된 관계”를 한꺼번에 행렬로 나타낸 것입니다.

2.2 조금 더 구체적으로

간단한 무방향(서로 연결이 양방향), 가중치가 없는(모든 선이 같음) 그래프를 예로 들어볼게요.

인접 행렬(Adjacency Matrix) (A)
- 노드를 1번부터 (N)번까지 있다고 할 때,
- (A_{ij})를 “노드 i와 노드 j가 연결되어 있으면 1, 없으면 0”으로 채운 (N\times N) 행렬.
- 예) 2번 노드와 5번 노드가 선으로 이어져 있으면 (A_{2,5}=1), 이어져 있지 않으면 0.
차수(degree)
- 각 노드가 “몇 개의 연결(선)”을 가지고 있는지
- 예) 노드 i가 3개의 이웃 노드와 연결 → i번 노드의 차수 = 3.
대각 행렬 (D)
- (D)는 대각선에 “각 노드의 차수”만 써 넣고, 나머지는 0으로 둔 행렬.
- 즉, (D{ii} =) (노드 (i)의 차수), (D{ij} = 0) (if (i \neq j)).
라플라시안 (L = D - A)
- 이제 라플라시안은 (D)에서 (A)를 빼서 만드는 행렬.
- (L{ii}) = (자신의 차수), (L{ij}) = (연결되어 있으면 -1, 아니면 0) 등으로 해석 가능.

쉽게 말해:

대각 원소( (L_{ii}) ) = “i번 노드가 가진 연결 개수”,

오프대각 원소( (L_{ij}) ) = “i,j가 연결되어 있으면 -1, 연결 없으면 0” (단, i≠j).

3. 왜 이렇게 만들까?

그래프에서 라플라시안은 “나와 이웃이 어떻게 연결됐는지”를 수학적으로 명확히 표현해줍니다.

한 노드 i를 보면, 라플라시안에서 (i,i) 위치는 “노드 i가 가진 연결(차수)”
i와 j(이웃)는 -1로 표기 → 즉, “서로 연결된 노드끼리는 -1로 가리킨다”는 아이디어.

이걸 통해 어떤 노드가 얼마나 연결됐는지, 이웃은 누구인지, 그리고 전체 구조가 어떤 모양으로 연결됐는지를 한 행렬로 표현할 수 있습니다.

4. 라플라시안 행렬의 예시

가령 노드가 3개(1,2,3)이고, 다음처럼 연결되어 있다고 합시다:

1 ↔ 2 연결됨
2 ↔ 3 연결됨
1 ↔ 3 은 연결 없음

그러면:

노드 1의 차수 = 1(노드 2와만 연결)
노드 2의 차수 = 2(노드1, 노드3와 연결)
노드 3의 차수 = 1(노드2와만 연결)

인접행렬 (A)는:
[
A = \begin{pmatrix}
0 & 1 & 0 \
1 & 0 & 1 \
0 & 1 & 0
\end{pmatrix}
]

대각행렬 (D)는:
[
D = \begin{pmatrix}
1 & 0 & 0 \
0 & 2 & 0 \
0 & 0 & 1
\end{pmatrix}
]

따라서 라플라시안 (L = D - A)는:
[
L = \begin{pmatrix}
1 & 0 & 0 \
0 & 2 & 0 \
0 & 0 & 1

\end{pmatrix}

\begin{pmatrix}
0 & 1 & 0 \
1 & 0 & 1 \
0 & 1 & 0

\end{pmatrix}

\begin{pmatrix}
1 & -1 & 0 \
-1 & 2 & -1 \
0 & -1 & 1
\end{pmatrix}
]

5. 라플라시안으로 뭘 할 수 있나?

5.1 연결 성분 개수

라플라시안에는 그래프가 여러 개로 나뉘었는지(connected component) 여부가 드러납니다.
예) “가장 작은 고윳값(eigenvalue)이 0이고, 그 중복도=그래프가 몇 개의 독립적인 덩어리인지”를 알려줍니다.

5.2 스펙트럴 클러스터링(2-way 군집)

2번째로 작은 고윳값(Fiedler 값)과 그 벡터를 보면, 그래프를 크게 2군집으로 나누는 단서를 얻을 수 있어요.
각 노드를 벡터 내 값이 양쪽으로 갈라지는지(+) 혹은 (-)인지 기준으로 분류.

5.3 확장(정규화 라플라시안, Bethe Hessian)

정규화 라플라시안은 “노드 차수가 클 때 생기는 영향”을 줄이기 위해 (D^{-1/2}) 같은 항을 곱해서 만든 것.
Bethe Hessian은 (r)이라는 파라미터로 변형한 라플라시안으로, 희박(sparse) 그래프 군집 검출에 효과적이라는 연구도 있음.

6. 중학생 시선에서 요약하자면

그래프에는 “점과 선”이 있음. 각 점(노드)이 몇 개의 선으로 연결됐는지 “차수”라고 부름.
라플라시안 행렬은 “노드별 차수”를 대각에 쓰고, 연결된 노드끼리는 -1로 표시하는 특별한 행렬이다.
이 행렬을 살펴보면, 그래프가 얼마나 잘 이어져 있는지, 또는 어떻게 쪼갤 수 있는지(군집) 등을 수학적으로 알 수 있다.
따라서 라플라시안은 그래프 이론과 데이터 분석에서 핵심 도구로 쓰임.

7. 한마디로...

“라플라시안은 (내 노드 차수) - (연결 관계)를 요약한 행렬로서, 그래프 구조를 스펙트럴(고윳값·벡터)로 분석하게 해준다. 그래서 ‘그래프가 몇 개 덩어리인지’(연결성), ‘어떻게 잘 나눌 수 있는지’(군집), ‘희박 그래프에서 복잡한 패턴을 찾을 수 있는지’ 등을 수학적으로 알게 해주는 것”이라고 이해하면 됩니다.

결론

중학생 수준의 설명으로 보면, “라플라시안” 은 ‘각 점이 가진 연결 개수와 이웃관계를 행렬로 간단히 표현한 것이다’ 라고 요약할 수 있어요. 그리고 이 행렬을 이용하면, 그래프가 어떤 구조를 가지고 있는지 수리적으로 분석하고, 네트워크를 분할(커뮤니티 찾기)하거나, 연결성이 떨어지는 부분(이어지지 않은 컴포넌트) 등을 찾을 수 있습니다.

아래 내용은 Saade, Krzakala, Zdeborová가 2014년에 발표한 “Spectral Clustering of Graphs with the Bethe Hessian” 논문(arXiv: 1406.1880)를 발췌한 것입니다. 이 논문은 그래프의 군집(community) 구조를 찾는 데 있어, 전통적인 인접행렬(adjacency)나 라플라시안(laplacian) 행렬 대신 Bethe Hessian(비등방적(?) 연산자인 non-backtracking operator와 관련이 있음)을 사용하는 방법을 제안합니다. 저자들은 이 Bethe Hessian이,
1) Sparse(희박) 네트워크(특히 Stochastic Block Model, SBM)에서 군집 검출 한계를 이론적으로 만족하는 성능(임계점 이하에서 군집 검출 가능),
2) 대칭 실수(symmetric, real) 행렬이 가지는 계산 효율성(메모리 이점, 고속의 선형대수 연산),
3) non-backtracking 행렬과 동일한 수준(혹은 더 나은 성능)의 군집 검출 역량,
을 모두 달성한다고 주장합니다.

아래에서는 Bethe Hessian(이른바 “deformed Laplacian”)의 정의, 원리, 수식, 그리고 왜 군집 검출에 좋으며 어떤 방식으로 non-backtracking operator와 연관되는지, 그리고 본 논문에서의 핵심 아이디어와 식(수식)을 최대한 자세하게 설명하겠습니다.

1. 문제 설정: 희박(Sparse) 그래프에서의 군집 검출과 SBM

군집(community) 또는 모듈 구조를 그래프에서 찾는 것은, 머신러닝·생물학·소셜네트워크 등 다양한 분야에서 중요합니다.
통계물리/네트워크 과학에서 Stochastic Block Model (SBM) 은 군집화 알고리즘의 벤치마크로 자주 쓰입니다.
- SBM에서 노드는 (q)개의 그룹(레이블) 중 하나를 가짐.
- 그룹 간(또는 그룹 내) 연결 확률이 달라서, “assortative”((c\text{in} > c\text{out})) 또는 “disassortative”((c\text{in} < c\text{out})) 구조가 나타날 수 있음.
- 희박 그래프(regime)에서, 평균 차수 (c)가 상수인 상태로 노드 수 (n \to \infty)를 생각하면, 군집 검출이 쉽지 않아짐.
SBM에서 잘 알려진 임계 조건:
- (\lvert c\text{in} - c\text{out} \rvert > q \sqrt{c}) 일 때, (즉 차이가 충분히 클 때) 군집 검출이 가능하다고 알려짐.
- 특히 (q=2)인 경우, (\lvert c\text{in} - c\text{out} \rvert > 2\sqrt{c})가 정확한 한계(일부 문헌에서 2(\sqrt{c})로 표현).
- 이 임계 이하에서는 “아무 알고리즘도” 정보에 근거해 군집을 복원할 수 없다고 증명됨(즉 임계점을 군집 검출의 이론적 한계로 본다).

2. 기존 접근: Non-backtracking operator vs. 표준 스펙트럴 방법

표준 스펙트럴 기법
- 인접행렬 (A)나 라플라시안 (L)의 고유벡터(eigenvector)를 이용해 노드를 분류.
- 높은 차수(덜 희박) 그래프에서는 성능이 좋으나, 희박 그래프에서는 서브옵티멀(임계점을 제대로 달성 못 함).
Non-backtracking operator (B)
- Krzakala 등(2013)에서 제안: 그래프의 ‘non-backtracking walk’(뒤로 돌아가지 않는 행보)에서 정의되는 (2m \times 2m) (또는 변형해서 (2n \times 2n)) 비대칭 행렬.
- SBM에서 임계점을 정확히 달성(즉 (\lvert c\text{in} - c\text{out}\rvert > q\sqrt{c}) 이면 군집 검출 가능).
- 단점: 행렬 크기가 크고(간선 단위, (m)은 간선 수), 비대칭 실수 행렬이라서 연산·메모리에 비용이 큼.

3. Bethe Hessian(deformed Laplacian): 핵심 아이디어

논문 저자들은 Bethe Hessian(또는 “deformed Laplacian”)이라고 불리는 대칭(실수) 행렬을 사용하면,

non-backtracking operator와 동등 수준 또는 더 나은 군집 검출 성능,
행렬 크기는 노드 수 (n\times n)이므로 메모리 이점,
대칭 행렬에 대한 선형대수 기법(고속·안정성) 활용 가능,
역시 SBM 임계점을 달성
한다고 주장합니다.

3.1 Bethe Hessian 정의

그래프 (G=(V,E)), 인접행렬 (A), 대각행렬 (D) (노드 차수(di)를 대각 원소로).
정규화 상수(regularizer) (r) (절댓값 (\lvert r \rvert > 1))를 잡고,

[
H(r) \;:=\; (r^2 - 1)\mathbf{I} \;-\; r\,A \;+\; D.
]
- 문헌에서 (\mathbf{I})는 항등행렬(identity).
- (r)이 매우 클 때((\lvert r \rvert > 1)), 이 행렬은 positive definite(모든 고윳값>0)가 됨.
이 (\displaystyle H(r))을 "Bethe Hessian" 혹은 "deformed Laplacian"이라 부름.

3.2 Bethe Hessian과 non-backtracking operator (B)의 연결

non-backtracking 행렬 (B)의 고윳값과 (H(r))의 고윳값은 Ihara-Bass 공식 등을 통해 밀접히 연결됨.
- (B)에서 실수 고윳값 (\lambda \neq \pm 1) → (\lambda)는 (\det [ ( \lambda^2 -1)\mathbf{I} - \lambda A + D ]=0) 와 동일
- 즉, (B)의 스펙트럼은 Bethe Hessian (\lambda)-파라미터와 수학적으로 결부.
결론: (r) 를 잘 선택(예: (r = \sqrt{\rho(B)}), 여기서 (\rho(B))는 (B)의 스펙트럴 반지름)하면, Bethe Hessian은 non-backtracking과 동등한 “유익한( informative) 고윳값”을 음의 방향으로 분리해낸다.
- 음의 고윳값 개수가 곧 군집 수((q))를 가리키며, 대응 고유벡터가 실제 군집 분할 정보를 제공.

3.3 Bethe Hessian과 Ising 모델, “Paramagnetic point”에서의 해석

논문에서는 Bethe Hessian이 Ising 스핀 글래스 모델의 Bethe 근사(Free Energy)에서 정의되는 “파라메트릭 점(paramagnetic point)에 대한 Hessian”임을 지적.
상전이(phase transition) 지점에서 Hessian이 음의 고윳값을 갖게 되는데, 그것이 곧 “새로운 군집(해석하면, 스핀 얼라인먼트) 구조”가 출현함을 의미.
그 점에서 고유벡터는 군집 방향 정보를 담는다.

4. 스펙트럼 분석의 실제: SBM에서 임계점 달성

SBM(균일형: (c\text{in}), (c\text{out})으로 구분)에서 Bethe Hessian의 스펙트럼을 분석 → “양수의 벌크( bulk of uninformative eigenvalues )”와 “음수의 소수 고윳값( informative eigenvalues )”이 분리된다.”
(\displaystyle r = \pm \sqrt{c}) 근방에서 “유익한 고윳값(감춰진 군집 정보가 들어있는 것)”이 음의 영역으로 떨어지고, 나머지 벌크는 양수 영역에 존재 → 사실상 임계 구간에서 군집 정보를 명확히 추출 가능.
(\displaystyle \lvert c\text{in} - c\text{out}\rvert > q \sqrt{c})이면, Bethe Hessian은 군집 구조를 “음수 고윳값” 부분으로 드러낸다.

4.1 정규화 파라미터 (r_c = \sqrt{\rho(B)})

실제로 (r)은 non-backtracking 행렬 (B) 의 스펙트럴 반지름 (\rho(B))의 제곱근으로 택하면 좋다.
(\rho(B))를 굳이 (B)를 구성하지 않고도, 별도의 “Quadratic eigenproblem”으로 구할 수 있다고 논문에서 기술.

5. 알고리즘 개요: “Bethe Hessian 스펙트럴 클러스터링”

입력: 그래프 (G), 노드 수 (n).
단계:
1. (옵션) (\rho(B)) 근사(또는 (\sqrt{c}) 등).
2. (r_c = \sqrt{\rho(B)}) (assortative)와 (-r_c) (disassortative) 설정.
3. Bethe Hessian 행렬 (H(r_c)), (H(-r_c)) 생성.
4. 음수 고윳값이 존재하면, 그 개수만큼(=군집 수) 고유벡터 추출 → k-means나 sign-based 분류.
5. assortative 구조는 (H(r_c))에서, disassortative 구조는 (H(-r_c))에서 음수 고윳값 벡터 활용.
출력: 군집 레이블(노드별).

5.1 장점

대칭 행렬 → 빠른 고윳값 분해(대형 sparse 대칭 행렬에 대해 효율적 알고리즘 풍부).
행렬 크기가 (n \times n) → 비대칭 non-backtracking((2m)-크기) 대비 메모리 절약.
SBM에서 임계점을 만족 → non-backtracking과 동일 혹은 그 이상의 군집 검출 성능.
군집 수(q)의 사전 지식 없어도, “음수 고윳값 개수”로 자동 결정 가능.

6. 실험 결과(논문 요약)

Synthetic (SBM) 테스트:
- Bethe Hessian이 non-backtracking operator보다 약간 더 좋은 or 비슷한 성능을 보이며, “Belief Propagation (BP) 오라클”과 유사하게 임계점까지 군집 검출 가능.
Real-world 네트워크 (정치 블로그, 축구팀, 돌고래 관계망, etc.):
- Bethe Hessian이 non-backtracking 등 전통적 방법 대비 성능이 좋거나 비등하며, 음수 고윳값을 통해 군집을 식별함.

7. 수식·원리 정리

7.1 핵심 수식

Bethe Hessian(Deformed Laplacian):
[
H(r) \;=\; (r^2 - 1)\mathbf{I} \;-\; r\,A \;+\; D.
]
SBM 임계조건:
[
\lvert c\text{in} - c\text{out} \rvert \;>\; q\,\sqrt{c}
\quad\Longrightarrow\quad \text{군집 검출 가능}.
]
연결: non-backtracking operator (B)의 실수 고윳값 (\lambda)와 (H(r))의 고윳값은
[
\det\bigl[ (\lambda^2-1)\mathbf{I} - \lambda A + D \bigr] \;=\; 0
\quad\Longleftrightarrow\quad \det H(\lambda) = 0.
]
→ (\lambda)가 (\pm 1) 외부 영역에 있으면, Bethe Hessian가 0의 고윳값을 갖는 (r)로 연결됨.
Ising 파라메트릭 해석:
Bethe Free Energy의 Hessian (\Rightarrow) 상전이 지점에서 음의 고윳값 발생 → 군집 정보.

7.2 직관

라플라시안 (L = D - A)는 (\lambda=0)에서 상호연결성, +1 고윳값 근처에서 군집 관찰 등 방식이 있는데, 희박 그래프에선 잡음이 많아 임계점 이하 성능 제한.
Bethe Hessian은 ((r^2-1)\mathbf{I} - r A + D) 형태를 잡음 제거·regularize해서, 유효하게 non-backtracking operator가 줄 수 있는 임계 성능을 “대칭 행렬” 형태로 구현한다.

8. 결론 및 의의

Bethe Hessian은 희박 그래프에서 군집화를 스펙트럴 방법으로 수행할 때,
- 임계점 ((\lvert c\text{in}-c\text{out}\rvert > q\sqrt{c}))을 달성,
- non-backtracking operator와 동등한 이론적 성능,
- 메모리·계산 이점(사이즈 (n\times n) + 대칭 실수 행렬).
결과적으로, 간단한(“non-parametric”) 접근(사전 정보 없이, 행렬 음의 고윳값 개수를 세어 군집 수를 자동 감지)으로도, Belief Propagation(Oracular parameter 필요) 수준의 군집 검출 성능을 낼 수 있음을 강조.

9. 참고 식과 그림 해설

논문 (Fig. 1)은 SBM에서 (r) 변화에 따른 Bethe Hessian 고윳값((\lambda)) 분포(스펙트럼)가 어떻게 변하는지 보여줌.
- (r)가 클 때, 모든 고윳값 > 0 (positive).
- (r)를 줄이면, 일부 고윳값이 0에 도달했다가 음수로 이동 → 해당 모드(고유벡터)가 군집 정보.
- (r = \sqrt{c}) 근처에서 (assortative) 관점, 0 이하로 분리된 고윳값이 (q)개 등장 → 군집화를 쉽게 결정.

정리: 왜 “Bethe Hessian”인가?

비교 우위:
- Adjacency/Laplacian: 희박에서 성능 한계.
- Non-backtracking((B)): 성능은 좋으나 비대칭 대규모 행렬.
- Bethe Hessian: 대칭이고, 크기가 (n). 임계점 달성 가능.
알고리즘:
1) 그래프에서 (\rho(B)) 추정 → (r_c=\sqrt{\rho(B)}).
2) (H(r_c)), (H(-r_c)) 계산 → 음수 고윳값(개수=군집 수), 해당 고유벡터로 분류.
SBM에서 입증: (\lvert c\text{in} - c\text{out}\rvert > q\sqrt{c}) 범위에서 군집 검출 가능.

결론적으로, Bethe Hessian은 스펙트럴 클러스터링 관점에서, “(non-)backtracking operator 수준의 이론 성능을, 대칭 행렬 형태로 좀 더 깔끔하게 구현”해 준다고 볼 수 있습니다. 이 접근은 다양한 실제 네트워크(정치 블로그, 돌고래 사회망, 어휘 연결망 등)에서도 좋은 성능을 보인다는 것이 논문의 핵심 주장입니다.

이상으로 논문의 주요 개념(수식, 원리, 분석)을 정리했습니다. “Bethe Hessian”이 제안된 배경(왜 non-backtracking과 연관?), 수학적 정의(식 (2), (3)), Ising-Bethe Free Energy와의 관계(9)~(10), SBM 임계점 해석, 그리고 실제 실험 결과까지 개괄적으로 살펴보았습니다.

아래 튜토리얼은 graph-tool 라이브러리에서 제공하는 laplacian 함수를 활용해, 그래프의 라플라시안(Laplacian)이나 Bethe Hessian(특정 파라미터 (r\neq 1)에서) 행렬을 생성하는 과정을 단계별로 살펴보고, 이를 실제로 파이썬에서 어떻게 구현하고 분석(예: 고윳값 스펙트럼 확인)하는지 소개합니다. 초보자도 쉽게 따라 할 수 있도록 상세한 한글 주석과 친절한 설명을 곁들였으니 참고하시기 바랍니다.

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

그래프의 라플라시안은 전통적으로 다음과 같이 정의됩니다:

무가중치·무방향 그래프에서,
[
L = D - A
]
- (A)는 인접행렬(adjacency matrix),
- (D)는 대각행렬로서, 각 노드(정점)의 차수(degree)를 대각 원소로 가짐.
정규화 라플라시안(Normalized Laplacian):
[
L_{\text{norm}} \;=\; I - D^{-\tfrac{1}{2}} \, A \, D^{-\tfrac{1}{2}}.
]
군집(clustering)·스펙트럴 방법에서 자주 쓰이는 형태.

그래프가 가중치 혹은 방향성(directed)을 가진다면, 차수나 대각 항 정의가 더 복잡하게 바뀌지만, 요지는 “노드의 연결 강도(또는 개수)만큼 자신을 보강하고, 인접노드와는 음의 값으로 연결”한다는 해석입니다.

2. graph-tool의 `laplacian` 함수 개요

graph_tool.spectral.laplacian(
    g, 
    deg='out', 
    norm=False, 
    weight=None, 
    r=1.0, 
    vindex=None, 
    operator=False, 
    csr=True
) -> csr_matrix or LaplacianOperator

주요 파라미터
1. g (Graph): 분석할 그래프 객체
2. deg (기본값 "out"):
  - 방향 그래프에서 차수를 어떻게 정의할지 결정
    - "in" : 노드 in-degree
    - "out" : 노드 out-degree
    - "total" : 양방향 합(= in + out)
  - 무방향 그래프면 의미가 크게 다르지 않음.
3. norm (bool, 기본값 False):
  - False → 일반 라플라시안
  - True → 정규화 라플라시안((L_{\text{norm}}))
4. weight (EdgePropertyMap):
  - 간선에 가중치가 있을 경우 제공
  - 가중 라플라시안을 계산할 때 참조
5. r (double, 기본값 1.0):
  - Bethe Hessian을 만들 때 사용하는 “정규화 파라미터(regularization parameter)”.
  - 만약 (r \neq 1)이고, norm=False이면, 라플라시안 대신 Bethe Hessian을 반환:
    [
    L_{\text{Bethe}}(r) = (r^2 - 1) I \;-\; r\,A \;+\; D.
    ]
6. vindex (VertexPropertyMap): 행/열 순서(인덱스) 지정 (미지정 시 내부 index 사용)
7. operator (bool, 기본값 False):
  - False → 희소 행렬(scipy.sparse) 형태 반환
  - True → LaplacianOperator(LinearOperator 서브클래스) 반환
8. csr (bool, 기본값 True):
  - operator=False일 때, True이면 csr_matrix, 아니면 coo_matrix 형태
반환:
- 기본: csr_matrix (희소)
- 혹은 operator=True라면 LaplacianOperator (메모리 절약·병렬화 등 장점)

2.1 Bethe Hessian이란?

[
\text{Bethe Hessian: } \quad
H(r) \;=\; (r^2 - 1)\mathbf{I} \;-\; r\,A \;+\; D.
]

논문([bethe-hessian], Saade et al. 2014)에서 제안된 deformed Laplacian.
희박(sparse) 그래프에서 군집 구조를 스펙트럴 방식으로 효과적으로 추출할 수 있는 행렬.
laplacian(g, norm=False, r!=1)로 호출하면 이 Bethe Hessian 행렬을 반환함(= “정규화 파라미터 (r)” 활용).

3. 파이썬 코드 예시 튜토리얼

아래 예시는:

정치 블로그(polblogs) 네트워크를 graph-tool에 내장된 예제로 불러오기
일반 라플라시안과 정규화 라플라시안(또는 Bethe Hessian)을 각각 생성
scipy.sparse.linalg를 이용해 고윳값(eigenvalues)를 구하고 시각화

3.1 Laplacian(일반) 고윳값 스펙트럼 확인

# laplacian_tutorial_basic.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) 그래프 로드: polblogs (정치 블로그 네트워크)
    g = gt.collection.data["polblogs"]
    
    # 라플라시안(기본=비정규화, operator=True => LinearOperator 반환)
    L_op = gt.laplacian(g, operator=True, norm=False)
    
    # 노드 수
    N = g.num_vertices()
    
    # 2) 고윳값 계산: LR (largest real), SR (smallest real)
    #    N//2개는 큰 부분, 나머지는 작은 부분
    ew1 = spla.eigs(L_op, k=N//2, which="LR", return_eigenvectors=False)
    ew2 = spla.eigs(L_op, k=N - N//2, which="SR", return_eigenvectors=False)
    
    # 고윳값 합치기
    ew = np.concatenate([ew1, ew2])
    
    # 3) 시각화
    plt.figure(figsize=(8, 2))
    plt.scatter(np.real(ew), np.imag(ew),
                c=np.sqrt(np.abs(ew)), alpha=0.6, edgecolors='none')
    plt.xlabel(r"Re($\lambda$)")
    plt.ylabel(r"Im($\lambda$)")
    plt.title("Laplacian Spectrum (un-normalized)")
    plt.tight_layout()
    plt.show()

if __name__ == "__main__":
    main()

코드 설명

g = gt.collection.data["polblogs"]
- graph-tool에서 제공하는 예시 그래프.
gt.laplacian(g, operator=True, norm=False)
- 일반 라플라시안(정규화 안 함).
- operator=True -> 반환값은 LaplacianOperator(LinearOperator). 메모리 절감 + 병렬 곱셈 지원.
spla.eigs(L_op, k=..., which="LR"/"SR")
- 부분 고윳값을 계산 (큰 것부터 k개 or 작은 것부터 k개).
- 스펙트럼 전체를 대략적으로 파악하기 위해 LR+SR 나눠서 병합.
고윳값(실부,허수부)을 산점도로 그려서 확인.

3.2 정규화 라플라시안(or Bethe Hessian) 사용 예시

# laplacian_tutorial_norm_bethe.py

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

def main():
    g = gt.collection.data["polblogs"]
    N = g.num_vertices()
    
    # (A) 정규화 라플라시안
    L_norm_op = gt.laplacian(g, norm=True, operator=True)
    ew1_norm = spla.eigs(L_norm_op, k=N//2, which="LR", return_eigenvectors=False)
    ew2_norm = spla.eigs(L_norm_op, k=N - N//2, which="SR", return_eigenvectors=False)
    ew_norm = np.concatenate([ew1_norm, ew2_norm])
    
    plt.figure(figsize=(8,2))
    plt.scatter(np.real(ew_norm), np.imag(ew_norm),
                c=np.sqrt(np.abs(ew_norm)), alpha=0.6)
    plt.xlabel(r"Re($\lambda$)")
    plt.ylabel(r"Im($\lambda$)")
    plt.title("Normalized Laplacian Spectrum")
    plt.tight_layout()
    plt.show()
    
    # (B) Bethe Hessian (r != 1, norm=False)
    # 예: r=2.0 (임의로)
    L_bethe_op = gt.laplacian(g, norm=False, operator=True, r=2.0)
    ew1_b = spla.eigs(L_bethe_op, k=N//2, which="LR", return_eigenvectors=False)
    ew2_b = spla.eigs(L_bethe_op, k=N - N//2, which="SR", return_eigenvectors=False)
    ew_b = np.concatenate([ew1_b, ew2_b])
    
    plt.figure(figsize=(8,2))
    plt.scatter(np.real(ew_b), np.imag(ew_b),
                c=np.sqrt(np.abs(ew_b)), alpha=0.6)
    plt.xlabel(r"Re($\lambda$)")
    plt.ylabel(r"Im($\lambda$)")
    plt.title("Bethe Hessian Spectrum (r=2.0)")
    plt.tight_layout()
    plt.show()

if __name__ == "__main__":
    main()

코드 해설

정규화 라플라시안: laplacian(g, norm=True, ...)
- 여기서는 (\displaystyle L_{\text{norm}} = I - D^{-1/2} A D^{-1/2}) 형태가 생성됨.
Bethe Hessian: laplacian(g, norm=False, r=2.0, operator=True)
- (\displaystyle H(r) = (r^2 -1) I - r\,A + D).
- (r=2.0)는 임의 선택. 실제론 그래프 특성에 맞춰 정함(예: (\sqrt{\text{avg.degree}}) 등).

4. 파라미터/옵션 정리

deg: in, out, or total
- 방향 그래프에서 어떤 차수를 사용할지.
- 무방향 그래프면 보통 "out" default.
weight: EdgePropertyMap
- 가중 라플라시안
- 수식상 (L{ii} = \sum_j w{ij}), (L{ij} = - w{ij}) (가중 연결)
r:
- norm=False일 때, r != 1이면 Bethe Hessian으로 간주.
- 논문([bethe-hessian])에서 제시한 군집 검출 최적화에 사용.
operator vs. sparse matrix:
- operator=True → 반환이 LaplacianOperator(LinearOperator).
  - 메모리 효율적, 병렬 곱셈 가능, scipy.sparse.linalg 연산과 호환.
- operator=False → csr_matrix 또는 coo_matrix (희소행렬).
csr: True/False
- True → csr_matrix, False → coo_matrix.

5. 라플라시안 행렬 활용

스펙트럴 클러스터링
- 라플라시안(특히 정규화 라플라시안)의 0 근처 고윳값/고유벡터를 사용 → 군집화
연결성 분석
- 무방향 그래프에서 라플라시안의 최소 고윳값(=0) 다중도가 connected component 수와 연관
Bethe Hessian으로 희박 그래프 군집 검출(논문 [bethe-hessian] 참고)
시계열·동적 해석 등 라플라시안 관련 PDE 해석(그래프 기반 전파 모델)

6. 요약 및 마무리

laplacian(g, ...) 함수는 그래프의 (정규화) 라플라시안이나, 특정 파라미터 (r\neq 1)일 때 Bethe Hessian(“deformed Laplacian”) 행렬을 만들어주는 중심 도구입니다.
스펙트럴 분석(고윳값·고유벡터)을 통해 네트워크 군집, 구조적 특성, 연결성, 동역학 해석 등을 할 수 있습니다.
파라미터:
- norm=True → 정규화 라플라시안
- r != 1 & norm=False → Bethe Hessian
- operator=True → 메모리 효율적 LinearOperator (병렬 지원)
응용: 군집화, 전파/연결성 분석, sparse 그래프에서 Bethe Hessian으로 고성능 군집 탐색 등.

이처럼 graph-tool의 laplacian 함수는 간단한 호출을 통해서도 다양한 라플라시안 계열 행렬을 빠르게 만들고, scipy.sparse.linalg를 이용한 스펙트럴 연산을 쉽게 접목할 수 있게 해줍니다. 도시·교통 빅데이터나 대규모 네트워크를 다룰 때, “부분 고윳값”을 효율적으로 구하기 위해 operator=True 모드를 자주 활용할 수 있다는 점도 기억해 두면 좋겠습니다.

즐거운 네트워크 분석 되세요!

아래 튜토리얼은 graph-tool 라이브러리의 spectral.incidence 함수를 사용해, 그래프의 인시던스(incidence) 행렬을 만들어보고 분석(예: 특이값 분해)하는 방법을 단계별로 살펴봅니다. 초보자를 위해 최대한 친절하게 파이썬 코드, 한글 주석을 상세히 포함했으며, 인시던스 행렬이 무엇이고 어떻게 해석되는지도 함께 설명합니다.

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

1.1 기본 개념

그래프에는 노드(정점)와 간선이 있습니다.

노드: 예) 도시, 사람, 교차로 등
간선: 노드들을 연결하는 연결(도로, 관계)

인시던스 행렬은 그래프의 노드와 간선 간의 “연결(incidence)” 정보를 행렬 형태로 나타낸 것입니다.

무방향 그래프((N)개의 노드, (M)개의 간선)일 때, 인시던스 행렬 (B)는 보통 (N \times M) 크기를 가집니다.
- 행: 노드, 열: 간선
- (B_{i,e} = 1) if 노드 (i)가 간선 (e)에 포함(involved)되어 있다, 아니면 0.
방향 그래프일 때는, “해당 간선이 나에게 들어오는가( +1 ), 나에게서 나가는가( -1 ), 무관하면 0” 등으로 정의되기도 합니다. (라이브러리마다 정의가 다를 수 있음)

이를 이용하면, 그래프의 구조를 노드(\leftrightarrow)간선 “누가 누구와 연결되었는가” 관점에서 파악할 수 있게 됩니다.

1.2 graph-tool에서의 정의

graph_tool.spectral.incidence 문서에서:

무방향 그래프:
[
B_{v,e} =
\begin{cases}
1 & \text{if edge } e \text{는 노드 } v \text{와 incident(연결)},\
0 & \text{otherwise}.
\end{cases}
]
방향 그래프:
[
B_{v,e} =
\begin{cases}
1 & \text{if } e \text{는 } v \text{로 incoming}, \
-1 & \text{if } e \text{는 } v \text{에서 outgoing}, \
0 & \text{otherwise}.
\end{cases}
]

즉, 열 하나(간선 (e))가 특정 노드 (v)와 어떤 관계인지 “+1, -1, 0”으로 표현.

2. 함수 시그니처 및 파라미터

graph_tool.spectral.incidence(
    g, 
    vindex=None, 
    eindex=None, 
    operator=False, 
    csr=True
) -> csr_matrix or IncidenceOperator

g (Graph): 분석할 그래프 객체
vindex (VertexPropertyMap): 노드(행) 순서를 정의하는 맵(없으면 내부 index 사용)
eindex (EdgePropertyMap): 간선(열) 순서를 정의(없으면 내부 index 사용)
operator (bool):
- False → 희소행렬(scipy.sparse) 반환
- True → IncidenceOperator(LinearOperator) 형태 반환(메모리 절약, 병렬 연산 가능)
csr (bool):
- True & operator=False일 때, csr_matrix 형태
- 그렇지 않으면 coo_matrix.

3. 파이썬 코드 예시: 인시던스 행렬과 특이값 분해

아래 예시는 graph-tool에 내장된 “political blogs” (정치 블로그) 그래프를 불러온 뒤, 인시던스 행렬을 생성하고, scipy.sparse.linalg.svds(부분 특이값 분해)로 특이값을 계산한 뒤 시각화하는 예입니다.

# incidence_tutorial.py

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

def main():
    # 1) 샘플 그래프 로딩: "polblogs"
    g = gt.collection.data["polblogs"]
    
    # 2) 인시던스 행렬 생성
    #    - operator=True => IncidenceOperator (LinearOperator) 반환
    #    - operator=False => 실제 희소행렬(scipy.sparse) 반환
    B_op = gt.incidence(g, operator=True)
    
    # 노드 수, 간선 수
    N = g.num_vertices()
    M = g.num_edges()
    print("Num vertices =", N, "Num edges =", M)
    
    # 3) 특이값(singular values) 계산
    #    - svds: 부분 특이값 분해
    #    - which="LM" => 큰 값부터?
    #    - which="SM" => 작은 값부터?
    #    => tutorial 문서 예시
    s1 = svds(B_op, k=N//2, which="LM", return_singular_vectors=False)
    s2 = svds(B_op, k=N - N//2, which="SM", return_singular_vectors=False)
    s = np.concatenate((s1, s2))
    s.sort()
    
    # 4) 시각화
    plt.figure(figsize=(8, 2))
    plt.plot(s, "s-", alpha=0.7, markeredgecolor='none')
    plt.xlabel(r"Index")
    plt.ylabel(r"Singular value $\sigma_i$")
    plt.title("Incidence matrix singular values for polblogs")
    plt.tight_layout()
    plt.show()

if __name__ == "__main__":
    main()

코드 해설

g = gt.collection.data["polblogs"]
- graph-tool에 내장된 정치 블로그 그래프.
B_op = gt.incidence(g, operator=True)
- 인시던스 행렬(혹은 연산자).
- operator=True → IncidenceOperator(LinearOperator) → 대형 그래프에서 메모리 효율, 병렬 곱셈 지원.
svds(...)로 특이값 분해(SVD)
- 인시던스 행렬은 직사각 형태(NxM)일 수 있으므로, 보통은 square matrix가 아님 → 고윳값 말고 특이값을 보는 게 합리적.
- “LM”(largest magnitude)과 “SM”(smallest magnitude) 나눠서 원하는 부분의 특이값을 구함.
시각화:
- 특이값 배열 s를 정렬 후 플롯
- 그래프 구조에서 인시던스 행렬의 특이값은 여러 구조적 성질(예: rank, connectedness, edge/node 관계 등)과 관련.

4. 인시던스 행렬의 해석

크기:
- (\text{행} = N(\text{노드 수}), \text{열} = M(\text{간선 수})).
- 무방향 그래프이면, 해당 간선이 어떤 노드와 incident하면 1, 아니면 0.
- 방향 그래프면 들어오면 +1, 나가면 -1 (혹은 라이브러리 규칙에 따라 반대).
특이값 분해:
- 인시던스 행렬은 보통 사각이므로 고윳값(고유벡터) 대신 SVD(특이값 분해)를 살펴본다.
- 랭크(rank): 그래프의 연결성과 관련(연결 그래프인 경우 incidence가 일정한 차원).
그래프 분석:
- 인시던스 행렬을 통해 “노드 vs. 간선” 관점에서, 어떤 노드가 많은 간선을 가지고 있는지, 어떤 간선이 여러 노드에 걸쳐 있는지 등을 계산 가능.
- 나아가 “cycle space”나 “cut space” 분석에 유용.

5. 파라미터 및 옵션 간단 정리

vindex, eindex
- 행(노드) 순서, 열(간선) 순서를 원하는 맵(VertexPropertyMap, EdgePropertyMap)으로 지정 가능.
- 예: vindex[node] = ..., eindex[edge] = ...로 커스텀 인덱스.
operator (bool)
- True → IncidenceOperator(LinearOperator), 메모리 절감 + 병렬 곱셈
- False → 실제 희소 행렬(scipy.sparse.csr_matrix or coo_matrix)
csr (bool)
- True & operator=False이면 csr_matrix 리턴,
- 아니면 coo_matrix.

6. 정리

incidence 함수는 그래프의 노드-간선 관계를 행렬(혹은 연산자)로 반환.
무방향 그래프 vs. 방향 그래프일 때 정의가 다름(방향일 경우 +1/-1로 구분).
(노드 수 x 간선 수) 크기의 행렬이므로, 정방 행렬이 아닌 경우가 많아 특이값(SVD) 분석이 중요.
operator=True 옵션을 주면 큰 그래프 처리 시 효율적(병렬·메모리).

요약

인시던스 행렬은 “노드 ↔ 간선” 연결 정보를 2차원 매트릭스로 표현한 것. 특이값 분해를 통해 그래프 구조적 특성을 파악하거나, 네트워크 해석(connectedness, cycle space 등)에 활용할 수 있습니다.

7. 추가 아이디어

랭크(rank) vs. 연결성
- 무방향 연결 그래프에선 (\text{rank}(B) = N-1) 등 흥미로운 이론적 결과가 있음.
방향 그래프
- 실제 (\pm 1) 할당(진입 vs. 진출)에 따라 행렬의 성질이 달라짐(“접합 행렬” 등).
큰 그래프 처리
- “operator=True + svds” 방식으로 부분 특이값만 빠르게 구해, 그래프 특성을 요약 가능.

위 아이디어들을 확장해보면, 인시던스 행렬을 다양한 그래프 알고리즘(회로망, 흐름, 커트셋, 주기(cycle) 탐색 등)에 적용할 수 있습니다. 즐거운 그래프 분석 되세요!

아래는 Stochastic Matrix(확률 행렬)에 대한 위키백과 영문 글 일부를 발췌한 내용을 한글로 꼼꼼히 설명하고, 필요한 수식/개념/원리에 집중하여 최대한 자세하고 친절하게 정리한 것입니다. (소제목, 내용, 식, 개념적 해설 포함)

1. 스토캐스틱(Stochastic) 행렬이란 무엇인가?

스토캐스틱 행렬(확률 행렬)은 마코프 체인(Markov chain)의 전이(transition)를 나타내는 정방행렬입니다. 즉, 행렬의 각 원소가 모두 음이 아닌 확률(0 이상 1 이하)을 나타내고, 보통 각 행(혹은 열)의 합이 1이 되도록 정의합니다.

Right stochastic matrix: 행(가로줄)의 합이 1이 되도록 정의. 즉, (\sum{j} P{i,j} = 1).
- 행벡터(확률분포)를 오른쪽에서 곱했을 때, 새 확률분포를 얻게 되므로 "right"라고도 함.
Left stochastic matrix: 열(세로줄)의 합이 1. 즉, (\sum{i} P{i,j} = 1).
- 열벡터(확률분포)를 왼쪽에서 곱하는 것에 대응.

이 글(원본)에서는 주로 “right stochastic matrix(행 합=1)” 기준으로 설명합니다.

1.1 용어

확률 행렬(probability matrix), 전이 행렬(transition matrix), 대체(substitution) 행렬, 마코프 행렬(Markov matrix) 라고도 불림.
마코프 체인(Markov chain)의 개념: 어떤 확률과정에서 “다음 상태”가 “현재 상태”에만 의존하는 성질(=마코프 성질). 이때 상태 간 전이 확률을 모아놓은 것이 스토캐스틱 행렬.

2. 간단한 예시: right stochastic matrix

행렬 (P)가 (n \times n)이고, 각 원소 (P_{i,j})는 0 이상 1 이하의 확률.
또한, 각 행의 합이 1:
[
\sum{j=1}^{n} P{i,j} = 1\quad \text{(모든 행 i에 대해)}
]
해석: (P_{i,j})는 “상태 i에서 상태 j로 넘어갈 확률”을 의미.
마코프 체인에서 확률분포를 행 벡터 (\pi)로 두면,
[
\pi{\text{(새)}} = \pi{\text{(이전)}} \cdot P
]
식으로 “다음 시간”의 분포를 구할 수 있음.

3. 스토캐스틱 행렬의 역사(마코프의 기여)

Andrey Markov (러시아 수학자, 1856~1922)가 20세기 초반(1906년 무렵) 처음으로 이 개념을 다룸.
원래는 언어학적 분석, 카드 셔플(card shuffling), 일반적인 확률론 연구에 이용.
이후 Andrey Kolmogorov 등이 마코프 과정을 연속시간으로 확장.
1950년대 이후, 경제학(econometrics), 회로이론(circuit theory), 행동과학, 지리학(사이클 분석), 주거 계획 등 수많은 분야에 적용.

4. 정의 및 성질

4.1 마코프 체인 전이행렬로서의 스토캐스틱 행렬

마코프 체인을 생각하면, 상태공간 (S)가 (n)개(유한)라고 하자. “상태 i에서 j로 가는 확률”을 (P_{i,j})라고 할 때, 전이행렬 (P)는:

[
P =
\begin{pmatrix}
P{1,1} & P{1,2} & \cdots & P{1,j} & \cdots & P{1,n} \
P{2,1} & P{2,2} & \cdots & P{2,j} & \cdots & P{2,n} \
\vdots & \vdots & \ddots & \vdots & \ddots & \vdots \
P{i,1} & P{i,2} & \cdots & P{i,j} & \cdots & P{i,n} \
\vdots & \vdots & \ddots & \vdots & \ddots & \vdots \
P{n,1} & P{n,2} & \cdots & P{n,j} & \cdots & P{n,n}
\end{pmatrix}
]

그리고
[
\sum{j=1}^{n} P{i,j} = 1 \quad (\text{각 i마다})
]
이는 “한 상태 i에서 가능한 모든 j로 전이 확률을 다 합하면 1”이 됨을 의미한다.

4.2 연산과 성질

만약 (P')과 (P'')가 둘 다 right stochastic 이라면, 그 곱 (P' \cdot P'')도 right stochastic.
[
(P' P'') 1 = P' (P'' 1) = P' 1 = 1
]
여기서 1은 “모든 원소가 1인 열벡터”.
(P^k) (k제곱) 또한 right stochastic이고, 이는 “k단계 후의 전이 확률”을 의미한다.
초기 확률분포 (\pi^{(0)})가 있을 때, (k)번 반복하면
[
\pi^{(k)} = \pi^{(0)} \cdot P^k.
]

5. 고유벡터(행벡터)와 stationary distribution

정지분포(Stationary distribution) (\pi):
[
\pi P = \pi
]
즉, “(\pi)가 바뀌지 않는” 고정점(fixed point) 확률분포.
스토캐스틱 행렬 (P)의 스펙트럼(고윳값)을 보면, 최대 고윳값이 1이 되고, 그에 대응하는 고유벡터(행벡터)가 하나 존재한다.
보통 “1이라는 고윳값”에 해당하는 (행)고유벡터가 바로 위 정지분포(확률분포) 역할을 할 수 있다.
irreducible + aperiodic 같은 조건(페론-프로베니우스 정리) 아래서는 이 정지분포가 유일하게 존재하고,
[
\lim_{k \to \infty} P^k =
\begin{pmatrix}
\pi \ \pi \ \vdots \ \pi
\end{pmatrix}
]
꼴(혹은 그와 유사)로 수렴한다는 점도 잘 알려짐(마코프 체인의 장기 분포).

6. 예시: Cat and Mouse (고양이, 생쥐) 문제

원문에서 나온 예시:

5개 상자가 일렬로 있고, 고양이와 생쥐가 각각 특정 위치에서 시작.
한 번씩 시간(t)이 증가할 때마다, 고양이와 생쥐는 각각 인접 상자로 무작위 이동(고양이는 생쥐 위치로 가면 게임 끝).
상태를 (고양이 위치, 생쥐 위치)로 잡으면, 일부 상태는 불가능하거나, 생쥐가 잡혀 게임이 끝나는 absorbing state로 볼 수 있음.
이 문제를 나타내는 5개 상태(사실은 압축해서 5개)로부터 전이 확률행렬 (P)를 구성.
결국, (cat=동일, mouse=동일 상자) 상태는 흡수상태(게임 종료).
행렬 곱으로 장기적으로 “생쥐가 언제 잡히는지(생존시간)”을 분석 → 기댓값 E[K]를 계산할 수 있음.

7. 확장: 확률벡터, 전이율, 응용

확률 벡터(probability vector): 모든 원소가 0 이상이고 합이 1인 벡터.
확률 행렬의 각 행(또는 열)이 확률 벡터가 되는 것 → “상태 i에서 j로 갈 확률”들의 목록.
스토캐스틱 행렬은 마코프 사슬(상태 전이) 외에도 확률론적 모델링 전반(유전자 교체, PageRank, 부동산 이동 등)에서 쓰임.

8. 결론적으로

정의: 스토캐스틱 행렬은 “행(혹은 열)이 1로 합산되는 음이 아닌 실수들로 구성된 정방행렬.”
용도: 마코프 체인, 확률분포의 전이, 정지 상태 계산 등 다양한 분야(통계, 금융, 생물, CS, 교통 등).
핵심 성질:
- 최대 고윳값이 1,
- (잘 연결된 경우) 그 고윳값에 해당하는 고유벡터(확률분포)로 수렴,
- 곱이 스토캐스틱 → 여러 단계 후 전이확률이 손쉽게 계산됨.
absorbing state(흡수상태), steady-state(정지상태) 등 마코프 체인 해석에서 매우 중요한 개념.

“직관적으로, 스토캐스틱 행렬은 ‘확률 분포를 또 다른 확률 분포로 바꿀 때’ 사용하는 선형 변환. 따라서 한 번, 두 번, k번 연속 곱해가며, ‘장기 상태’를 찾으면 그게 바로 ‘stationary distribution’이 된다.”

9. 참고식

Right Stochastic Matrix:
[
P{i,j} \ge 0, \quad \sum{j} P_{i,j}=1.
]
Left Stochastic Matrix:
[
P{i,j} \ge 0, \quad \sum{i} P_{i,j}=1.
]
Doubly Stochastic:
[
P{i,j} \ge 0, \quad \sum{j} P{i,j}=1, \sum{i} P_{i,j}=1.
]
정지분포 (\pi):
[
\pi P = \pi.
]

10. 요약

스토캐스틱 행렬은 각 원소가 확률(0 이상)이고, 각 행(또는 열) 합이 1이 되는 정방행렬.
마코프 체인의 전이 확률을 나타내며, 행렬연산을 통해 한 상태분포에서 다른 상태분포로 변환.
장기적으로(무한히 곱할 때) 특정 정지분포(steady-state)에 도달할 수 있으며, 이는 고윳값 1과 연결.
활용: 통계, 통계역학, 랜덤워크(PageRank), 교통흐름분석(전이 확률), 생물학적 진화(유전자 변이), 등 다양.

이상으로, 위키백과 내용을 바탕으로 스토캐스틱 행렬(확률 행렬)에 관한 개념, 역사, 성질, 응용을 상세히 정리했습니다.

아래 튜토리얼은 graph-tool 라이브러리에서 제공하는 transition 함수를 사용해, 그래프(네트워크)의 전이 행렬(transition matrix) 을 생성하고, 이를 활용해 간단한 스펙트럴(고윳값) 분석을 시도하는 예시 코드와 함께 자세한 한글 설명을 제공하는 가이드입니다.

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

전이 행렬(transition matrix) 은 일종의 “확률 행렬(stochastic matrix)” 개념을 그래프에 적용한 것으로서, 각 노드(정점)에서 이웃 노드로 이동하는 확률을 나타냅니다.

예: 무방향 그래프에서, 노드 (i)의 차수가 (d_i)라면, (i)에서 연결된 이웃 노드로 이동할 확률은 (1 / d_i).
방향 그래프에서는 out-degree를 고려하여, 한 노드의 out-edge로 향할 확률을 동일하게 나누어 가질 수 있습니다.

정의상, 전이 행렬 (T)는 확률(스토캐스틱) 행렬이 되므로, 마코프 체인(Markov chain) 해석에서 “노드 간 전이 확률”로 해석할 수 있습니다.

1.1 수식적으로

아래와 같이 표현할 수 있습니다.

[
T{ij} =
\begin{cases}
\frac{A{ij}}{di}, & \text{(노드 i의 차수가 }d_i \text{, } A{ij}=1 \text{면 이웃)}\
0, & \text{(연결 없음)}
\end{cases}
]

(A)는 인접행렬(adjacency matrix).
(d_i)는 노드 (i)의 차수(degree).
가중치가 있으면, (A{ij}) 대신 가중치 (\text{weight}(i,j))를 이용하고, (d_i = \sum{j} \text{weight}(i,j)) 로 정의.

graph-tool에서 transition(...) 함수는 위 개념을 자동으로 계산해, 전이 확률행렬(혹은 해당 연산자)을 만들어 줍니다.

2. 함수 `transition(g, weight=None, vindex=None, operator=False, csr=True)`

graph_tool.spectral.transition(
    g, 
    weight=None,
    vindex=None,
    operator=False,
    csr=True
) -> csr_matrix or TransitionOperator

2.1 주요 파라미터

g (Graph)
- 분석할 그래프 객체.
weight (EdgePropertyMap, optional)
- 간선 가중치가 있을 경우 이를 지정.
- 지정하면 전이확률 계산 시, “노드 i의 (가중) out-degree” = (\sum_j \text{weight}(i, j)) 을 분모로 사용.
- 없으면 무가중치(=1)로 취급.
vindex (VertexPropertyMap, optional)
- 행/열에서 노드를 어떤 순서로 배치할지. 미지정 시 그래프 내부 인덱스 그대로 사용.
operator (bool)
- False면 희소행렬(scipy.sparse) 반환
- True면 TransitionOperator(LinearOperator). 메모리 절약 + 병렬 연산 가능.
csr (bool)
- operator=False일 때, True면 csr_matrix, 아니면 coo_matrix 반환.

2.2 반환값

전이 행렬 (T) (형태: csr_matrix or TransitionOperator).

3. 튜토리얼 예시 코드

다음은 graph-tool에 내장된 정치 블로그("polblogs") 그래프를 불러와 전이 행렬을 생성하고, 이를 이용해 부분 고윳값(또는 eigs)을 구해 시각화하는 예시입니다.

# transition_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) 샘플 그래프 로딩: "polblogs" (정치 블로그 네트워크)
    g = gt.collection.data["polblogs"]
    
    # 2) 전이 행렬 생성
    #    - operator=True => TransitionOperator 반환(LinearOperator)
    #    - operator=False => 실제 희소행렬(sc.sparse)의 csr 또는 coo
    T_op = gt.transition(g, operator=True)
    
    # 노드 수
    N = g.num_vertices()
    print("Number of vertices:", N)
    
    # 3) 고윳값(eigenvalues) 계산
    #    - which="LR": real part가 큰 것부터 k개
    #    - which="SR": real part가 작은 것부터 k개
    #    => 스펙트럼 대략 살피기 위해 각 절반씩 구해 합침
    ew1 = spla.eigs(T_op, k=N//2, which="LR", return_eigenvectors=False)
    ew2 = spla.eigs(T_op, k=N - N//2, which="SR", return_eigenvectors=False)
    ew = np.concatenate((ew1, ew2))
    
    # 4) 시각화
    plt.figure(figsize=(8, 2))
    plt.scatter(np.real(ew), np.imag(ew),
                c=np.sqrt(np.abs(ew)), alpha=0.6, edgecolors='none')
    plt.xlabel("Real part of eigenvalue")
    plt.ylabel("Imag part of eigenvalue")
    plt.title("Transition matrix spectrum (polblogs)")
    plt.tight_layout()
    plt.show()

if __name__ == "__main__":
    main()

코드 해설

graph-tool에서 "polblogs" 그래프 로드
gt.transition(g, operator=True): 전이 연산자(TransitionOperator)를 생성
scipy.sparse.linalg.eigs(...)로 부분 고윳값 계산(‘LR’ + ‘SR’)
고윳값 실부/허수부를 2D 산점도로 시각화

4. 전이 행렬 해석 팁

확률 행렬(스토캐스틱)
- 전이 행렬 (T)는 행합이 1(무방향 그래프라면, out-degree=degree)인 확률 행렬.
- 한 번 곱할 때마다 “확률분포”가 다음 스텝에서의 분포로 전이.
최대 고윳값 = 1
- 스토캐스틱 행렬은 고윳값 1을 가지며, 그 대응 고유벡터(정지 분포)가 존재(irreducible+aperiodic이면 유일).
PageRank나 임의 랜덤워크
- 전이 행렬은 “랜덤 서퍼가 노드 사이를 이동할 때” 쓰는 확률과 유사.
- 다만, 편향이나 감쇠 인자 등이 있으면 변형이 필요.
스펙트럼에서
- (\lambda=1) 근처에 있는 고윳값(들)은 장기 거동(steady-state)과 관련.
- 고윳값이 1보다 작으면(실수 부분 기준), 무한번 곱할 때 해당 모드(기여)는 사라짐(감쇠).

5. 파라미터 활용 예시

가중치(weight): 그래프가 가중치 있는 edges를 가짐 → (\text{weight}(i,j))를 인접 행렬 값으로 사용. 전이확률 계산 시, 노드 (i)의 가중치 합으로 나누어 (\frac{\text{weight}(i,j)}{\sum_{k}\text{weight}(i,k)}).
vindex: 행/열에서 노드를 임의 순서로 배치하고 싶을 때 지정.
operator=True: 대규모 그래프에서 효율성(메모리, 병렬 곱)
csr=True: 희소행렬 형식 중 CSR(압축 행 인덱스) 사용.

6. 종합 정리

transition 함수는 그래프(무방향·유향·가중치 포함)의 랜덤워크 전이행렬을 쉽게 생성.
전이행렬 = “각 노드에서 이웃 노드로 이동할 확률” 행렬 → 즉, 스토캐스틱(확률) 행렬.
마코프 체인 해석 가능: (확률분포) (\times) 전이행렬 (T) → 다음 단계 분포.
전이행렬의 고윳값(특히 최대 고윳값=1) → 정지분포(steady-state)나 랜덤워크의 장기 거동을 시사.

한 줄로

“전이행렬은 그래프에서 이웃으로 이동할 확률을 나타내는 스토캐스틱 행렬로, 마코프 체인 관점에서 노드 분포가 어떻게 변하는지 분석하는 핵심 도구.”**

7. 추가 아이디어

정지분포(stationary distribution) 찾기
- 전이행렬 T에서 (\pi) s.t. (\pi T = \pi)
- 보통 (\lambda=1) 대응 (왼쪽) 고유벡터.
무작위 초기 분포에 대해 (\lim_{k\to\infty} \pi^{(0)} T^k) = 정지분포(유일하다면).
PageRank 등에서 “teleportation” 등을 더해 확률행렬 수정 가능.
커뮤니티 탐색: 전이행렬 기반 random walk로 군집화(울리케 럭스버그 스펙트럴 클러스터링 등).

이상으로 transition 함수를 이용해 그래프의 전이행렬을 생성·분석하는 방법과 예시 코드를 살펴보았습니다. 현업에서 무작위 랜덤워킹(교통흐름, 사용자 이동, 통신 패킷 경로 등) 모델링 시, 네트워크 전이행렬을 자주 사용하게 됩니다. 그런 경우 graph_tool의 transition 함수를 손쉽게 활용하면 됩니다.

즐거운 네트워크 분석 되세요!

아래 튜토리얼은 graph-tool 라이브러리에서 제공하는 modularity_matrix 함수를 사용해, 네트워크의 모듈러리티(modularity) 행렬을 생성하고, 이를 토대로 스펙트럴(고윳값) 분석 등을 시도하는 방법을 단계별로 소개합니다. 초보자도 쉽게 따라 할 수 있도록 한글 주석과 자세한 설명을 충분히 포함했습니다.

1. 모듈러리티(Modularity)와 모듈러리티 행렬이란?

1.1 모듈러리티 개념

모듈러리티(modularity)는 네트워크(그래프)에서 군집(community) 구조를 평가하기 위한 대표적 지표입니다.
- M.E.J. Newman과 M. Girvan이 제안.
- “네트워크를 여러 집단(커뮤니티)으로 나눴을 때, 내부 연결이 촘촘하고(같은 집단 안) 외부 연결이 드문 정도”를 정량화.

1.2 모듈러리티 행렬 (B)

Newman의 논문([newman-modularity])에서 제시된 바에 따르면, 모듈러리티 행렬은
[
B = A - \frac{k \cdot k^T}{2m}
]
형태로 정의하는 경우가 많습니다.
- 여기서
  - (A)는 그래프의 인접행렬,
  - (k)는 각 노드의 차수(벡터),
  - (m)은 전체 간선 수의 절반(무방향 그래프에서).
- 그래프에서 “무작위 그래프와의 차이(= 실제 인접행렬 - 기대값)”를 나타냄.
graph-tool의 modularity_matrix 함수는 내부적으로 위와 유사한 식(수식에서 (\frac{k_i k_j}{\sum k}) 형태)을 적용해 모듈러리티 행렬을 생성하며, 결과물을 LinearOperator 형태로 반환합니다(희소행렬 대신).

2. 함수 시그니처와 파라미터

graph_tool.spectral.modularity_matrix(
    g,
    weight=None,
    vindex=None
) -> LinearOperator

g: 그래프 객체(Graph).
weight: (optional) EdgePropertyMap (간선 가중치). 없다면 무가중치(=1).
vindex: (optional) VertexPropertyMap으로 행/열에서 노드 순서를 지정할 수 있음. 기본은 내부 인덱스 사용.
반환: B, 즉 모듈러리티 행렬을 표현하는 LinearOperator(sparse 형태).

(\textbf{Note}): modularity_matrix 함수는 희소행렬(scipy.sparse)이 아니라 LinearOperator 객체로 반환합니다. 내부적으로 곱셈 연산을 정의해서, 큰 그래프도 효율적으로 처리할 수 있도록 되어 있습니다.

3. 파이썬 예시 코드

아래 예제에서는 graph-tool에 내장된 "polblogs" (정치 블로그) 그래프를 사용, 모듈러리티 행렬을 구한 후, 부분 고윳값을 계산해 스펙트럼(실수·허수부) 시각화까지 보여줍니다.

# modularity_matrix_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) 예시 그래프 불러오기: "polblogs"
    g = gt.collection.data["polblogs"]
    N = g.num_vertices()
    
    # 2) 모듈러리티 행렬 생성
    #    - 함수가 LinearOperator 객체로 반환
    B_op = gt.modularity_matrix(g, weight=None, vindex=None)
    
    # 3) 고윳값(eigenvalues) 계산
    #    - which="LR": 실수부가 큰 고윳값부터 k개
    #    - which="SR": 실수부가 작은 고윳값부터 k개
    #    => 두 가지를 합쳐 전체 스펙트럼을 대략 얻어봄
    ew1 = spla.eigs(B_op, k=N//2, which="LR", return_eigenvectors=False)
    ew2 = spla.eigs(B_op, k=N - N//2, which="SR", return_eigenvectors=False)
    ew = np.concatenate((ew1, ew2))
    
    # 4) 시각화
    plt.figure(figsize=(8, 2))
    plt.scatter(np.real(ew), np.imag(ew),
                c=np.sqrt(np.abs(ew)), alpha=0.6, edgecolors='none')
    plt.xlabel(r"Re($\lambda$)")
    plt.ylabel(r"Im($\lambda$)")
    plt.title("Modularity matrix spectrum (polblogs)")
    plt.tight_layout()
    plt.show()

if __name__ == "__main__":
    main()

코드 해설

g = gt.collection.data["polblogs"]:
- graph-tool에서 제공하는 정치 블로그 네트워크.
gt.modularity_matrix(...):
- weight=None → 무가중치(=1).
- 반환값은 B_op (LinearOperator).
scipy.sparse.linalg.eigs(B_op, ...)로 고윳값 계산.
산점도(실수축 vs. 허수축)로 고윳값 분포 시각화.

4. 모듈러리티 행렬의 해석

모듈러리티 행렬 (B)는 네트워크가 커뮤니티 구조를 얼마나 갖고 있는지 스펙트럴 방식으로 분석하는 도구:

네트워크가 램덤(무작위) 그래프 대비 얼마나 “내부 연결”이 많은지를 행렬 형태로 표현.
고윳값 0 근처, 양/음 고윳값 벡터 등이 실제 커뮤니티 분할에 힌트를 줄 수 있음.
- 예) 뉴먼의 spectral modularity maximization 기법에서, 모듈러리티 행렬의 최대 고윳값 대응 고유벡터를 사용해 2-way 분할 등을 시도.
희소성: 보통 그래프가 희박하면(간선 적은 경우) (B)도 sparse하게 구현 가능.
graph-tool은 LinearOperator 형태로 제공 -> 대규모 그래프도 메모리 부담 덜고, 필요한 연산(곱셈, 부분 고윳값)을 효율적으로 수행.

4.1 수식 형태 (무방향, 무가중치)

[
B{ij} = A{ij} - \frac{k_i k_j}{2m}
]

(A)는 인접행렬.
(k_i)는 노드 (i)의 차수.
(m = \sum_{i} k_i / 2) (전체 간선 수).
가중치가 있으면 (A_{ij}) 대신 (\text{weight}(i,j)), (k_i = \sum \text{weight}(i,j)).

5. 확장: 실제 커뮤니티 검출 과정

실제로 커뮤니티를 찾으려면, 모듈러리티 극대화(Newman 2006) 기법 등에서 이 행렬의 고윳값·고유벡터를 이용:
- 고윳값 분해 → 주성분(가장 큰 양의 고윳값) 고유벡터를 sign-based 분류 → 2-way 커뮤니티
- 또는 여러 고윳값을 뽑아 k-means → multi-way 커뮤니티
- graph-tool 라이브러리 내 minimize_blockmodel_dl등 다른 내부 알고리즘도 있으니 상황에 따라 적절히 사용 가능.

6. 주의/팁

operator=True:
- 내부적으로 B를 전부 만들지 않고, 행렬-벡터 곱등만 정의하여, 큰 그래프에서도 효율적.
- 고윳값 계산 시 memory 절감.
weight:
- 간선 가중치가 있으면, 인접행렬 원소가 그 가중치가 되어, (\frac{k_i k_j}{2m})에서 (k_i)=노드(i)의 가중합.
고윳값 계산:
- (\text{which="LR"}) → 실수부가 큰 순
- (\text{which="SR"}) → 실수부가 작은 순
- modularity matrix는 양/음 고윳값이 두루 나타날 수 있어, 커뮤니티 구조 해석 시, 특정 부분의 고윳값만 중요할 수 있음.

7. 마무리

modularity_matrix 함수: 모듈러리티 기반 스펙트럴 분석 용도의 행렬(LinearOperator)을 생성.
뉴먼-걸번이 제안한 모듈러리티 개념(“실제 연결 - 무작위 예상 연결”)을 행렬 형태로 나타냄.
커뮤니티 구조를 찾는 데 유용: 고윳값·고유벡터를 통해 군집을 스펙트럴 방식으로 추론.
그래프가 크면 operator=True로 반환된 B를 직접 곱 연산 통해 효율적으로 고윳값/벡터 추정 가능.

“모듈러리티 행렬”은 네트워크 군집 탐색에서 역사적으로 중요한 방법론이며, graph-tool이 이를 Lazy(LinearOperator) 방식으로 다룬다는 점이 실무나 대규모 그래프 분석에 큰 장점이 될 수 있습니다.

즐거운 네트워크 분석 되세요!

Sylen

AI가 재밌는 걸

이전 포스트

graph.correlations

다음 포스트

graph_tool.spectral

1. 그래프(네트워크)란?

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

2.1 개념 한 줄 요약

2.2 조금 더 구체적으로

3. 왜 이렇게 만들까?

4. 라플라시안 행렬의 예시

\end{pmatrix}

\end{pmatrix}

5. 라플라시안으로 뭘 할 수 있나?

5.1 연결 성분 개수

5.2 스펙트럴 클러스터링(2-way 군집)

5.3 확장(정규화 라플라시안, Bethe Hessian)

6. 중학생 시선에서 요약하자면

7. 한마디로...

결론

1. 문제 설정: 희박(Sparse) 그래프에서의 군집 검출과 SBM

2. 기존 접근: Non-backtracking operator vs. 표준 스펙트럴 방법

3. Bethe Hessian(deformed Laplacian): 핵심 아이디어

3.1 Bethe Hessian 정의

3.2 Bethe Hessian과 non-backtracking operator (B)의 연결

3.3 Bethe Hessian과 Ising 모델, “Paramagnetic point”에서의 해석

4. 스펙트럼 분석의 실제: SBM에서 임계점 달성

4.1 정규화 파라미터 (r_c = \sqrt{\rho(B)})

5. 알고리즘 개요: “Bethe Hessian 스펙트럴 클러스터링”

5.1 장점

6. 실험 결과(논문 요약)

7. 수식·원리 정리

7.1 핵심 수식

7.2 직관

8. 결론 및 의의

9. 참고 식과 그림 해설

정리: 왜 “Bethe Hessian”인가?

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

2. graph-tool의 laplacian 함수 개요

2.1 Bethe Hessian이란?

3. 파이썬 코드 예시 튜토리얼

3.1 Laplacian(일반) 고윳값 스펙트럼 확인

코드 설명

3.2 정규화 라플라시안(or Bethe Hessian) 사용 예시

코드 해설

4. 파라미터/옵션 정리

5. 라플라시안 행렬 활용

6. 요약 및 마무리

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

1.1 기본 개념

1.2 graph-tool에서의 정의

2. 함수 시그니처 및 파라미터

3. 파이썬 코드 예시: 인시던스 행렬과 특이값 분해

코드 해설

4. 인시던스 행렬의 해석

5. 파라미터 및 옵션 간단 정리

6. 정리

요약

7. 추가 아이디어

1. 스토캐스틱(Stochastic) 행렬이란 무엇인가?

1.1 용어

2. 간단한 예시: right stochastic matrix

3. 스토캐스틱 행렬의 역사(마코프의 기여)

4. 정의 및 성질

4.1 마코프 체인 전이행렬로서의 스토캐스틱 행렬

4.2 연산과 성질

5. 고유벡터(행벡터)와 stationary distribution

6. 예시: Cat and Mouse (고양이, 생쥐) 문제

7. 확장: 확률벡터, 전이율, 응용

8. 결론적으로

9. 참고식

10. 요약

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

1.1 수식적으로

2. 함수 transition(g, weight=None, vindex=None, operator=False, csr=True)

2.1 주요 파라미터

2.2 반환값

3. 튜토리얼 예시 코드

코드 해설

4. 전이 행렬 해석 팁

5. 파라미터 활용 예시

6. 종합 정리

한 줄로

7. 추가 아이디어

2. graph-tool의 `laplacian` 함수 개요

2. 함수 `transition(g, weight=None, vindex=None, operator=False, csr=True)`