ai tech 21회차

# 그래프

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

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

하지만 모든 정점 쌍이 반드시 간선으로 직접 연결되는 것은 아니다

그래프는 네트워크로도 불린다.

정점은 노드로, 간선은 엣지 혹은 링크로 불린다.

 

# 복잡계

사회는 70억 인구로 구성된 복잡계

통신 시스템은 전자 장치로 구성된 복잡계

정보과 지식, 뇌, 신체도 복잡계

복잡계는 구성 요소간의 복잡한 상호작용이 특성이다.

그래프는 복잡계를 효과적으로 표현하고 분석하기 위한 언어이다.

SNS 같은 복잡계는 사용자들이 노드이고 사용자들간의 연결이 엣지이다.

쇼핑몰 같은 복잡계는 사용자와 각각의 물건들이 노드이고, 사용자와 물건간의 연결이 엣지이다.

인터넷도 라우터들간의 상호작용 연결,

웹도 웹페이지간의 하이퍼링크 연결,

위키피디아도 작성자와 각 문서간의 연결로 나타낼 수 있다.

즉, 복잡계는 구성 요소들 간의 상호작용으로 이루어진다.

상호작용을 표현하기 위한 수단이 그래프이며,

복잡계를 이해하고 복잡계에 대한 정확한 예측을 하기 위해서는

복잡계 이면에 있는 그래프에 대한 이해가 반드시 필요하다.

그래프를 공부해서 복잡계가 등장하는 수많은 분야에 활용할 수 있다.

 

# 정점 분류 문제(node classification)

정점이 여러 유형을 가진 경우 각 정점의 유형을 추측하는 문제이다.

트위터에서의 공유 관계를 분석하여 각 사용자의 정치적 성향을 알 수 있다.

그래서 어떤 정점의 정치적 성향도 알아낼 수 있다.

 

어떤 단백질의 상호작용을 분석해서 단백질의 역할을 알아낼 수도 있다.

 

# 연결 예측 문제(link prediction)

거시적 측면에서는 네트워크가 어떻게 변화할지에 대한 것이다.

예를 들어 페이스북을 그래프로 나타내고,

사람들이 더 많이 상호작용 할 지 하지 않을 지에 대한 관측을 할 수 있다.

 

미시적 측면에서는 각 정점이 앞으로 어떤 정점과 연결 될지에 대한 예측을 하는 것이다.

추천시스템들이 이 방식을 사용한다.

어떤 유저가 앞으로 어떤 물건과 연결될 지 예측을 할 수 있기 때문이다.

 

# 군집 분석 문제(community detection)

연결 관계로부터 사회적 무리를 찾아낼 수 있을까에 대한 것이다.

 

# 랭킹 및 정보 검색 문제(ranking, information retrieval)

웹이라는 거대한 그래프로부터 어떻게 중요한 웹페이지를 찾아낼 것인가

 

# 정보 전파 및 바이럴 마케팅 문제(information cascading, viral marketing)

정보는 네트워크를 통해 어떻게 전달될 것인가?

어떻게 이 정보전달을 최대화 할 수 있을 것인가?

 

# 방향이 없는 그래프와 방향이 있는 그래프

방향이 없는 그래프는 간선에 화살표가 없지만,

방향이 있는 그래프는 간선에 화살표가 있다.

논문의 인용을 나타낸 인용 그래프나 트위터에서의 팔로우 그래프는 방향이 있는 그래프로 나타낼 수 있다.

협업을 나타내는 협업 관계 그래프나 서로 친구를 맺는 페이스북 친구 그래프는 방향이 없는 그래프로 나타낼 수 있다.

 

# 가중치가 없는 그래프와 가중치가 있는 그래프

간선에 가중치가 있으면 간선 부분에 표현한다.

전화를 몇번 주고 받았는지를 나타내는 전화그래프나 두 정점이 얼마나 유사한지를 나타내는 유사도 그래프는 가중치가 있는 그래프로 나타낼 수 있다.

페이스북 친구 그래프 같이 단순하게 친구관계만 나타내는 그래프는 가중치가 없는 그래프로 나타낼 수 있다.

 

# 동종 그래프와 이종 그래프

동종 그래프는 단일 종류의 정점을 가지고,

이종 그래프는 두 종류의 정점을 가진다.

이종 그래프는 또한 다른 종류의 정점 사이에만 간선이 연결 될 수 있다.

