그래프(Graph)란?

• 본 포스팅은 네이버커넥트재단과 신기정 교수님(KAIST AI대학원) 자료를 참고하여 작성하였습니다

1. 그래프(Graph)란?

그래프 : 정점(노드) 집합과 간선 집합으로 이루어진 자료 구조로서 네트워크(network)라고도 불리운다
=> 방향, 가중치 유무, 노드 종류(동종, 이종) 등에 따라 유형이 분류될 수 있다

2. 그래프 기호 표기

3. 그래프 필수 개념

• 경로 : 노드u와 v를 연결하는 노드들의 순열

• 경로 길이 : 경로 상의 노드의 수
• 노드간의 거리 : 노드 간의 최단 경로 길이
• 그래프의 지름 : 노드 간 거리의 최댓값
• 연결성 : 해당 노드의 이웃들의 수
  • N(d) : 이거는 이웃한 노드들의 집합

• 지역적 군집계수 : 노드가 군집이 되려하는 정도
• 노드4개중 쌍이 6개(4C2) 중 실제 연결된것이 3개 : 3/6
• 연결성이 0인 노드에서는 정의안됨 (분모가 0이므로)
• 전역 군집 계수 : 각 노드에서의 지역적 군집 계수의 평균 (정의가 안되는 노드는 제외)