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

AGM 에서는 멤버쉽이 단순이 있거나 없다는 것만을 나타냈습니다.
실제 상황에서는,
예를 들어 같은 동아리 멤버여도
활동적인 사람과, 그렇지 않은 사람이 있습니다.

AGM 은 이 둘의 멤버쉽을 같은 것으로 처리합니다.
때문에 커뮤니티에 속한 사람의 활동 정도를 반영하지 못하였습니다.

멤버쉽의 활동 정도, strength 를 도입한 것이 BIGCLAM 입니다.

BIGCLAM

BIGCLAM은 membership strength F 를 사용합니다.
$F_{uA}$ 는 커뮤니티 A 에 대한 u 의 멤버쉽 강도(=membership strength) 입니다.
값이 높을 수록 그 커뮤니티에서 더 활동적이라는 의미를 갖고,
$F_{uA} = 0$ 인 경우는 A 의 커뮤니티 멤버가 아니라는 것을 의미합니다.
$F$ 는 음수가 되진 않습니다.

커뮤니티 A 에 대해 노드 u, v 의 엣지는 다음과 같이 표현됩니다.

\[P_A(u,v) = 1 - \exp(-F_{uA} \cdot F_{vA})\]

u와 v 가 A 에 대한 맴버쉽이 높을 수록
exp 가 낮은 값이 나와 1에 가까워 집니다.
$(-F_{uA} \cdot F_{vA})$ 의 최소값은 멤버쉽이 아닌 경우, 0 이고
이때 $P_A$ 가 0 이 됩니다.

단순히 노드 u, v 가 엣지를 가질 확률은, AGM 방식과 동일하게

\[P(u,v) = 1- \prod_{C} (1 - P_C(u,v))\]

로 표현할 수 있습니디.(독립적이므로)

커뮤니티에 대한 멤버쉽 강도 F 는 행렬로 표현할 수 있습니다.
그림과 같이

그림@@

행은 노드, 열을 커뮤니티로 두고 하나의 행렬로 표현이 됩니다.
이를 활용하여 엣지의 확률을 편하게 구할 수 있습니다.

노드 사이 엣지의 확률은
\(P(u,v) = 1- \prod_{C} (1 - P_C(u,v))\) 였고
\(P_A(u,v) = 1 - \exp(-F_{uA} \cdot F_{vA})\) 이므로

대입하면
\(P(u,v) = 1 - \exp(-\Sigma_C F_{uC} \cdot F_{vC} )\) 가 되고,
exp 내부의 항은 두 벡터의 dotproduct 이므로
\(P(u,v) = 1 - \exp(-F_{u} \cdot F_{v}^T )\) 로 정리할 수 있습니다.

이제 주어진 네트워크 G(V,E) 에서 F 를 추정해 봅시다.
AGM 포스팅의 예제와 동일한 방식으로 수행합니다.

그래프 전체의 엣지의 집합 E 의 likelihood 를 다음과 같습니다.

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

이를 직접계산하기는 어려우므로 로그를 사용합니다.
log-likelihood, $l(F)$ 는 다음과 같습니다.
\(l(F) = \underset{(u,v)\in E} \Sigma log(1-exp(-F_u \cdot F_v ^T)) - \underset{(u,v)\notin E} \Sigma F_u \cdot F_v ^T\)

이는 Gradient ascent 를 사용해서 F 를 최적화 할 수 있습니다.

F의 단일 행 $F_u$ 의 그레디언트는
$\nabla l(F_u) = \underset{v\in \mathcal{N}(u)}\Sigma F_v \frac{\exp(-F_u F_v^T)}{1-\exp(-F_uF_v^T)} - \underset{v \notin \mathcal{N}(u)}\Sigma F_v$ 가 됩니다.

최적화를 위해
F의 행마다

1. u번째 행의 그레디언트 $\nabla l(F_u)$ 를 구합니다.
2. 행을 업데이트 합니다. $F_u : F_u \leftarrow F_u + \eta \nabla l(F_u) $
3. $F_u$ 에 음수 벡터가 있으면 0으로 바꿔줍니다.

을 수행합니다.

위의 식에서 $\underset{v \notin \mathcal{N}(u)}\Sigma F_v$ 을 계산하는 작업은 시간이 오래 걸립니다.
행렬 F 에서 $v$ 행이 아닌 모든 행들을 계산해야합니다.
속도를 높이기 위해서는 이 항을 다음과 같이 바꿉니다.
$\underset{v \notin \mathcal{N}(u)}\Sigma F_v = (\Sigma_v F_v - F_u - \underset{v \in \mathcal{N}(u)}\Sigma F_v)$

\(\Sigma_v F_v\) 는 캐시하여 계산하면,
$| \mathcal{N}(u)|$ 만큼만 계산하면 됩니다.

이런식으로 네트워크가 주어졌을 때
멤버쉽 강도에 대한 행렬 F 를 추정할 수 있습니다.