[Social Network] Strongly Connected Component (강결합)

🧐Social Network Analysis

 

💡 강결합 (Strongly Connected)?

• 방향성 그래프일 때 어떠한 노드라도 다른 노드로 가는 길이 존재
• 약결합은 방향성 없는 그래프일 때 다른 노드로 가는 길이 존재하면 된다.

 

💡 강결합 컴포넌트 (Strongly Connected Component) 란 ?

• 모든 노드의 쌍은 서로 연결돼 있다.
• 위 특성과 함께 더 큰 SCC는 존재하지 않는다.
• 아래 그림에서의 강결합 컴포넌트 = {A,B,C,G} , {E}, {F}, {D}

모든 강결합 컴포넌트 간의 간선을 이으면 DAG(Directed Acyclic Graph)가 된다.

 

🔍 Proof by contradiction(수학적 귀류법)을 이용한 증명

 

증명 1.

• 강결합 컴포넌트간을 이은 G'가 두개(S, S')가 있으며,  두 강결합 컴포넌트 간 정점 v를 공유한다고 가정하자 

• 위와 같이 정점 v가 겹치면 또 하나의 SCC가 만들어진다.
• => SCC는 만족하기 위해서는 더 큰 SCC가 존재하면 안된다. 따라서 모순(Contradiction)이다.

증명 2.

• G'가 DAG가 아니라고 가정하자.

• DAG가 아닌 G'은 강결합 컴포넌트들 사이에 간선이 생겨 하나의 SCC로 묶여지는 모순이 발생한다.

 

 

🔍 정점 v가 포함된 SCC에 속한 다른 정점들 쉽게 찾기

 

쉽게 찾기 위해서는  v에서 나올 수 있는 원소와 v에서 들어 올 수 있는 원소 간 교집합되는 원소들을 찾으면 된다.

하지만 In(v)를 찾기에는 계산하는데 많은 비용이 발생한다. ( Computational issue )

 

G 그래프의 간선들의 방향을 뒤집은 그래프의 Out(v)가 원래 G의 In(v)와 같음을 알 수 있다.

따라서 In(v)를 계산하는 것 대신에 간선들의 방향을 뒤집은 그래프의 Out(v)를 구해주자.

위의 방식의 계산 비용이 더 적게 나와 더 효율적이라고 볼 수 있다.

 

자료 출처 : cc224w.stanford.edu

 

궁금하신 것이 있으시면 언제든지 댓글 달아주세요!