중첩 기반 접근법

1. 간단한 소셜 네트워크 예시:

철수(1) - 영희(2) - 민수(3)
   |         |
지영(4) --- 상우(5)

2. 먼저 각 노드의 이웃 집합을 구합니다:

N(철수) = {영희, 지영}
N(영희) = {철수, 민수, 상우}
N(민수) = {영희}
N(지영) = {철수, 상우}
N(상우) = {영희, 지영}

3. 공통 이웃 수 계산 (S_{u,v}):

S_{철수,영희} = |{영희} ∩ {철수, 민수, 상우}| = 0
S_{철수,민수} = |{영희, 지영} ∩ {영희}| = 1
S_{영희,지영} = |{철수, 민수, 상우} ∩ {철수, 상우}| = 2

4. 임베딩 벡터 예시 (2차원):

z_철수 = [0.8, 0.2]
z_영희 = [0.7, 0.3]
z_민수 = [0.5, 0.5]
z_지영 = [0.3, 0.7]
z_상우 = [0.4, 0.6]

5. 손실 함수 계산 예시:

철수-영희 쌍에 대해:

z_철수^T z_영희 = [0.8, 0.2] · [0.7, 0.3]
                = 0.8×0.7 + 0.2×0.3
                = 0.56 + 0.06
                = 0.62

L_{철수,영희} = ||0.62 - 0||^2 = 0.3844

영희-지영 쌍에 대해:

z_영희^T z_지영 = [0.7, 0.3] · [0.3, 0.7]
                = 0.7×0.3 + 0.3×0.7
                = 0.21 + 0.21
                = 0.42

L_{영희,지영} = ||0.42 - 2||^2 = 2.4964

6. 전체 손실 함수:

L = L_{철수,영희} + L_{철수,민수} + ... + L_{지영,상우}

8. 최적화 목표:

• zu^T z_v 값이 S{u,v}에 가까워지도록 조정
• 공통 이웃이 많을수록 임베딩 벡터간 내적값이 커지도록
• 공통 이웃이 적을수록 임베딩 벡터간 내적값이 작아지도록

9. 실제 활용:

• 친구 추천: 내적값이 높은 노드 쌍 추천
• 커뮤니티 탐지: 비슷한 임베딩을 가진 노드들을 그룹화
• 링크 예측: 높은 내적값을 가진 미연결 노드 쌍 예측

10. 장점:

• 구조적 유사성 보존
• 계산 효율성
• 확장성

이러한 방식으로 네트워크의 구조적 특성을 저차원 임베딩 공간에 효과적으로 인코딩할 수 있습니다. 공통 이웃 수를 기반으로 한 이 접근법은 특히 소셜 네트워크에서 노드 간의 유사성을 잘 포착할 수 있습니다.

---

경로 기반 vs 중첩 기반

경로 기반과 중첩 기반의 차이점과 장단점을 실제 예시로 비교 설명해드리겠습니다.

1. 같은 네트워크로 비교:

철수 - 영희 - 민수 - 지영
        |         |
      상우 ----- 동준

2. 두 방식의 접근 차이:

경로 기반:

철수-민수 관계: A²_{철수,민수} = 1 (2단계 경로)
철수-지영 관계: A³_{철수,지영} = 1 (3단계 경로)

중첩 기반:

철수-민수 관계: S_{철수,민수} = 1 (공통 이웃: 영희)
철수-지영 관계: S_{철수,지영} = 0 (공통 이웃 없음)

4. 주요 차이점:

계산 방식:

• 경로 기반: k단계 경로 존재 여부
• 중첩 기반: 공통 이웃의 수

수식:

• 경로 기반: L = Σ ||zu^T z_v - A^k{u,v}||²
• 중첩 기반: L = Σ ||zu^T z_v - S{u,v}||²

5. 장단점 비교:

경로 기반 장점:

• 전역적 구조 파악 용이
• 긴 거리 관계도 포착
• 정보 전파 분석에 유리

경로 기반 단점:

• 계산 복잡도 높음 O(|V|³)
• k값 선택의 어려움
• 메모리 사용량 많음

중첩 기반 장점:

• 계산 효율적 O(|E|)
• 지역적 구조 잘 포착
• 커뮤니티 탐지에 효과적

중첩 기반 단점:

• 원거리 관계 파악 어려움
• 희소 네트워크에서 성능 저하
• 방향성 관계 표현 한계

6. 적합한 사용 케이스:

경로 기반:

• 정보 흐름 분석
• 영향력 전파 모델링
• 전체 네트워크 구조 파악

중첩 기반:

• 친구 추천 시스템
• 커뮤니티 탐지
• 소셜 클러스터링

7. 실제 예시 비교:

소셜 네트워크 분석:

경로 기반: "철수는 지영과 3단계 떨어져 있다"
중첩 기반: "철수와 지영은 공통 친구가 없다"

친구 추천:

경로 기반: "가까운 거리에 있는 사람 추천"
중첩 기반: "공통 친구가 많은 사람 추천"

8. 복잡도 비교:

경로 기반: 
- 시간: O(|V|³) (행렬 곱)
- 공간: O(|V|²) (인접행렬)

중첩 기반:
- 시간: O(|E|) (이웃 비교)
- 공간: O(|V| + |E|) (이웃 리스트)

결론적으로, 두 방법은 각각의 장단점이 있으며, 분석하고자 하는 네트워크의 특성과 목적에 따라 적절한 방법을 선택해야 합니다. 실제 응용에서는 두 방법을 보완적으로 사용하는 것도 좋은 전략일 수 있습니다.