반응형 분류 전체보기359 Structure Role in Network ## Role role이란 다른 말로 function(기능)이다. 직관적인 예로 먹이 사슬에서 각각의 종들의 역할을 생각하면 된다. 또 다른 예로는 회사에서 회장이 맡은 임무, 부장이 맡은 임무, 인턴이 맡은 임무 등을 생각하면 된다. 대표적인 Role의 종류는 다음 3가지와 같다. - Hub : Center of stars - community : members of cliques(= edge들을 많이 포함하고 있는 노드들의 집단에서의 노드) - outlier : 떨어진 애들 여기서 community는 직관적으로도 알 수 있겠지만 dense하게 밀집되어있다. ## Role vs Group Role과 Group의 공통점은 노드들의 집합이라는 점이다. 하지만 role은 구조적으로 비슷한 위치에 있는 노드들.. 2021. 12. 7. Extract Subgraph Enumeration(ESU) Motif와 graphlets을 찾기 위해선 두가지 문제를 해결해야한다 1. Enumerating : k-size의 subgraph를 만드는 것 2. Counting : subgraph를 세는 것 하지만 이러한 것을 푸는 과정에서 NP-Problem에 맞닥뜨린다. NP-Problem은 비결정론적 문제로 한마디로 푸는데 너무 오래 걸린다는 단점이 있다. 따라서 이러한 문제를 맞닥뜨리지 않기 위해선 notif 사이즈가 작아야한다. ## Extract Subgraph Enumeration(ESU) 이를 설명하기 전에 기본 개념을 잡고 가자 \( V_{subgraph} \) : 현재까지 찾아진 subgraph의 집합 \( V_{extraction} \) : 구조화된 subgraph에서 생성할 수 있는 후보집합 .. 2021. 12. 7. Graphlets ## Graphlets graphlets은 subgraph와 비슷한 개념이다. non-isomorphic subgraph이다.(모양에 초점). subgraph는 하나하나의 그래프를 본것이지만 graphlets은 subgraph의 집합이라고 생각하면 된다. graphlets은 노드에 숫자가 써져있다. 이 말은 node의 관점에서 역할을 나눈다는 것이고 node의 역할 하나하나에 초점을 맞춘 것이다. 반면에 motif는 building block 관점에서 정의한 거시적인 개념이 크다.(구조 중심) graphlets과 motif는 모두 해당 그래프가 어떤 local structure를 기반으로 구성되어 있는지 판단할 수 있다는 것이다. ## Graph Degree Vector(GDV) 이는 노드 역할에 대한 .. 2021. 12. 7. Subnetwork, subgraph, motif ## Subnetwork 그래프를 이루는 특정 노드 집합(edge)의 집합 = building block ## Subgraph 노드의 번호는 상관하지 않고 edge의 방향 구조만 상관 있음. 즉, 모양만 고려한다. 이를 non-isomorphoic 하다라고 한다. 노드가 3개 있을 때 나올 수 있는 subgraph는 다음과 같이 13개가 있다. 위 그림과 같은 13가지의 subgraph가 얼마나 있는지 세는 것이 다음에 다룰 motif 분석의 핵심이다. 그러면 이러한 subgraph의 개수를 통해 어떤 지표를 나타낼 수 있을까? 이 지표는 significance 라고 한다. 예시를 들어 significance에 대해 설명하겠다. 내가 만든 그래프에 #1 번 모양의 subgraph의 개수가 10개가 있다고.. 2021. 12. 7. Small World 2021.12.06 - [Graph Mining] - Random Graph Random Graph ## Random Graph Random Graph는 그래프를 실제 세계와 비슷하게 생성을 하고, 이를 통해 내가 분석한 graph와 비교하기 위해서 생성을 한다. 즉, 평가지표를 위한 하나의 수단이다. 기존의 그래프 생성 방 bigdata-analyst.tistory.com 앞서 Random하게 생성한 G_np는 실제 세계와 틀리다는 점을 알아봤다. 따라서 실제 세계와 비슷한 random graph를 생성하기 위해 다른 방법을 찾아본다 ## Edge Locality G_np를 사용했을 때 clustering coefficient가 낮은 이유는 local structure를 고려하지 못함이라고 설명을 하였.. 2021. 12. 6. Random Graph ## Random Graph Random Graph는 그래프를 실제 세계와 비슷하게 생성을 하고, 이를 통해 내가 분석한 graph와 비교하기 위해서 생성을 한다. 즉, 평가지표를 위한 하나의 수단이다. 기존의 그래프 생성 방식에는 두가지가 있다 1. \( G_{nm} \) : n개의 노드와 m개의 edge가 있을 때 랜덤 그래프 생성. 이 때, uniform한 확률로 edge 를 뽑아내는 방식 2. \( G_{np} \) : 확률 p를 이용하여 원래의 edge 개수와 동일하게 선택하는 방식 예를 들어 위 그림과 같은 graph가 있다고 가정하자. 여기서 node는 4개 ,edge는 2개이다. 이러한 그래프에서 이 값을 갖고 fully connected된 그래프를 생각한다. 그리고 fully connec.. 2021. 12. 6. 이전 1 ··· 7 8 9 10 11 12 13 ··· 60 다음 반응형
