데이터과학 기초-(13)그래프 이론

그래프 이론과 복잡계 네트워크

그래프 이론: Graph Theory

정점의 집합과 간선의 집합으로 구성된 그래프를 연구하는 수학의 한 분야
그래프: G=(V,E)
-V:정점의 집합, E:간선의 집합

네트워크 과학: Network Science

다양한 학문 분야에 펼쳐져 있던 복잡계의 연구 대상들이
-'네트워크'라는 하나의 주제로 통일되면서 발생한 학제간 연구 분야
복잡계 네트워크: Complex Network
-사회 현상의 탐구: 소셜 네트워크 - 사람과 사람 사이의 관계 분석
-생명 현상의 탐구: 단백질 네트워크 - 분자와 분자 사이의 관계 분석
-자연 현상의 탐구: 상전이 현상 - 네트워크 동역학으로 분석 가능

작은 세상 네트워크: Small- World Network

6단계의 분리: 세상이 참 좁은 이유에 대한 과학적 설명
소수의 원거리 연결만으로도 전체 네트워크의 평균거리가 크게 짧아짐

척도 없는 네트워크: Scale-Free Network

빈익빈 부익부: 네트워크에서 허브가 생겨나는 이유에 대한 과학적 설명
선호적 연결에 의해 평균 이상으로 많은 링크를 가진 허브가 탄생함
-> 멱함수 분포를 가진다.

단백질 접힘 문제: Protein Folding Problem

단백질의 아미노산 서열이 어떻게 고유한 접힌 구조를 결정하는가?
주어진 아미노산 서열만으로 단백질의 접힌 구조를 예측할 수 있을까?

네트워크 분석: Network Analysis

자연과학, 생명과학, 사회과학 등 모든 분야를 아우르는 데이터 과학 분야
-소셜 네트워크 분석:SNA, Social Network Analysis
-복잡계 네트워크 분석: Complex Network Analysis
주유 탐구 주제:
-중심성 분석: Centrality Analysis
-군집 분석: Cluster Analysis

네트워크 분석을 위한 기본 용어:

방향 그래프, 무방향 그래프: directed and undirected
가중치 그래프, 가중치 없는 그래프: weighted and unweighted
인접 행렬, 인접 리스트: adjacency matrix and list
단순 경로, 경로 길이, 랜덤 워크: simple path, path length, random walk

네트워크 분석을 위한 기본 정보:

노드(정점)와 연결(간선)의 수: Number of nodes and edges
평균 차수: Average degree
밀도, 반경, 반지름: Density, Diameter, Radius
평균 최단 거리:Average shortest path length
강연결/약연결 컴포넌트:
-Number of Strongly Connected Components(SCC)
-Number of Weakly Connected Componenets(WCC)

오렌지

네트워크의 중심성과 페이지 랭크

중심성 분석: Centrality Analysis

네트워크에서 중심부에 위치한 (가장 중요한) 노드를 찾기 위한 방법
-예) 인스타그램에서 10대 남성에게 가장 영향력이 높은 인플루언서는?

중심성 지수: Centrality Measures

-차수 중심성: Degree Centrality
-인접 중심성: Closeness Centrality
-매개 중심성: Betweenness Centrality
-페이지랭크: PageRank

차수 중심성: Degree Ceentrality

한 노드에 연결된 모든 연결의 개수로 중심성을 평가하는 지수

방향 그래프에서는 in-degree와 out-degree로 구분

인접 중심성: Closeness Centrality

한 노드가 다른 노드들로 가는 최단 경로가 얼마나 짧은 지를 평가

가정: 다른 모든 노드들로 가능 경로가 짧을수록 중심성이 높을 것이다.
-평균 최단 경로 길이가 짧은 노드일수록 중심성이 높다.

매개 중심성: Betweenness Centrality

한 노드가 네트워크의 다른 노드 간의 연결에 얼마나 기여하는지를 평가

페이지 랭크: PageRank

고유벡터 중심성: Eigenvector Centrality
-단순히 치구가 많은 노드와 핵인싸 친구가 많은 노드라면?

Katz 중심성: 고유벡터 중심성을 방향 그래프에 적용

페이지랭크 중심성:
-핵인싸와 친구인 노드가 모두 인싸일까?
-특정 노드의 영향력은 그 노드의 차수에 반비례해서 전파되어야함

중심성 지수의 비교

페이지 랭크와 구글 검색 엔진

협동 네트워크의 중심성 분석

Dataset: NetScience Collaboration Network
Coauthorship-pajek포맷:netscience.net