Structural Hole

1. Structural hole

• Structural hole 
  • 정보격차를 가진 두 개인 사이의 연결
  • 예시)
    • few structural hole : 학과 내에서의 교류
    • many structural hole : 타과와 많이 교류
• Network Constraint
  • 두 노드의 관계가 얼마나 일치하는지에 대한 값
    • 1/(친구수)
    • 예시)
      • network constraint가 낮으면 겹치는 친구가 없다 --> 타과생
      • network constraint가 높으면 겹치는 친구가 많다 --> 우리 과 사
• Redundant
  • 정보가 얼마나 중복되는가 (불필요한가)
  • 예시)
    • 자신의 친구들끼리 모여있다.
    • network constraint가 높다.
    • strongly tied
• 결론
  • 그래서 network constraint가 낮다는 것은 structural hole이 많다는 것을 뜻한다.
  • 그래서 정보일치성이 낮다는 것은 정보격차를 가진 개인 간의 연결이 있다는 것이다.
  • 그래서 낮은 network constraint는 실제로 좋은가?

2. How to detect dense community?

• Network community
  • 자기들끼리의 connection이 많고 바깥쪽으로는 적은 집합, 관계가 많이 겹치는 집합
  • 예시)
    • cluster
    • group
    • community
    • module
    • Micro-markets in sponsored search
    • Zachary's karate club network
• Definition of community
  • 우리는 clusterling을 위해 두가지 질문에 답해야 한다.
    • Q1. how to compute betweenness?
    • Q2. how to select the number of clusters?
  • A1. Girvan-Newman algorithm
    • division method for decomposing a network into hierarchical modules
    • 논리 
      • 그래프의 natural module을 찾기 위해 high betweenness를 가진 edge를 지운다.
      • 왜냐하면 high betweenness인 edge는 traffic of information의 bottleneck이기 때문이다.
      • 따라서 그래프를 파편화할 때 betweenness가 높은 edge를 끊는 것이 설득력 있다.
        • betweenness
          • 해당 edge를 통과해야만 하는 shortest path의 개수
            • 한 노드를 기준으로 잡고 BFS를 통해 그 노드로 가는 shortest path 개수 센다.
            • 수식
    • algorithm
      • 각 edge의 betweenness를 계산한다.
      • 가장 높은 betweenness를 가진 edge를 제거한다. --> 만약 같다면?
      • 남은 edge의 betweenness를 다시 계산한다.
      • 모든 edge가 사라질 때까지 반복한다.
      • 당연히 알고리즘이 진행될수록 module은 작아진다.
    • edge betweenness vs edge strength
      • betweenness는 그래프 구조만 사용한다.
      • strength는 weight를 사용한다.
    • 참고) www.youtube.com/watch?v=LtQoPEKKRYM
  • A2. Modularity Q
    • Girvan-Newman algorithm을 사용하며 언제 멈추어야 적절한 clusterling일지 알 수 있어야 한다.
    • '얼마나 잘 나뉘었는가'를 수치로 나타낸 것이 modularity Q이다. (-1~+1)
    • 기댓값이 0.3 ~ 0.7이면 partitioning이 잘 된 것이다. mod가 max일 때 가장 좋다.
    • Modularity Q
      • 네트워크가 얼마나 잘 partitioning 되었는가?
      • sum of {(# edges within group s) - (expexted # edges within group s})
    • 짚고 넘어간다: 왜 modularity를 decomposing의 기준으로 삼는가? (실제 edge 개수 - expected edge 개수)가 클수록 군집되어있기 때문에 community일 확률이 높다. 이것이 모든 community(라고 간주한 것)의 Q값 합을 구하는 이유
    • 왜 Q를 진작 optimize하지 않는가?
      • 모든 값을 계산해야 Q값이 나오기 때문이다.

3. Network with signed edge

• Signed edge
  • node가 positive인지 negative 관계인지 예측하는 것이 목적이다.
• Structural balance
  • balanced : (+,+,+) (+,-,-)
  • unbalanced : (+,+,-) (-,-,-)
  • 어떤 세 노드도 이 규칙에 위배되지 않는 그래프가 balanced graph
    • 모든 positive edge로 연결된 node는 한 set으로 취급 가능하다.
    • negative relationship은 이 set 간에만 이뤄진다.
  • 예시) international relationship