2-1 정보의 흐름
1. 예제 - 새로운 일자리 소개
: 친한 친구보다 지인(acquaintances)이 더 일자리를 소개 해주더라
2. 우정에 대한 관점(2)
- Structural: 우정은 네트워크의 다른 부분을 span한다.
- Interpersonal: 두 사람 사이의 우정은 strong또는 weak 중 하나다.
3. 구조적 역할: Triadic Closure
: 한 네트워크에서 두 사람이 공통적으로 한 명을 친구로 두면 두 사람이 친구일 확률이 높아진다.
- Triadic Closure == High clustering coefficient
4. Granovetter's Point(2)
(1) 내재된 edge들은 사회적으로 강하지만, 네트워크의 다른 부분을 spanning하는 edge들은 사회적으로 약하다.
(2) 내재된 edge들은 정보 접근 측면에서 중복이 많지만, 긴 범위의 edge들은 여러 정보를 얻게 해준다(get a job).
5. Granovetter's 개념 설명(4)
- Bridge edge: 제거되면 그래프는 disconnect된다.
- Local bridge: Edge of Sapn(끊어졌을 때 돌아가는 노드의 길이) > 2인 경우
- edge의 유형: Strong, Weak
- Strong triadic closure: 두 Strong tie들은 세번째 edge를 암시한다. → local bridge가 weak tie임을 만족시킴! (no Strong!)
6. local bridge가 weak tie임을 증명!
- 주장: 노드 A가 Strong Triadic Closure를 만족하고 최소 2개의 strong ties에 포함되면, A에 인접한 모든 local bridge는 weak tie이어야 한다!
- 증명: A가 B, C와 Strong Triadic Closure를 만족한다. 그러면 B와 C사이에는 edge가 존재해야한다. 그러면 B와 C사이에는 Strong edge가 없으므로 모순이다! 따라서 A와 B사이에는 weak tie만 존재할 수 있는 것이다!
7. 실제 데이터에서 tie strength
: who-talks-to-whom graph → email, messenger, cell phone, facebook ...
8. Neighborhood Overlap
(N(i) = 노드 i의 이웃 노드들의 집합)
(합집합으로 나눠 정규화하는 이유: neighbor가 큰 사람은 누구와도 overlap이 큼)
→ Overlap = 0이면 edge는 local edge이다!
9. Edge Overlap vs. Strength
: 서로 전화를 많이 했으면(Strength↑) → 겹치는 이웃도 많다!(Edge Overlap↑)
10. 링크 제거
(weak ties는 edge overlap이 낮고 strong ties는 높다)
11. Structural Holes?
: Structural Hole의 개수가 많을 수록 좋은 정보를 많이 얻을 수 있고, 사회에서 영향력이 크다.
+ network constratint: 특정 사람의 이웃들이 서로간 얼마나 많이 중복되어 있는지 보여주는 수치
Robert: network constraint 수치가 낮다, Structural Hole이 많다,
James: network constraint 수치가 높다, Structural Hole이 적다,
2-2 네트워크 커뮤니티
1. 네트워크 커뮤니티란?
: 내부 노드는 많이 연결되어 있고, 외부로 나가는 연결은 적은 집합.
Communities = Clusters = Groups = Modules
2. 커뮤니티를 찾는 방법
: Girvan-Newman Algorithm(거번 뉴만 알고리즘)
(1) 배경 지식:
· betweenness: 그 edge를 지나는 가장 짧은 경로의 수
(2) 알고리즘: 네트워크의 계층적 분해!
→ 모든 edge의 betweenness를 구한다. → betweenness가 가장 높은 edge부터 끊는다. →
→ 모든 edge가 사라질 때까지 반복한다. → 이후 남은 connected component들은 커뮤니티이다.
3. 커뮤니티를 찾을 때 고려해야하는 2가지!!
(1) betweenness를 어떻게 계산할거냐?!?!
: 짧은 경로의 개수 알아내기 → 말단 노드부터 root 노드까지 edge flow를 구하기
( node flow = 1 + (자식 노드의 edge betweenness의 합) )
(2) 커뮤니티를 몇개로 만들거냐?!?!
: Modularity Q를 정하자!
Modularity란 네트워크가 커뮤니티로 얼마나잘 분할 되었나 측정하는 척도로 [-1, 1]의 범위를 갖는다.
▷ 그룹 내 엣지가 많아야 좋은 clustering이다.
그렇다면 많다의 기준은 무엇일까?
바로 "기댓값과의 격차"이다.
기댓값 보다 실제 엣지의 수가 클 수록 좋은 clustering이다.
▷ expected # edges within group(그룹 내 엣지 개수의 기댓값)은 어떻게 구해야 할까
→ Null Model을 사용. (G' 그래프라고 칭하겠다.)
아래의 사항들을 만족하는 그래프 G'를 형성한다.
- 동일한 degree 분배이지만 무작위로 연결한다.(degree는 해당 노드의 연결된 엣지 수..? )
- G`을 multigraph로 여겨야 한다.
- degree가 ki이고 kj인 노드 i와 j의 기댓값(expected number)은 다음과 같다.
▷ 따라서 Q가 양수면 기댓값보다 edge의 수가 더 많았음을 의미한다!
0.3 < Q < 0.7이면 커뮤니티라고 정의해도 좋다!
아직 Q를 구하는 법을 잘 모르겠다..
아래의 포스팅을 참조하면 좋을 듯하다.
https://jimmy-ai.tistory.com/15
[그래프 이론] Modularity 뜻, 계산 예시(그래프 분할 평가)
그래프 분할(Graph Partition) 다음과 같은 그래프가 있다고 가정을 해봅시다. 이제 이 그래프를 2개의 그룹으로 나누어보겠습니다. 그래프 분할을 위한 여러 알고리즘을 적용할 수 있겠지만 속마음
jimmy-ai.tistory.com
'Computer Science > Software Application' 카테고리의 다른 글
| [소응] 15장 Sponsored Search Markets (0) | 2023.12.15 |
|---|---|
| [소응] 10장 Matching Markets (0) | 2023.12.15 |
| [소응] 9장 Auctions(경매) (0) | 2023.12.15 |
| [소응] 3장 부호있는 네트워크 (0) | 2023.10.11 |
| [소응] 1장 웹 그래프(Web Graph) (0) | 2023.09.13 |
