[NA] #3 네트워크와 커뮤니티(Community Structure in Networks)

 

 

지난 포스팅에서는 네트워크의 특성을 노드 수준에서 정량적으로 측정하는 여러 중심성 지수들을 살펴보았습니다. 

'중심성' 지수가 네트워크에서 중요한 노드가 무엇인지를 찾아낼 수 있도록 도왔다면, 네트워크 내의 Community Structure는 '서로간에 밀접하게(densely) 연결된 노드들의 집합'을 구분할 수 있도록 합니다. 밀접하게 연결된다는 것은 무엇을 의미할까요? 

 

오늘은 이에 대한 실마리를 얻기 위해 네트워크의 유사도와 군집도 그리고 Community를 탐지하는 기본 아이디어에 대해 알아보도록 하겠습니다. 

---

Community Structure in Networks

우리는 종종 네트워크를 도식화할 때, 아래 그림과 같은 형태로 나타내곤 합니다. 왜 이러한 그림이 '네트워크'라는 개념의 상징적인 이미지로 자리잡게 되었을까요? 우리는 일반적으로 네트워크 내에도 비슷한 성향을 지니는 개체들끼리 하나의 그룹(Group)으로 표현할 수 있다고 생각하기 때문입니다. 사회과학적으로 이러한 그룹이 생성되는 원리에 대해 먼저 알아보겠습니다. 

 

Response to Granovetter

Granovetter는 '사람들은 어떻게 새로운 직장을 찾는가?'에 대한 연구를 진행했습니다.

사람들은 자주 만나는 친구가 아닌, 드물게 만나는 지인(Acquaintances)을 통해 직장에 대한 정보를 얻는다

 

이를 바탕으로 두 가지 유형의 관계를 생각해볼 수 있습니다. 

• 네트워크에서의 구조적(Structural) 역할: 링크가 네트워크의 어떤 부분을 연결하는가?
• 얼마나 친한 사이(Interpersonal)간 연결: 링크가 강한 연결관계를 나타내는가 or 약한 연결관계를 나타내는가?

다음의 그림을 통해서 위 두 가지 유형을 이해해보도록 합시다. 

노란색 회사를 다니고 있는 A와 파란색 회사를 다니고 있는 C는 동질적인 그룹 내에서는 강하게 연결되어 있으며, 이질적인 그롭과 약하게 연결되어 있습니다. A와 C를 연결하는 약한 관계는 서로 다른 회사의 정보가 교류되는 유일한 링크가 됩니다. C는 같은 회사 근무자들로부터는 절대 접근할 수 없는 노란색 회사에 대한 정보를 유일하게 A로부터 전해들을 수 있으며 반대의 경우도 마찬가지 입니다. 한편 노란색 회사에 근무하는 A와 B는 강하게 연결된 근무자의 수가 다르지만 그들 사이에서 공유되는 정보는 대부분 중복되거나 접근하기 쉬울 것입니다. 이를 구조(Structure)와 정보(Information)의 관점에서 정리해보면 다음과 같습니다:

• 동일한 그룹(Group)내에 직원들 간 연결 즉, 구조적으로 결속된(embedded) 링크들은 사회적으로도 강하게 연결(Strong Tie)되어 있음
  • 강하게 연결된 링크를 통해 이미 알고 있는 중복된(redundant) 정보들을 주고 받게 됨
• 서로 다른 그룹에 속하는 직원들 간 연결 즉, 서로 다른 네트워크를 연결하고 있는(long-range) 링크들은 사회적으로 약하게 연결(Weak Tie)되어 있음
  • 약하게 연결된 링크를 통해 새로운(new) 정보를 얻을 수 있게 됨

Granovetter의 주장에 따르면 network community는 강하게 연결된 노드의 집합(tightly connected sets of nodes)입니다. 위에서는 그룹(Group)이라고 표현 했지만, (1) 내부적으로 강한 연결이 많은 노드와 (2) 몇몇 외부적으로 연결된 노드들로 이루어진 집합을 우리는 커뮤니티(community)라고 정의합니다. 주어진 네트워크에서 커뮤니티를 찾는 방법은 무엇이 있을까요? 이와 관련된 연구 분야가 'community detection'으로 다양한 접근이 이루어지고 있습니다. 

 

Community Detection

기본적으로 커뮤니티 탐지(Community Detection)는 네트워크에서 노드들을 군집화(clustering)하는 것입니다. 서로 간에 밀접하게 연결된 노드들의 집합을 하나의 클러스터로 정의하고 이러한 클러스터를 찾는 것을 목적으로 합니다. 먼저 군집(cluster)와 커뮤니티(community)는 어떤 차이가 있을까요?

