ok-lab

Contents 네트워크에는 밀집(Density), 차수(Degree), 길이(Length) 등 다양한 지표가 존재하며, 이를 측정하기 위한 방법도 다양하게 존재한다. 본 글에서는 이를 측정하는 방법에 대해서 알아본다. Density Density는 그래프의 밀집 정도를 의미한다. 예를 들어, 완전 연결 그래프의 경우 Density는 1이 될 것이다. 완전 연결 그래프는 Complete Graph 혹은 Clique로 부르기도 한다. 이때 평균 차수는 다음과 같이 계산할 수 있다. \[ m = \begin{pmatrix} n \\ 2 \end{pmatrix} = \frac{n (n-1)}{2} \] \[ \left \langle k \right \rangle = \frac{2m}{n} = \frac{n(n..

Contents Walk, Trail 등 다양한 구조를 가진 그래프가 존재한다. 본 글에서는 각 그래프에 해당하는 이름에 대해서 살펴보고 해당 그래프의 특징을 알아보고자 한다. 먼저 Walk를 다루기 이전에 그래프에서의 Length가 어떤 것인지 알아보자. Length Length는 그래프의 길이를 의미한다. 노드의 개수가 아닌 엣지들이 지나가는 길의 수를 의미하는 것이며, 이를 Hop이라고 한다. $V_5$에서 $V_1$까지는 총 2-hop을 나타내고, $V_5$에서 $V_3$까지는 3-hop을 나타낸다. 그렇다면 Hop의 수는 어떻게 구할 수 있을까? Walk 보행(Walk)은 복잡하게 보이지만, 그래프의 노드를 통과하는 하나의 스텝(step)일 뿐이다. Walk는 움직일 때 거치는 엣지의 수를 의미..

Contents 노드를 임베딩(Embedding)하는 이유는 노드의 정보를 vector로 표현할 수 있다면 Classification, Cluster 등 다양한 기법을 사용할 수 있는 것 뿐만 아니라 Node Classification, Community Detection 등에도 활용이 가능하다. 그렇다면 어떻게 노드를 벡터로 변환할 수 있을까? 이에 대한 내용은 Leskobec 교수님의 Node2Vec을 살펴보거나 DeepWalk를 보면 자세히 알 수 있으며 본 강의에서는 Random Walk, Node2Vec 이전에 제안된 노드 임베딩 기법의 개략적인 내용에 대해서만 다룬다. Random Walk, Node2Vec 등의 모델은 여기를 참고하면 된다. 그래프에서의 노드 간의 유사도를 최대한 보존하면서 ..

Contents Community 군집이란 Cluster 혹은 Community를 의미하며, 집합에 속하는 노드 사이에는 만은 엣지가 존재하고, 집합에 속하는 노드와 그렇지 않은 노드 사이에는 적은 수의 엣지가 존재해야 한다. 아래의 그림을 예로 들면, 11개의 군집이 있는 것을 확인할 수 있다. 온라인 소셜 네트워크에서도 군집을 찾아볼 수 있다. 이때는 사회적 무리(Social Circle)를 의미하는 경우가 많다. 예를 들어, 같은 회사 동료라는 사회적 무리와 가족 관계 혹은 고등학교 친구 등과 같은 사회적 무리를 의미한다. 이때의 사회적 무리는 회사 동료, 가족 관계, 고등학교 친구 뿐만 아니라 같은 지도 교수님한테 지도받은 학생들, 대학 동기 등 다양한 사회적 무리를 나타낼 수 있다. 온라인 소셜..

Contents 그래프를 통한 influence는 정보 혹은 행동, 고장, 질병 등 다양한 influence가 존재할 수 있다. 예를 들어, 온라인 소셜 네트워크를 통해 다양한 정보를 전파할 수 있다. 컴퓨터 네트워크에서는 일부 장비의 고장이 전파되어 전체 네트워크를 마비시킬 수도 있다. 최근에 이슈가 된 코로나-19라는 질병이 사회라는 거대한 소셜 네트워크를 통해 전파되는 것도 언급할 수 있다. 이처럼 다양한 influence를 그래프로 표현할 수 있을 것이다. 이와 같은 전파 과정을 체계적으로 이해하고 대처하기 위해서는 그래프의 구조를 제대로 이해하고 있어야 한다. 본 글에서는 Cascade model 중 두 가지 모형을 다룬다. 첫 번째 모형은, 의사결정 기반의 Cascade model이다. 먼저 ..

본 글에서는 DGL 을 통한 Link Prediction을 GraphSAGE를 통해 진행한다. Link Prediction은 두 노드가 연결되어 있는지, 아닌지를 확인하는 문제로 이해할 수 있다. 패키지 불러오기 본 글에서는 DGL 과 PyTorch 그리고 인접행렬을 만들거나 연산을 진행하기 위한 numpy와 scipy를 사용한다. import dgl import dgl.function as fn import torch import torch.nn as nn import torch.optim as optim import torch.nn.functional as F import itertools import numpy as np import scipy.sparse as sp from sklearn.metr..

Contents 본 글에서는 DGL 패키지를 이용해서 그래프를 생성하는 방법에 대해서 다룬다. DGL 패키지는 그래프를 다루기 위한 패키지로 그래프를 생성하거나 기존 연구에서 제안된 함수(GCN, GraphSAGE 등)를 호출을 통해 편리하게 사용하도록 도와주는 패키지다. 패키지 불러오기 import dgl import torch 기본적으로 dgl은 PyTorch와 함께 사용한다. tensorflow도 사용하는 것이 가능하지만 본 글에서는 PyTorch를 이용한 dgl을 다루어 볼 것이다. 필요한 함수는 dgl이며 pip install을 통해 설치하면 된다. 그래프 생성하기 dgl에서 그래프를 생성하는 것은 매우 간단하다. dgl 내에 내장된 graph 함수를 사용하면 바로 만들 수 있다. g = dgl..

Contents Graph Convolution Neural Network(GCN)는 2017년에 처음으로 제안된 모델이다[논문]. 우수한 성능을 보이고 있으며, GNN에 CNN을 접목하기 시작한 계기가 된다. 본 글에서는 이론적인 내용은 자세히 다루지 않고, DGL을 사용해서 GCN을 만들어볼 것이다. GCN에 대한 상세한 내용은 여기를 참고하면 된다. 1. Load Package GCN을 사용하기 위해서는 Pytorch, torch_geometric, Tensorflow, PyG 등 다양한 프레임워크들이 존재하지만 본 글에서는 가장 간단한 DGL을 이용해서 GCN을 구현한다. 구현하기에 앞서 먼저 필요한 패키지들을 호출하자. import numpy as np import dgl from dgl.nn ..

Contents Fourier Transform을 사용하는 이유를 다루기에 앞서 기본적인 선행 지식이 요구되기에 Laplacian이 무엇인지 부터 짚고 넘어가자. Laplacian operator는 기울기를 확인하기 위한 연산자 정도로만 이해하면 된다. 그래프는 euclidean space에서 정의할 수 없기 때문에 mainfold 구조에서의 Graph signal을 통해 신호를 확인하려고 하는 것이다. 이때 Graph signal은 node가 가지고 있는 feature를 의미한다. 예를 들어, social network의 경우에는 해시태그의 수가 될 수 있고, 연령 등의 정보가 될 수 있다. Euclidean space에 있는 다양체를 리만 다양체에서 정의된 함수로 일반화 하는 과정을 Laplace B..

Contents Centrality concepts Centrality concepts는 그래프에서 어떤 노드가 얼마나 중요한지 측정하는 것이다. 중심성의 개념은 여러 가지 방법으로 측정할 수 있으며, 중심성을 측정하는 척도의 종류는 다음과 같다. 연결 중심성(Degree Centrality) 고유벡터 중심성(Eigenvector Centrality) 카츠 중심성(Katz Centrality) 페이지랭크(PageRank) 매개 중심성(Betweeness Centrality) 근접 중심성(Closeness Centrality) 연결 중심성, 고유벡터 중심성, 카츠 중심성, 페이지랭크 중심성과 같은 경우는 연결성을 바탕으로 중심성을 측정하는 방법이고, 매개 중심성, 근접 중심성과 같은 경우는 위상학적 관점으..