728x90 반응형 network3 [CS224w] Subgraphs and Motifs Subgraphs and MofitsIntroduction and Motivationsubgraph는 network의 block과도 같다. subgraph는 network의 특징이나 구별하는데 매우 도움이 된다.특히 많은 도메인에서 반복되는 구조는 그래프에서 어떤 기능이나 행동(function or behavior)을 결정짓는다.Definition: Subgraph주어진 그래프 $G=(V, E)$에 대하여 2가지 방법으로 subgraph $G'=(V', E')$ 를 정의할 수 있다.Def 1. Node-induced subgraph $V' \subset V$$E' = \{ (u,v) \in E \ | \ u, v \in V' \}$$G'$ is the subgraph of $G$ induced by $V.. 2023. 11. 28. [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. 이전 1 다음 728x90 반응형
