1강 - 그래프 이론

1강. 그래프 이론 기초

1. 그래프란 무엇인고, 왜 중요할까?

• 정점 집합과 간선 집합으로 이루어진 수학적 구조

• 하나의 간선은 두 개의 정점을 연결

• 모든 정점의 쌍이 반드시 간선으로 연결되는 것은 아님

• 우리 주변에는 많은 복잡계가 존재 → 그래프를 통해 효과적으로 표현 가능

• 복잡계를 이해하고 복잡계에 대한 정확한 예측을 하기 위해서는 복잡계 이면에 있는 그래프에 대한 이해가 반드시 필요함

• 정점 분류 문제 : 트위터에서 공유 관계를 분석하여 각 사용자의 정치적 성향 파악 or 단백질의 상호작용을 분석하여 단백질의 역할

• 연결 예측 문제 : 페이스북 소셜네트워크 진화

• 추천 문제

• 군집 분석 문제

• 랭킹 및 정보 검색 문제

• 정보 전파 및 바이럴 마케팅 문제

2. 그래프 관련 필수 기초 개념

• 간선에 방향이 없는 그래프

• 간선에 방향이 있는 그래프

• 간선에 가중치가 없는 그래프

• 간선에 가중치가 있는 그래프

• 동종 그래프 : 단일 종류의 정점

• 이종 그래프 : 두 종류의 정점

• 정점들의 집합 : V

• 간선들의 집합 : E

• 그래프 : G=(V,E)

• 정점의 이웃 : 정점과 연결된 다른 정점