본질적으로 같은 의미를 갖으며, 'communities = clusters = groups = modules'로 표현

 

그러나 목적과 수단이 서로 다른 배경에서 출발했습니다. 군집화는 특성에 의해 나누어진 군집을 발견하는 것이 목적인 반면, 커뮤니티 탐지는 나누어진 군집을 발견하여 군집 별 특성을 이해하는 것이 목적입니다. 또한 군집화는 다양한 특성(multi-attributes)을 동시에 고려하여 유사한 데이터를 묶어주는 역할을 한다면, 커뮤니티 탐지는 네트워크 형태의 데이터에 한정하여 연결 관계(링크)를 고유한 특성으로 활용합니다. 커뮤니티 탐지 알고리즘은 크게 'Member-based'와 'Group-based' 접근으로 나눌 수 있습니다. 먼저 더 직관적이고 이해하기 쉬운 Member-based approach에 대해 알아보겠습니다. 

 

Similarity and Cluster in the network

네트워크 커뮤니티에서 'Member'라고 함은 결국 해당 군집을 구성하는 'Node'를 의미합니다. 즉 비슷한 노드가 모여 하나의 커뮤니티를 구성하게 되는 것입니다. 그렇다면 서로 다른 노드 간에 비슷한 정도를 어떻게 측정할 수 있을까요? 이 때 사용하는 것이 유사도 척도(Similarity measures)입니다. 노드 간 유사도 척도에는 1) 자카드(Jaccard) 유사도, 2) 코사인(Cosine) 유사도, 3) SimRank 등이 있습니다. 기본적인 아이디어는 다음과 같습니다. 

그래프 내부의 인접한 두 노드의 이웃이 얼마나 겹치는가?

 

앞서 설명한 겹치는 이웃의 수를 보고 유사도를 측정하는 방법을 구조적 등위성(Structural Equivalence)이라고도 합니다. 소셜 네트워크를 생각해보면, 겹치는 친구(지인)가 많을수록 유사한 유저라고 볼 수 있습니다. 

$$\sigma (v_i,v_j)=|N(v_i)\cap N(v_j)|$$

$$N(v_i):노드v_i의이웃노드들의집합$$

이 때, $i$ 와 $j$ 의 단순 유사도는 $i$ 의 이웃 집합과 $j$ 의 이웃 집합의 교집합의 원소 갯수가 됩니다. 다만 이 수치는 그래프 크기에 따라 범위가 달라지므로 정규화할 필요가 있습니다. 빈번하게 사용되는 기법은 자카드 유사도와 코사인 유사도 등을 활용 가능합니다. 

 

자카드 유사도(Jaccard Similarity)

$${\sigma }_{Jaccard}(v_i,v_j)=\frac{|N(v_i)\cap N(v_j)|}{|N(v_i)\cup N(v_j)|}$$

 

코사인 유사도(Cosine Similarity)

$${\sigma }_{Cosine}(v_i,v_j)=\frac{|N(v_i)\cap N(v_j)|}{\sqrt{|N(v_i)|\times |N(v_j)|}}$$

 

실제 그래프에 적용하여 유사도를 계산해보겠습니다. 먼저 $v_2와v_5$ 의 유사도를 측정하기 위해서는 각 노드의 이웃 노드 집합을 확인해야 합니다. $v_2$ 의 이웃 노드는 $v_1,v_3,v_4$ 이고, $v_5$ 의 이웃 노드는 $v_3,v_6$입니다. 따라서 자카드 유사도는 $\frac{1}{4}$, 코사인 유사도는 $\frac{1}{\sqrt{3}\cdot \sqrt{2}}=\frac{1}{\sqrt{6}}\approx 0.4$ 입니다. 

이를 바탕으로 군집이 형성되었을 때, 노드들이 얼마나 서로 뭉쳐 있는가를 평가하는 지표를 군집 계수(Clustering Coefficient)라고 합니다. 

$$C(v_i)=\frac{NumberofPairsofNeighborsof{v}_{i}thatareConnected}{NumberofPairsofNeighborsof{v}_i}$$

Modularity Q (군집성)

두번째로 살펴볼 주요 아이디어는 $Modularity$ 입니다. 커뮤니티 구조는 랜덤 네트워크의 구조와는 달라야 함을 기억하면 됩니다. 

모듈성(Modularity)은 시스템의 컴포넌트가 분리되고 재결합될 수 있는 정도,
조금 더 쉽게 표현하면 그 자체로 하나의 완전한 기능을 수행할 수 있는 독립된 실체

 

