[Graph] 12/25 간단하게 알아보는 Graph 1

1. Graph 란 무엇인가?

1.1. Graph의 정의

$G$라고 표현하며, 구성요소는 일반적으로 $V$(Vertex), $E$(edge)로 구성된다.

이때 vertex를 node라고 하기도 한다. [여기서는 node로 통일한다.]

따라서  $G(V,E)$ 으로 나타낸다. 

Graph 이미지

 

1.2. Node, Edge, Adjacency matrix, Degree matrix, Laplacian matrix

1.2.1 Node와 Edge

Node란 객체의 정보를 나타낸다. 이때 정보를 node features 또는 node attributes라고 한다. 

Edge란 node 간의 연결을 의미한다.

 

간단한 예시로 Social Network Serive(SNS)가 있다.

사람들 하나하나를 Node라고 하면, features의 경우 해당 사람의 정보(키,나이,이름,..), Edge를 사람들 간의 follow로 나타낼 수 있다.

SNS 예시

 

1.2.2. Adjacency matrix $A$

connection matrix라고 불리기도 하며, 기호는 $A$라고 표현한다.

이름만 봐도 알 수 있듯이 node간의 연결을 나타내는 edge를 한눈에 볼 수 있도록 하는 matrix이다.

• 행(columns)은 node를 의미한다.
• 열(row)는 node의 연결 여부를 0 또는 1로 표현한다.

아래는 예시 그림이다.

 

adjacency matrix의 특징은 정방행렬(square matrix)이라는 것이다.

이는 모든 node의 연결을 표기해야 하므로 당연한 특징이다.

또한 후에 배울 Undirected graph의 $A$는 대칭행렬(symmetric matrix)이라는 특징이 있다.

 

1.2.3. Degree matrix $D$

Graph에서 node의 특징을 나타내는 것은 node features가 있지만, 어떤 node가 중요한지는 모른다는 점이 있다.

다시 말해서 어떤 node의 상대적 크기를 모른다.

 

그렇다면 어떻게 해야 node의 중요도를 계산할 수 있을까?

간단하게 node에 연결된 edge수를 셈(count)하는 것을 크기(degree)라고 나타낼 수 있다. 

$deg$의 경우 임의의 node $i$에서 edge가 끝나는 개수를 셈 한 것이다. 즉, node $i$에 edge가 몇 개 있는지 셈한 것

 

참고로 방금 알아본 degree matrix는 undirected matrix에서 사용되는 방법이다.

directed matrix에서 사용되는 방법은 indegree와 outdegree의 조합이다.

• indegree($deg^-$): node $i$가 수신받은 edge 수
• outdegree($deg^+$): node $i$가 송출한 edge 수 

후에도 언급되지만, undirected graph는 directed graph의 특수한 경우이므로,아래와 같다.

degree, indegree, outdegree 특징은 대각행렬(diagonal matrix) 이라는 것.

 

1.2.4. Laplacian matrix $L$

앞서서 adjacency matrix와 degree matrix에 대해서 알아보았다. 그러나 이들을 비교하면서 graph를 표현하기란 비효율적이다. 따라서 이를 해결하기 위해 "한 번에 표현한 것"이 바로 Laplacian matrix이다.

 

사용 조건은 많이 까다롭다. 사용되는 graph는 아래의 조건을 만족해야 한다.

• undirected graph
• unweigthed graph
• without loops or multiple edges

조건은 까다롭지만 연산은 간단하다.

$L=D-A$

이때 D는 degree matrix, A는 adjacency matrix이다.

그렇다면 조건이 왜 이렇게 까다로울까? 이는 위에서 언급하였듯이 한 번에 표현하기 위해서 이다.

만약 graph에 loops가 있거나 directed graph인 경우 Laplacian matrix를 한번에 보기 어려울 것이다.

 

특징으로 smoothness가 있다. 

간단하게 설명하면, Laplacian matrix을 사용하면, node $i$가 neighbor nodes와 얼마나 차이가 나는지 알 수 있다는 것

자세한 설명은 링크 참고

 

1.2.5. 기타

Laplacian matrix를 normalizing 한 matrix를 소개한다. 이러한 matrix를 다음과 같이 부른다.

symmetric normalized Laplacian matrix $L^{sym}$

이를 통해서 degree의 영향을 줄이고 graph의 구조를 비교하기 쉽게 만들어 준다.

즉, node의 중요성이 상대적으로 동등해지고 서로 다른 그래프 간의 유사성을 쉽게 파악할 수 있게 한다.

참고로 element는 다음과 같다.

 

1.3. Graph의 종류

Graph에는 다양한 종류가 있다. 

• Undirected graph
• Directed graph

이외에도 다양한 Graph가 있지만 기본적인 두 가지를 알아본다.

 

1.3.1. Undirected graph

node를 연결하는 edge 간에 방향이 없음을 의미한다.

즉, node 간에 일방적인 연결이 아닌 상호 연결을 의미한다.

node $i$가 노드 $j$에 연결, node $j$가 node $i$에 연결

 

1.3.2. Directed graph

Undirected graph와는 다르게 Directed graph의 경우 방향이 존재하며, 이로 인해서 다양한 종류가 있다.

즉, node 간의 일방적인 연결성이라는 특성으로 인해 다양한 Directed graph가 존재한다.

node $i$가 노드 $j$에 연결(or node $j$가 node $i$에 연결 )

Directed graph의 종류로 simple directed graph, complete graph, oriented graph가 있다.

 

1.3.2.1. simple directed graph

• multiple edges: 2개 이상의 edge가 동일한 node 2개에 연결되어 있는 것

• loops: edge의 연결이 자기 자신을 연결하는 것

 

이러한 multiple edges와 loops가 없는 것을 simple directed graph라고 한다.

loops가 없기 때문에 adjacency matrix의 대각값들은 모두 0이다.

 

1.3.2.2. complete graph

각 edge가 bidirected(양방향)인 것을 의미한다. 즉, undirected graph를 의미한다.

이를 통해서 undirected graph는 directed graph의 특수한 경우라고 볼 수 있다.

 

1.3.2.3. oriented graph

edge연결에 대칭성이 없는 graph를 의미한다. 

특히 complete oriented graph를 토너먼트(tournament)라고 한다.

Tournament(좌), oriented graph (우)

 

다음 글은 weighted graph에 대해서 알아보도록 한다.

 

참고자료

[1] https://en.wikipedia.org/wiki/Complete_graph

[2] https://mathworld.wolfram.com/DirectedGraph.html

[3] https://mathworld.wolfram.com/OrientedGraph.html

[4] https://mathworld.wolfram.com/Graph.html

[5] https://mathworld.wolfram.com/AdjacencyMatrix.html

[6] https://junklee.tistory.com/112

[7] https://en.wikipedia.org/wiki/Laplacian_matrix