Day_03. Signed graph

Signed Graph
--web graph –각 정부기관의 웹사이트 연결성을 그래프로 작성, Bow-tie structure 형태를 지니며 연결되어있었다.

Adjacent node / incident edge
--adjacent-노드끼리 이웃하는 상황
--incident edge -- 한 노드에서 공유하는 엣지가 있을 때


Walk/path/trail
--walk = 특정 노드에서 다른 노드로 이동하는 상황
-----open walk = 시작 노드와 종료 노드가 다름
-----close walk = 시작 노드와 종료 노드가 같음
--trail = 모든 엣지를 1회만 방문하는 것
--path = 노드와 엣지를 1회만 방문시
-----size of path = 방문한 엣지의 수

오일러 tour = 모든 엣지는 1방만 방문하며 모든 노드를 탐색하는 것

Hamilton cycle = 시작점으로 다시 돌아오는 형태로 모든 node를 방문하는 것

Random walk = 처음 선택한 노드에서 다음노드 방문이 임의로 진행되는 것, 이때 엣지의 weight 는 확률이라고 볼수있다


Connectivity = 노드 사이에 엣지가 있어서 이동이 가능한 상황
-----strongly connect = 임의의 노드에서 방향성을 가지면서 연결되있는거
-----weakly connect = 방향성없이 노드끼리 연결되거나, 방향성 그래프에서 연결이 안되있음


Component = 비방향성 상황에서 연결된 것, sub graph라고 한다
-----weakly = 비방향성 상황에서
-----strongly = 방향성 그래프 상황에서


Shortest path = a에서 b로 이동시 가장 빠르게 이동가능한 경로
Diameter = Graph 의 직경, graph 에서 가장큰 길이를 가지는 노드의 길이
-----실사용 경우 = 통신선로를 설치시 최소한의 경로로 설치 해야됨
-----web graph에서 평균 diameter는 19~20 hop을 가진다, 하지만 현재 web의 크기에서 10배로 커져도 diameter크기는 19~21 정도이다, 큰폭으로 성장하지 않음



Special graph
---Tree = 방향성 없는 그래프,cycle이 존재하지 않고 임의의 2노드를 선택해도 경로가 존재함, cycle이 없음
---minimum spanning tree = 생성한 spanning tree가 최소한의 비용을 가질 때 MST라 한다
-----통신망 생성에서 가장 많이 사용하는 Graph
---steiner tree = 전체 노드가 아닌 특정 노드들만을 넣어서제작한 tree


Complete graph
---각 노드에서 다른 노드로 가는 엣지가 존재한다, 이때 엣지의 개수 = n(n-1)/2


Planer graph
--엣지가 겹치지 않는 그래프



Bipartite graph
--노드를 2가지 그룹으로 나누고 연결은 다른 그룹간의 엣지만 연결된다
----Affiliation network = 1사람이 다수의 그룹에 포함되는 것을 표시하는 그래프
----bipartitie graph metrix = 개인 – 그룹 의 상황을 인접 행렬로 표시할 때 사용한다
--개인을 X 행렬
--그룹을 X^T 행렬로 표현 가능 

X * X^T = 사용자간의 관계를 나타낸다

X^T * X = 그룹간의 유사도를 나타낸다


Complete graph
=모든 노드가 같은 degree로 유지되는 그래프


Bridge
=해당 edge를 제거시 graph가 component 로 구분되어 쪼개지는 edge