Day_02. Graph Essentials

2.graph essential

Konigsburg의 다리문제
--오일러의 그래프 증명


네트워크 역시 graph이다
--twitter의 예시, 각사용자를 노드로 사용자간의 관계를 edge로 표현가능


Food chain
--먹이사슬을 방향성이 있는 그래프로 볼수 있다, 초식동물이 먹히는 등의 상하관계가 있기 때문

Social Network 와 Network analysis

Basic graph
--엣지는 다양한 값을 지정 가능하고 이때 주최자의 선택에 따라 거리, 비용이 여기에 들어간다
--socail media 에서 한 개인이 한 개의 노드에 해당한다
--Graph의 size 측정 = node의 개수 ,edge의 집합=E로 표기



Directed/Non-directed graph의 정의
--엣지에 화살표로 방향이 있는 그래프
--하나의 노드에서 그려져있는 엣지의 개수가 degree가 된다 Di로 표기
--Directed graph에서 2가지 degree ,in/out edge
--증명1. 비방향성 그래프에서 degree의 총합은 엣지 개수의 2배
--증명2,홀수의 degree그래프 + 짝수 degree 그래프 = 2|E|
--각각의 노드는 indegree 의 합과 out degree의 합은 같다

Node distribution
--전체 노드에서 선택된 degree에 맞는 노드의 수 = P degree = 선택된 degree에 해당하는 node의 수 / 전체 노드수


Degree distribution plot
--대부분의 social network에서 대다수의 사람들이 영향력이 적고, connection이 극소수만 많은 connection을 가진다



Subgraph
--전체 그래프에서 일부를 때서 만든 그래프


그래프의 저장 방식
--인접행렬, 인접 리스트, 엣지 리스트
--주의사항 = 데이터의 손실은 없게, 수학적 처리가 잘되게
--인접 행렬의 특징 = 대부분의 행렬이 0으로 채워져 있다
---------------------------sparse 하다, 공간의 활용이 떨어진다
--인접 리스트이 특징 = 실제 연결되어있는 노드끼리만 구성되어 공간의 활용이 좋다


Null graph & empty graph
---null graph 인 상황 , null graph는 empty graph 일수 있지만 역은 성립이 안된다
---empty graph = edge가 empty


Matrix transpose
--행렬의 가로를 세로로 변화 --> 방향성 graph의 transpose 는 기존 행렬과 다르다, 비 방향성 graph의 transpose는 같다


Simple, multi graph
--노드사이에 간선이 1개인것과 여러 개의 차이, multi graph의 matrix는 연결된 간선의 수를 적어준다


Signed graph
--각 노드간에 Negative , positive 가 있는데 친근/적대적 관계, social power status (양수=강함, 음수=약함 )등으로 표현가능