이러한 개념을 적용해보면, $Q\propto \sum _{s\in S}$[(# edges within group s ) - (expected # edges within group s)]

• Modularity Q: 네트워크(network)가 커뮤니티들(communities)로 얼마나 잘 나누어져(partitioning) 있는가에 대한 정량적 수치를 의미합니다. 
• Partitioning: 하나의 노드가 어떠한 커뮤니티(community)에 속하도록 네트워크를 분할해 나가는 것을 의미합니다. 
• Q: 커뮤니티 s의 edge 수 - 기대되는 커뮤니티 s의 edge 수

이 수치가 클수록 즉, Edge 수 차이가 클수록 매우 Strong Community라고 할 수 있습니다. 따라서 Modularity Q를 최대화하는 것으로 커뮤니티를 구성할 수 있습니다. 그렇다면 기대되는 커뮤니티 s의 edge 수를 찾으려면 어떻게 할까요? 이를 위해 Null Model (Configuration Model)이 필요합니다. 

 

Configuration Model

우리는 앞서 Modularity의 아이디어는 커뮤니티 구조는 랜덤 네트워크의 구조와는 달라야한다고 했습니다. 즉 Q를 정의할 때, 기대되는 커뮤니티 s의 edge 수는 랜덤하게 연결된 네트워크에서 기대값으로 나타냅니다. 실제 네트워크 G는 n개의 노드와 m개의 엣지를 가지고 있다고 합시다. 이를 이용해 동일한 차수의 분포를 가지고 있지만 uniformly random하게 연결된 rewired network G'을 생성할 수 있습니다. 노드 i와 노드 j의 degree를 $k_i,k_j$ 라고 한다면, edge의 기대값은 $k_i\times \frac{k_j}{2m}$ 이 됩니다. 여기서 $\frac{k_j}{2m}$ 는 노드 j와 연결될 확률을 의미하며, 모든 노드는 2번씩 count되기 때문에 2m이 분모가 됩니다. rewired network G'은 multigraph를 가정하므로 노드 i의 degree인 $k_i$를 곱해주어 기대값을 계산합니다. 

$$Q(G,S)=\frac{1}{2m}\sum _{s\in S}\sum _{i\in s}\sum _{j\in s}(A_{ij}-\frac{k_i{k}_j}{2m})$$

$A_{ij}$: Node i와 Node j 사이의 edge 수

$\frac{k_i{k}_j}{2m}$: 기대되는 커뮤니티 s의 edge 수

$\frac{1}{2m}$: Normalizaing 상수

 

다시 Modularity Q에 대한 정의로 돌아와 보면, m개의 엣지를 가진 그래프가 가질 수 있는 엣지의 합은 최대 2m이므로 normalizing 상수값(=2m)으로 나누어 주면, Q는 [-1, 1] 사이의 값을 가지게 정규화 됩니다. 보통 0.3과 0.7 사이 정도면 Significant Community Structure가 존재함을 의미합니다. 오늘 배운 Modularity에 대해 잘 이해하고 계시면, 추후에 다루어질 많은 커뮤니티 탐지 기법에 대한 이해도가 높아질 것이라 생각합니다. 

 

다음 포스팅에서는 대표적인 커뮤니티 탐지 알고리즘은 Girvan-Newman 알고리즘과 Louvain 알고리즘에 대해 알아보도록 하겠습니다. 

[참고자료]

1. https://www.reliantsproject.com/2020/06/10/concept-4-job-opportunities-and-granovetters-strength-of-weak-ties/

Concept 4: Job Opportunities and Granovetter’s Strength of Weak Ties, THE RELIANTS PROJECT

2. https://www.pnas.org/doi/10.1073/pnas.0601602103

3. https://medium.com/@kengoiwt/community-structure-strategies-kpis-and-networks-6406230beffc

Community structure, strategies, KPIs, and networks

4. https://velog.io/@00springbom00/%EB%8D%B0%EC%9D%B4%ED%84%B0%EA%B3%BC%ED%95%99-%EA%B8%B0%EC%B4%88-14%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC%EC%9D%98-%EC%9C%A0%EC%82%AC%EB%8F%84%EC%99%80-%EA%B5%B0%EC%A7%91%EB%8F%84

데이터과학 기초-(14)네트워크의 유사도와 군집도

5. https://www.semanticscholar.org/paper/Social-Media-Mining%3A-Major-Concerns-in-Social-Media-Kaur-Kaur/d37e44ace15d781a5f4555ec3b099a826739d033

https://www.semanticscholar.org/paper/Social-Media-Mining%3A-Major-Concerns-in-Social-Media-Kaur-Kaur/d37e44ace15d781a5f4555ec3b099a826739d033

6. https://link.springer.com/article/10.1007/s10115-022-01704-6