네트워크,network: 노드(node)와 에지(edge)로 이루어진 자료구조.
네트워크(network) = 그래프(graph)
노드(node) = 버텍스(vertex)
링크(link) = 에지(edge)
노드(node) = 버텍스(vertex)
링크(link) = 에지(edge)
자료구조로, 그래프(graph) 혹은 네트워크 그래프(network graph)를 씀.
그래프의 분류:
방향성이 있는 지 여부. 무방향(undirected), 무방향(directed graph)
가중치 여부
그래프는 테이블(table), 인접행렬(adjacent matrix) 등으로 표현 가능.가중치 여부
음의 가중치 허용 여부? QQQ
등등1.5.1. 커뮤니티 탐지(community detection) ¶
네트워크에 어떤 서브그룹이 있는지 탐색하고, 그 그룹 간의 관계를 통해 네트워크의 특성을 파악하는 방법.
단어
community : 노드들이 속한 클러스터
community : 노드들이 속한 클러스터
클러스터 탐지 방법 (2가지) - ~를 기준으로 한 나누기(=구분하기)
modularity를 기준으로 나누기
modularity는 클러스터가 잘 이뤄졌는지 확인할 수 있는 지표로 활용됨. 1에 가까울수록 클러스터링이 잘 이루어졌다고 판단할 수 있음.
modularity는,
modularity 공식
betweenness를 기준으로 나누기modularity는,
community 내의 밀도 계산과
community 간의 밀도 계산으로 판단.
유사한 노드나 커뮤니티를 점진적으로 합치는 방식임.community 간의 밀도 계산으로 판단.
modularity 공식
$\displaystyle Q=\frac1{2m}\sum_{i,j}\left[ A_{ij}-\frac{k_i k_j}{2m} \right]\delta(c_i,c_j)$
여기서
$\displaystyle A_{ij}$ : 노드 $\displaystyle i,j$ 의 weight
$\displaystyle k_i$ : 노드 $\displaystyle i$ 에 부여된 edge weight의 합 $\displaystyle =\sum A_{ij}$
$\displaystyle c_i$ : 노드 $\displaystyle i$ 가 속한 community
$\displaystyle \delta(u,v)$ : 같은 community일 때는 1, 다르면 0 indication function?
$\displaystyle m$ : $\displaystyle \frac12\sum A_{ij}$
여기서
$\displaystyle A_{ij}$ : 노드 $\displaystyle i,j$ 의 weight
$\displaystyle k_i$ : 노드 $\displaystyle i$ 에 부여된 edge weight의 합 $\displaystyle =\sum A_{ij}$
$\displaystyle c_i$ : 노드 $\displaystyle i$ 가 속한 community
$\displaystyle \delta(u,v)$ : 같은 community일 때는 1, 다르면 0 indication function?
$\displaystyle m$ : $\displaystyle \frac12\sum A_{ij}$