Itnto

머신러닝 관점에서 그래프는 3개지 task를 수행할수있다. 3가지 task를 위해 Feature engineering을 수행하는데 각 level단계에서 수행하는 방법들을 알아보자.

1.Node Feature

▪ Node degree ▪ Node centrality ▪ Clustering coefficient ▪ Graphlets

1.1 Node degree

각 노드의 특징을 edge의 개수로 취급한다. 노드의 edge의 개수로만 평가하니 주변 이웃노드들이 달라져도 반영이 되지않는다.

1.2 Node centrality

1.2(1) Eigenvector centrality

주변노드의 중요도를 고려해서 자신의 중요도를 계산한다. 주변 이웃 노드가 많다고해서 중요도가 높은것이아니라 중요도가 높은 노드가 자신의 이웃인것이 중요하다는 것이다.

사진에서 power iteration 방법으로 수렴하는 값으로 고유벡터를 구할수있다. n by n 행렬 n개의 고유값중에서 가장 큰 고유값을 선택하여 그 고유벡터에서 제일 큰값에 해당되는 노드가 중요도가 가장 높다.

1.2(2) Betweenness centrality

각 노드쌍마다 최단경로를 계산했을때 그 사이에 우리가 알아보고자하는 노드를 거쳐가는지 개수를 통해 centrality를 파악한다.

1.2(3) Closeness centrality

기준노드와 다른 노드들사이에 최단거리의 합을 통해 중심성을 알아볼수있다.

1.3 Clustering coefficient

기준 노드의 주변 이웃노드들이 얼마나 밀집하게 뭉쳐있느냐를 평가 척도로 한다. 주변노드끼리의 edge개수/주변노드 완전연결

1.4 Graphlets

그래프릿을 활용해서 기준노드를 그래프릿에 root노드로 비교하면서 벡터화한다.

2.Link Feature

링크는 각 그래프의 각 시점에서의 edge로 보며 각 시간대에서 노드쌍간의 연결성을 평가하여 다음 시점에서 반영한다. 노드쌍간의 연결성을 평가하는 지표로써는 다음과 같은 방법이 있다.

2.1 Distance based feature

두 노드의 최단거리를 활용하는 방법 이 방법은 B-H 와 D-F는 동일한 점수를 갖지만 B-H가 연결성이 좀더 좋은 점을 반영하지 못한다.

2.2 Local neighborhood overlap

두 노드사이의 이웃노드를 활용한 방법이다. Adamic-Adar index 방법같은경우 공통된 이웃노드의 edge의 개수가 작을수로 좀더 정보력을 가진다.

2.2 Global neighborhood overlap

로컬적인 방법으로는 노드A와 노드E의 연결성을 설명이 불가능하다. 하지만 두노드는 한 노드만 거쳐가면 연결이되는데 이런한 부분을 설명하기 위해 Katz index방법을 사용한다. 베타는 멀리있는 long-path의 중요도를 낮춰주는 파라미터이다.

3.Graph Feature

그래프의 유사성을 파악하기위해 위해 우리는 커널을 사용할것이다. 파이는 커널의 사용수단에따라 달라진다.

3.1 Bag of node

노드의 개수만을 사용한 방법

3.2 Bag of node degree

차수를 활용해서 벡터를 만들어서 사용하는 방법

3.3 Graphlets

그래프릿을 활용하여 그래프 전체적인 구조를 파악한다음 벡터화한다. 두개의 벡터를 내적하여 유사성을 확인하는데 노드의 개수가 달라지면 값이 왜곡되어 정규화를 통해 해결한다.

글을 쓰게된 이유

수정 해야 할 부분

0f643c661da0956fc45cbd3edd74eba2abf588ed