아래는 Ki-ichiro Hashimoto가 1989년에 발표한 논문 "Zeta Functions of Finite Graphs and Representations of p-Adic Groups" (출처: Advanced Studies in Pure Mathematics 15, 1989, pp.211-280) 내용 일부를, 가능한 한 친절하고 자세하게 정리한 것입니다. 증명 스케치나 개념 설명에 집중하여, 그래프의 유한 그래프의 제타함수(Zeta Functions), p진수 군(p-adic groups) 표현론과의 연관 등을 핵심적으로 다룹니다. 실제 논문은 풍부한 수식과 더 광범위한 맥락을 포함하고 있으니, 여기서는 소개된 절(subset) 위주로 용어, 수식, 개념, 원리를 꼼꼼히 해설해보겠습니다.

---

0. 서론(Introduction)

0.1 다루는 두 가지 문제

논문에서는 (1) 유한 그래프의 조합론적 문제와, (2) p진 군(p-adic group)의 이산 부분군(discrete subgroup) 및 그 표현(Representation)에 관한 산술적 문제를 함께 다룹니다. 표면상 전혀 달라 보이지만, 저자에 따르면 둘은 “그래프 제타함수(Zeta function of finite graphs)”라는 개념으로 긴밀히 연결됩니다.

• 유한 그래프 (X) (나무(tree)가 아님)에서, 폐 경로(closed path)를 어떻게 ‘새로 정의된 제타함수’를 통해 세고, 그 성질로부터 그래프의 구조(스펙트럼, 위상적 성질 등)를 알 수 있는가?
• 한편, p진 군의 이산 부분군 ( \Gamma \subset \mathrm{SL}(2, K)) (또는 더 일반적으로 rank-one 군)에서 정의되는 Ihara형 제타함수가, 실제로는 특정 “정규성(regularity) 조건을 만족하는 유한 그래프”의 제타함수와 동일한 구조를 갖는다는 사실.

즉, “p진 군에서의 Selberg류 제타(Selberg-Ihara zeta) = 그래프 제타함수”라는 발견을 일반화하고, 그 결과로부터 그래프 이론과 p진 군 표현론 모두에 유용한 결론들을 도출합니다.

