Structual Holes / Network Communities

Robert가 다른 커뮤니티와 연결되어있음 -> 로버트가 Structual Hole에 있다. -> 이쪽으로 좋은게 다 모인다!

 

network constraint : 어떤 사람의 아는사람들이 얼마나 redeundant하냐(겹치냐) : dense하냐 느낌..?

-> 낮으면 내가 없어지면 서로 모르는 사이가 된다.

 

----------

커뮤니티 : 단단하게 연결된 노드 집합 = 클러스터 = 그룹 = 모듈 -> 각 회색부분이 dense하기 때문에 이미지에서는 3개

sponsored search : 검색어와 관련있는 광고를 보여주는게 좋음

-> 검색어도 많고 회사도 많고 변화함. 사람이 전해줄 수 없다.

-> 매커니즘 존재. advertiser : 광고주, query : 검색어

 

<how to find communities>

- Strong하고 Weak한 것에도 정도가 있음.

- Edge betweenness : 어떤 엣지를 지나야 되는 쇼티스트 패스의 개수.

7.5의 경우 5 + (2/5) = 7.5임. 우상단으로 가는 케이스는 2가지 방법이 있기 때문.

 

real network에서 edge betweeness가 낮다 : embed되어있음. 높은 것들은 커뮤니티를 연결함 = 스트롱

-> 패턴이 비슷하다.

 

 

- girvan-newman 알고리즘 : undirect unweight network를 대상으로 함

1. betweeness 계산

2. 가장 높은 것 끊어주기 

를 아무 엣지도 안남을 때 까지 반복

7-8번 사이 : 49라는 것 이해됨. 3-7사이도 3*11 느낌.

8-12는 3-7과 포지션이 같음 -> 사실상 모든 엣지 비트윈네스를 구해놓은것!

 

그럼 먼저 7-8을 끊어야함. 그럼 그래프는 2개의 커뮤니티로 나뉘어지겠지?

-> 다음으로 3-7을 끊는게 아니라, 다시 계산해야함.

 

다 끝나면 전체적으로 hierarchical(계층적) cluster형이 된 것.

 

-> 그렇다면.... 클러스터의 개수는 도대체 어떻게 알아낼까? 거먼뉴먼 알고리즘 보면 하나씩 계산해야하는데 음.......

 

아까와 같은 나비모양 그래프가 아니고선 눈으로 계산하기 힘들다

-> 찝어서 트리와 유사한 계층적 구조로 만든다!

A-H는 쇼티스트 패스가 2개

A-G는 반드시 D를 거쳐서 가야함. → 길이 1개.

A-J는 G로오는게 1, H로 오는게 2개니까 3개. A-I도 3개. → A-K는 6개겠지.

-> 시작노드를 어떻게 잡냐에 따라 달라질 수도..?

A-J = A-G + A-H.

우측의 숫자는 쇼티스트 패스의 개수임.

 

그럼 비트윈네스를 어떻게 구할까?

노드마다 node flow를 설정하여 위의 노드로 올려준다.

기본적으로 노드마다 1씩 가지고 있다.

깊이가 가장 깊은 노드를 시작으로 기준이 되는 노드까지 BFS방식으로 flow up 해준다.

 

I와 J를 보면, 1과 flow up 당해서 받은 0.5를 더해 1.5를 갖고 있다

-> I를 보면 상위 노드인 G,H의 최단 경로가 2,1 이기에 2:1 비율로 flow up 해줘야 한다.

 

이후 가장 큰 edge betweenness를 제거하는 과정을 반복하는 것.

 

<how to compute betweenness)

Modularity Q : 얼마나 잘 network를 prtitioning했는가에 대한 수치 = 얼마나 잘 communities들로 구분되어 있는지.

그룹들 (각각 S의 엣지 수와 예상되는 엣지 수(null모델)의 차이)의 합으로 구해짐. 클수록 잘 구분된 네트워크.

 

Q값이 좋은 measure로서 역할을 하려면 특정 구간 안에 들어오도록 nomalize해줘야함. -1~1로.

각 클러스터에서 0.3~0.7로 들어온다면 클러스터링이 잘 이루어진 것.

 

-> 모듈러리티 값이 높은게 좋은 클러스터링

-> 하나씩 잘라가면서 모듈러리티 값을 계산하여 그 값이 최상일 때 멈춤.

 

