Affilation Graph Model

해당 포스팅은 스탠포드의 Jure Leskovec 교수님의 강의 와 Mining of Massive Datasets(Jure Leskovec, Anand Rajaraman, Jeff Ullman) 책 을 참고하였습니다.

The Affilation-Graph Model

Affiliation-graph model(AGM) 는 생성모델(=generative model) 로,
커뮤니티(=community)로부터 그래프를 생성하는 매커니즘입니다.

이 모델에서는 커뮤니티를 통해, 노드 쌍의 엣지가 있을 확률을 구할 수 있습니다.

AGM, B 는 다음과 같이 표현됩니다.
$B(V,C,M,{p_C})$

• 노드의 집합 V, 커뮤니티의 집합 C, 멤버쉽 M 을 갖습니다.
• 각 커뮤니티 c 는 확률 $p_c$ 를 갖습니다.

AGM의 그래프 생성 매커니즘은 다음과 같습니다.

1. 켜뮤니티가 지정된 수가 주어지고, 특정 수의 노드가 주어집니다.
2. 각 커뮤니티는 멤버로서 어떠한 노드들의 집합도 갖을 수 있습니다.
   이는 커뮤니티에서 맴버쉽이고, 모델의 파라미터 입니다.
3. 커뮤니티 C 는 그것과 관련된 확률 $p_c$ 를 갖습니다.
   이 확률은 커뮤니티 C 에 속한 두 맴버가 엣지로 연결될 확률입니다.
   이 확률 또한 모델의 파라미터입니다.
4. 노드의 쌍이 두개 이상의 커뮤니티에 있을 때,
   둘 다의 구성원인 커뮤니티의 중 하나라도 3번에 따라 엣지가 생기면 그 쌍은 엣지가 있는 것 입니다.(하나만 연결되도 연결된다.)
5. 여러 커뮤니티에 속해 있더라도 한 커뮤니티에서 맴버 두개 사이에서 엣지가 생기는지에 대한 확률은 독립적입니다.( 같은 노드여도 다른 커뮤니티에서 연결되는 것은 상관이 없다.)

노드 u와 v는 C,D 의 커뮤니티이고, 이 커뮤니티들은 $p_C,p_D$ 를 갖는다고 가정하고,
여기서 edge (u,v) 가 있을 확률을 구해봅시다.
우선, 엣지가 없을 확률을 먼저 구합니다.
C 에 속하는 멤버가 엣지로 연결되지 않을 확률 (1-$p_C$) 와
D 에 속하는 멤버가 엣지로 연결되지 않을 확률 (1-$p_D$) 가 있고,
이 둘은 5번에 의해 독립적이므로
C,D 에 속하는 멤버가 둘다 엣지로 연결되지 않을 확률은 (1-$p_C$)(1-$p_D$) 입니다.
그러므로 C,D 중 아무 멤버나 엣지로 연결될 확률은
$1 - (1-p_C)(1-p_D)$ 입니다.

이 방식을 일반화 시켜서
특정 노드 u, v 의 엣지가 존재할 확률은
다음 같이 쓸 수 있습니다.

\[p_{uv} = 1-\underset{C\ in \ M} \prod(1-p_C)\]

노드 u, v 가 어떠한 커뮤니티에도 속하지 않는 경우가 있습니다.
이 경우 확률을 0으로 설정하게 되면 이후 작업에 어려움이 있어
대신 아주 작은 값 $\epsilon$ 으로 설정합니다.

이렇게 단일 엣지의 확률을 구하는 식을 찾았습니다.

이를 통해 그래프 전체의 엣지의 집합 E 의 likelihood 를 다음과 같이 구할 수 있습니다.

\[\underset{(u,v)\ in\ E}\prod p_{uv} \underset{(u,v)\ not\ in\ E}\prod (1-p_{uv})\]

이 likelihood 를 사용하여 커뮤니티의 확률 $p_C$ 를 구할 수 있습니다.

다음과 같은 그래프에서,

두개의 커뮤니티 C,D 가 있고, 각각 확률 $p_C , p_D$ 를 갖는다고 봅시다.
C = {w,x,y}, D = {w,y,z} 를 갖고.

여기서 (w,x) 에 대해 생각해봅시다.
$M_{wx}$ = {C} 이므로
$p_{wx} = 1-(1-p_C)=p_C$ 입니다.

유사하게 x,y 는 C 에 있고, y,z 는 D 에 w,z 는 D 에 있습니다.
$p_{xy} = p_C , p_{yz} = p_{wz} = p_D$ 이고
w,y 의 경우 C,D 모두에 있습니다.
그러므로 $p_{wy} = 1 - (1-p_C)(1-p_D) = p_C + p_D - p_C p_D$ 입니다
x,z 의 경우 같이있지 않으므로 $p_{xz} = \varepsilon$ 입니다.

이것으로 likelihood를 계산할 수 있고 다음과 같이 나타냅니다.

$p_{wx}p_{wy}p_{xy}p_{yz}(1 − p_{wz})(1 − p_{xz}) $

위의 식들을 사용하여 다음과 같이 표현할 수 있습니다.

$(p_C)^2p_D(p_C+p_D-p_Cp_D)(1-p_D)(1-\epsilon)$

마지막항의 입실론은 매우 작은 값이므로 1로 둬도 됩니다.

이 식을 최대로 하는 $p_C$ 와 $p_D$ 를 찾아야합니다.
우선, 모든 항들은 $p_C$ 에 독립적이거나, $p_C$가 커짐에 따라 커집니다.
$-p_Cp_D$ 의 경우도, $p_D <1$ 이므로 3번째 항도 $p_C$ 에 따라 커집니다.
때문에 likelihood를 최대화하기 위해서는 $p_C$ = 1 이 됩니다.

다음으로 $p_C=1$ 일 때, $p_D$ 를 찾습니다.
위의 식은 $p_D(1-p_D)$ 로 바뀝니다.
그리고 이 값은 $p_D=0.5$ 일때 최대값을 갖습니다.

이와 같이, 실제 주어진 그래프를 사용하여
커뮤니티의 확률 파라미터를 구할 수 있습니다.
이렇게 구한 파라미터로 실제 네트워크를 생성하여 분석이나 예측하는데 활용할 수 있습니다.