CS224W - 04.Community Structure in Networks

in Data on Graph


Community Structure in Networks

  • Chapter03. Role에 대한 공부.
    Chapter04: Community에 대한 공부

    gnn04-1

    • 결국, 이번 챕터의 목적은 ‘서로 간에 밀접하게(Densely) 연결된 노드들의 집합을 찾는 것’
    • 클러스터의 개념으로 이해해도 좋을 듯

  • Community에 대한 알고리즘적인 논의 이전에, Community에 대한 ‘시회과학적’인 논의로 먼저 시작.

    • ‘Mark Granovetter’ 박사: 1960년대에 ‘사람들이 과연 어떻게 새로운 직장을 찾는가?’에 대해 연구

    • 놀라운 그의 발견: ‘사람들은 그들의 (자주 만나는) ‘친한 친구’가 아니라 (드물게 만나는) 지인(Acquaintances)에게 연락한다. 왜?

      • 이에 대한 그의 답 (이론)
        1. “Friendship을 두 가지 관점으로 바라볼 수 있다.”
          • Structural perspective: 링크가 네트워크의 어떤 부분을 연결하는가?
          • Interpersonal perspective: 누군가로의 링크가 Strong한가 Weak한가?

        #### Structural role: Triadic Closure

          • Triadic Closure라는 개념
            (= High clustering coefficient)
            gnn04-2
          • 어떤 edge가 더 일어날 법한가? 답은 ‘a-b’
            a-c는 네트워크 상에서 3 steps away, 하지만 a-b는 공통된 두 명의 친구를 갖고 있다.
            공통된 친구를 갖고 있으면, 그들 또한 친구가 될 가능성이 더 높다.
        1. “Edge (Link)를 두 가지 관점에서 바라볼 수 있다.”
          • Structure의 관점
          • 구조적으로 단단히 결속된 Edge들 (Structurally embedded edges)들은 Socially strong
          • 네트워크의 다른 부분들에 걸쳐있는 (spanning) Long-range Edges들은 Socially weak
        • Information의 관점
          • Structurally embedded edges들은 정보 접근의 관점에서 몹시 redundant
          • Long-range Edges들은 네트워크의 다른 부분들로부터 정보를 들을 수 있게 돼 새 직업을 얻는 데에 도움이 됨

        gnn04-3

  • 이 이론은, 2007년에, Onnela에 의해 증명됨

    • 사용한 데이터: EU 소속 국가 인구의 20%의 휴대폰 네트워크 데이터

    • Edge Weight는 통화횟수로 정의

    • 결과: 통화횟수가(=Inter-personal strength of friendship) 많을수록, 정말 Neighbor Overlap 지수 또한 높아지더라.
      -> 이는 Mark Granovetter 박사의 이론의 Triadic Closure을 증명한 것으로 보임.

      • 아래는 이해를 돕기 위한 이미지
        gnn04-4
        gnn04-5

        • Edge Removal by Strength, Link Removal by Overlap 실험도 같은 결과를 말해줌
          -> ‘정말로 Strong ties/edges를 가진 Communities라는 게 존재한다.’
    결국, '사람들이 새로운 직업을 찾을 때 평소에 자주 보는 친한 친구들이 아닌, 간간히 보는 지인들을 통해서 찾는 경향이 강한' 이유는, 
Mark Granovetter 박사의 이론에 따르면, 'Link' 혹은 'Edge'는 연결된 양상이 친분의 성격을 나타내어줄 수 있고 (Structural), 
또 그 친분 간에는 경중을 따질 수 있는데(Interpersonal), 이들을 종합해 보았을 때, 가까운 친구들보다는 지인들이 사회적인 유대는 적을 수 
있지만(socially weak), 오히려 더 유익한 정보를 많이 가져다 준다는 점에서 Acquaintance로 부터 새로운 직업을 찾는 경향이 많은 것.  
그리고 이는 2007년에 실데이터를 사용하여 증명함.

Network Communities

  • Granovetter 박사의 이론에 따르면 ‘네트워크는 단단하게 연결된 (Tightly connected) 노드들의 집합들’로 구성되어 있다.
  • Network Communities에 대한 정의
    내부적으로는 수많은 연결들로, 외부적으로는 적은 연결들로 구성된 노드들의 집합
    • cf. Communities = clusers = groups = modules
      gnn04-6

