Graph
그래프란 정점과 간선으로 이루어진 구조
하나의 간선은 반드시 두개의 정점을 연결한다
정점 : vertex,node
간선 : Edge,link
우리의 사회및 모든 다양한 것들은 구성요소간의 복잡한 살호작용으로 이루어진 복잡계이다
이것을 표현하는 방식이 바로 그래프이다
그래프란 복잡계를 간단하게 표현하는 방식이다
정점 분류문제 (node classification) ex) 어떠한 계정이 어떠걸 리트윗했는지를 간선으로 표현. 사람(node)의 보수성, 진보성을 판별하는
랭킹 및 정보검색문제 : 웹이라는 거대한 그래프로부터 어떻게 중요한 웹페이지를 찾아낼까?
군집분석문제 : 연결관계로 부터 사회적 무리(군집)을 찾아낼 수 있을까?
정보전파 & 바이럴 마케팅 문제 : 정보라는 것이 어떻게 네트워크를 통해 전파가 될까?
본강의에서는 위의 문제들을 해결하는 기술들을 배우게될 예정
1주일이라는 짧은 시간이라 기초를 배우고 직관적인 방법론적인 설명
간선에 방향이 있는 directed graph vs undirected graph
협업관계그래프, 페이스북 친구그래프 : undirectied
인용그래프, 트윈터 팔로우 그래프 : directed
간선에 가중치가 있는 그래프 : 전화그래프, 유사도 그래프
간선에 가중치가 없는 그래프 : 페이스북 친구 그래프, 웹그래프
동종 그래프 vs 이종그래프
이종그래프는 두종류의 node를 가진다 . 서로다른 정점 사이에만 간선이 연결된다. Ex) 사용자,상품사이의 전자상거래 내역
동종그래프는 단일종류의 정점을 가진다
node의 집합 V, edge의 집합 : E,
G = (V,E)
Nout(1), Nin(1)이런거
그래프의 표현 및 저장
Networkx를 사용하여 그래프를 표현
snap.py라는 라이브러리도 많이 사용한다.
1 |
인접 리스트
1 : [2.5]
2 : [1,3,5]
3: [2]
5: [1,2]
인접행렬
간선이 있으면 1, 없으면 0
방향성이 없으면 대각으로 대칭
있으면 다름
희소행렬을 사용하면 저장공간을 절약할 수 있음 (대부분의 원소가 0일때)
1. 실제그래프 vs 랜덤그래프
실제 그래프란 다양한 복잡계로부터 얻어진 그래프를 의미한다
본수업에서는 MSN 메신저 그래프를 실제 그래프의 예시로 사용하겠다.
랜덤그래프란 확률적 과정을 통해 생성된 그래프를 의미한다
에르되스-레니 랜덤그래프
임의의 두 node사이의 간선 존재여부가 동일한 확률분포로 나타내어짐
G(n,p)는 n개의 정점, 두개의 정점 사이에 간선이 존재할 확률 = p
2. 작은 세상 효과
정점 u와 v사이의 경로란
u에서 시작해서 v에서 끝나야 한다
순열에서 연속된 정점은 반드시 간선으로 연결되어있어야 한다.
경로, 거리, 및 지름
경로는 여러가지지만 이중 가장 짧은 경로의 길이가 거리이다
그래프에서 지름은 정점간 거리의 최댓값이다.
작은 세상 효과
임의의 두사람을 골랐을 때 이들은 몇단계의 지인을 거쳐야 연결되는가?
위치타에서 보스턴까지 지인을 6단게거치면 가능
MSN에서도 정점간의 평균거리는7정도밖에 되지 않는다
단 거대연결구조만을 고려하였다.
이러한 현상을 작은세상효과라고 한다.
작은 세상효과는 높은 확률로 랜덤그래프에도 존재한다.
체인 사이클 격자그래프에는 이 작은세상그래프효과가 존재하지 않는다.
연결성에 두터운 꼬리분포
연결성?
정점의 Degree란 그정점과 연결된 간선의 수 : |N(v)| 라고 표현하기도 함
랜덤그래프의 연결성 분포는 높은 확률로 정규분포와 유사하다
실제 그래프는 연결성이 두터워서 hub 정점이 존재할 수있는데
랜덤그래프에서는 정규분포를 띌 가능성이 높다
연결요소
- 연결요소에 속하는 정점들은 경로로 연결될 수 있습니다.
- 1의 조건을 만족하면서 정점을 추가할 수 없다.
실제그래프에는 대다수의 정점을 포함하는 거대연결요소가 존재한다
MSN메신저 그래프에는 99,9%의 정점이 하나의 거대연결요소에 포함된다
정점들의 평균 연결성이 1보다 충분히 큰경우, 랜덤그래프에도 높은 확률로 거대연결 요소가 존재한다.
군집이란 정점들의 집합
같은 군집안에서의 정점 사이에는 많은 edge가 존재
지역적 군집 계수 : 그 정점이 군집을 형성하려는 정도
Ci = 정점 i의 이웃쌍중 간선으로 직접 연결된 것의 비율
정점i의 지역적 군집계수가 높으면 이웃들이 연결되어있다.-> 정점 i와 이웃들이 군집을 형성한다
전역 군집 계수
전체 그래프에서 군집의 형성정도를 측정
각 정점에서 지역적 군집계수의 평균이다. 단 지역적 군집계수가 정의가 안되면 짤
세상에는 많은 군집이 존재한다
homophily : 유사한 정점끼리는
공통이웃이 있는경우 공통이웃이 두정점을 매개하는 역할
