군집 탐색

배치 모형(Configuration Model)

배치 모형은 네트워크 과학에서 매우 중요한 개념으로, 네트워크의 구조를 이해하고 분석하는 데 사용되는 null 모델입니다.

실제 예시를 들어보겠습니다:

1. 대학교 동아리 네트워크를 생각해봅시다.

• 각 학생(정점)의 친구 수(연결성)를 유지하면서
• 실제 친구관계(간선)를 무작위로 재배치합니다

예를 들어:

• 철수가 원래 영희, 민수와 친구였다면 → 연결성 2 유지
• 재배치 후 철수는 다른 두 명(예: 지영, 현우)과 친구가 될 수 있습니다

2. SNS 팔로워 네트워크도 좋은 예시입니다.

• 각 사용자의 팔로워 수는 그대로 두고
• 누구와 연결되는지는 무작위로 바꿉니다

이 모형의 핵심은:

• 각 정점의 연결 개수(degree)는 보존
• 하지만 누구와 연결되는지는 무작위로 재배치
• 이를 통해 실제 네트워크의 특성을 통계적으로 비교 분석 가능

이 모형을 통해 실제 네트워크가 얼마나 무작위성에서 벗어나 있는지, 어떤 특별한 패턴을 가지고 있는지 분석할 수 있습니다.

---

군집성

• 군집 탐색의 성공 여부

• 그래프화한 군집 s의 내부 간선의 수가
• 배치 모형에서 만든 군집 s 내부간선의 수의 기대값 보다 커야한다.