그럼, 이 Communities를 어떻게 발견할 수 있을까?

  • 답: Modularity라는 개념을 도입할 것이고, 우리는 Modularity를 Maximize하는 바로 그 Communities를 찾아내면 된다.
    We can identify communities by mazimizing modularity.

  • Communities: 단단히 연결된 노드들의 집합 (sets of tightly connected nodes)
    gnn04-8

  • Modularity Q

    • 네트워크가 communities로 얼마나 잘 나누어져(partitioned) 있는가에 대한 측정
    • Partitioned된 Disjoint communities에 대해 Modularity를 다음과 같이 계산
      gnn04-7
      • 다음 식의 값을 크게 만드는 Communities 그룹을 찾는 게 목적이고, 이를 얻어내기 위해서는 Null Model이 필요한데, 앞서 3강에서 했던 ‘Configuration Model’의 사고 적용
    • Configuration Model
      • Community가 얼마나 잘 Partitioned 되어있는지를 평가하기 위해 필요한 ‘비교 기준’이 되는 모델
      • Real graph G가 있으면, 이 그래프에서 Node의 개수(m)와 Edge의 개수(n)는 알 수 있음.
      • 이를 갖고 Rewired network G’를 만든다!
        • 특징
          gnn04-9
    • Modularity 계산의 정확한 식을 나타내면 다음과 같은 식이 도출
      gnn04-10

      • 생각해보면, Configuration Model은, 실제 그래프의 Degree Distribution은 지키되, 아무렇게나 만들어낸 모델인데, Q(G,S) 값이 크다는 말은, 아무렇게나 만드는 모델보다, 이 현실 그래프 자체가 뭔가 유의미함을 담고 있다는 것이고, 따라서 Communities의 존재 또한 타당하다고 평가할 수 있을 것 같음.

      • Modularity 값은 -1과 1사이의 값.

      • 보통 0.3과 0.7 사이 정도면 Significant Community Structure가 있음을 의미

      • Modularity를 아래와 같이 다른 form으로도 나타내어 볼 수 있음
        gnn04-11

Louvain Algorithm

  • Community detection을 위한 Greedy Algorithm

  • 시간복잡도 O(nlogn), 이 때 n은 노드의 개수

  • 가중치 그래프도 지원하고, Hierarchical communities detection도 가능
    • cf. Dendrogram을 통해 네트워크의 Hierarchical한 구조를 나타낼 수 있다.
      gnn04-12
  • 네트워크에 널리 사용된다.
    • 빠르고, 수렴도 빠르고, High Modularity output을 도출해주기 때문
  • 요컨대, Louvain algorithm greedily maximizes modularity

Louvain Algorithm의 Process에 대한 설명

  • 매 pass 마다 두 phases를 지난다.
    • Phase1: Partitioning or Optimization
      • Node-Communities 멤버들간의 오직 local change를 통해 Modularity를 optimize
    • Phase2: Aggregation
      • 새 네트워크를 만들기 위해, Phase1을 통과한 결과들을 Super-nodes로 Aggregate

    • Phase1, 2를 Modularity의 증가가 없을 때까지 Iteratively Repeat

      gnn04-13

  • 각 Phase에 대해 조금 더 구체적으로 들어가보자.

    Phase1 (Partitioning)

    • 각 노드를 Distinct 한 Community 에 넣는다.
    • 각 노드 i에 대해 Louvain 알고리즘은 두 가지 연산을 진행
      • 연산1: 노드 i를 어떤 neighbor j의 community 속에 넣으면 발생하는 modularity 값의 변화량을 측정 (Modularity delta: ΔQ)
      • 연산2: 노드 i를, 가장 큰 ΔQ를 발생시키는 community로 이동

    • ΔQ의 변화가 없을 때까지 Phase1 계속 실행

    • 물론, 노드를 택하는 순서가 결과에 영향을 주기는 하지만, 그렇다고 이 순서가 결과에 큰 영향을 주는 것은 아니기 때문에 보통 이에 대해 큰 주의를 기울이진 않음.

      여기서 말하는 ΔQ는 어떻게 계산하나?

      gnn04-14

      • 뿐만 아니라, 현재 속한 Community가 D라면, ΔQ(D→i) 또한 쉽계 계산해낼 수 있음.
      ΔQ식 더 자세히 보기

      gnn04-15

    Phase2 (Restructuring)

    • Phase1에서 얻어진 communities를 super-nodes 로 압축!
      • Super-node들 사이에 하나의 Edge라도 있으면 연결!
      • 두 Super-node 간의 edge 가중치는 커뮤니티 간 모든 Edge 가중치들의 합
    • 다시 Phase1으로 (한 개의 Community를 찾을 때까지 계속 반복하면 된다)
      gnn04-17

  • Pseudo-Code
    gnn04-16

  • 요약

    * Modularity  
