'complex networks'에 해당되는 글 1건

  1. 2010.07.06 네트워크 분석
물리2010. 7. 6. 22:32

mean separation

<d>=\frac{1}{N(N-1)}\sum_{i,j, i\neq j}d_{ij}

(d_{i,j}는 i, j의 shortest path)

 

Efficiency

\mathcal{E}=\frac{1}{N(N-1)}\sum_{i,j,i\neq j}\frac{1}{d_{ij}}disconnect 된 (크기가 유한한) 네트워크의 지름을 측정할때 유용함.

 

Betweenness Centrality and load(부하)

b_i=\sum_{j,k\in N, j\neq k}\frac{n_{jk}(i)}{n_{jk}}   (BC)

n_{jk} : j와 k사이의 shortest path way의 수

n_{jk}(i) : shortest path way 중에서 i를 지나는 경로수

 

\mathcal{L}_i=\sum_{i,k\in N, j\neq k} \mathcal{L}_{j\mapsto k}(i)(모둔 노드쌍(j, k)에 대해 \mathcal{L}_{j\mapsto k}(i)를 더한값)
\mathcal{L}_{j\mapsto k}(i) : j에서 k의 최단경로로만 패킷이 지나갈때 i를 지나는 패킷의 양(최단경로가 여러개면 나누어서 전달됨)

 

두 이웃 도수간의 상관관계

<k_{nn}>(k): 한 노드의 이웃 노드들의 평균 링크의 수

(솔직히 좀 이상한 값으로 느껴짐, 링크가 k인 모든 노드가 같은 <k_{nn}>(k)를 가질리가 없음.)  

(a) 감소하는 경우: link가 많은 노드와 적은 노드가 연결됨, 비유사성 결합(인터넷, 단백질)

(b) 증가하는 경우: 링크가 많은 노드와 많은 노드가 연결됨, 유사성 결함(사회 연결망)

(c) 변하지 않는 경우: 링크가 많은 노드와 적은 노드가 관련성없이 연결됨(random network)

k가 큰 경우, 상관함수(correlation function)는 <k_{nn}>(k)\sim k^{-\nu}과 같은 관계를 가지는 것도 존재합니다.

(a)의 경우 \nu > 0, (b)의 경우 \nu < 0, (c)의 경우 \nu = 0 

 

 

유사성 지표

r=\frac{<k_1 k_2>-<(k_1 + k_2)/2>^2}{<(k_1^2 + k_2^2)/2>-<(k_1 + k_2)/2>^2} 

일종의 Pearson correlation 

r이 양수이면 양의 상관관계, 음수이면 음의 상관관계, 0이면 무관.

집결계수(clustering coefficient)

C_i = \frac{2E_i}{k_i(k_i -1)}
어떤 노드 i가 가지고 있는 링크의 수 k_i

E_i는 노드 i 에 연결된 노드들 사이의 연결선수를 말한다. 

\frac{k_i(k_i-1)}{2} 는 그 노드들 사이의 최대 연결 가능 선수를 의미한다. 

링크가 k개인 노드의 평군 clustering coefficient는 C(k)라고 쓴다. 

네트워크가 계층적 집단구조(hierarchical modular structure)를 가지면  C(k)\sim k^{-\eta} 같은 멱급구 함수가 된다. 

 


 

이 글은 스프링노트에서 작성되었습니다.

Posted by blindfish