[Social Network] Balanced Signed Network ( 균형잡힌 부호형 네트워크) with Non-complete Graph

이전 글에서는 Complete Graphs에서 Balanced 한 지 안 한 지 확인해보았다.

 

하지만 네트워크가 완전 그래프가 아닐 때,

🧐 Signed Network가 Balanced인지 아닌지 어떻게 확인 할 수 있을까?

 

Network is balanced if and only if it contains no cycle with an odd number of negative edges

네트워크는 홀수개의 (-) 간선을 갖는 사이클을 갖고 있지 않을 때 balanced하다.

💡 Balanced인지 확인하는 법

 

1. (+) 간선으로만 구성된 Connected Components를 찾자.

 ( 만약 이 Connected Components에 (-)간선이 있다면 Unbalanced한 것이다!)

 

2. 각 Connected Components들을 수퍼 노드(Super Node)라 하자.

 

3. BFS를 사용하며 노드들의 편을 만들어 Global Coalitions을 만족하지 확인해주자.

 

4. 만약 Global Coalitions을 만족하지 않으면 Unbalanced한 것이다.

자료 출처 : cc224w.stanford.edu

 

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