란치네티-포춘토-라디치 벤치마크

시리즈의 일부
네트워크 과학
이론.
그래프 복합망 전염 소세계 스케일 프리 커뮤니티 구조 퍼콜레이션 진화 제어가능성 그래프도면 사회적 자본 링크분석 최적화 호혜성 폐쇄 호모필리 감수성 우선첨부 균형이론 네트워크 효과 사회적 영향
네트워크 유형
정보(컴퓨팅) 텔레커뮤니케이션 운송 사회의 과학적 협업 생물학적 인공신경 상호의존적 시맨틱 공간의 의존 흐름 온칩의
그래프
특징들 클리크 요소 인하. 사이클 자료구조 가장자리 고리 이웃 경로. 꼭짓점 인접 목록 / 행렬 발생목록/행렬 종류들 초당파 완성하다 연출된 들뜬 라벨링 멀티 랜덤 가중
메트릭 알고리즘
중심성 도 모티프 클러스터링 정도분포 구색성 거리 모듈화 효율성.
모델들
위상 랜덤그래프 에르트 ő스 - 레니 바라바시-알베르트 비앙코니 바라바시 피트니스 모델 와츠-스트로가츠 지수난수(ERGM) 랜덤 기하학(RGG) 쌍곡선(HGN) 계층적 확률적 블록 블록모델링 최대 엔트로피 소프트 구성 LFR 벤치마크 역학 부울 네트워크 대리인 기반의 전염병/SIR
목록 분류
토픽 소프트웨어 네트워크 과학자 카테고리:네트워크 이론 카테고리:그래프이론
v t

Lancichinetti–Fortunato–Radicchi 벤치마크는 벤치마크 네트워크(실제 네트워크와 유사한 인공 네트워크)를 생성하는 알고리즘입니다. 이들은 사전에 알려진 커뮤니티를 가지고 있으며 다양한 커뮤니티 탐지 방법을 비교하는 데 사용됩니다.^[1] 다른 방법에 비해 벤치마크의 장점은 노드 정도의 분포와 커뮤니티 크기의 이질성을 설명한다는 것입니다.^[2]

알고리즘이.

노드 정도와 커뮤니티 크기는 지수가 다른 거듭제곱 법칙에 따라 분포됩니다. 벤치마크는 정도와 커뮤니티 크기가 각각 다른 지수인$$γ {\displaystyle$$\$}$ 및 β${\displaystyle$\beta}를 갖는 거듭제곱 법칙 분포를 가진다고 가정합니다. ${\displaystyle N}$ $\{\backslash$$displaystyle N}$은 노드 수이고 평균 ${\displaystyle 차}$${\displaystyle 수}$는${\displaystyle }$$⟨k$ ⟩ $displaystyle$ \$langle$ k\rangle }입니다.$혼합$ 파라미터 μ {\$displaystyle$ \mu}가 있는데, 이는 벤치마크 노드가 속한 커뮤니티에 속하지 않는 노드의 이웃 노드의 평균 비율입니다$.$ 이 매개 변수는 커뮤니티 사이에 있는 에지의 비율을 제어합니다.^[2] 따라서 네트워크의 노이즈 양을 반영합니다. 극단에서 $\mu$ = ${\$displaystyle$\mu$ = 0}일 때 모든 링크는 커뮤니티 링크 내에 있으며 μ = 1 {\displaystyle \mu = 1}일 때 모든 링크는 서로 다른 커뮤니티에 속한 노드 사이에 있습니다.

다음 단계를 사용하여 벤치마크 네트워크를 생성할 수 있습니다.

