반응형 Graph Mining12 Lovain Algorithm ## Lovain Algorithm 앞서 설명한 Newman Method(2021.12.08 - [Graph Mining] - Newman Method ) 는 computing power가 많이 드는 문제점이 있었다. 반면에 Lovain Algoritm은 빠른 community detection 방법이다. 이는 greedy algorithm 기반으로 O(nlogn)의 시간 복잡도를 갖고 있다. 또한 Lovain Algorithm은 weighted graph와 hierarchial community에 모두 동작한다. 동작과정은 간단하게 보면 다음과 같다. modularity optimization -> community aggreation -> 1st pass -> 2nd pass ## 동작과정 1단계 처.. 2021. 12. 8. Newman Method ## Newman Method Newman Method는 Edge Betweenness를 이용한 communities detection method 이다. 여기서 edge betweenness는 betweenness centrality(2021.12.08 - [Graph Mining] - Centrality)의 edge 버전이라고 생각하면 된다. 즉, 두 community를 연결해주는 weak edge가 betweenness centrality가 가장 높다. Newman Method는 undirected, unweighted network에서만 동작한다. 이 method의 진행과정은 다음과 같다. 모든 edge에 대해서 edge betweenness를 계산 가장 값이 높은 것을 제거 connected c.. 2021. 12. 8. Communities ## Granovetter's theory Granovetter's의 이론에서 edge에 대한 연결이 정의된다. 1. structure : strong한 관계와 weak한 관계가 있다.(여기서 weak는 존재는 하지만 밀집되어서 있지 않는 노드들) 2. infromation : weak 부분이 정보를 교류하게 할 수 있는 중요한 역할을 한다. 위 그림을 보면 직관적으로 이해할 수 있을 것이다. ## Edge Overlap node i 에서 node j 로 갈 때 경로 경우의 수가 많으면 edge overlap이 높다고 표현한다. 이 때 i와 j의 직접연결은 제외한다. (weak edge는 edge overlap이 낮다) Edge overlap은 다음 수식을 따른다. $$ O_{ij} = \frac{| N.. 2021. 12. 8. 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. 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. 이전 1 2 다음 반응형