- 그래프를 Community들로 나눌 때의 평가 기준이 됨  
- Community들의 숫자를 결정  
  
* Louvain Modularity Maximization  
- Greedy한 알고리즘  
- 성능 좋고, 큰 사이즈의 네트워크에도 확장성도 좋다

Detecting Overlapping Communities: BigCLAM

  • 앞에서의 Community들은 모두 Non-Overlapping 이었음.

  • Overlapping Community를 Detect할 수 있는 방법은 없을까?

    gnn04-18

  • 역시 2가지 Step으로 구성
    • Step1
      • Node Community affiliation에 근거하여 graph generative model을 정의
      • 여기서는 그 모델로 Community Affiliation Graph Model (AGM) 모델을 다룰 것
    • Step2
      • Graph G가 AGM을 통해 만들어졌다는 가정 하에, best AGM을 찾자!
        (= Step1에서 AGM 모델을 정의한 이후, MLE를 찾겠다.)

AGM

gnn04-19

  • Generative Model : Community affiliation으로부터 어떻게 네트워크가 generate되는가?
  • Model Parameters: V, C, M, {p_c}
    • V: Nodes
    • C: Communities
    • M: Memberships
    • p_c: Community C의 노드들이 서로 연결되어 있을 Likelihood
      • 이 때, 다수의(multiple) communities에 속해있는 노드들은 multiple coin flips!
        gnn04-20
      • p(u,v): u,v가 서로 연결되어 있을 확률
      • 공통된 그룹의 수가 많을수록 연결될 가능성이 커짐
    • 예시
      gnn04-22
  • AGM은 Overlapping 양상에 따라서 다양한 Community Structure를 표현할 수 있음
    (Non-Overlapping, Overlapping, Nested 모두 표현 가능)
    gnn04-23

  • 의문: Model로부터 Graph를 Generate하고 있는데, Graph가 있으면 Model을 얻을 수는 없을까?
    gnn04-24

    • Maximum Likelihood Estimation 사용
    • Given 그래프를 G라고 하면 다음식을 만족하는 F (model/parameter)를 찾으면 된다.
      gnn04-25
      • “모델을 받아서, 이를 Graph Generation에 사용하고, 이 graph가 real graph와 가장 비슷하도록!”
      • “Model Parameter가 주어졌을 때, 내 Graph Probability를 측정할 수 있다면, argmax를 찾아보자!”
    • F,G가 주어졌으면, F가 G를 Generate할 Likelihood를 구해보자.
      gnn04-26

  • ‘AGM’ 모델의 Relaxing 같은 교수님의 Relaxing AGM에 대한 설명

    • 위의 모델은 0,1을 사용하여 노드들이 given community의 member인지아닌지를 따짐
    • 하지만 그보다, 모든 node community membership의 strength를 따져보자는 접근 -> “Relax” the AGM!
      gnn04-27
      -> 기존의 문제를, 모든 노드에 대해 Vector F를 찾는 문제로 바꾸어 놓음

BigCLAM Model

  • 노드 u와 v가 연결되어 있을 확률은, shared memberships의 strength에 비례함
    gnn04-28

  • 결국 BigCLAM 모델은 네트워크 G(V,E)가 주어졌을 때, 다음 l(F)를 Maximize하는 F를 찾는 것
    gnn04-29

References

CS224W: Community Structure in Networks