실제 그래프(real graph)와 랜덤 그래프(random graph)

1. 실제 그래프(real graph)

 

실제 그래프(real graph)는 실제 존재하는 complex system으로부터 데이터를 얻어 표현한 그래프

 

그림1. 실제 그래프의 예시1

 

그림2. 실제 그래프의 예시2

MSN은 옛날에 microsoft에서 서비스하던건데 지금은 안한다고 한다

 

실제 그래프는 어떻게 이해해야할까? 잘 이해하기위한 비교대상이 필요하다. 

 

그것이 바로 random graph

 

 

2. 랜덤 그래프(random graph)

 

In mathematics, random graph is the general term to refer to probability distributions over graphs.

 

Random graphs may be described simply by a probability distribution, or by a random process which generates them

 

확률적 과정을 통해 생성한 그래프

 

확률분포에 따라 여러가지가 있지만

 

가장 단순한 Erdős-Rényi Random Graph G(n,p)는 n개의 node를 가지고 임의의 두 node 사이 link가 존재할 확률은 p로 모두 동일하며 link가 존재하는 모든 사건은 서로 독립이다.

 

당연한건데 link가 존재하지 않을 확률은 1-p

 

예를 들어 1번과 2번이 연결되어있다는 사실은 1번과 3번에 link가 존재할 확률과 무관하다.

 

 

 

3. 예시로 알아보는 Erdős-Rényi Random Graph

 

G(3,0.3)이 만들어내는 그래프와 각각 생성될 확률은?

 

 

선이 연결될 가능성은 3가지인데 각각은 연결된다, 연결안된다 2가지가 가능하므로 2*2*2=8개가 존재한다.

 

동그라미된 부분만 살펴보면 2가지 link가 존재할 확률은 각 사건이 독립이므로 0.3*0.3인데

 

하나의 link가 존재하지 않을 확률은 0.7이고 각 사건이 서로 독립이므로 0.3*0.3*0.7