0.2 배경: Ihara 제타함수(Ihara's Zeta)

• Ihara가 1960년대에, p진 필드 (K) 상의 (\mathrm{SL}(2,K)) 이산 부분군 (\Gamma)에 대해 Selberg 제타함수를 모방한 제타함수 (Z_\Gamma(u))를 정의. 이는 마치 “유한체 위에서 정의된 (커브) 해석적 제타”와 유사한 이론적 성질을 갖는다.
• 나중에 Serre(, Sunada 등)에 의해, 이 Ihara 제타함수 (Z_\Gamma(u))가 사실상 “(\Gamma)가 작용하는 유한 그래프(quotient)가 k+1 정규(valency) 그래프”일 때, 동일하게 해석된다는 사실이 알려짐.
• 저자는 이를 더욱 넓은 설정(랭크-1 p진군 등)으로 확장한 뒤, “그래프 제타함수”가 어떻게 ‘p진 군의 표현(spectral decomposition)’과 연결되는지를 설명한다.

---

1. 그래프(Graph)와 멀티그래프(Multigraph)의 정의

논문에서는 비(非)방향성 멀티그래프 (X)를 다룬다. 즉,

1. 멀티그래프: (정점 집합 (V_X), 에지 집합 (E_X), 에지 양끝점을 정하는 ‘incident map’ (e)) 로 이뤄짐.
2. 중복 에지(multiple edges)나 고리(loop)가 있을 수 있음.
3. 에지가 양방향을 구별하지 않는(비방향성) 구조.
4. 부분 경로(path), 폐 경로(closed path), 환(circuit), 축소(reduced) 경로 등에 대한 정의를 체계적으로 함.

예: 멀티그래프에서 어떤 에지 (e)가 ({y, y^{-1}}) 식으로 대응될 때, (y)가 “정방향”, (y^{-1})이 “역방향”이라 부르는 편의를 쓴다.

---

2. 유한 그래프의 제타함수(Zeta Functions)

2.1 유한 그래프 (X)와 기본군((\pi_1(X)))

• (X)가 연결된 유한 그래프일 때, “기본군 (\pi_1(X,P_0))”는 자유군(free group)으로, 그 랭크 (r)는 (#(E_X) - #(V_X) + 1).
• 축소 폐 경로(reduced closed path) 와 (\pi_1(X))의 원소 간의 일대일 대응(‘사이클(cycle) <-> (\pi_1)의 켤레류(conjugacy class)))을 사용해 제타함수를 정의.

2.2 정의: 그래프 제타함수 (Z_X(u))

논문에서는 Ihara 스타일로,
[
ZX(u) \;:=\; \exp \Bigl(\sum{\substack{C \in \mathcal{R}!\mathcal{C}!\mathcal{P}\\text{원소 }C \text{축소 폐경로}}} \frac{u^{\ell(C)}}{\ell(C)}\Bigr),
]
여기서 (\ell(C))는 경로 (C)의 길이. (\mathcal{R}!\mathcal{C}!\mathcal{P})는 모든 원소가 축소이고, (자신의 제곱 등)을 통해 ‘backtracking(역추적)’이 없는 폐경로들의 집합.
결과적으로,

• (Z_X(u))는 유한 그래프에서의 “축소 폐 경로”를 지수적 공식으로 모은 것이라는 점.
• Ihara(정규 그래프)나 Serre(카버(cover) 이론), Sunada(스펙트럼, 그래프) 등이 연구한 구조를 일반화.

논문 주요 정리(정리 2.22 등)는 이 (Z_X(u))가 유리함수(rational function)임을 증명.

---

3. 그래프 스펙트럼(Spectrum)과의 연관

그래프 (X)의 인접행렬 (A) (nxn 대칭행렬), 그 고윳값 집합(스펙트럼)은 “스펙트럴 그래프 이론”의 주된 연구대상이다. 저자는 특히:

• 정규(regular) 그래프: 각 정점 valency가 (q+1) 일정할 때, Ihara(1966)가 “(\det(I - Au + qu^2))” 형태와 (Z_X(u))가 관련 있음을 보였다.
• 양단성(bipartite) 그래프: 스펙트럼이 ±(\lambda) 쌍, 0 등으로 나타나는 등의 특성을 지님. 이 경우 그래프 제타함수에서 ((1+qu)) 같은 인자가 따로 등장.

그 결과,

1. Ihara가 보인 “정규 그래프 (X)”에서의 제타함수 공식:
   [
   Z_X(u)^{-1} \;=\; (1-u^2)^{r-1} \; \det[I - A\,u + q u^2],
   ]
   (r)은 그래프의 독립 사이클 수.
2. Bipartite 그래프에서 유사 식.

Ramanujan 그래프(“(|\lambda_i| \le 2\sqrt{q})”) 등도 동일 맥락. 이론적으로, 제타함수의 근들이 그래프의 고윳값(eigenvalues) 정보와 밀접히 연결됨을 논의.

---

4. 하모닉 함수(Harmonic functions)와 Hodge decomposition

그래프 이론에서, 조화(harmonic) 함수는 “각 정점 (v)에서, 인접한 변들(또는 이웃정점)에서 함수값의 합이 0”이 되는 조건을 만족하는 함수. 이것이:

• ((1-u))이라는 단순 폴인(인자 factor)을 제타함수에서 만들어냄 (차수 1, 즉 한 차원짜리 기여).
• 이런 조화함수 공간이 그래프의 첫 번째 호몰로지 (H^1(X))와도 일대일 관련(Hodge 이론)됨.

결국 조화조건((p*(T_1)f = - f) 등)과 중심성(loop, cycle 등) 분석을 통해, “((1-u))가 몇 번 중복해서 곱해지는지(=차수)”가 “그래프의 독립사이클 수 (r)와 동일하다”는 점(정리 5.26, 4.16 등)을 보임.

---

5. 연산자 (\mathbf{C}[T_1, T_2])와 증명

저자는 universal covering 트리 (\widetilde{X})에서 정의되는 작용(“correspondence” (T_1, T_2))을 다룬다.

• bipartite이면, 정점이 (V_1 \cup V_2)로 분할됨, 그 사이를 오가는 에지집합에 대해 (T_1, T_2)가 “incidence relation”을 반영.
• (\mathbf{C}[T_1, T_2])는 이 두 연산자(“수반(symmetric) 관계를 만족”)를 생성하는 비교환(noncommutative) 다항식 환.
• Representation: 유한 그래프 (X)에서 (\pi_1(X))가 작용 -> 그 induced module (M^1(X)) 위에 (\mathbf{C}[T_1, T_2])가 표현됨.

이를 통해:

1. 정리 (2.22) “(Z_X(u))는 rational”
2. 정리 (3.14) “반이진(bipartite) 정규 그래프에 대해, (Z_X(u))가 (\det(I - \cdots)) 형태로 factorization”
3. 결과적으로, (X)가 정규(or 반이진 세미레귤러)일 때, 제타함수의 특정 인자 ((1-u), (1 \pm q u), (1 - q_1q_2 u)) 등이 그래프 스펙트럼 ({\lambda_i})와 직접 짝지음이 생김.

---

6. p진 군(Representations)과의 연결

이 부분이 논문의 후반부 핵심이다:

• p진 군 (G) (랭크-1 유형) 에서의 정점 안정자(parahoric subgroup) (B \subset G).
• Hecke 대수 (\mathfrak{H}(G, B)) 와 (\mathbf{C}[T_1, T_2]) 사이의 동형이 성립하는 상황에서, “유한 그래프 (X)”의 (\mathbf{C}[T_1, T_2])-표현과 “p진 군의 단위적(irreducible unitary) 표현”이 동일한 방법으로 분해.
• 그 결과, 정리 (IV): 그래프 제타함수의 특정 인자(특수근, 근들의 중복도)가 곧 p진 군 표현론에서 “L(^2)-공간의 분해, 다중도”와 동일함을 밝혔다.

다시 말해, “p진 군의 중복도(multiplicity) = 그래프 제타함수의 인자의 차수”라는 식으로 대응.

---

7. 제타함수의 특수값 및 복잡도(Complexity) 등

7.1 스패닝 트리 수(Complexity)

그래프 (X)의 스패닝 트리(Spanning tree) 개수를 (K(X))라 할 때,

• (\det(I - Au + qu^2))에서 (u=1) 근방 확장(“정리 7.7 등”)을 통해 “(\lim_{u \to 1}(1-u)^r Z_X(u))”가 “스패닝 트리 수” 등과 관련됨.
• 실제로, Ihara형 제타함수가 “수론에서의 대수곡선의 제타함수”와 흡사한 구조(“Class number formula” 유사)를 갖는다.

예시: “(K(X)=)(n-2 \det(...))” 등 공식이 성립.

7.2 모듈라 곡선(Modular curve) 케이스

p진 군 (\mathrm{SL}(2, K))의 특정 부분군은 “modular curve”와 대응. 이때 클래스 수(function field의 class number)와 “((1-u)^{r} Z_X(u))의 (u=1)에서의 값”이 일치하는 현상. Eichler-Shimura, Serre 이론 등과 연결된다.

---

8. 기타 (Miscellaneous) — 그래프 조작 및 제타함수 변환

마지막 부분에, 그래프 연산(complementary, line graph, Cartesian product 등)을 통해 새 그래프를 구성했을 때, 그 제타함수(또는 스펙트럼)가 어떻게 변하는지를 일괄적으로 분석:

1. 보족 그래프(complementary graph) (X^c): 정규 그래프 (X)에서 (\mathrm{Spec}(X^c))의 변화, 그에 따른 (Z_{X^c}(u))의 식.
2. Line graph (L(X)): (\mathrm{Spec}(L(X))) 알면 (Z_{L(X)}(u))도 쉽게 구할 수 있다.
3. Cartesian product (X_1 \times X_2), Conjunction (X_1 \wedge X_2), Strong product (X_1 * X_2), Join (X_1 + X_2), Composition (G[X_1, \dots, X_p]) 등. 각각 그래프 스펙트럼의 테두리에 있는 결과((\mathrm{Spec})를 모아서 (\mathrm{Spec}) 등)로부터 (\mathrm{Z}_X(u))를 유도.

---

9. 여러 예시(Especially small graphs 등)

논문 부록에서는 (n \le 6) 또는 (m<8) 등 소규모 그래프(조건: end point(말단점) 없는, 중복 에지와 loop 존재 가능) 30여 개를 전부 분류해, 각각에 대해

• “특성다항식 ( \phi_X(z) )” (즉, 인접행렬의 characteristic polynomial)
• “제타함수 (Z_X(u))”

를 실제로 전개해 보인다. 이는

1. Ramanujan 여부(근이 (\pm \sqrt{q}) 근방에 있는지) 확인,
2. ((1-u)) 군집(multiplicity) 등,
3. 스펙트럼 계산이 어렵지 않은 예제에서 “모두 손으로 계산 가능”

을 보여주는 대규모 예시를 제공한다.

---

결론 요약

Ki-ichiro Hashimoto의 이 논문은,

1. 유한 그래프 (X) 에서 정의한 “Ihara-형 그래프 제타함수” (Z_X(u))가 (\det(I - Au + qu^2))-류 공식(특히 정규/반이진 그래프)으로 유리함수임을 보인다.
2. 그래프의 “스펙트럼(eigenvalues)” 분석(인접행렬 분석)과 제타함수의 근(poles, zeros) 사이의 직접적 관계를 밝힌다.
3. 그래프의 하모닉 함수를 통해 “((1-u)) 인자”가 나타나는 이유를 해석((H^1)-cohomology = harmonic space).
4. p진 군(랭크1)에서의 이산 부분군 (\Gamma)가 만드는 “유한 그래프 (X)와 제타함수 (Z_X(u))”가 곧 “p진 군의 표현론(특히 B-고정벡터가 있는 부분) 분해”에 상응함을 보인다.
5. 스패닝 트리 수(Complexity)나 modular curve에서의 class number와 그래프 제타함수의 특수값((u=1) 근방)도 유사한 형태.

이 모든 결과는, 그래프 제타함수가 “대수곡선(congruence zeta)”, “Selberg zeta” 등의 유비를 가짐을 강력히 시사하며, “p진 군 표현론” 및 “스펙트럴 그래프 이론” 양쪽에서 매우 흥미로운 상호작용이 존재한다는 점을 강조한다.

“다른 언어(군이론 vs. 그래프이론)로 표현된 구조가 사실상 동일한 지표(제타함수) 아래 만나며, 여기서 얻는 스펙트럼, 위상 invariants, representation multiplicity 등이 일대일 대응한다.”

이것이 본 논문의 핵심 기여이며, 이후 (Sunada, Lubotzky-Phillips-Sarnak, Drinfeld 등) 많은 연구에 영감을 주었다고 볼 수 있다.

아래는 Krzakala et al.(2013)의 논문 “Spectral redemption: clustering sparse networks” (arXiv: 1306.5550v2)에서 발췌한 내용을 가능한 한 친절하고 자세하게 정리한 것입니다. 이 논문은 ‘희소(sparse) 네트워크에서 스펙트럴 기법이 기존에는 서브옵티멀하다고 알려져 있던 상황’을 극복하기 위해, 비(非)반환(non-backtracking) 랜덤 워크 연산자를 이용한 새로운 스펙트럴 군집 알고리즘을 제안합니다. 이로써 “정규성(regularity)이 떨어지는 희소 그래프”에서도 ‘단순 인접행렬(adjacency matrix) 기반’ 기법들이 놓치는 문제를 해결할 수 있다는 주요 성과를 보입니다.

---

1. 배경과 문제의식

1.1 네트워크 군집(community) 문제와 스펙트럴 방법의 한계

• 군집(모듈) 검출: 사회·생물·기술 네트워크에서, 노드를 ‘비슷한 것끼리’ 그룹화하는 전형적 문제.
• 대표 알고리즘 크게 두 갈래:
  1. 통계적 추론 모델(stochastic block model 등)을 이용해 ML/MAP/Bayes 방식으로 검출 (예: Belief Propagation 등).
  2. 스펙트럴 기법: 인접행렬(A), 라플라시안(L), 모듈러리티 행렬(M) 등의 고윳값/고유벡터 이용 → 군집 파악.

그동안 스펙트럴 기법이 (상당한 고밀도(dense) 그래프나 정규 그래프)에서는 잘 작동해 왔지만, 최근 연구(예: [9–12])에서 희소 그래프(sparse graph)의 경우 기존 스펙트럴 기법이 성능이 확 떨어지고 “올바른 군집을 찾지 못한다”는 사실이 드러남.

1.2 임계점(Detectability threshold)과 블록 모델(Block model)

• Stochastic block model(SBM): 노드를 (q)개 군집으로 나누고, 군집 내/간 간선이 확률적으로 연결되는 (가장 널리 쓰이는) 확률적 모델.
• 네트워크가 “너무 희소” 해지면, 임의 잡음이 커서 군집을 찾기 “불가능”해지는 임계점을 이론적·통계역학적으로 분석할 수 있음([9–11]).
• But, 실제로 Belief Propagation 등은 이 임계점 근처까지 “군집 검출 가능” (optimal) 인데, 전통 스펙트럴 기법(예: 인접행렬 A, 라플라시안 L)은 임계점보다 훨씬 이전에 “실패” → 큰 갭(gap)이 존재.

논문 핵심 질문: “(\mathrm{Adjacency})나 (\mathrm{Laplacian}) 대신 다른 연산자를 사용하면, 희소 그래프에서도 임계점 근방까지 스펙트럴 기법이 작동할 수 있지 않을까?”

---

2. 비(非)반환(non-backtracking) 연산자 (B)

2.1 정의

• 그래프 (G=(V,E))가 주어졌다고 할 때, 각 간선 (e \in E)에 대해 “방향”을 붙인 edge를 (2|E|)개 생각(오고 가는 방향).
• Non-backtracking 행렬 (B)은 이 (2|E|\times 2|E|) 행렬로 정의:
  [
  B_{(u\to v),(w\to x)} \;=\;
  \begin{cases}
  1, &\text{if }v=w \text{ 그리고 } u\neq x,\
  0, &\text{otherwise}.
  \end{cases}
  ]
  즉, “현재 edge가 (u\to v)”일 때, 다음 edge가 (v \to x)가 되려면 “v=w”이어야 하고, 단 “뒤로 돌아가지 않기((u\neq x))” 조건을 만족해야 1.

2.2 왜 좋은가?

1. 고차수(large degree) 정점이 스펙트럼에 끼치는 악영향(예: 인접행렬에서, 고차수 노드가 강한 고윳값을 야기 → 유효 군집 신호가 묻힘)을 완화. Non-backtracking은 “즉시 되돌아오는” 행보 금지로, 고차수 노드 주변에서 특이점이 크게 부각되지 않음.
2. 트리 모양의 대가리(leaf), 덩치 작은 부분이 주는 잡음 등이 (\pm 1) 근처 고윳값만 생성하거나 무시될 수 있음.
3. 그래프 이론(“Ihara–Hashimoto” zeta function 등)에서 잘 알려진 사실: (B)의 스펙트럼 분포는 (\pm 1) 근처를 제외하고는 (|\lambda| \le \sqrt{c}) 범위(bulk) 내에 거의 묶임 → 군집과 연관된 큰 고윳값(또는 바깥 값)들이 더 뚜렷이 분리.

2.3 결과

• SBM에서, (B)의 최대 고윳값(leading eigenvalue)은 대략 (c) (평균 차수).
• “두 번째(혹은 그 이상의) 유의미 고윳값”이 “실수부가 bulk (\sqrt{c})보다 큰” 곳에 위치하면, 그 벡터가 곧 군집 구조를 반영. 임계점 ((c{\mathrm{in}} - c{\mathrm{out}})/2 > \sqrt{c}) 조건과 정확히 맞아떨어짐 → 임계점을 넘어서면 잡음에 파묻히지 않음.
• 이로써 (B)-기반 스펙트럴은 Belief Propagation과 같은 “최적” 임계점(Detectability threshold)까지 작동.

---

3. 실제 요약: 희소 그래프 클러스터링에서 “스펙트럴 구원(Spectral Redemption)”

1. 전통 스펙트럴(인접행렬 (A)나 라플라시안 (L)) → (\lambda_2) (두 번째 고윳값) 손실, 잡음 등에 매몰.
2. 새롭게 비반환 행렬 (B)를 정의, 이를 대각화(=고윳값 분해).
3. 2번째 고윳값(또는 그 앞뒤 고윳값들)이 확실히 군집 구조를 가리키며, 희소 네트워크에서도 임계점까지 “정확 군집” 가능.

---

4. 정리해석 (수식, 개념, 원리)

4.1 임계점(Detectability threshold) 요약

• 2개 군집(q=2, 크기반반, in–out 차이)일 때, 조건:
  [
  (c{\mathrm{in}} - c{\mathrm{out}}) ~>~ 2\,\sqrt{\,c\,}.
  ]
  이를 넘지 못하면, 통계적으로 (분류 정확도) = 무작위 수준.
• 인접행렬 (A)로는 (\lambda{\text{signal}} = \frac{c{\mathrm{in}} - c_{\mathrm{out}}}{2} + \ldots)가 bulk((\pm 2\sqrt{c}))에 파묻힘. → 스펙트럼이 제대로 분리되지 않아 실패.

4.2 Non-backtracking operator (B)

• 크기: ((2m)\times(2m)). (m=|E|). 원소는 ({(u\to v), (w\to x)}) 간 전이 가능(하지만 뒤로 돌아가지 않음)인지 나타냄.
• 스펙트럼 특징:
  • Leading eigenvalue (\approx c).
  • bulk이 (|\lambda|\le \sqrt{c}) 디스크 내.
  • 2nd eigenvalue (\lambda2 \approx (c{\mathrm{in}} - c_{\mathrm{out}})/2) (단순화).
  • (\lambda_2 > \sqrt{c})이면 군집 벡터가 분리됨 → 정확 검출.

4.3 BP(Belief propagation)와의 연관

• BP 알고리즘의 메시지 업데이트를 고차원에서 선형화하면, 결국 ((I - \frac{c{\mathrm{in}}-c{\mathrm{out}}}{2}B)) 식의 고윳값 문제로 귀결.
• (\lambda(B)>\ldots) ↔ BP에서 비자명 해(community)를 찾는 안정성.

---

5. 실험결과, 실제 네트워크 적용

5.1 블록모델 실험

• 희소(Sparse) 조건(c=상수). 기존 (A), (L), (M), “random walk matrix Q” 등은 임계점 (\gg) 이전에 성능=0(랜덤과 동일).
• (B)-기반은 BP와 거의 동일 수준, 임계점까지 성능이 유지 → “격차 해소(spectral redemption).”

5.2 실제 데이터

• Football(미국대학 미식축구), Polblogs(정치블로그), Polbooks(정치서적) 등 ground truth가 존재하거나 널리 알려진 네트워크에 (B) 스펙트럼을 계산:
  • 실수값이 원판((|\lambda|\le\sqrt{c})) 밖에 나와있는 개수가 “커뮤니티 수”와 대략 일치.
  • 해당 고유벡터로 노드를 투영 → sign 또는 k-means 등으로 분류 시, 적절한 성능.

결론: 실제 world network에서도 ((B)-스펙트럼)이 기존 인접행렬 등보다 분명히 구분 좋음.

---

6. 요약 및 의의

• 희소그래프 군집: 전통 스펙트럴 기법은 (a) 고차수 노드 잡음, (b) localized eigenvector 문제 등으로 임계점 이전에 실패.
• Non-backtracking 행렬 (B) 사용 시:
  1. 최대(leading) 고윳값=평균 차수 (c).
  2. bulk (\subset{\lambda:|\lambda|\le\sqrt{c}}).
  3. 2nd등 eigenvalue (\approx (c{\mathrm{in}}-c{\mathrm{out}})/2), 임계점 ((>2\sqrt{c}))까지 분리 잘 됨.
• 따라서 “스펙트럴 알고리즘이 BP 등과 동등(optimal) 성능”을 시현.
• 이론 근거: Ihara–Hashimoto zeta function, Belief propagation의 선형 근사, random matrix 이론에서의 비반환 행보와 bulk 분포.
• 결론: “스펙트럴 기법의 구원(Spectral redemption)” → sparse에서조차 임계점 근방까지 군집 가능케 함.

향후 과제:

• 다양한 실수치(가중) 네트워크에 (B)를 일반화(엣지 가중치 (s(u,v))로 치환).
• (B)의 근본적 스펙트럼 경계((\sqrt{c}) 부근) rigorously 증명.
• BP보다 계산이 빠르고 파라미터가 불필요하다는 장점, 다양한 실제 데이터셋으로 확장 실증.

결국, 저자들은 새로운 연산자(노드가 아닌 ‘유향 에지’를 상태로 잡고 “뒤로 되돌아가지 않는” 전이를 표현)를 통해, “희소 그래프 군집화”에서 스펙트럴 기법이 기존 기법의 한계를 극복할 수 있음을 강력히 보여준다. 이는 그래프 군집뿐 아니라, 다양한 sparse data 분석에서 일반화 가능해, 후속 연구에서 큰 영향력을 발휘했다.

아래 튜토리얼은 graph-tool 라이브러리에서 제공하는 hashimoto 함수를 이용해, Hashimoto(또는 non-backtracking) 행렬을 생성하고 활용하는 방법을 단계별로 설명합니다. 초보자도 쉽게 따라 할 수 있도록 파이썬 코드 예시와 한글 주석을 충분히 담았으니 참고하시기 바랍니다.

---

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

1.1 개념 및 동기

• Hashimoto 행렬(Hashimoto matrix)은 그래프 이론에서 “Non-backtracking” 랜덤 워크(non-backtracking walk)를 표현하기 위해 정의된 비(非)대칭 행렬입니다.
• Non-backtracking이란? 한 번 이동한 간선의 “역방향”으로 즉시 돌아가지 않는(백트래킹 금지) 규칙을 가진 행보를 뜻합니다.
• Krzakala 등([krzakala_spectral] 논문)에서, 이 Hashimoto 행렬을 기반으로 스펙트럴 군집(community detection)을 수행하면, 희소(sparse) 그래프에서도 기존 인접행렬 기반 스펙트럴 기법보다 월등히 좋은 결과를 얻을 수 있음을 보였습니다.

1.2 전통 인접행렬과의 차이

• 인접행렬 (A)는 ((|V|\times|V|)) 대칭 행렬
• Hashimoto 행렬 (H) 은 ((2|E|\times 2|E|)) (또는 compact 버전이면 (|V|\times|V|) 형태)
• 행렬의 각 행·열이 “유향 edge(방향 포함한 간선)” 혹은 “노드 쌍”을 인덱스로 삼아, 백트래킹 없는 전이만 1로 표시.

그 결과, 고차수(large degree) 노드가 불균형하게 끼치는 악영향을 줄이고, 희소 그래프에서도 스펙트럼 분석이 더 안정적으로 이루어집니다.

---

2. graph_tool의 hashimoto 함수 개요

graph_tool.spectral.hashimoto(
    g,
    index=None,
    compact=False,
    operator=False,
    csr=True
) -> [csr_matrix or HashimotoOperator or CompactHashimotoOperator]

• g: 대상 그래프 객체(Graph)
• index (EdgePropertyMap): 해시모토 행렬에서 행·열 인덱스를 어떤 간선 순서로 매핑할지 지정.
• compact (bool):
  • False(기본)면 실제 non-backtracking 행렬((2|E|\times 2|E|)) 생성
  • True면 (|V|\times|V|)짜리 “compact” 버전( Hashimoto–Krzakala 식) 생성
• operator (bool):
  • False → scipy.sparse 행렬 반환
  • True → HashimotoOperator(LinearOperator) 반환(메모리 절감 + 병렬 연산 지원)
• csr (bool):
  • True → csr_matrix
  • False → coo_matrix

반환:

• 보통은 csr_matrix (희소행렬)이 기본
• operator=True면 HashimotoOperator(혹은 compact면 CompactHashimotoOperator) 형태

2.1 compact=True 옵션

문서에서:
[
H_{\text{compact}} \;=\; D^{-1/2}\,(A)\,D^{-1/2} - \dots
]
(정확한 식은 [hashimoto]나 [krzakala_spectral] 참고)
이는 ((|V|\times|V|)) 크기이며, (\mathrm{diag}(d(v))) 등을 이용해 정의함.

• Krzakala 등에서 군집 검출에 유용함을 입증.

---

3. Hashimoto 행렬과 스펙트럴 분석: 초보자용 예시

아래 예시는 football 네트워크(미국대학 미식축구 팀 간 경기) 데이터를 사용해, 해시모토 행렬을 생성하고 고윳값(eigenvalues)을 계산·시각화하는 파이썬 코드입니다.

# hashimoto_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) 샘플 그래프 불러오기: "football"
    #    graph-tool에서 제공하는 예시 데이터 중 하나.
    g = gt.collection.data["football"]
    
    # 2) Hashimoto(Non-backtracking) 행렬 생성
    #    - operator=True => HashimotoOperator (LinearOperator)
    #    - operator=False => 실제 희소 행렬(csr_matrix or coo_matrix)
    #    여기서는 operator=True로 해봄
    H_op = gt.hashimoto(g, operator=True, compact=False)
    
    # 유향 edge의 개수는 2 * g.num_edges()
    N = 2 * g.num_edges()
    
    # 3) 부분 고윳값 계산(eigs): which="LR", "SR"
    #    - LR => (Largest Real) : 실수 부분이 큰 쪽
    #    - SR => (Smallest Real) : 실수 부분이 작은 쪽
    #    => 전체 스펙트럼 대략 파악
    ew1 = spla.eigs(H_op, k=N//2, which="LR", return_eigenvectors=False)
    ew2 = spla.eigs(H_op, k=N - N//2, which="SR", return_eigenvectors=False)
    ew = np.concatenate((ew1, ew2))
    
    # 4) 시각화
    plt.figure(figsize=(8, 4))
    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("Hashimoto matrix spectrum for Football network")
    plt.tight_layout()
    plt.show()

if __name__ == "__main__":
    main()

코드 해설

1. g= gt.collection.data["football"]:
   • graph-tool이 내장한 “college football” 네트워크 데이터.
2. H_op = gt.hashimoto(g, operator=True, compact=False)
   • compact=False → 전형적인 non-backtracking 행렬((2|E|\times 2|E|))
   • operator=True → sparse 행렬 대신 HashimotoOperator 반환(가상 연산자).
3. spla.eigs(H_op, k=..., which="LR/SR")
   • (\mathrm{scipy.sparse.linalg}) 모듈로 부분 고윳값 추출(양 극단).
   • 희소행렬(또는 연산자)에 대해 효율적으로 작동.
4. 산점도(실수부 vs. 허수부) → “Hashimoto 행렬 스펙트럼”을 시각적으로 확인.

---

4. Hashimoto 행렬: 원리와 활용

4.1 행렬 정의 (compact=False)

• 비방향 그래프일 때, 간선 (|E|)개, 각 간선은 두 방향이 있음 → 유향 edge (\to) 인덱스 0~2|E|-1
• [
  H_{(u\to v),(w\to x)} \;=\;
  \begin{cases}
  1, & \text{if } v = w \text{ and } u\neq x,\
  0, & \text{otherwise}.
  \end{cases}
  ]
• ((u \to v))에서 다음 스텝 ((w \to x))가 성립하려면 “(v=w)” 즉, 같은 정점을 잇지만, “금방 온 방향으로 돌아가지 않음((u \neq x))”이어야 하므로 1.

4.2 (compact=True) 모드

• (|V|\times |V|) 크기의 (\tilde{H}) 행렬(“Compact Hashimoto”)
• Krzakala et al.([krzakala_spectral])에서, 이 압축 버전 (\tilde{H}\approx D^{-1/2} A D^{-1/2}) - ??? 형태로, “희소 그래프 군집”에 우수한 스펙트럼 성질 가짐.

4.3 스펙트럴 분석, 군집 검출

• 희소 그래프에서, 인접행렬 기반 스펙트럴 클러스터링은 고차수 노드/노이즈 문제로 fail 가능.
• Hashimoto(Non-backtracking) 행렬은 (\pm 1) 근처 외 bulk가 (|\lambda|\le \sqrt{c})에 몰리고, 2번째(등) eigenvalue가 군집 정보 반영(“spectral redemption”).
• “정규 그래프(d-regular)”이면, 행렬 B 스펙트럼이 (\pm\sqrt{d-1}) 원(복소평면) 근처에 bulk가 분포 etc.

---

5. 정리와 주의사항

1. operator=True:
   • 실제 큰 희소행렬을 구성하지 않고, 곱(행렬-벡터)을 정의하는 연산자만 생성 → 메모리 절약, 병렬 최적화.
2. 복소 고윳값:
   • Hashimoto 행렬은 비대칭 → 고윳값이 일반적으로 복소수.
3. “편향/가중”:
   • hashimoto 함수는 “무가중” 그래프 기준. 가중 그래프용 non-backtracking은 직접 조정 필요(별도 구현 혹은 compact 변형).
4. Edge index:
   • index 인자에 edge property map을 주면, 사용자 정의 순서대로 행·열을 매핑.

---

6. 결론

• hashimoto 함수는 Hashimoto(=non-backtracking) 행렬을 손쉽게 생성하는 graph-tool 기능.
• sparse 그래프 분석에서, 인접행렬 등의 전통 스펙트럴 방식보다, 군집 구조나 topological feature 탐지에 유리.
• 간단 예시: “football” 네트워크의 스펙트럼 시각화. 실제로, 해시모토 행렬 스펙트럼에서 바깥쪽 실제(또는 복소) 고윳값이 군집을 반영하는 경우가 많음.

추가 아이디어

• (compact=True) 버전 써서 (|V|\times|V|) 행렬로 더 적은 크기 다루기
• 큰 그래프에서 operator=True → 부분 고윳값(eigs)만 구해 고차원 문제 해결
• 스펙트럴 clustering: “두 번째 고윳값(또는 real eigenvalue outside bulk)” 기반으로 노드 분류(sign or k-means)

이상으로, graph-tool의 hashimoto 함수를 이용해 non-backtracking 행렬을 생성·활용하는 기초 튜토리얼을 마칩니다. 현업(도시·교통 네트워크, 소셜 그래프 등)에서 희소·이질적인 연결구조를 가진 대규모 그래프를 분석할 때, 해시모토 행렬 기반 스펙트럴이 강력한 도구가 될 수 있습니다.