반응형 Graph Mining12 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. Network Properties ## Graph Network 속성들 Degree Distribution : P(k) Path Length : h Clustering coefficient : C Connected Component : s ## Degree Distribution Degree의 개수의 분포를 나타냄 $$ P(k) = N_{k} / N $$ N = 총 degree의 개수, N_k = k번째 노드의 degree ## Path Length A 노드에서 B 노드로 가기 위해 거쳐야 할 노드(or 엣지)들 A -> G로 가기 위해 ACBDCDEG 방법 등 여러가지 방법이 있음 여기서 파생되는 개념은 shortest path length(=distance) 크루스칼 알고리즘 처럼 가장 짧은 루트를 선택 여기서 Undirected와 .. 2021. 12. 6. Graph Mining 기초 본 글은 인천대학교 최대진 교수님의 강의에 기반하여 작성하였습니다 ## Graph Mining Large-Scale의 데이터를 다룰 때 통계치를 기반으로는 한계가 있다. 이를 극복하기 위해 그래프를 이용하여 유의미한 결과를 추출하는 것을 말한다. 대표적인 예시 : Edge가 가장 모여있는 Community를 찾는 것, 페이스북 사람들의 연결관계, 추천시스템 ## Graph Graph G = (V,E,W)로 이뤄져 있다. 여기서 대문자 V,E,W는 모두 집합의 형태이다. - V = Vertex set (node 집합) - E = Edge set - W = Weight set Graph Data structure : 엔티티 간의 관계, p2p network(path2path network) ## Graph .. 2021. 12. 6. 이전 1 2 다음 반응형
