그래프(graph)란 무엇인가?

1. 그래프(graph)

 

정점(vertex) 집합과 간선(link) 집합으로 이루어진 수학적 구조

 

네트워크(network)라고도 부른다.

 

정점은 node라고도하고 간선(link)은 edge라고도 한다.

 

두개의 정점을 연결하는 선이 간선(link)

 

정점 쌍이 반드시 간선으로 직접 연결될 필요는 없다.

 

그림1. 그래프 구조 예시

 

1,2,3,4,5,6 숫자 점이 정점(node)

 

각 node가 연결되는 선들이 간선(link)

 

이들의 모임이 그래프(graph), 네트워크(network)

 

특히 3번과 6번은 직접 연결되어있지 않다

 

 

2. 그래프의 중요성

 

2-1) 복잡계(complex system)

 

A complex system is a system composed of many components which may interact with each other

 

서로 상호작용을 하는 많은 구성요소들 간의 모임

 

사회는 70억 인구들이 서로 상호작용을 하면서 형성된 complex system

 

통신시스템은 전자장치(desktop, laptop, mobile 등등)들이 와이파이, 인터넷 등으로 상호작용하면서 형성된 complex system

 

정보, 지식, 뇌, 신체 등도 complex system

 

정보는 왜 complex system??

 

컴퓨터정보, 요리정보, 게임정보들이 서로 모인 complex system

 

이런 complex system은 그래프를 이용해서 표현할 수 있다.

 

그래프는 complex system을 효과적으로 표현하고 분석하기 위한 하나의 언어다.

 

 

complex system을 이해하고 구성요소들간의 상호작용을 정확히 예측하기위해 complex system을 표현하는 그래프에 대한 이해가 필요하다

 

 

그래프를 잘 알면 complex system이 등장하는 여러 분야, 가령 전산학,물리학,생물학,화학,사회과학 등 다양한 분야에 그래프 인공지능을 활용할 수 있다.

 

 

3. 예시로 알아보는 그래프의 표현

 

 

3-1) SNS

 

 

사용자의 계정이 하나의 node

 

각 팔로우 관계가 link로 되어있는 graph

 

 

3-2) 전자상거래 구매 내역

 

 

 

 

사용자와 구매물품들이 node

 

사용자가 어떤 물품을 구매했는지 관계를 나타낸 link

 

 

3-3) 인터넷

 

 

 

라우터 간 연결이 하나의 인터넷을 표현하는 graph

 

HTML 문서 간 연결이 하나의 웹페이지를 구성함

 

사용자가 HTML 문서를 만들어 wikipedia가 구성됨

 

 

3-4) 기타

 

 

뇌의 뉴런 연결, 지식 그래프, 화학 분자, 단백질의 상호작용 등도 모두 하나의 complex system을 표현하는 graph