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. 실제 그래프(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..
서로소 집합 알고리즘(disjoint set) 그래프 내에서 여러개의 node가 존재할 때 2개의 node를 선택해서 이 node가 서로 같은 node에 속하는지 판별하는 알고리즘 예를 들어 다음과 같이 8개의 node가 존재한다면 이런 경우는 부모 node가 자기 자신인 경우이다 이제 1과 2가 연결되었다고 생각해보자 이런 경우 2의 부모 node는 1이 된다 이렇게 합쳐나가는 과정을 union알고리즘이라고 부른다 이번엔 2와 3도 연결되었다고 가정해본다면 그러면 3의 부모 node는 2가 되는데 3과 1이 연결되었다는 것은 어떻게 아는가? 3의 부모 node는 2이고 2의 부모 node는 1이라서 부모 node만 보고서는 판단할 수가 없다 그렇지만 재귀함수를 사용하면 3의 부모 node가 2를 가리키..
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. 문제 https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return하도록 solution ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