전자 상거래 구매내역 같은 사용자와 상품 정점 사이에만 간선이 연결되는 경우가 이종 그래프이고,

어떤 배우가 어떤 영화에 출연했는지를 나타내는 그래프도 배우와 영화 사이에만 간선이 연결되므로 이종 그래프이다.

 

# 그래프 분류해보기

 

# 방향성이 없는 그래프의 이웃

그래프는 정점 집합과 간선 집합으로 이루어진 수학적인 구조이다.

정점들의 집합을 V,

간선들의 집합을 E,

그래프를 G = (V, E)로 적는다.

 

정점의 이웃은 그 정점과 연결된 다른 정점을 의미한다.

정점의 이웃들의 집합을 보통 N(v)혹은 Nv로 적는다.

위 그림에서 1번 노드의 이웃은 2번, 5번이다.

 

# 방향성이 있는 그래프의 이웃

방향성이 있는 그래프에서는 나가는 이웃과 들어오는 이웃을 구분한다.

정점 v에서 간선이 나가는 이웃의 집합을 Nout(v)로 적는다.

정점 v에서 간성이 들어오는 이웃의 집합을 Nin(v)로 적는다.

 

# NetworkX

파이썬 라이브러리

그래프를 생성, 변경, 시각화 할 수 있다.

그래프의 구조와 변화를 분석할 수 있다.

 

# NetworkX import

# 그래프 초기화

# 그래프에 정점 추가하기

# 그래프에 간선 추가하기

# 그래프 시각화 하기

 

# 그래프의 표현 및 저장하는 방법

1. 간선 리스트

2. 인접 리스트

3. 인접 행렬

 

# 간선 리스트

방향성이 없는 경우 단순하게 순서쌍으로 나타낸다.

어떤 노드와 어떤 노드의 관계를 하나로만 나타낸다.

방향성이 있는 경우 출발점, 도착점 순서쌍으로 나타낸다.

간선리스트는 어떤 관계를 찾기 위해서 모든 내용을 뒤져봐야한다는 단점이 있다.

 

# 인접 리스트

방향성이 없는 경우 딕셔너리에 리스트 형태로 저장한다.

방향성이 있는 경우 들어오는 이웃들 딕셔너리와, 나가는 이웃들 딕셔너리에 각각 리스트 형태로 저장한다.

인접리스트는 어떤 관계를 찾기 위해서 특정 노드만 찾아보면 되기 때문에 효율적이다.

 

# 인접 행렬

방향성이 없는 경우 대각행렬 형태로 대각선을 기준으로 대칭하는 결과를 보여준다.

방향성이 있는 경우 특정 노드에서 특정 노드로 이동하는 내용을,

특정 행에서 특정 열로 이동하는 형태로 작성할 수 있다.

# Network 그래프를 표현하고 저장하기

행렬에 0이 많을 경우에는 희소 행렬로 나타내면 저장 공간을 많이 아낄 수 있다.

다만 0이 거의 없는 경우에 희소 행렬로 나타내면 속도가 많이 줄어든다.

 

# 실제 그래프와 랜덤 그래프

실제 그래프는 다양한 복잡계로부터 얻어진 그래프를 말한다.

소셜 네트워크, 전자상거래 구매내역, 인터넷, 웹, 뇌, 단백질 상호작용, 지식 그래프 등

MSN 메신저 그래프는 1억 8천만 사용자정점이 13억 메세지를 주고받은 간선으로 나타낼 수 있다.

랜덤 그래프는 확률적 과정을 통해 생성한 그래프를 의미한다.

 

# 랜덤 그래프의 예시: 에르되스-레니 랜덤 그래프

에르되스-레니 랜덤 그래프는 임의의 두 정점 사이에 간선이 존재할 확률이 동일한 확률 분포로 결정된다.

G(n:정점의 갯수, p:정점 사이에 간선이 존재할 확률)로 나타낼 수 있다.

정점 간의 연결이 서로 독립적이다.

각 간선이 존재할 확률이 0.3이므로 간선이 없을 확률은 0.7이다.

그래서 위에서의 각각의 그래프가 생성 될 확률이 계산된다.

 

# 경로

정점 u와 v사이의 경로는 u와 v로 끝나는 순열이고, 연속된 순열은 실제 간선으로 연결되어 있어야 한다.

따라서 경로는 같은 정점이 두번 등장하더라도 문제가 되지는 않는다.

 

# 경로의 길이

경로의 길이는 경로에 놓이는 간선의 수이다.

