1. degree 어떤 node V의 degree란 V에 연결된 link의 수 혹은 V의 neighbor의 수와 같다. 그래서 V의 degree를 $d(V)=\left | N(V) \right | $로 표기 1은 2,5와 연결되어 있어서 1의 연결성은 2이다. 2. direction graph 방향성이 있는 그래프의 경우 나가는 연결성(out degree)와 들어오는 연결성(in degree)을 구분한다. 당연하겠지만 나가는 연결성(out degree)는 특정 node V에서 나가는 방향과 연결된 node의 수이고 $d_{out}(V)=\left | N_{out}(V) \right | $으로 표기 들어오는 연결성(in degree)는 특정 노드 V에 들어오는 방향으로 연결된 node의 수이고 $d_{in..
1. 연결 중심성(degree centrality) 한 node에 연결된 모든 edge의 개수 weighted 그래프의 경우 모든 weight의 합 directed 그래프의 경우 incoming degree는 그 node의 인기도, outcoming degree의 경우 그 node의 영향력 등으로 해석이 다를 수 있다. 2. eigenvector centrality(고유벡터, 위세 중심성) 연결 중심성이 오직 연결된 edge에만 의존한다는 점에서 아쉬워서 다른 node들간의 연관성도 보고 싶다는 것 그래프의 인접행렬 A와 node의 eigenvector centrality를 나타내는 벡터 $C_{e}$에 대하여 $\lambda C_{e} = AC_{e}$ 를 만족시키는 $C_{e}$ $C_{e}$는 A의..
1. path 두 node u와 v사이 path란 다음 두 조건을 모두 만족하는 순열이다. u에서 시작해서 v로 끝난다. 부분순열에서 연속된 두 node는 link되어 있다. 왕복하는 1,4,3,4,6,8도 1에서 8까지 path인데 1에서 시작해서 8로 끝나고 어느 두 연속된 node도 link되어 있어서 그렇다. 5에서 6은 끊어져있으니 1,3,4,5,6,8은 path가 아니다. 2. the length of path 해당 path에 존재하는 모든 link의 길이를 말한다. 1,4,6,8에는 3개의 link가 존재하므로 길이는 3 물론 link 1개의 길이가 1일때 그렇다 3. distance 두 node u와 v사이 distance는 모든 path중 최단경로의 길이 u와 v사이 모든 path를 구해..
1. 실제 그래프(real graph) 실제 그래프(real graph)는 실제 존재하는 complex system으로부터 데이터를 얻어 표현한 그래프 MSN은 옛날에 microsoft에서 서비스하던건데 지금은 안한다고 한다 실제 그래프는 어떻게 이해해야할까? 잘 이해하기위한 비교대상이 필요하다. 그것이 바로 random graph 2. 랜덤 그래프(random graph) In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random pro..
1. 그래프의 수학적인 표현 그래프는 “정점 집합과 간선 집합으로 이루어진 수학적 구조”라고 정의했으므로 정점의 집합을 V, 간선의 집합을 E라 하여 G=(V,E)로 표기 2. Neighbor 어떤 node의 neighbor은 그 node와 직접적으로 연결된 모든 node의 집합 V의 neighbor을 N(V)로 표기 자기 자신은 Neighbor라고 하진 않아 3. directed graph directed graph에서는 나가는 neighbor와 들어오는 neighbor을 구분한다. 어떤 node V에서 link가 나가는 방향으로 연결된 node는 V의 outcoming neighbor라 하고 $N_{out}(V)$로 표기 link가 node V로 들어오는 방향으로 연결된 node는 V의 incomin..
1. directed graph link에 방향성이 없고 두 node가 대등한 관계를 가질 수 있는 경우 undirected graph link에 방향성이 있어서 두 node의 주체와 대상의 관계가 확실하고 의미있는 경우 directed graph 페이스북 친구는 서로 친구가 되어있어야 가능하므로 대등한 관계를 가져서 방향이 없는 그래프 인용 그래프의 경우 논문을 누가 인용했는지, 인용의 대상이 무엇인지 분명하므로 방향성이 있는 그래프 트위터 팔로우 그래프는 내가 태연을 트위터 팔로우 하더라도 태연은 나를 팔로우 하지 않잖아 두 node사이에서 양쪽 방향으로 관계를 맺을 수도 있다. 물론 오른쪽 표기를 굳이 쓰진 않는다 사실 어느정도 주관적인 개념이다. 왜냐하면 주체와 대상의 관계가 있음에도 큰 의미가 ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
