강의 복습 내용
- 그래프관련 필수 개념
- 정점, 간선, 방향성, 가중치
- 동종, 이종 그래프
- 실제 그래프, 랜덤 그래프
- 경로, 거리, 지름
- 작은 세상 효과
- 연결성
- 연결 요소
- 군집
얻은 지식
그래프
용어
- 그래프
- 정점과 간선 집합으로 이루어진 수학적 구조
네트워크로도 불림
- 정점(vertex)
- 간선
중요성
- 다양한 복잡계(complex system)를 표현
- 사회, 통신 시스템, 정보, 뇌와 신체
- 구성요소간의 복잡한 상호작용이 많다.
- 이러한 상호작용을 표현하는데 사용되는게 그래프
- 복잡계를 이해하고 정확한 예측을 위해서는 그래프에 대한 이해가 필요하다.
예시
- SNS
- 각 사용자는 정점
- 서로 친구이면 간선으로 연결
- e쇼핑
- 사용자와 물건이 정점
- 어떤 특정물건을 구매하면 간선으로 연결
- 인터넷
- 각 라우터, 하이퍼링크, 위키피디아 작성들을 표현한다.
다양한 그래프 관련 인공지능 문제
- 정점 분류 문제
- 트위터에서 공유(retweet)관계를 분석하여 정치적 성향찾기
- 단백질의 상호작용을 분석하여 단백질의 영향 찾기
- 연결 예측 문제
- 거시적,미시적으로 볼 수있다.
- 거시적으로는 주어진 그래프가 어떻게 성장할지
- 페이스북은 어떻게 진화할지(성장할지 줄어들지, 더 상호작용할지 안할지)
- 미시적은 각 정점이 어떤 정점과 연결될지
- 추천 문제
- 쇼핑 추천문제로 어떤 물건을 구매하면 만족도가 높을지
- 군집문제
- 서로 밀접하게 연결된 정점(군집)을 찾는 문제
- 의미있는 군집을 찾아서 분류하기
- 연결 관계로부터 사회적 무리(social circle)을 찾아내기
- 랭킹 및 정보 검색 문제
- 다양한 웹페이지에서 원하는, 중요한 웹페이지를 찾기
- 정보전파 및 바이럴 마케팅
- 소셜네트워크로 정보가 전파된다.
- 이러한 정보는 어떻게 전달될지, 어떻게 정보를 최대화 할지
그래프 관련 필수 기초 개념
분류
- 방향이 있나 없나
- 두 정점이 같은 위치이면 방향이 없는 그래프
- 두 정점이 트위터 팔로우와 같이 정점간의 방향이 있는 그래프
- 가중치가 있나 없나
- 간선에 숫자를 통해 의미를 부여할 수 있으면 가중치가 있는 그래프로 분류한다.
- 주관적다.
- 동종(unpartite),이종(bipartite) 그래프
- 이종그래프는 두 종류의 정점을 가진다.
- 다른 종류의 정점 사이에서만 간선을 연결한다.
- 동종 그래프는 단일 종류의 정점을 가진다.
표현법
- v는 정점들의 집합
- E는 간선들의 집합
- G는 그래프
- 이웃(neighbor)은 정점과 연결된 다른 정점
- 정점v의 이웃들의 집합을 N(v),\(N_v\)로 적는다.
- 방향성있는 이웃
- 나가는 이웃\(N_out(v)\), 들어오는 이웃\(N_in(v)\)으로 구분
- v를 기준으로 들어오거나 나가는 정점들의 집합
그래프를 이용한 기계 학습
실제 그래프와 랜덤 그래프
- 실제 그래프
- 다양한 복잡계로 얻어진 그래프
- msn
- 사용자(정점), 메시지를 주고받은 관계(간선)
- 랜덤 그래프
- 확률적 과정을 통해 생성한 그래프
- 에르되스-레니 랜덤 그래프
- G(n,p)
- n개의 정점
- 임의의 두개의 정점 사이에 간선이 존재할 확률p
- 정점간의 연결은 서로 독립적
- G(3,0.3)은 간선이 있을확률0.3, 간선이 없을 확률은 0.7이다.
경로
- 정점 u와 v의 사이의 정점들의 순열
- u에서 시작하여 v에서 끝난다.
- 각 정점은 간선으로 연결 되어있어야한다.
- 경로의 길이
- 거리(distance)
- 그래프의 지름(diameter)
- 정점간 거리의 최댓값
- 모든 최단 경로중 최대인것
작은 세상 효과
- 실험
- 임의의 두사람을 골랐을때 몇단계의 지인을 거쳐 연결될까
- 여섯단계 분리 실험
- 오마하와 위치타로부터 보스턴까지 지인으로만 편지를 몇단계를 거쳐 전달될까?
- 평균 6단계를 거쳤다고 한다.
- 작은 세상 효과(small-world effect)
- 사람들이 소수의 공통된 지인을 통해 연결되어있다.
- 랜덤그래프에도 존재한다.
- 한사람당 100명의 지인일때, 5단계만 되어도 100^5명의 사람과연결된다.
- 존재하지 않는 경우
- 체인, 사이클, 격자 그래프는 존재하지 않는다.
- 서로 거리가 먼 정점들이 존재한다.
연결성(두꺼운 꼬리 분포)
- 정점의 연결성
- 정점과 연결된 간선의 수
- d(v), \(d_v\)혹은 \(\mid N(v)\mid\)로 적는다.
- 나가는 연결성\(d_out(v)\), 들어오는 연결성\(d_in(v)\)
- 실제 그래프의 연결성 분포는
두꺼운 꼬리를 갖는다.
- 연결성이 매우 높은 허브(hub)정점이 존재함
- 많은 정점들이 연결성이 적지만, 일부 연예인과같은 소수의 정점들은 많은 연결성을 가지고 있다는 의미
- 랜덤 그래프의 연결성 분포는 정규 분포와 유사
- 연결성이 매우 높은 정점이 존재할 가능성이 0
거대 연결 요소
- 연결요소(connected component)
- 정점들의 집합
- 연결요소에 속하는 정점들은 경로로 연결될수 있다.
- 정점을 추가할수 없다.
- 정점을 추가할 수 없다는 의미는 {1,2,3,4}라고 하면 5라는 정점을 추가가 가능하므로 {1,2,3,4}는 연결요소가 아니다.
- 거대 연결 요소(giant connected component)
- 대다수의 정점을 포함
- 실제그래프에 존재
- msn을 예시로 99.9%의 정점이 하나의 거대 연결 요소에 포함된다고 한다.
- 대부분의 사람은 메신저로 연결이 다 가능하다고 생각
- 랜덤그래프에도 존재
- 정점들의 평균 연결성이 1보다 충분히 커야한다고 한다.
군집 구조
- 군집(community)
- 집합에 속하는 정점 사이에 많은 간선이 존재
- 집합에 속하는 정점과 속하지 않은 정점사이에는 적은 수의 간선이 존재
- 지역적 군집 계수(local clustering coefficient)
- 한 정점에서 군집의 형성 정도를 측정
- 한 정점의 지역적 군집계수는 정점의 이웃 쌍중 간선으로 직접 연결된것의 비율
- 정점1의 이웃은 4개, 총 6개의 이웃쌍이 존재[(2,3),(2,4)(2,5)(3,4)(3,5)(4,5)]
- 이웃쌍은 이웃 조합 2와 같다
- 식은 (4*3)/2가 된다.
- 그중 3개의 쌍이 간선으로 직접 연결[(2,3),(2,4),(3,5)]
- 지역적 군집계수는 3/6=0.5가 된다.
- 지역적 군집계수와 군집
- 지역적 군집계수가 높으면 해당 정점과 그 이웃들은 군집을 형성한다.
- 전역 군집 계수(global clustering coefficient)
- 전체 그래프에서 군집의 형성 정도를 측정
- 각 정점에서의 지역적 군집 계수의 평균
- 실제 그래프에서는 군집 계수가 높다.
- 많은 군집이 존재
- 동질성
- 서로 유사한 정점끼리 간선으로 연결될 가능성이 높다고 한다.
- 같은 동네 친구야~
- 전이성
- 공통이웃이 있으면 공통이웃이 매개가 된다.
- 얘는 내 동네 친구야~
- 랜덤 그래프에서는 군집계수가 높지 않다.
실습
그래프의 표현 및 저장
- NetworkX라이브러리
import networkx as nx로 임포트
- 그래프 선언
G = nx.Graph() 방향성 없는 그래프G = nx.DiGraph() 방향성 있는 그래프
- 그래프 관련 메소드
- 정점 추가
- 정점의 수 반환
- 정점의 목록 반환
- 간선 추가
- 간선 목록
- 그래프 출력
- 그래프의 정점의 위치를 정해주는 함수
pos = nx.spring_layout(그래프)
- 정점 출력 및 색과 크기 설정
nx.draw_networkx_nodes(G,pos,node_color,node_size)
- 간선 출력
nx.draw_networkx_deges(G,pos)
- 각 정점 라벨 출력
nx.draw_networkx_labels(G,pos,font_size,font_color)
그래프 저장 및 표현
- 간선리스트
nx.to_edgelist(G)- 두 정점들의 순서쌍으로 저장
- 방향성이 있으면 (출발정점,도착정점)으로 저장
- 인접리스트
nx.to_dict_of_list(G)- 각정점의 이웃정점들을 리스트로 저장
- 인접 행렬
nx.to_numpy_array(G)nx.to_scipy_sparse_matrix(G)
- 행과 열을 정점으로
- 각 요소는 간선이 있으면 1, 없으면 0
그래프 특성
- 거리 계산
nx.single_source_shortest_path_length(Graph,v)- v를 시작 정점으로 하여 graph의 모든 정점의 거리를 반환
- 균일 그래프
- 작은 세상 그래프
- 군집 계수 크다
- 지름 작다
- 실제 그래프와 비슷한 구조를 가진다
- 지름이 작다는것은 6단계면 다 연결이 된다는 의미를 가진다.
- 실제 그래프도 6단계면 연결되므로 작은 지름을 가진다.
- 랜덤 그래프
좀더 찾아보기
- real graph, random graph
- 거대 연결 요소(giant connected component)
피어세션 정리
- 왜 지름이 작고 군집계수가 크면 실제 그래프와 비슷한 구조인지?
- 저번 kaggle
- decay는 0.1정도 넣으니 좋았다.
- 데이터 전처리 조작해보기
- 그냥 기본 세팅이 좋았다.
- 앙상블
- 랜덤그래프는 어디서 쓸까
- 의사결정트리 랜덤포레스트 쓸거같다.
- 가설 세울때?