1단계: $지수$$$γ가 ${\$displaystyle$$\gamma}인 거듭제곱 법칙 분포를 따르는 노드로 네트워크를 생성하고 $kmin$ {\$displaystyle$k_{\min } ${\displaystyle {및}_{}}$k $max$ {\$displaystyle$k_{\max }의 극단을 선택하여 원하는 평균 ${\displaystyle \mathrm{차수}}$를 얻기 위해$$⟨ k ⟩ {\$displaystyle$ \langle k\rangle }입니다.

2단계:${\displaystyle }$(${\displaystyle 1}$- ${\displaystyle \mu )}$ ${\displaystyle ($1 -$\mu)}$개의 모든 노드의 링크 중 일부는$$ 동일한 커뮤니티의 노드와 있는 반면, 부분 $\mu {\displaystyle }$ ${\displaystyle \mu}$개는 다른 노드와 있습니다$$.

3단계: 지수 $\beta$가$${\$displaystyle \beta}$인 거듭제곱 법칙 분포에서 커뮤니티 크기를 생성합니다$.$ 모든 크기의 합은 N ${\displaystyle N}$과 같아야 합니다$.$ 최소 및 최대 커뮤니티 크기 ${\displaystyle {smin}_{}}$ ${\$ 및$$ ${\displaystyle {smax}_{}}$ ${\$는 격리되지 않은 모든 노드가 적어도 하나의 커뮤니티에 있도록 커뮤니티 정의를 충족해야$$ 합니다.

${\displaystyle s_{\min}>k_{\min}}$

${\displaystyle s_{\max}>k_{\max}}$

4단계: 처음에는 커뮤니티에 할당된 노드가 없습니다. 그런 다음 각 노드가 무작위로 커뮤니티에 할당됩니다. 커뮤니티 내의 이웃 노드 수가 커뮤니티 크기를 초과하지 않는 한 새 노드가 커뮤니티에 추가되고, 그렇지 않으면 외부에 머무릅니다. 다음 반복에서 "홈리스" 노드는 일부 커뮤니티에 무작위로 할당됩니다. 해당 커뮤니티가 완료된 경우, 즉 크기가 모두 소진된 경우 해당 커뮤니티의 임의로 선택한 노드는 연결을 해제해야 합니다. 모든 커뮤니티가 완료되고 모든 노드가 하나 이상의 커뮤니티에 속하면 반복을 중지합니다.

5단계$:$^[2] 각 노드의 커뮤니티 외부 링크 수가 $혼합{\displaystyle }$ 매개변수 μ ${\displaystyle \mu}$와 거의 동일하도록 노드의 재배선을 구현합니다.

테스트

파티션을 겹치지 않는 커뮤니티로 간주합니다. 각 반복에서 무작위로 선택된 노드의 커뮤니티는 무작위로 선택된 노드가 $커뮤니티$ C ${\displaystyle$ $C$$}$에서 나올 확률을 나타내는 $p{\displaystyle (C)}$ ${\displaystyle$ p$(C)}$ 분포를$$ 따릅니다$.$ 일부 커뮤니티 찾기 알고리즘에 의해 예측되고 $p{\displaystyle ({C2\mathrm{}}_{}}$ ${\displaystyle$ p$(C_{2})}$ 분포를$$ 갖는 동일한 네트워크의 파티션을 생각해 보십시오. 벤치마크 파티션에 $p{\displaystyle ({C1\mathrm{}}_{}}$ ${\displaystyle p(C_{1})}$ 분포가$$ 있습니다. 결합 분포는 $p{\displaystyle ({}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\displaystyle {C\mathrm{}}_{}}$ 2${\displaystyle {}_{}}$ ${\displaystyle$ p$(C_{1}, C_{2})}$입니다$.$ 이 두 파티션의 유사성은 정규화된 상호 정보에 의해 포착됩니다.

${\displaystyle I_{n}={\frac {\sum _{C_{1},C_{2}}p(C_{1},C_{2})\log _{2}{\frac {p(C_{1},C_{2})}{p(C_{1})p(C_{2})}}}{{\frac {1}{2}}H(\{p(C_{1})\})+{\frac {1}{2}}H(\{p(C_{2})\})}}}$

= ${\displaystyle 1}$ ${\$displaystyle I_{$n}$=$1}$에서 벤치마크와 탐지된 파티션이 동일하고 = 0 {\displaystyle I_{n}=0}에서 탐지된 파티션은 서로 독립적입니다.

참고문헌