K-Core & Katz index

KAIST AI 대학원 신기정 교수님의 수업인 데이터마이닝 및 소셜 네트워크 분석 수업 필기입니다.

 

K-Core

 

Idea : nodes with degree less than k are removed until all remaining nodes in the network have at least k degree

         (k보다 작은 차수를 가진 노드는 네트워크의 모든 나머지 노드가 최소한 k 차수를 가질 때까지 제거)

k-core : subgraph where all nodes have 2 degree of at leat k

          (모든 노드가 최소 k의 2차수를 갖는 부분 그래프)

node coreness : a measure that quantifies the participation of a node to the network core

 

step 1

왼: 초기 Graph, 중: 초기 Graph에서 dgree 1 node 색칠, 오: 파랑 node의 edge 제거 dgree가 1인 node가 하나 더 생김

• remove all nodes with degree 1(degree가 1인 node 제거)
• recalculate degree of remaining nodes and only nodes \(v\) with \(d(v) > 1\) are retained to define 2-Core of the graph

step 2

왼: k개의 이하의 node를 제거하면서 반복, 오: 최종적인 K-Core

• ndoes \(v\) with \(d(v) \leq 2\) are removed to define the 3-Core

** at each step, if removal of a node and its edges causes the degree of one of its neighbors to drop below k, then that neighbor is also removed from the graph

(각 단계에서 노드와 그 간선을 제거하면 이웃 중 하나의 차수가 k 아래로 떨어지면 해당 이웃도 그래프에서 제거됩니다.)

 

K-Core 참조: https://youtu.be/ZI5VUkUAcwg

Katz Index

Idea : Measures influence by  taking into account the total number of walks between a pair of nodes

- /(\alpha\) : Attenuation factor in range [0, 1/\(\lamda\)] where \(\lamda\) is the largest eigenvalue of A

 

두 node 사이의 Number of walks of length k는 Adjacency Matrix를 k만큼 제곱하면 node i, j 사이의 length k만큼의 Number of walks를 알 수 있습니다!

 

Compute using Power Iteration

Katz index를 쉽게 계산하는 법은 아래와 같습니다. 조금 더 이해하기 위해서는 아래 youtube link를 참조하면 이해하기 쉽습니다.

Katz index 계산: https://www.youtube.com/watch?v=jeq0EGglGUM