Graph Mining
Roles, Communities
- node에 대한 분석
- 집단에 대한 분석
Roles - 한 노드를 중점으로 많은 노드와 연결되어 있는 노드들을 Role이라 표현하며 같은 부류일 것이다.
Communities - 다 연결은 되어있지만 집단적으로 모여있다. ex) 친구관계 가까운 친구, 먼 친구 하지만 다 친구라는 연결되어 있음
-> Component 와 다르다
Roles
What are Roles?
- Roles are "functions" of nodes in a network
- Roles are measured by structural behaviors
- centers of stars (hub) (많은 노드들을 연결하는 중심에 있는 노드, 묶어주는 역할)
- members of cliques (community)
- peripehral nodes (outliers, 끼지 못하는 노드들)
노드들을 색칠, 정의를 내린다
Roles vs Groups in Networks
- Role : A collection of notes which have similar positions in a network
Role - 서로 연결은 안되어있을 수 있지만 구조적으로 유사한 역할을 하기 때문에 포지션으로 연결
Group - 노드간 연결이 서로 잘 되어 있다.
Roles : More Formally
-
Structural equivalence : 구조적으로 바라본다, 서로가 다를지라도 구조적으로 역할로 비슷하면 묶는다.
-
노드가 star이면서 clique일 수 있다.
recursive Feature Exntacion
- 모든 네트워크를 합친 네티워크 에곤 네트워크
- Neighborhood degree의 나
- Recursive Featurer Extraction
인접행렬을 대입했더니 아웃풋이 나옴
node x Role Role x Feature = node x Feature로 표현 가능
Application : Structural Similarity
Task : Cluster nodes based on their structural similarity
Centrality : A Specific Role of Nodes in the Network
Centrality (or Perstige)
- Some nodes are more important than others
노드의 중심성을 측정하는 것은 여러가지가 있다. 그 중 4가지를 배운다
- Degree centrality
- Closeness centrality
- Betweenness centrality
- Eigenvector centrality
Degree Centrality
- The node with the most connections is most important
본인을 제외한 노드와 연결된 수 만큼 / But 오른쪽, 아래쪽 그림을 보고 의아할 수 있다. Degree로 완벽하게 파악하기 어렵다.
Closeness Centrality
- The node in the middle of the action is most central
노드들을 얼마나 가깝게 연결해주냐
- 나를 중심으로 나머지 모든 노드들의 거리(홉 카운트)를 측정
- 거리의 평균을 구함, 역수.
- 값이 클 경우 나와 가깝다, 작을수록 나와 멀다
Degree와 경향이 비슷하다. 하지만 오른쪽 아래쪽 그림 같은 경우 차이가 더 자세히 보여준다.
Betweenness Centrality
- The node you have to go through is most central
집단들을 연결해주는 것이 더 중요하다. 집단들을 연결해주는 매개체가 중요하다.
ex) brokering between groups, control of information, innovation, collaboration
분모 : N-1 C 2, 분자 :
Eigenvector Centrality
- The node that connects to the important nodes is impotant
노드의 연결성을 depth로 평면에 적용했을 때, 물을 바닥에 뿌렸을 때 물의 흐름이 가장 많은 곳에 있는 노드가 중요하다 라는 개념을 생각해보자.
ex) 나란 사람이 비욘세를 팔로우하는 것 보다, 비욘세가 팔로우 하는 사람이 더 중요하지 않겠는가?
-
A node's eigenvector centrality is proportional to the centrality of it's neighbors
-
A node can have higher eigenvector centrality
Pagerank centrality
- 구글이 왜 떴는가?
검색엔진 : 이전에 검색은 텍스트를 기반으로 결과를 보여주었다.
레리 페이지(구글 창업자) : 텍스트 기반의 알고리즘 만족도가 낮다.
-> 어떤 검색을 했을때 어떤 페이지로 이동하더라 라는 정보를 수집.
-> 검색 내용이 중요한 것이 아닌 검색 후 페이지의 이동의 흐름이 중요하다.
-> 어떤 페이지를 더욱 방문하냐가 더 중요. page rank를 매김
Network Centralization
- A measyre how centrality is distributed in the network
탈중앙화가 얼마나 되어있는가, 값이 높을경우 중앙화가 되어있다.
Prestige
- Centrality in directed networks is called "Prestige"
Community Analysis : Motivation
그래프를 그려봤을 때 엣지가 몰려있는 곳은 무엇을 의미할까?
집단 노드를 어떻게 분석하고 어떻게 해석할 수 있을까?
Granovetter's Theory
- Granovertter makes a connection between the social and structural role an edge
- Weak, Strong tie - 가끔, 자주 만나는 사이
Grano's offical - 사회 집단은 이 집단에서 저 집단으로 연결되는데 오래걸리거나 짧게 걸린다. 같은 정보를 공유할 때 Strong, 다른 정보 Weak
Edge Strength in Real Data
- For many years Granovetter's theory was not tested
- But, today we have large who-talks-to-whom graphs
- Onnela - 전화번호부의 네트워크 확인 (2007)
Edge Overlap
neighbors가 얼마나 겹치는가를 계산
현실 세계에 반영해보니 실제로 존재
Computing Communities : Overview
Modularity and Network Communities
그룹을 만들었다고 가정하였을 때 그룹안에 있는 Edge 수 - 예상되는 평균 Edge 수 > 0 : 모듈화가 더 잘 되어있다.
- 모듈을 정확히 정의하기 어렵다.
- 그룹을 지어놓는다는 것이 경우의 수가 너무 많다.
예상되는 평균 Edge 수를 어떻게 구하는가?
Null Network Configuration Model
- Given real G on nodes and m edges, construct rewired network G
- 예상되는 Egde 수
s->S : 한개의 그룹을, 전체 그룹개수만큼 더함
-1<=Q<=1 을 구하기 위해 2m을 나눔
Computing Communities : Newman Method
Newman Method : Intuition
- Considering Edge Betweenness
Community detection weak tie 부터 Strong tie를 끊는다.
weak tie 부터 끊기 때문에 점점 모듈화가 잘 되어지다가 Strong tie도 끊어지기 때문에 모듈화가 점점 낮아진다.
