2강 - 그래프 패턴

2강. 그래프 패턴

• 실제 그래프: 실제 그래프란 다양한 복잡계로부터 얻어진 그래프를 의미한다.

• 랜덤 그래프: 확률적 과정을 통해 생성한 그래프이다.

• 에르되시-레니 랜덤 그래프 - 임의의 두 정점 사이에 간선이 존재하는지 여부는 동일한 확률 분포에 의해 결정된다. ex) G(3,0.3) 정점이 3개이며 간선 연결 확률이 0.3인 그래프

• 경로: u에서 시작해서 v에서 끝나야하고 연속된 정점은 간선으로 연결되어 있어야 한다.

• 거리: 최단경로의 길이를 의미한다.

• 지름: 정점간 거리의 최댓값이다.

• 작은 세상 효과: 인간 관계에서 몇 단계만 거치면 서로 연결되어 있다는 것을 보인 이론

• 여섯단계이론: 인간관계는 6단계만 거치면 지구상 대부분의 사람과 연결될 수 있다는 사회 이론이다.

• 연결성: 정점의 연결성은 정점과 연결된 간선의 수를 의미한다. 따라서 이웃의 수와 같다.

• 연결요소

1. 연결 요소에 속한 모든 정점을 연결하는 경로가 있어야 한다.

2. 또 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안된다.

• 군집구조: 집합에 속하는 정점 사이에는 많은 간선이 존재하고 집합에 속하지 않은 정점과는 적은 수의 간선이 존재하는 구조이다.

• 지역적 군집 계수: 정점 I의 지역적 군집의 계수는 정점 i의 이웃쌍중 간선으로 직접 연결된 것의 비율을 의미한다. 예를 들어 아래와 같은 사진의 군집이 있을때 이웃 4개는 총 6개의 연결쌍을 만들 수 있고 3개의 쌍이 직접연결 되어 있으므로 3/6 = 0.5 의 군집 계수를 갖는다.

• 전역 군집 계수: 지역적 군집 계수의 평균.