Day_01_0. Graph Essentials

Graph Essential

--Konigs berg 다리문제
----2개의 섬과 7개의 다리문제로 다리를 1번씩 건너서 섬 전체를 지나기문제

--Modeling the problem by graph theory
----복잡한 사항을 그래프를 이용해 단순화 시키는 것

--Network
----network는 그래프, 네트워크 상의 문제는 보통 그래프 이론으로 해결이 가능하다
----twitter- 트위터는 사용자들에게 정보를 제공할 때 가장 최소의 비용으로 정보를 전달하는 방법등의 문제 해결

--Food web
----먹이사슬 관계로써 피식자, 포식자 간의 “관계”가 있다 – 방향성을 가지는 네트워크와 같다 

--도로망
----각 도시를 Node로, 도시간의 연결을 edge로 두고 생각할수 있다, 도로는 비 방향성 네트워크

--social network analysis
----소셜 network에서 node=각각의 개인 , edge=개인간의 관계

--소셜 Network의 분석 = social network analysis = ANA
----분석의 특징: 다양한 분야의 지식이 필요하다, Social science, statistics, computer science 등



Graph basics
--Nodes & edge
----네트워크는 graph로 볼수있다, 이때 node는 지점, 사용자등 edge는 관계, 연결로 대응된다
----소셜네트워크에서 node = 사람, edge는 친구관계등이 될수 있다, 노드의 집합은 V=V1,V2,V3..Vn 으로 표기, 그래프의 크기는 노드의 개수이다 (|V|=n)


--edges
----노드간의 연결, ties, relationship 으로 해석, 엣지의 집합 = E=E1,E2,E3..En, Edge의 크기 = |E|=m

--Directed edge and Directed graph
----엣지에 방향성이 존재하는 것, 비-방향성 그래프에서는 두 엣지가 같은 상황이다

--Neighberhood & Degree – in/outdegree
----방향성을 가지는 graph에서 , 노드에서 나가는 방향의 edge --> outdegree , 노드로 들어오는 방향의 edge -->in degree 로 표현하고 D^out D^in 으로 표현
----비 방향성의 그래프에서 degree의 합 = 엣지 수의 * 2
----방향성 그래프에서 indegree의 합= out degree의합
----어떤 노드에서 나가면 어떤 노드에서는 들어오기 때문에 같다

--degree distribution
----정의 = 그래프에서 node가 가지는 엣지의 개수 분포등을 표시, 분석에 아주 중요한 요소
----표기 = Pd = nd/n = Pdegree = 해당 degree노드의 개수/전테 노드의 개수 -->전체Pd의 합=1

--degree distribution plot
----x축은 degree, y축은 degree에 해당하는 node를 표기

--subgraph
----완전한 그래프에서 일부를 그린 그래프, 원본 graph에 존재하지 않는 edge는 그릴수 없음