반응형 graph5 Centrality ## Centrality graph에서 중앙 역할을 하는 node(= 중요한 역할을 함) 그럼 중앙 역할의 의미가 무엇일까? 이는 중앙 역할의 정의에 따라 달라진다. 이러한 Centrality의 종류는 4가지가 있다. Degree Centrality : 많은 degree를 가진 노드가 중요할 것 Closeness centrality : 관계 중요도(weight) 기반 Betweennewss Centrality : Dense와 Dense를 연결해주는 subnetwork 노드 Eigenvector Centrality : 큰 네트워트를 연결 ## Degree Centrality 많은 degree를 가진 노드가 가장 중요할 것이다라는 생각에서 파생된 개념 Degree Centrality는 다음과 같이 계산된다 .. 2021. 12. 8. 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. 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. 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 다음 반응형