-null 모델 : 어떤 그래프 위에 n개의 노드와 m개의 엣지가 있다 했을때, 가상의 G'그래프를 만들어 보는 것. 이 때 커넥션만 랜덤하게 바꾸는 것. -> node degree = 엣지의 개수는 유지한 상태에서 랜덤 커넥션을 만들면 그 결과물이 G'가 됨.

-> i, j노드의 엣지의 개수가 기대값인데, 계산해보면 똑같이 m이 나옴.

 

 

<Signed network>

signed network : +- 부호의 관계를 갖고 있는 네트워크. 연결되었다고 다 좋은게 아니다!

 

구조적 균형.

Balanced network : 구조적으로 균형이 잡혀 있는 네트,워크.

친구의 친구는 내 친구, 내 적의 적은 내 친구, 내 친구의 적은 내 적 -> 삼각형에서 balanced는 모든 엣지가 + or 하나의 엣지만 +.

 

Balanced함. 그러나 모두가 평화로운 상태가 아니다.

+와 + 사이에 -가 존재하기 때문에 자연스럽게 둘로 나뉘어져 global coalitions를 형성함.

 

 

local view에서는 밸런스를 만들기 위해 엣지를 채운다.

global view를 보면, 두 편으로 나눌 수 있음.

-> 동일한 작업에 해당.

 

 

완전한 그래프가 아닐때 어떻게 밸런스드인지 확인할 수 있을까?

홀수개의 - 간선을 갖는 사이클을 갖고 있지 않을 때 balanced하다.

이미지를 잘 펴면 사이클임.

 

밸런스드 하다는건 무조건 사이가 좋은게 아님! 지속되는 것이 밸런스드

 

찾는 방법

1. + 간선으로만 구성된 connected components를 찾는다.

2. 그 컴포넌트는 사이가 좋으니 하나의 수퍼노드로 생각

3. 수퍼노드 사이에 +엣지가 있다면 하나가 되어야함. 따라서 수퍼노드를 다 만들고 나면 -엣지만 남게 된다

4. 이 수퍼노드를 가지고 BFS(너비우선탐색)를 하면서 side(편)을 나눈다.

-> 만약 global coalitions를 만족하지 않으면 unbalanced한 것.

1,2,3,5 : 서로 +로 연결되어 있음. 한 컴포넌트고, 더 커질 수 없음.

4 : 이렇게 노드 하나도 컴포넌트임.

-> 이런식으로 묶으면 수퍼노드 총 7개가 된다.

 

Reduced Graph : 이렇게 컴포넌트로 묶어져서 간소화된 그래프

네거티브 엣지는 다른 편 간에만 있어야함. 그러나 위 이미지를 보면 같은편간에도 네거티브 엣지가 있음

-> Unbalanced

 

 

<Exploring Real Data>

실제 데이터에서 밸런스 이론이 맞나? 확인해보는 것.

밸런스드 트라이아드의 경우 예측치(P0)보다 높은 값을 보이므로 밸런스 이론에 적합.

언밸런스드 트라이아드의 경우, 위의 케이스는 예측치(P0)보다 낮은 값을 보이므로 밸런스 이론에 적합한데, 아래 케이스는 적합하지 않다.

 

 

나는 우리 동기들밖에 몰라! -> A, embeddedness가 굉장히 높은 엣지.

b -> 임베디드니스가 굉장히 낮음.

embeddedness가 높다 = 주변 관계가 밀접하다

 

- Epinions의 그래프 : positive tie는 더 embedded하는 경향이 있다. -> positive tie는 커뮤니티에 속한다.

x축은 shared neighbors의 수. 임베디드니스가 높으면 + 엣지가 많아진다.

randomize 시키면 아무런 연관성이 없지만, 실제에서는 올라간다! -> 관련이 있다.

- Wiki의 그래프 : 찬성 반대가 공개된다면 -> Positive가 더 많아진다.

 

- +가 많으면 기준보다 많이 클러스터링하고, -가 많으면 좀 덜 클러스터링한다.

 

 

 

----------

다른 이론. 방향성이 추가됨.

+ : 상대가 스테이터스(지위)가 더 높다, - : 상대가 더 낮다.

이볼빙 네트워크 : 시간의 흐름에 따라 변화하는 상황.

 

밸런스는 편을 나누는 관점에서 소셜 네트워크를 봄 -> 방향성이 무시됨.

스테이터스는 hierachical함. 누가 높고 낮은지.

이미지처럼 1+-> 2+->3 이기 때문에, 1이 3보다 높을 수 없음 -> 사이클이 없다.