본문 바로가기
728x90
반응형

CS224W26

[Community Detection] Girvan-Newman (GN) Algorithm Girvan-Newman: Divisive hierarchical clustering based on edge betweennessCommunity Detection우리는 그래프(네트워크)를 여러개의 모듈, 클러스터, 커뮤니티의 집합체로 생각한다.graph를 partitioning하여 micro-market을 찾을 수 있다. 소셜네트워크에서는 서로 겹치는(overlapping) social circle 혹은 circles of trust를 찾을 수 있다. 여기서는 undirected & unweighted network에서의 community detection에 알아보자. Edge betweenness해당 edge를 통과하는 최단거리의 개수 (Number of shortest paths passing t.. 2023. 11. 14.
[CS224w, 2018] Network Properties and Real World Key properties주로 4가지 성질에 대해서 알아보자. degree distribution($P(k)$), path length($h$), clustering coefficient($C$), connected components($s$)에 대해 살펴보자. 1. Degree distribution노드 차수(degree)의 분포를 $P(k)$로 부른다. 이때 $k$는 degree를 의미한다. 전체 노드 개수를 $N$, 노드 차수가 $k$인 노드의 개수를 $N_k$라 하면 $P(k) = \cfrac{N_k}{N}$ 이다.2. Paths in a graphpath는 노드의 수열(sequence of nodes)을 나타낸다. 이때 차례로 나타나는 노드는 이전 노드와 연결되어있어야 한다.path는 self .. 2023. 10. 22.
[CS224w, 2018] Network Representation Directed & Undirected 위 그림의 왼쪽 빨간색 그래프는 무방향 그래프(undirected graph)이다. link는 symmetric, reciprocal 하다는 특징이 있다. 예를 들어 친구관계(서로 친구관계), 또는 협업(collaboration, 방향성이 없음)을 표현할 때 사용될 수 있다. 오른쪽 그림의 녹색 그래프는 방향 그래프(directed graph)이다. link는 종종 arc라고도 불린다. phone call이다 SNS에서의 follow 등을 표현할 수 있다. Node degrees (노드 차수)일반적으로 노드의 이웃하는 edge의 개수를 의미하고, $k$를 이용하여 표기한다.Undirected Graph노드 $i$의 이웃하는 edge의 개수를 $k_i$라 한다. 아래.. 2023. 10. 17.
[CS224w, 2018] Network Centrality Motivation social network가 주어졌을 때, 어떤 node가 더 중요 (more important, influential) 할까? 이때 centrality measure는 node 중요도를 설명해줄 수 있다. Centrality measure로 Geometric measure, Spectral measure, Path-based measure, Subgraph-based measure가 있다. Geometric Measures In-degree Centrality \[ c_{\text{deg}}(x) = d_{in}(x) \] distance가 $1$인 node의 개수이다. 또한 majority voting과 동일하다. Closeness Centrality 더 central한 node일.. 2023. 10. 16.
[CS224w] Relational GCN (RGCN) Extending GCN to handle heterogeneous grphas그림과 같이 relation은 하나인 directed graph에 대하여 GCN을 적용해보자. 그렇다면 edge의 방향에 따라 message passing이 이루어지도록 설계하면 될 것이다. 그렇다면 다양한 relation type이 존재한다면 어떻게 message passing을 할 것인가?어쩔 수 없이 relation 마다 학습하는 weight가 다르게 설계를 한다.(cs224w 강의자료에서는 보기 쉽게 같은 색으로 구분하였다)즉, 각각의 relation type마다 다른 신경망을 적용하여 convlution을 구현할 수 있다.Introduce a set of neural networks for each relation t.. 2023. 8. 9.
[CS224w] Motivation of Heterogeneous Graphs Motivation지금까지 살펴본 GCN, GraphSAGE, GAT, GIN 모두 노드의 성질(property)이 같은 그래프이다.node feature가 차원이 커도 모든 노드들의 차원이 같기 때문이다. 그러나 실제 그래프 데이터 구조에서 노트 성질, 엣지 성질 등이 다양하기 때문에 앞에서 살펴본 homogeneouse graph로는 충분하지 않다. 노드의 성질이 2개인 경우예: Paper node, Author node엣지의 성질이 다양한 경우예: Cite, Link하나의 그래프 내에서, 노드와 엣지의 성질이 모두 다양한 경우도 가능하다2개의 노드와 2개의 엣지가 있다면, 2*2*2=8가지 가능한 relation이 존재한다.보다시피 relation type은 (node_start, edge, nod.. 2023. 8. 8.
728x90
반응형

티스토리툴바