[소프트웨어 응용] Network Community & Community Detection

Network Community

Network Community

앞서 살펴본 Granovetter’s theory

→ 네트워크는 강하게(빽빽하게) 연결된 노드들의 집합들로 구성되어있다는 것을 보았다.

Network Communities

: 내부에는 많은 연결이 존재하고, 외부에는 적은 연결이 있는 노드들의 집합

→ 클러스터, 그룹, 모듈이라고도 한다.

🙄 실제 네트워크 상에서 커뮤니티를 어떻게 식별하고 찾아낼까

real-world에 대한 관찰) Zachary’s Karate club network

사회적 관계에서 라이벌 관계 또는 갈등과 다툼이 일어나면 그룹이 흩어지더라.

→ 네트워크에서 엣지 몇 개를 제거 했더니, 그룹이 나누어 지더라 (커뮤니티의 형성)

→ 이 성질을 이용해서, 최소의 개수로 엣지를 제거했을 때, 그룹이 분리되면 그 그룹들을 커뮤니티로 볼 수 있겠다.

Community Detection

Method) Girvan-Newman - Strength of Weak Ties

Edge betweenness: 어떤 엣지를 지나가는 shortest path의 개수

이 값이 크면, 전체 네트워크에서 정보의 흐름에 중요한 역할을 한다.

예를 들어, 한강에 다리가 하나 뿐이라면, 강북-강남을 오가기 위해서는 그 다리를 무조건 건너가야 한다. 그만큼 이 다리는 전체 도로 네트워크에서 중요한 역할을 한다.

커뮤니티A와 커뮤니티B를 연결하는 weak tie에 경우, A에서B를 가려면 이 weak tie를 지나가야 할 것이다. 따라서 weak tie는 edge betweenness가 커뮤니티에 내재된 strong edge보다 크다.

만약 한강에 있는 다리를 모두 없애게되면 서울은 강북과 강남이라는 두 개의 커뮤니티로 나눠지게 된다. 한강 다리가 아닌, 강북 도심에 있는 도로의 경우 아무리 없애도 서울을 강북과 강남으로 쪼갤 수 없다. 한강 다리는 강북, 강남 사이의 weak tie이고, 강북의 도로는 strong tie이다. weak tie를 잘라내면 최소한의 개수로 클러스터링을 할 수 있다.

→ 이렇게 weak tie를 잘라내서 커뮤니티를 찾아내는 것이 Girvan-Newman의 알고리즘이다.

Girvan-Newman Algorithm:

• undirected unweighted network상에서

• 모든 엣지의 betweenness를 계산하고

• betweenness가 가장 높은 엣지를 제거한다.

→ 그리고 다시 계산하고 제거하고를 반복한다.

(엣지를 제거하면 betweenness가 바뀌기 때문에 재계산 해야한다)

→ 언제까지 ? 쪼개진 컴포넌트들이 커뮤니티일 때까지

(얼마나 쪼개야 커뮤니티라고 볼 수 있는지는 또 생각해볼 문제다. 강북과 강남을 커뮤니티라고 볼 수 있으면 한강다리만 제거하고, 더 작은 지역구를 커뮤니티로 본 다면, 여러 도로들도 제거해야 할 것이다. 보통 커뮤니티의 개수를 정해서 그 개수만큼 쪼갠다. )

→ 네트워크는 2개, 4개, 8, 16, … 개로 쪼개지게 된다. : Hierarchical decomposition

이 방법으로 네트워크에서 커뮤니티를 찾아내려면 또 생각해볼 문제가 2가지가 생긴다.

• 어떻게 betweenness를 계산할 것인지?

• 커뮤니티의 개수를 어떻게 정할 것인지?

Sol1) Betweenness 계산

1. 한 노드A를 찝어 올려서 A를 루트로 하는 트리처럼 모양을 잡는다. → 레벨을 맞춰서 놓음
   1. A는 레벨0, A의 인접 노드들은 레벨1, 그 노드들의 인접 노드들은 레벨2, ..

2. 모든 노드에 대해 A에서 출발해서 올 수 있는 shortest path의 개수를 계산한다. → A부터 BFS (너비우선탐색)
   1. 노드 X의 shortest path 개수는 부모거 더한 값이다

3. 최하위 노드부터 다시 올라가면서 betweenness를 계산한다.
   1. 최하위 노드는 1을 부모 노드에게 나누어준다. 이 때 나눠주는 비율은 각 부모 노드의 shortest path의 개수비율로 나누어준다.
   2. 그 위의 노드는 자식 노드로부터 받은 값에 1을 더한 값을 또 부모한테 나누어준다. 이 때도 shortest path 개수 비율로 나누어준다.
   3. A까지 계산하면 된다.

4. 노드A 외에 다른 모든 노드에 대해서 1~3 과정을 반복해서 얻어진 betweenness값을 다 더하면 된다.

Sol2) The number of clusters 선택

몇 개의 클러스터로 나누는 것이 좋은가 → 이를 판단하는 지표 Modularity

Modularity Q

: 커뮤니티를 얼마나 잘 쪼갯는가를 나타내는 지표이다.

$$Q \propto \sum_{s\in S}[ (\# \text{edges within group }s) - (\text{expected }\#\text{ edges within group }s)$$

• s: 전체 네트워크 S에서 파티셔닝된 커뮤니티

• 실제 각 그룹 안에 있는 엣지의 개수와 기댓값과의 차이의 합이다.

• 기댓값은 널 모델을 가정했을 때의 값이다.

• 이 값이 크다는 것은 기댓값과 차이가 크다는 것

• 보통은 이 값은 [-1, 1] 사이로 정규화해서 사용한다.

• 이 값이 양수이면 : 기대했던 그룹 내의 엣지 수보다 실제 값이 더 크다는 것

• 정규화된 Q(G, S)의 값이 어느정도면 좋을까
  • 경험적으로, 0.3<Q<0.7 정도면 이건 커뮤니티다라고 판단할 수 있다!

결론

• Girvan-Newman Algorithm으로 네트워크를 쪼개나가다보면, 모듈라리티 값이 증가하다가 감소하게 됨 → 모듈라리티 값이 최대일 때, 멈추면 된다.