Day_01_3. Graph Essentials

Network Flow

--Network flow
----예시)무한히 공급되는 수도에서 싱크대까지 물을 대는데 캐파가 정해진 파이프에서 최대한으로 흐를수 있는 양은 얼마일까?
----예시)소셜 네트워크에서 개인이 메시지를 보낼수있는 양이 제한될 때 얼마나 많은 용량을 준비해야 어떤상황에도 대비할수 있을까?

----특징
-----방향성이 있는 가중치 그래프
-----전송 가능양은 엣지에 정해진 용량만큼만 보낼수 있다
-----손실이 없다는 가정하에 인입과 도착한양의 flow는 보존된다

--ford-fulkerson algorithm
----모든 엣지에서 사용하지 않은 용량이 있는 엣지를 탐색하는 알고리즘

--residual network
----네트워크상에서 얼마나 많은 용량이 네트워크에 남았는지 확인한다

--intution
----원본 네트워크에 flow가 없을 때 용량 잔존량
----방향성 그래프에서 흐르는양을 제어하기 위해 흐르는 방향의 반대방향으로 flow를 조절해서 용량을 조정


--augmentation / augmenting path
----잔종량을 가지고 원본그래프보다 많은양을(잔존량을 다른곳으로 이동시키며) 전송하게 해준다



Maximum pipatite matching
--definition 정의
----2분법 그래프로서 인접 노드는 다른색을 칠하며 그룹을 나누는 것.각노드는 1번씩만 선택이 가능하다


Bridge/weak ties,bridge detection
--bridge / localbridge
----브릿지:엣지중 제거하면 연결된 컴포넌트의 수가 증가하는 엣지, 해당 엣지를 제거하면 노드가 섬이 되어버린다
----로컬 브릿지: 제거하면 최소 경로가 2이상으로 증가하는 엣지

--strength of ties
----연결성의 강/약
-----소셜 네트워크상에서 강한 연결=친구관계 약한 연결=지인 관계 등으로 표현가능

--bridge and tie strength
----노드가 삼각형의 형상을 가질 때 모서리의 연결은 약한 연결을 의미한다

그림에서 A B C연결에서 푸른색의 연결라인이 약한 연결성을 의미한다

Day_01_2. Graph Essentials

Special graph
--gree& forest
----트리는 비방향성 그래프의 예, 어떤 node의 쌍이던 길이 1개만 있다, cycle이 없다, tree상의 |V|=|E|+1 (전체 노드 = 전체 엣지+1)
----forest 숲 = tree의 집합

--spanning tree
----모든 노드를 포함하는 그래프의 subgraph ,1개의 graph에 다수의 spanning tree가 있다
----대다수의 spanning tree가 가중치 그래프를 기반으로 작성되고 최소비용 spanning tree를 minimum spanning tree(MST)라 한다

--steiner tree
----spanning tree와 비슷하나 terminal 노드(여러 개의 node를 연결해주는 노드)가 2개 있을 때 가중치가 가장 줄어든다는 이론

--complete graph
----엣지들이 서로 겹치지 않는 상태로 그려진 그래프

--bipartite graph – 이분그래프
----인접 노드(서로 연결된) 끼리 서로 다른 색으로 칠할수 있는 그래프, 모든 노드가 2가지로 나눌수 있으며 같은 그룹끼리는 연결되지 않는 그래프


--affiliation graph
----이분 그래프의 일종으로 개인, 그룹으로 볼수있어서 다tndml 개인 노드가 특정 노드에 연결되어 있는 형태

--social affiliation network
----소셜 네트워크는 거대한 affiliation 의 조합이다, 1개인이 여러그룹(독서,운동 클럽등)에 소속될수 있고 해당 그룹의 집합이 소셜 네트워크를 이루기 때문


--regular graph
----모든 노드가 동일한 degree를 가지는 형태( 각노드의 연결된 엣지의 수가 같다)
----complete graph 는 regular graph의 한가지 예이다


--bridge
----다리처럼 해당 엣지를 제거하면 연결된 컴포넌트가 줄어드는 것, 그래프가 조작나는 중요한 엣지

--egocentric network
----전체 그래프에서 특정인원을 기준으로 추출한 네트워크



Graph algorithms -->graph/Netwok traversal algorithms
--graph와 tree의 탐색
----소셜미디어에서 사용자의 평균 나이를 계산한다면?
----하나의 시작지점에서 모든 사용자를 방문한다, 이때 한 사용자는 1번만 방문한다
----깊이를 먼저 탐색할까? = Depth first search –DFS
----넓이를 먼저 탐색할까? = Breadth First search - BFS


--깊이 우선 탐색=DFS
----노드에서 다음 노드로 이동시 하단에 있는 노드를 먼저 방문
----STACK 구조 기반

--넓이 우선 탐색=BFS
----노드에서 다음노드 이동시 옆에 있는 노드를 먼저 방문
----Queue 구조 기반



Finding shortest paths
--shortest path – 최단거리
----graph가 connected (모든 노드가 연결된상태)에서 임의의 노드 pair에서 가장 빠르게 갈수 있는길(path)

