Community Structure in Networks
Community Structure in Networks
🙄 네트워크 안에서 어떤 노드들은 서로 뭉쳐있지 않을까?
→ real-world를 보면 사람들은 각자 여러 커뮤니티를 형성하고 있음
→ 커뮤니티는 무엇일까여
real-world에 대한 관찰)
- 사람들간의 관계: 사람-사람이 모두 같은 관계를 형성하지 않더라. 친한 사이도 있고, 그냥 아는 지인 사이도 있다.
→ 노드들간의 링크가 다 다르다. 강한 연결, 약한 연결이 있다.
- 커뮤니티: 친한 사람들끼리는 커뮤니티를 형성하더라.
→ 네트워크 구조에서 strong edge를 이루는 노드들끼리 커뮤니티를 형성한다.
- 네트워크 상에서 정보의 흐름: 유용한 정보는 친한 사이보다는 그냥 아는 지인으로부터 얻는 경우가 많더라. 친한 친구들은 이미 나랑 공유하는 게 많고, 서로 다 알고 있음.
→ 유용한 정보는 weak edge를 따라 전달된다.
Granovetter’s Explanation
→ social(네트워크)과 edge의 구조적 역할의 연결에 대하여
- structurally embedded edges → socially strong
spanning edges → socially weak
: 구조적으로 내장된(커뮤니티 속)에 있는 엣지로 연결된 노드들은 사회적으로도 강한 연결 관계를 가짐
- long range edges → gather information
structurally embedded edges → redundant information
: weak edge로부터 유용한 정보들을 얻고, strong edge들로부터는 이미 아는 정보들을 얻음
이러한 구조에 대한 설명을 위한 몇가지 정의
Bridge edge: 이 엣지를 지우면, 연결 그래프 → disconnected
Local bridge: 이 엣지(A-B)를 지우면, 연결이 끊어지지는 않지만, A-B를 가려면 돌아가야 하는 엣지.
- 돌아가는 거리의 기준 - Edge of span > 2
- Span : 해당 엣지가 없다면, 돌아가야 하는 거리
- 만약 성수대교(성수-압구정)가 없어지면, 성수에서 압구정갈 때 빙 돌아가야 하는 것과 같다.
두 종류의 Edge
- Strong : 친구
- Weak : 지인
Strong triadic closure
- 두 엣지 strong edge이면 → 세번째 edge가 생긴다.
- A-B, A-C가 strong edge이면 B-C 사이에도 edge가 생긴다.
- 세번째 edge: strong or weak 상관없이 “생긴다”는게 핵심
- 공통 친구가 있으면 그들 사이에도 관계가 생기는 거
Local bridge와 Strong triadic closure
왜? strong triadic closure가 성립하고, local bridge(A-B)가 strong tie라면
→ embedded edge인 (A-C) strong edge가 있으면
→ B-C 사이에도 strong triadic closure에 의해 edge가 생긴다.
→ 근데 이게 strong이면, A-B는 local bridge가 아니게 됨
(A-B가 없어도, A→C→B로 갈 수 있으니까)
⇒ 모순이다. 따라서 local bridge는 weak tie
Neighborhood Overlap
neighbordooh: 1hop으로 갈 수 있는 노드
(엣지 하나로 인접한 노드들)
Edge overlap
: 엣지로 연결된 두 노드(i, j)들간의 겹치는 이웃이 얼마나 있는가
N(i) : i의 이웃 노드 개수
이 값이 크면, 두 노드 간에 겹치는 이웃이 많다는 의미이고, 작으면 겹치는 이웃이 적다는 의미.
→ 만약 교집합만 센다면, 이웃 노드 수가 많으면 그냥 overlap이 커지기 때문에 합집합으로 나눠줌.
overlap = 0 ?
노드 i, j는 이웃이지만, 겹치는 이웃이 없다면 ⇒ local bridge
만약 겹치는 이웃이 하나라도 있다면(overlap > 0),
i-j 엣지가 끊어져도 2hop으로 i→j 갈 수 있기 때문에 local bridge❌
edge overlap과 strength
🙄 strong edge인 노드들은 겹치는 이웃도 많을까?
real-wolrd에 대한 관찰)
사람들의 통화 기록을 분석
base: 전화를 많이 하면 친하다. (strong edge)
실제로 전화를 많이 한 사람들 간에는 겹치는 친구들이 많더라.
→ strong edge → edge overlap ↑
실제 네트워크 속 엣지들은
- strong tie→ 노드들이 더 밀집된 곳, 커뮤니티 안에 많음. → 오버랩도 커짐
- weak tie→ 커뮤니티와 다른 커뮤니티를 연결하고 있음.
네트워크에서 엣지를 지워보자
네트워크에서 엣지를 하나씩 지워가며, 컴포넌트(커뮤니티)의 사이즈가 어떻게 줄어드는지
[1] 엣지의 strength에 따라
방법1. strength가 높은 것부터 지우기 시작 (weak부터)
방법2. strength가 낮은 것부터 지우기 시작 (strong부터)
결과는 weak tie부터 지워나갔을 때, 커뮤니티가 더 빠르게 와해된다.
why?
- strong tie는 지우더라도, 커뮤니티 상에서는 계속해서 중복되는 데이터들이 전달되기 때문에 그 영향력이 더 작다.
- 그러나 weak tie를 제거하면 유용한 정보들, 다른 분야의 데이터들을 습득하는 기회가 줄어들기 때문에 더 빨리 커뮤니티가 와해된다.
[2] 오버랩 크기에 따라
방법1. 오버랩이 작은 엣지부터 지우기 시작
방법2. 오버랩이 큰 엣지부터 지우기 시작
위의 결과로 예상이 되겠지만, 오버랩이 작은 엣지부터 지우기 시작했을 때, 훨씬 더 빠르게 커뮤니티가 와해됨.
위에서 weak부터-strong부터 사이의 차이 보다 더 큰 차이로 빠르게 와해된다.
오버랩이 낮을 수록 → 커뮤니티 안에 내재되어 있기보다, 커뮤니티와 커뮤니티를 연결하는 엣지이다.
⇒ 커뮤니티에 깊숙하지 않은 엣지를 지울수록 커뮤니티가 빠르게 와해된다.
⇒ 커뮤니티에 깊숙하지 않은 엣지가 전체 큰 네트워크를 연결하는 데에 영향력이 크다.