2강. 그래프 패턴
•
실제 그래프: 실제 그래프란 다양한 복잡계로부터 얻어진 그래프를 의미한다.
•
랜덤 그래프: 확률적 과정을 통해 생성한 그래프이다.
•
에르되시-레니 랜덤 그래프 - 임의의 두 정점 사이에 간선이 존재하는지 여부는 동일한 확률 분포에 의해 결정된다. ex) G(3,0.3) 정점이 3개이며 간선 연결 확률이 0.3인 그래프
총 8가지 형태가 나올 수 있고 각각의 확률은 위와 같다.
•
경로: u에서 시작해서 v에서 끝나야하고 연속된 정점은 간선으로 연결되어 있어야 한다.
예를 들어 1,4,6,8은 경로가 될 수 있지만 1,5,7은 경로가 될 수 없다.
•
거리: 최단경로의 길이를 의미한다.
•
지름: 정점간 거리의 최댓값이다.
•
작은 세상 효과: 인간 관계에서 몇 단계만 거치면 서로 연결되어 있다는 것을 보인 이론
•
여섯단계이론: 인간관계는 6단계만 거치면 지구상 대부분의 사람과 연결될 수 있다는 사회 이론이다.
•
연결성: 정점의 연결성은 정점과 연결된 간선의 수를 의미한다. 따라서 이웃의 수와 같다.
실제 그래프의 연결성 분포는 두터운 꼬리를 갖는다. 따라서 연결성이 매우높은 허브정점이 존재한다. 하지만 랜덤 그래프의 연결성 분포는 정규 분포와 유사하기에 허브가 존재하기 힘들다.
•
연결요소
1.
연결 요소에 속한 모든 정점을 연결하는 경로가 있어야 한다.
2.
또 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안된다.
간단히 말해서 다른 요소들과 연결되어 있지 않으면서 연결된 구조들을 연결 요소라고 부른다.
•
군집구조: 집합에 속하는 정점 사이에는 많은 간선이 존재하고 집합에 속하지 않은 정점과는 적은 수의 간선이 존재하는 구조이다.
•
지역적 군집 계수: 정점 I의 지역적 군집의 계수는 정점 i의 이웃쌍중 간선으로 직접 연결된 것의 비율을 의미한다. 예를 들어 아래와 같은 사진의 군집이 있을때 이웃 4개는 총 6개의 연결쌍을 만들 수 있고 3개의 쌍이 직접연결 되어 있으므로 3/6 = 0.5 의 군집 계수를 갖는다.
•
전역 군집 계수: 지역적 군집 계수의 평균.
실제 그래프에서는 동질성과 전이성으로 인해 군집 계수가 높고 군집이 많이 존재한다.
동질성: 유사한 정점끼리 간선으로 견결될 가능성이 높다는 성질
전이성: 공통 이웃이 있는 경우 공통 이웃이 매개 역할을 해주는 성질
랜덤그래프에서는 동질성과 전이성이 나타나지 않기 때문에 군집계수가 높지 않다.