--Dijkstra’s algorithm = 다익스트라 알고리즘
----비-방향성 가중치 그래프에서 효과가 있다
----시작노드 s에서 어떤 노드든 해당 노드로 이동하는 최소한의 node비용을 계산
----최단거리와 해당 거리의 길이를 산출한다



Finding Minimum Spanning Tree
--Prim’s algorithms
----Minimum spanning tree
------random 노드를 선택
------다음 노드 선택시 엣지의 가중치가 낮은 노드로 이동(아직 선택되지 않은 노드에서)
-----막다른 노드에 왔을 때 이전 노드로 돌아와서 다시 낮은 가중치를 탐색한다
-----전체로 확장 될때까지 진행한다

Day_01_1. Graph Essentials

graph representation
--graph representation
----그래프는 보기에는 직관적이나 수학적 계산 및 컴퓨팅 tool을 사용하기에는 적합하지 않음
-----목적=정보를 손실하지 않고 그래프 그리기,컴퓨터로 계산하기 쉽고 수학적 방법론이 있다

--근접 행렬-adjacency metrix
----x축의 table에서 서로 관계가 있으면 1, 없으면 0으로 표현
----social media 에서는 사용하기 나쁨, 대다수의 field가 0으로 채워져 있기 때문(sparse 함)

--근접 리스트 – adjacency list
----실제 관계가 겅립된 사람들만 표시하는 것, nodes -- > connected to로 표현

--edge list
----각 노드간 엣지만 모아서 list화 시킨 것, 훨씬 간결하고 효과가 좋다


Type of graph
--null / empty graph
----null graph = 각 노드가 null인 것 , node가 하나도 없는 것, 당연히 edge도 없다
----empty graph = 노드는 있으나 노드 사이에 edge는 없다
----null graph는 는 empty그래프가 될수 있으나 역은 성립하지 않는다

--Directed / indirected / mixed graph
----방향성 directed에서의 엣지간의 역은 성립하지 않는다
----비-방향성 undirected에서는 역도 같다

--simple / multi graph
----각 node간의 연결이 1개일 때 = single , 1개이상 = multi graph , 근접행렬에서 table은 연결된 숫자만큼 적어둔다

--weighted graph
----가중치 그래프로서 각 node사이의 edge에 수치가 적혀있다 G(V,E,W)로 표기
----가중치 graph 상에서 w가 0이면 node가 연결 사항이 없는 것

--signed graph
----weigh의 표기가 binary(0/1 , +/- , -1/1)으로 표기된 것
----가중치 그래프 상에서 w가 0이면 node간 연결사항이 없는 것


--web graph
----web상에서 site가 어떻게 서로 연결되어 있는지 표현
----일반적으로 directed, multi graph 의 형태
----node는 site, edge는 link로 대입
----loop 도 존재한다( 자기자신에게 돌아오는 링크)


connectivity in graph
--Adhacent nodes and incident edges
----두개의 node가 연결되어 있을 때 adjacent 하다고 표현
----incedent = 2개의 edge가 1개의 end-point를 공유할 때 쓰는 표현, 방향성 graph에서는 방향성까지 같아야 incedent 하다고 표현한다


--walk/path/trail/tour/cycle
----walk = incedent 하면서(경로가 겹치면서) node를 방문하는 것
------------open walk = 시작지점에서 끝나지 않는 것
------------close walk = 시작 지점에서 끝나는 것
------------length of walk = 방문한 edge의 수
----trail = graph 상에서 각 엣지를 1회이상 방문하지않고 전체를 방문하는것
------------close tail = 시작지점에서 trail 이 끝나는 것, tour, circuit이라고 한다
----path = edge가 모두 같은 방향으로 이동하며 edge가 겹치지 않는 것,
------------모든 노드를 방문할 필요는 없다, path의 크기는 방문한 엣지의 수

----example)
----Eulerian tour – 모든 edge를 1회만 방문해서 전체 node탐색
----hamiltonian cycle – edge를 1회만 방문하여 다시 시작점으로 돌아온다


--random walk
----시작 node에서 다음 node로의 이동이 random 으로 진행
----mark a spot on the ground 게임(격자무늬의 바닥에 동전의 앞뒤에 따라 동서남북으로 이동하는것, 동전이 많으면 방향도 증가한다)


--connectivity 

----node i와 j가 엣지를 이용해 서로 연결되어 있을때를 의미
----방향성 graph에서의 strongly connection –노드 i에서 j로 가는 길이 있다
----방향성 graph에서의 weakly connection – 노드 i에서 j로 갈수 없다


--component
----비방향성 graph에서 -->연결된 subgraph
----방향성 graph 에서 --> 어떤 노드의 쌍에서도 이용이 가능하며 반대도 가능하다


--shortest path 최단거리
----2개의 node 사이에 가장 짧은 거리로 이동하는 것
----보통 node간의 이동은 최단거리를 기준으로 진행한다
----n- hop neighborhood 는 n번만에 이동 가능한 node들을 의미함


--Diameter 직경
----그래프상에서 가장 긴 거리의 path를 graph의 diameter

--근접행렬과 연결성
----근접행렬상에서 노드 I,j사이의 node의 수

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는 그릴수 없음