CS224W 14.1-14.2 Community Detection in Networks

Youtube 강의는 13, 2021-fall 강의자료상으로는 14 chapter에 해당됨

1. Granovetter의 이론

구조, 정보의 두가지 측면에서 살펴본 Granovetter의 이론

1.1. 구조(Structure)

• 구조적으로 빽빽하게 연결된 Edge는 사회적으로 '강함'을 나타냄 (밀접한 관계나 가까운 사람들 간의 관계)
• 네트워크의 다른 부분을 연결하는 장거리 엣지는 사회적으로 '약함'을 나타냄
  • 서로 다른 사회적 그룹 사이를 연결하며, 새로운 정보나 기회를 가져오는 경향이 있습니다.

1.2. 정보(Information)

• 거리 엣지는 네트워크의 다른 부분에서 정보를 수집하고 일자리를 얻을 수 있게 해줍니다.
  • 다양한 지역의 사람들과의 연결은 다양한 정보에 접근할 수 있는 기회를 제공합니다.
• 구조적으로 포함된 엣지는 정보 접근 면에서 과다하게 중복됩니다.
  • 이는 비슷한 정보를 공유하는 밀접한 관계나 그룹들 사이의 관계에서 나타납니다.

2. 삼각폐쇄(Triadic closure)

• 삼각폐쇄는 높은 클러스터링 계수(clustering coefficient)를 의미

  • 만약 A와 B가 공통의 친구 C를 가지고 있다면,
    • A와 B는 더 자주 만날 가능성이 있습니다.
      $\rightarrow$ 그들 모두 C와 시간을 보내기 때문
    • A와 B는 서로를 더 신뢰할 것입니다.
      $\rightarrow$ 공통의 친구가 있기 때문
    • A는 A와 B를 함께 모이게 하는 동기를 가집니다.
      $\rightarrow$ A는 두 개의 격리된 관계를 유지하는 것이 어려우므로 이러한 관계를 유지하기 위해 노력할 것입니다.

• 또한, Bearman과 Moody에 의한 경험적 연구에 따르면, 클러스터링 계수가 낮은 청소년 여자들은 자살을 고려할 가능성이 더 높다는 결과가 나왔습니다.

3. Granovetter의 이론에 대한 추후의 실험

3.1. 개요

• Granovetter의 이론은 40년간 실험된적이 없었으나, 2007년에 최초의 실험이 진행됨 (call count 그래프)
• Granovetter의 이론이 이제 대규모 데이터를 통해 실험되고 있는 것은 중요한 발전입니다. 이는 이론을 현실 세계에 대입하여 그 유효성을 검증하는 데 도움이 됩니다.

  • 이메일, 메신저, 휴대전화, 페이스북 등이 있습니다.
    • Onnela와 그 동료들의 2007년 연구에서는 유럽 연합(EU) 국가의 인구의 20%에 해당하는 휴대전화 네트워크를 다뤘습니다.
    • 엣지의 가중치: 전화 통화 횟수입니다.

3.2. 결과

• 관찰 : 사용량이 높은 링크들은 높은 중첩을 가짐
• 범례 :
  • True (실제 데이터): 실제 데이터를 의미합니다.
  • Permuted strengths (치환된 강도): 네트워크 구조를 유지하되 엣지 강도를 무작위로 재할당합니다
• 시사점 : 실제 데이터에서 사용량이 높은 링크들이 서로 높은 중첩을 보인다는 것을 보여줍니다. 이는 네트워크 내에서 활발하게 상호작용하는 그룹들이 있다는 것을 시사합니다.

3.3. Edge removing (커뮤니티 파티셔닝?)

• 강도에 따라 엣지를 제거하거나, 중첩에 따라 엣지를 제거하는 경우, 기준값이 작은(low)수를 제거할수록 largest community가 더 잘 발견됨을 확인

4. Network Community

4.1. Definition

• 커뮤니티 : 빽빽하게 연결된 노드들의 집합
• 모듈러리티 (모듈성) $Q$ :
  • 네트워크가 커뮤니티로 분할되어 있는 정도를 측정하는 지표입니다.
  • 네트워크가 그룹으로 분할되었다고 가정할 때, 각 그룹 내부의 엣지 수와 기대되는 엣지 수의 차이를 모두 합한 값입니다.
  • 널 모델(null model)이 필요합니다. (기대되는 엣지 수를 결정하기 위한)

4.2. Null model

• 같은 차수 분포를 가지지만 균일하게 무작위로 연결된 연결(rewired network):

  • 각 노드는 동일한 차수를 유지합니다.
  • 무작위로 연결되어 있으며, 이는 다중 그래프로 간주됩니다(노드들 간에 여러 개의 엣지가 존재할 수 있음).
  • 차수가 $d_i$와 $d_j$인 노드 $i$와 $j$ 사이의 예상되는 엣지 수는 $d_i * d_j / m$입니다.
  • 전체로 보면 총 $2m$개의 유향 엣지가 있습니다(즉, i->j와 j->i를 각각 포함하여).
  • 각 노드로부터 나가는 엣지 중 노드 j로 랜딩할 확률은 $d_i! * d_j! / (2m)^2$입니다.
  • 이것은 주어진 그래프의 구조를 유지하면서 그래프를 재배열하여 동일한 차수 분포를 가진 무작위 그래프를 생성하는 방법을 설명합니다.

• 노드 $i$와 $j$ 사이에 예상되는 에지의 수?

  • 두 노드 i와 j 사이의 예상되는 엣지 수는 각 노드의 차수에 비례합니다. 노드 i와 j의 차수를 각각 d_i와 d_j라고 하면, 이들 사이의 예상되는 엣지 수는 $d_i * d_j / m$입니다.

  • $G'$의 (다중 그래프에서) 예상되는 엣지 수는 모든 노드 쌍에 대해 위의 값을 합산하여 구할 수 있습니다. 즉, $Σ(i∈V) Σ(j∈V) (d_i * d_j / m)$를 모든 노드 쌍에 대해 합산합니다. 이는 각 노드의 차수를 제곱하여 전체 합을 구하는 것과 같습니다.

  • 따라서, $G'$의 예상되는 엣지 수는 $(Σ(d_i^2) / m^2)$의 합산으로 계산됩니다. 이는 $(Σ(d_i)^2 / m)$과 동일합니다.

  • 이 null 모델에서는 차수 분포와 총 엣지 수가 보존되므로, 실제 그래프와 동일한 구조를 유지하면서도 그래프를 재배열할 수 있습니다. 이 모델은 가중 그래프와 가중치 없는 그래프 모두에 적용될 수 있습니다. 가중 그래프의 경우에는 각 엣지의 가중치를 고려하여 노드의 차수를 계산합니다.

4.3. Modularity (모듈성)

• 수식 $Q(G, S)$

  $Q(G,S) = \frac{1}{2m}\displaystyle\sum_{s\in S} \sum_{i\in S} \sum_{j\in S} (A_{ij}-\frac{k_i k_j}{2m})$

• Normalizing const에 의해 -1에서 1의값을 갖음
• 일반적으로 $Q$가 0.3~0.7사이의 값이라면 중요한 커뮤니티 구조가 발견되었음을 의미
• 그렇다면 중요한점은, 이 $Q$값을 최대화하는 커뮤니티 $S$를 어떻게 찾을것인가 하는것!