추가적으로 생각해보면 간선의 수는 정점의수에서 1을 뺀 것과 같다.

 

# 거리

거리는 정점 u와 v사이의 최단 경로의 길이이다.

# 지름

정점 간 거리의 최대 값이다.

# 작은 세상 효과

임의의 두 사람을 골랐을 때, 몇 단계의 지인을 거쳐 연결되어 있을까?

여섯 단계 분리 실험

사회학자 스탠리 밀그램에 의해 1960년대 실험

오마하와 위치타에서 500명의 사람을 뽑음

보스턴에 있는 한 사람에게 편지를 전달하도록 함

 

즉, 사람들이 소수의 공통된 사람들을 통해서 연결되어 있다는 사실을 작은 세상 효과라고 한다.

 

# 랜덤 그래프와 작은 세상 효과

작은 세상 효과는 높은 확률로 랜덤 그래프에도 존재한다.

모든 사람이 100명의 지인이 있다고 가정하면,

다섯 단계를 거치면 100억명의 사람과 연결 될 수 있다.

그러나 지인이 중복될 경우가 분명히 있을 것이므로 100억명 보다는 적게된다.

하지만 모든 그래프에서 작은 세상 효과가 존재하는 것은 아니다.

체인 그래 프 , 사이클 그래프, 격자 그래프 같은 경우는 작은 세상 효과가 거의 존재하지 않는다.

# 연결성

정점의 연결성은 그 정점과 연결된 간선의 수를 의미한다.

 

# 두터운 꼬리 분포

실제 그래프의 연결성 분포는 두터운 꼬리를 갖는다.

랜덤 그래프의 연결성 분포는 높은 확률로 정규 분포를 따른다.

 

즉, 랜덤 그래프의 연결성을 확률 분포로 나타내면 정규 분포 형태이고,

실제 그래프의 연결성을 확률 분포로 나타내면 두터운 꼬리 분포 형태이다.

 

# 연결 요소

 

# 거대 연결 요소

실제 그래프에는 거대 연결 요소가 존재한다.

거대 연결 요소는 대다수의 정점을 포함한다.

아래 그래프에서 왼쪽에 대각선 형태로 그려진 그래프들은 친구가 서로 독립되고 크기가 작은 그룹들이고,

거대연결요소 하나가 거의 대부분의 정점을 갖는다.

랜덤 그래프에도 높은 확률로 거대 연결 요소가 존재한다.

하지만 정점의 평균 연결성이 1보다 커야한다.

평균 연결성이 3정도 되면 대부분의 정점이 거대 연결 요소에 포함되게 된다.

 

# 군집

집합에 속하는 정점 사이에는 많은 간선이 존재하고,

집합에 속하는 정점과 그렇지 않은 정점 사이에 적은 수의 간선이 존재할 때,

그 집합을 군집이라고 한다.

# 지역적 군집 계수

한 정점에서의 군집 형성 정도를 측정한다.

위 그림에서 간선이 생길수 있는 모든 경우의 수는

2, 3

2, 4

2, 5

3, 4

3, 5

4, 5

총 6개인데, 이중에 실제로는 3개만 직접 연결되어 있으므로 3/6이다.

 

일반적으로 간선이 줄어들수록 지역적 군집 계수는 감소하게 된다.

연결성이 0인 정점에서는 이웃 자체가 없을것이기 때문에 지역적 군집 계수가 정의되지 않는다.

정점 i의 지역적 군집 계수가 높다는 것은 정점 i의 이웃들도 높은 확률로 서로 연결되어 있는것을 뜻한다.

즉, 정점 i와 그 이웃들은 높은 확률로 군집을 형성한다.

 

# 전역적 군집 계수

전체 그래프에서의 군집 형성 정도를 측정한다.

모든 정점의 지역적 군집 계수의 평균을 내면 된다.

다만, 지역적 군집 계수가 정의되지 않는 정점은 제외한다.

 

# 높은 군집 계수

실제 그래프는 높은 군집 계수를 보여준다.

즉, 많은 군집이 존재한다.

이유는 동질성과 전이성이 있다.

 

랜덤 그래프에서는 지역적, 전역 군집 계수가 높지 않다.

간선 연결이 독립적인 확률로 얻어지기 때문에,

이웃이 존재하든 안하든 간선 연결 확률은 같고, 동질성과 전이성이 없다.

 

# 군집 계수 및 지름

작은 세상 그래프가 실제 그래프와 가장 비슷한 결과를 보인다.