Day_09. Evolution of random graph

Evolution of random graph



Random graph 에서 p 의 형상
=0이면 edge가 없는 node만 있음
=1이면 모든 node간 edge가 연결되어 있다



가장큰 connected component
=giant component 라고 부름


Phase 의 변형(transition)이 발생하는 지점

C의 값이 1.0이 되는 지점(증명은 pass한다)

Degree의 분배 (distribution)
=Edge의 생성은 독립확률이다
=이항분포를 따르며
=n이 무한으로 갈때는 포아송분포를 따른다


Local/ Global clustering coefficient 수치
=p로 같음

Random graph의 특징
=Degree distribution = power-law 법칙을 따르지 않음
=Average path length = 만족한다
=Clustering coefficient = underestimate 로 만족하지 않는다


Small world Model
=average path length 가 6이하로 전세계를 연결 가능하다
=regular 한 형태의 그래프를 가진다
=노드간 연결인 edge의 분포 형태는 비슷하다

==min은 (n- |i-j|) 와 |i-j)의 절대값에서 작은 것을 선택하는 연산
=Small-world 모델은 random graph와는 상극이다
===장점과 단점이 반대 상황이다


Small world model properties (속성)
Regular lattice 와 random graph 의 차이

가장 최적의 상태는 0.01~0.1사이이다

격자 그래프(lattice graph)

Small world 그래프의 모형으로 베타의 값이 증가할수록 edge를 random 으로 rewired 시킨다

의 확률을 가지며
가 0이면 basically regular lattice 그래프

가 1이면 random graph 와 같다
Rewired = 한 개의 노드를 선정해서 기존에 연결된 edge를 때서 다른 node에 붙히는 것


Preferential attachment model
=small world model 이 power-law 모델을 대응하지 못하기 때문에 생긴 해념
=새 node가 추가될때마다 들어온 new노드를 기존 node와 연결시 이미 존재하는 노드의 연결된 확률로 연결한다
=degree가 높은 노드와 새로 들어온 node가 연결될 확률이 올라가는 것 –power-law모델을 만족한다


연결될 확률

연결될 확률 = 해당 노드의 도수/ 모든 degree의 합

새 노드v를 연결할 때 총 degree의 합인 7을 분모에, 방향성 그래프이기 때문에 해당 노드의 indegree 수치를 분자에 두고 계산한다



Configuration model
=자신이 생성한 node의 degree에 맞는 edge를 그림
=stub,half-edge 아직 상대방 노드와 연결되지 않았기 때문에 반쪽자리 edge
=각 반쪽 edge (stub, half-edge에 연번을 부여)를 임의로 연결한다

**생성방법**
1.노드 id를 degree의 수치에 따라 반복해서 쓴다
2.섞는다
3.순서대로 선을 이어준다
**형상(toplogy)는 유지되며 노드의 연번은 없다**

Vertex copying model
새로운 node의 추가시 기존 node의 edge의 연결을 복사해서 연결하는것