Scale-free Networks Well Done

Ivan Voitalov; Pim van der Hoorn; Remco van der Hofstad; Dmitri Krioukov

Source-linked AI summary

Scale-free Networks Well Done

Ivan Voitalov, Pim van der Hoorn, Remco van der Hofstad, Dmitri Krioukov

arXiv:1811.02071v22018년 11월 5일physics.soc-phcs.SIphysics.data-an

TL;DR

현실 세계 네트워크의 degree distribution에서 power law를 탐지하는 일은 이상적인 순수 power law에서 벗어나는 현상과 estimator 불안정성 때문에 복잡하다. 이 논문은 regularly varying distribution을 정의하고, extreme value theory에 기반한 일관된 estimator를 확립하며, scale-free network가 드물지 않음을 보인다.

문제
기존 power-law 탐지 방법은 정수값 degree sequence에서 estimator 불안정성에 직면하며, 순수 power-law 가정은 잡음이 있는 현실 세계 네트워크를 부적절하게 표현한다.
방법
이 논문은 regularly varying distribution을 정의하고, extreme value theory를 사용해 일관된 tail-exponent estimator를 식별하며, degree-sequence classification scheme을 통해 이를 적용한다.
결과
대표적인 현실 세계 degree sequence에 적용한 결과, power-law degree sequence를 보이는 네트워크가 상당한 비율을 차지하는 것으로 나타나 scale-free network가 드물지 않음을 확인한다.
시사점 및 한계
순수 power law라는 요구를 완화하면 empirical network에서 scale-free structure를 탐지할 수 있는 더 광범위하고 현실적인 기반을 얻는다.
시사점 및 한계
Regularly varying distribution은 hypothesis testing의 대상이 될 수 없으므로, finite sequence classification에는 p-value와 같은 통계적 가중치를 부여할 수 없다.

Abstract

from arXiv · show

We bring rigor to the vibrant activity of detecting power laws in empirical degree distributions in real-world networks. We first provide a rigorous definition of power-law distributions, equivalent to the definition of regularly varying distributions that are widely used in statistics and other fields. This definition allows the distribution to deviate from a pure power law arbitrarily but without affecting the power-law tail exponent. We then identify three estimators of these exponents that are proven to be statistically consistent -- that is, converging to the true value of the exponent for any regularly varying distribution -- and that satisfy some additional niceness requirements. In contrast to estimators that are currently popular in network science, the estimators considered here are based on fundamental results in extreme value theory, and so are the proofs of their consistency. Finally, we apply these estimators to a representative collection of synthetic and real-world data. According to their estimates, real-world scale-free networks are definitely not as rare as one would conclude based on the popular but unrealistic assumption that real-world data comes from power laws of pristine purity, void of noise and deviations.

I. 서론

이 논문은 power law를 regularly varying distribution으로 다루어 power-law degree distribution을 식별하기 위한 엄밀한 정의와 통계적으로 일관된 방법의 부재를 해결한다. 이보다 포괄적인 framework와 최신 statistical analysis를 바탕으로 scale-free network가 드물지 않다고 결론짓는다.

널리 합의된 정의가 degree distribution이 power-law인지 또는 근사적으로 power-law인지 규정하지 않기 때문에, real-world scale-free network를 엄밀하게 평가할 수 없으며 논쟁이 계속되고 있다 [18] [23] [24] [26] [27].
순수한 power-law degree distribution 대신 regularly varying degree distribution을 허용하면 scale-free network가 확실히 드물지 않다는 사실이 드러난다.
이 논문은 complementary cumulative distribution function이 regularly varying일 때 distribution을 power-law로 정의하며, tail exponent γ를 보존하면서 유한 degree에서 임의의 편차를 허용한다.Regularly varying distribution은 slowly varying function을 포함하며 순수한 power law보다 훨씬 더 포괄적이다.
모든 regularly varying distribution에 적용되고, true γ로 수렴하며, 최적의 finite-sample estimation을 제공하는 double-bootstrap method로 자동화할 수 있는 estimator를 식별한다.
[19, 20]의 method와 달리, 이 estimator는 nontrivial slowly varying function을 갖는 impure power law에서도 일관성을 유지하며, 여기에는 preferential-attachment model의 degree distribution도 포함된다.
이 논문은 hypothesis test와 p-value에 의존하는 대신 여러 개의 일관된 γ-estimator를 사용하고, 추정값이 서로 일치하는지에 따라 sequence를 분류한다.

II. POWER-LAW 분포

이 절에서는 power-law 분포를 regularly varying 분포로 엄밀하게 정의한다. 이 정의는 낮은 degree에서 임의의 형태를 허용하면서도 power-law tail을 보존한다. Pure power-law은 slowly varying function이 상수인 특수한 경우이며, 정의의 점근적 성격 때문에 가설검정은 불가능하다.

II. POWER-LAW 분포: Power-law 분포는 regularly varying 분포로 정의되며, 그 tail은 slowly varying function에 의해 조절되는 power law를 따른다.이 정의는 tail exponent를 바꾸지 않으면서 pure power-law에서 벗어나는 것을 허용한다.
II. POWER-LAW 분포: Pure power-law은 slowly varying function이 상수인 특수한 경우다. 정수값인 경우는 generalized zeta 분포이고, 연속값인 경우는 Pareto 분포다.따라서 pure power-law은 regularly varying 분포의 작은 부분집합에 불과하다.
II. POWER-LAW 분포: Regular variation은 high-degree tail만 제약하므로, 분포는 임의로 큰 고정 threshold 아래에서 어떤 형태든 취할 수 있다.그 점근적 성격은 전통적인 scale-free 공식의 직관을 형식화하면서 유한 degree에서 non-power-law 형태를 허용한다.
II. POWER-LAW 분포: Regular variation은 본질적으로 점근적이므로, regularly varying 분포를 사용한 가설검정은 불가능하다.정의는 k →∞의 극한을 다루며 임의로 큰 threshold 아래의 형태를 제한하지 않는다.

III. 꼬리 지수의 일관된 추정량

이 절에서는 regularly varying 분포의 꼬리 지수에 대한 통계적으로 일관된 extreme-value 추정량 세 가지—Hill, Moments, Kernel —를 전개한다. 이들의 보장은 i.i.d. 표본을 필요로 하며, 꼬리에 초점을 둔 tuning과 bootstrap 선택을 통해 일관성을 해치지 않고 유한 표본에 적용할 수 있다.

추정량 선택: Hill, Moments, Kernel 은 regularly varying 분포의 power-law 지수를 결정하는 extreme value index ξ를 일관되게 추정한다.일관성이란 표본 크기가 증가할수록 slowly varying 성분과 무관하게 추정값이 참 ξ로 수렴한다는 뜻이다.
가정과 범위: 일관성 결과는 regularly varying 분포에서 추출한 i.i.d. samples를 가정하며, 다른 network model로 증명을 확장하는 일은 여전히 미해결 연구 과제다.저자들은 주어진 실제 degree sequence에 대해 이러한 가정을 엄밀하게 정당화할 수 있는 hypothesis test는 없다고 밝힌다.
해석: Negative or near-zero ξ estimates는 degree sequence가 Fréchet MDA에서 생성되었을 가능성이 낮고, 따라서 regularly varying일 가능성도 낮음을 나타낸다.이 진단은 명시적으로 정성적이다. 저자들은 그 가능성이 낮다는 정도를 엄밀하게 정량화할 수 없다고 지적한다.
Order-statistic tuning: 추정량은 κ개의 가장 큰 order statistics를 사용하지만, 일관성을 위해서는 꼬리 변동과 slowly varying-function 효과를 제한하도록 κ가 n과 함께 발산하면서도 n보다 작아야 한다.n개의 관측값을 모두 사용하면 slowly varying function이 추정값에 영향을 줄 수 있다.
Order-statistic tuning: double-bootstrap method는 estimation error를 최소화해 optimal κ*를 선택하며, κ*가 n에 대해 sublinear하게 증가하기 때문에 consistency를 보존하는 것으로 증명되었다.따라서 저자들은 Hill, Moments, Kernel을 bootstrap procedure가 optimal하면서도 consistent하다는 것이 증명된, 일관되고 안정적이며 효율적인 추정량의 최대 부분집합으로 식별한다.

IV. 추정량 성능 평가

Appendix D는 synthetic distribution과 network-model degree sequence에 대해 세 가지 extreme-value estimator를 평가하고, regular variation 하에서 그리고 network degree가 i.i.d.가 아닌 경우에도 수렴함을 보인다. PLFit [19, 20]와 비교하면, EV estimator는 충분히 양호한 distribution에서 PLFit와 비슷한 성능을 보이지만 distribution이 pure power law에서 벗어나면 이를 크게 능가한다.

Extreme-value estimator: 세 EV estimator는 모두 regularly varying distribution에서 참 ξ로 수렴하지만, regularly varying이 아닌 distribution에서는 수렴하지 않는다.또한 regularly varying distribution으로 수렴하는, regularly varying이 아닌 distribution의 수열에 대해서도 수렴한다.
Network-model 평가: 개별 degree가 고정된 degree distribution에서 추출된 i.i.d. sample이 아닌데도 EV estimator는 network model에서 생성된 degree sequence에 대해 수렴한다.평가에는 configuration model, preferential attachment, random hyperbolic graph와 함께 다양한 distribution에서 sampling한 random sequence가 포함된다.
PLFit 비교: distribution이 충분히 양호하지 않거나 pure power law에서 더 멀리 떨어져 있을 때 EV estimator는 PLFit [19, 20]를 유의하게 능가한다.distribution이 충분히 양호하면 PLFit의 estimation accuracy와 convergence rate는 EV estimator의 것과 비슷하지만, small-degree 영역이 잘못된 power-law exponent를 시사할 때 PLFit의 성능은 낮다.

V. 멱법칙 차수열

regularly varying degree distribution에서는 가설검정이 불가능하다. 해당 class가 nonparametric이고 무한차원이면서, finite sample이 power-law tail을 숨기거나 모방할 수 있기 때문이다. 따라서 이 논문은 세 exponent estimator에 기반한 보수적 분류를 제안하며, multiple degree sequence을 갖는 network에 이를 적용할 때는 판단이 필요하다고 지적한다.

slowly varying function이 무한차원의 nonparametric distribution class를 형성하므로, hypothesis testing으로 regular variation을 엄밀하게 확립할 수 없다.따라서 이 family에 대해 finite sample을 검정하는 것은 하나의 수가 특정 distribution에서 나왔는지를 검정하는 것과 유사하며, 이는 불가능하다.
slowly varying function이 임의로 넓은 sample 범위에서 실제 tail을 가릴 수 있으므로, finite sample은 정확성을 보장하지 않으며 수렴 시작 시점도 알려 주지 않는다.parametric family와 달리, ℓ(k)가 임의로 나쁠 수 있을 때 estimator나 test가 수렴을 드러내는 데 필요한 sample size는 알려져 있지 않다.
adversarial example은 sample이 genuine Pareto tail을 숨기거나 거짓으로 이를 시사할 수 있음을 보여 주며, detectable behavior는 sample size가 관련 tail-scale threshold를 넘어선 뒤에야 나타난다.mixture example에서는 tail의 징후가 나타나려면 n이 1/f보다 충분히 커야 한다. non-regularly-varying example에서는 Fig. 1에서 확인되듯 n이 cγ^-1을 넘어설 때에만 deviation이 나타난다.
이 논문은 formal hypothesis-test probability가 아니라 세 estimator가 반환하는 ξ 값에 기반한 보수적 power-law 정의를 채택한다.hardly-power-law regime에 대한 제안 threshold는 명시적으로 임의적이며, 저자들은 모든 ξ 값이 양수인 경우를 power-law sequence로 정의하는 대안도 가능하다고 지적한다.
directed, multipartite, multilayer, multiplex 또는 temporal structure를 갖는 network에서 network를 power-law로 labeling할지는 multiple degree sequence 중 어떤 것을 고려하느냐에 달려 있다.저자들은 이 선택이 disease spread와 같은 특정 network question에 연결되지 않는 한 취향의 문제라고 규정한다.

VI. 실세계 네트워크

필터링된 KONECT degree sequence에 Hill, Moments, Kernel estimator를 적용한 결과, 기존에 식별된 power-law network 중 다수가 확인되는 반면 알려진 non-power-law 사례는 기각된다. 네트워크 유형 전반에서 power-law degree sequence는 흔하며, 상당한 비율은 발산하는 second moment를 보인다.

VI. 실세계 네트워크: 분석에서는 무방향, 방향성, bipartite network 유형을 포괄하는 115개의 필터링된 KONECT network에 Hill, Moments, Kernel estimator를 적용한다.명시된 preprocessing 단계에 따라 temporal, unavailable, duplicate, incomplete, self-loop, multi-edge 사례를 제외한다.
VI. 실세계 네트워크: estimator는 Internet, WWW, protein-interaction, social-membership, citation, recommendation network를 포함해 기존에 보고된 power-law network 다수를 power-law로 분류하는 반면, 알려진 non-power-law network는 그렇지 않은 것으로 분류한다.not power-law로 분류된 사례로는 California road network와 Amazon의 방향성 out-degree sequence가 있다.
VI. 실세계 네트워크: 유한한 degree sequence에서는 서로 다른 exponent estimate가 나올 수 있으므로, 연구에서는 distribution의 서로 다른 부분을 살펴볼 수 있는 일관된 multiple estimator를 사용할 것을 강조한다.이 문제는 slowly varying function ℓ(k)가 nontrivial할 때 특히 중요하며, 이론적으로 정당화된 order statistic의 bootstrap 선택을 통해 안정적이고 효율적인 estimator의 maximal subset을 구성하게 된다.
VI. 실세계 네트워크: 도출된 prevalence estimate는 의 앞선 비교와 substantially different picture를 제시하지만, 결과를 직접 비교할 수는 없다.비교는 직접적인 수치 평가가 아니라 질적인 대조로 제시된다.

VII. 결론 및 논의 · 부록 A: Heavy tail을 갖는 분포의 유형

이 논문은 power law를 regularly varying distribution으로 정의하고, 일관된 extreme-value estimator를 사용해 scale-free network가 드물지 않음을 보인다. 논의에서는 중요한 한계와 미해결 문제를 제시하며, 부록 A에서는 regularly varying distribution을 더 넓은 heavy-tailed 분류 체계 안에 위치시킨다.

VII. 결론 및 논의: Power law는 regularly varying distribution으로 정의되며, Pareto distribution과 zeta distribution은 그중 작은 pure-power-law 부분집합이다.Regular variation은 실제 network에서 “log-log scale에서의 직선”이라는 직관을 형식화하는 포괄적 틀을 제공한다.
VII. 결론 및 논의: Extreme-value theory는 일관된 tail-exponent estimator와 degree sequence를 위한 분류 체계를 제공한다.이 접근법은 regularly varying distribution과 Fréchet distribution의 maximum domain of attraction 사이의 연결을 이용한다.
VII. 결론 및 논의: Regular-variation 분류는 power-law distribution을 생성할 수 있는 network mechanism을 다루지 않는다.Mechanism은 network 진화를 구동하는 stochastic process를 근사하는 서로 다른 network model에 대응하므로 별도의 주제다.
VII. 결론 및 논의: 유한 표본에 대한 regular-variation 주장은 regularly varying distribution에 대해서는 hypothesis testing이 불가능하므로 p-value와 같은 통계적 가중치를 부여받을 수 없다.따라서 논의에서는 유한 sequence에 유의성 값을 부여하기보다 empirical power-law detection의 다른 측면을 개선하는 데 초점을 둔다.
VII. 결론 및 논의: 미해결 문제로는 i.i.d. 가정 완화, 수렴 속도 확립, network snapshot sequence 처리, integer-valued degree를 위한 신뢰할 수 있는 estimator 설계가 있다.기존 estimator는 고려한 실험에서 수렴하지만, preferential attachment를 넘어서는 수렴 증명은 없으며 integer-valued data는 불안정성과 느린 수렴을 일으킬 수 있다.
VII. 결론 및 논의: Double-bootstrap 일관성 증명에는 Pareto distribution과 zeta distribution이 위반하는 second-order condition이 필요하지만, 실험에서는 수렴한다.따라서 이 경우의 empirical convergence에는 이에 대응하는 일관성 증명이 없다.
VII. 결론 및 논의: 대표적인 실제 degree sequence에 일관된 estimator를 적용한 결과 scale-free network가 드물지 않음이 확인된다.이 estimator는 엄밀한 empirical power-law detection에서 현재의 state of the art를 나타내며, 구현은 에서 이용할 수 있다.
부록 A: Heavy tail을 갖는 분포의 유형: Heavy-tailed distribution은 부록 A에서 가장 포괄적인 분포군을 이루며, exponential보다 더 느리게 감소하는 tail로 특징지어진다.부록에서는 이 분류 체계를 검토하고, regularly varying distribution을 자주 접하는 가장 단순한 분포군으로 소개한다.

1. 두꺼운 꼬리 분포 … 1. 극값 분포와 그 최대 유인 영역

이 논문은 두꺼운 꼬리 분포의 광범위한 부류를 regularly varying distribution으로 좁힌다. 이 분포는 유용한 꼬리 특성을 유지하면서 추론에 다루기 쉬운 표현을 제공한다. 이어서 regular variation을 Fréchet 극값 극한과 연결하고, 이 틀을 사용해 꼬리 지수를 추정한다.

1. 두꺼운 꼬리 분포: 두꺼운 꼬리 분포의 CCDF는 지수적으로 감소하는 것보다 더 느리게 감소하지만, 이 부류는 광범위하여 일반적인 형태로 다루기 어렵다.Long-tailed distribution과 subexponential distribution은 더 좁은 부분 부류이며, regularly varying distribution은 후자의 특히 다루기 쉬운 부분 부류를 이룬다.
1. 두꺼운 꼬리 분포: Regularly varying distribution은 subexponential 거동을 물려받는다. 충분히 큰 합은 여러 개의 중간 크기 항보다 하나의 비정상적으로 큰 합산항에 의해 발생하는 경우가 일반적이다.Regularly varying 부류는 heavy-tailed 부류보다 엄밀히 좁지만, 통계적 추론에 유용한 간결한 표현을 갖는다.
2. Regularly varying distribution: Regularly varying distribution은 CCDF가 power function과 slowly varying function의 곱으로 주어지는 분포로 정의되며, 논문은 이 부류를 power-law distribution의 정의로 사용한다.이 분포는 높은 변동성을 모델링할 수 있지만, regular variation이 성립하지 않는다고 해서 해당 분포가 heavy-tailed도 subexponential도 아니라는 뜻은 아니다. lognormal이 그 반례다.
3. Regularly varying distribution의 가장 단순한 예: Regular variation은 Pareto 변수에 flooring을 적용하거나 Poisson distribution을 Pareto 평균과 혼합하는 경우를 포함해, 실제적인 degree-distribution 구성에서도 보존된다.Mixed Poisson distribution은 Pareto mixing variable과 동일한 기댓값과 꼬리 지수를 가지며, hidden-variable 및 graphon 기반 network model에서 나타난다.
Appendix B: Regularly varying distribution의 꼬리 지수에 대한 일관된 추정량: 꼬리 지수에 사용되는 추정량은 extreme-value index를 대상으로 설계되었으며, 분포가 extreme-value maximum domain of attraction에 속한다는 더 넓은 가정 아래에서 consistent하다.모든 regularly varying distribution은 이 가정을 만족하므로, extreme-value theory 틀을 사용하는 근거가 된다.
1. 극값 분포와 그 최대 유인 영역: Extreme-value theory는 정규화된 최댓값이 non-degenerate limit으로 수렴하는지를 연구하며, 그 극한은 지수 매개변수 ξ로 분류된다.적절한 위치 및 척도 수열을 사용했을 때 정규화된 최댓값이 수렴하면, 해당 분포는 extreme-value maximum domain of attraction에 속한다.
1. 극값 분포와 그 최대 유인 영역: Regular variation은 Fréchet maximum domain of attraction에 속하는 것과 정확히 동치이며, 꼬리 지수 γ는 extreme-value index ξ = 1/(γ−1)에 대응한다.따라서 추정량은 regularly varying 꼬리 지수에 대응하는 Fréchet index를 추정한다.

2. Hill’s estimator … Appendix C: 경험적 degree sequence의 tail exponent 추정

이 논문은 regularly varying distributions와 더 넓은 extreme-value domains를 포괄하는 일관된 tail-exponent estimator를 제시하고, 경험적 degree sequence에서 발생하는 finite-sample irregularity와 실무적 문제를 다룬다. 이어 기술적으로 명시된 절차를 사용해 synthetic 및 real-world network data에 이 방법들을 적용한다.

2. Hill’s estimator: Hill’s estimator 는 κ/n → 0이고 κ → ∞일 때 tail exponent γ > 1인 모든 regularly varying distribution에 대해 일관적이다.이는 의 Theorems 4.1과 4.2에서 따른다.
3. Moments estimator: Moments estimator 는 κ/n → 0, κ → ∞, log(n)^δ/κ → 0 조건에서 Fréchet-domain distributions를 넘어 모든 extreme-value domains로 consistency를 확장한다.어떤 δ > 0에 대해 이 조건들이 성립하면 estimator는 임의의 ξ ∈ R에 대해 almost surely 수렴한다.
4. Kernel estimator: Kernel estimator 는 n → ∞, h → 0, hn → ∞일 때 임의의 ξ ∈ R에 대해 일관되게 적용 가능하다.가능한 singularity를 피하기 위해 사용자가 선택한 kernel φ와 parameter λ > 1/2를 사용한다.
Appendix C: 경험적 degree sequence의 tail exponent 추정: 경험적 degree sequence에서는 Kernel estimator가 logarithmically spaced fraction h_i ∈ [1/n, 1]을 스캔하며, tail을 더 조밀하게 조사하기 위해 s = [0.3n]개의 값을 사용한다.구현에서는 규정된 kernel procedure로 최적의 h*를 찾은 뒤 κ* = ⌊nh*⌋를 선택한다.
5. Smooth Hill estimator: smooth Hill estimator 는 [κ + 1, rκ]에 걸쳐 Hill estimate를 평균내어 erratic finite-sample behavior를 억제하면서도 모든 integer r ≥ 2에 대해 일관성을 유지한다.따라서 original Hill estimator보다 stable region을 쉽게 식별할 수 있다.
6. Pickands estimator: Pickands estimator 는 임의의 ξ ∈ R에 대해 일관적이며 regular variation이 타당한지 실무적으로 점검할 수 있게 한다.κ의 함수가 전부 음수라면 regularly varying 가정을 뒷받침하기 어렵다.
6. Pickands estimator: Pickands estimate는 tied integer-valued data에서 정의되지 않을 수 있고 volatile하며 inefficient하고 high-variance이지만, uniform noise는 tie를 일관되게 해소한다.Estimator의 단점 때문에 generalized Pickands variants 가 제안되었다.

1. 최적 order statistics 개수 찾기

유한 표본 추정량은 최댓값 관측치 개수 κ에 의존하므로, 이 논문은 AMSE 기반 double bootstrap을 사용해 κ를 선택한다. 이 선택은 second-order condition하에서 이론적으로 일관되지만, 실험에서는 해당 조건이 성립하지 않을 때도 좋은 성능을 보였다.

1. 최적 order statistics 개수 찾기: 유한한 empirical degree sequence에서는 추정량이 κ개의 최댓값 표본만 사용하므로 κ가 자유 매개변수로 남으며, 일관성은 κ와 n이 모두 발산할 때에만 확립된다.따라서 이 절에서는 점근적 일관성 결과를 유한 표본에 자동으로 적용되는 처방으로 간주하지 않고 κ∗를 선택하는 데 초점을 둔다.
1. 최적 order statistics 개수 찾기: AMSE 기반 double bootstrap은 bootstrap 표본들에서 두 개의 일관된 추정량을 결합해 최적 κ∗를 추정하며, 일관성, 안정성, 적용 가능성 을 기준으로 선택된다.이는 empirical asymptotic mean squared error를 최소화하고, 두 bootstrap 표본 크기에서 절차를 반복한 뒤 원자료에 사용할 κ를 선택한다.
1. 최적 order statistics 개수 찾기: 구현에서는 기본값으로 r = 500개의 bootstrap 표본과 t = 1/2를 사용하므로, 두 번째 bootstrap 표본 크기는 n2 = n/2가 된다.여기서 r은 bootstrap 표본의 개수이고 t는 첫 번째와 두 번째 bootstrap 표본의 크기를 결정한다.
1. 최적 order statistics 개수 찾기: Bootstrap 일관성 증명에는 second-order condition이 필요하므로, 이 조건이 없는 분포에서는 수렴이 보장되지 않지만 실험에서는 그러한 경우에도 좋은 성능을 보였다.이 논문은 실제 데이터에서 해당 조건을 검증하기 어렵거나 불가능할 수 있다고 지적하지만, 실험에서는 결과 추정치가 실제 값에 빠르게 수렴했다.

2. 정수 데이터 다루기

정수값 degree sequence는 일관된 power-law estimator를 불안정하게 만들 수 있으므로, 이 논문은 tail exponent를 바꾸지 않으면서 안정성을 높이기 위해 estimation 전에 균일 대칭 noise를 추가한다.

2. 정수 데이터 다루기: 연속 regularly varying sample을 반올림하면, sample sequence와 order statistic의 개수 κ의 함수로서 consistent estimator가 불규칙하게 작동할 수 있다.반올림된 sequence가 동일한 exponent를 갖는 regularly varying sequence로 남아 있음에도 이러한 불안정성이 발생한다.
2. 정수 데이터 다루기: 균일 대칭 noise는 tail exponent를 바꾸지 않으면서 정수값 sequence에서 estimator 안정성과 수렴을 크게 향상한다.y_i = x_i + u_i에서 noise variable u_i는 [−1/2, 1/2]에서의 i.i.d. uniform 분포를 따른다.
2. 정수 데이터 다루기: 추가된 noise가 없으면, 세 estimator는 noise가 있는 경우보다 Zeta distribution에서 추출한 정수 sample에서 더 큰 relative root mean squared error를 보인다.Figure 5는 다양한 sequence length n과 exponent γ를 평가한다.

3. double bootstrap 방법을 사용한 estimator 작동 예시

double-bootstrap 예시는 consistent estimator가 유한한 empirical degree distribution의 서로 다른 부분을 분석할 수 있으며, slowly varying function이 trivial하지 않을 때 서로 다른 estimate를 산출함을 보여준다. 따라서 real-world network data에는 여러 consistent estimator를 사용할 것을 권장한다.

Estimator 작동: 서로 다른 consistent estimator는 유한한 empirical degree distribution의 서로 다른 부분을 탐색할 수 있으며, 이로 인해 서로 다른 estimate를 반환할 수 있다.slowly varying function ℓ(k)이 trivial하지 않을 때 특히 중요하다.
Estimator 작동: Hill estimator는 Libimseti’s in-degree sequence에 대해 더 높은 α = 1/ξ estimate를 제공하는데, 이는 최적 κ∗가 다른 estimator들의 값보다 상당히 작기 때문이다.따라서 Hill은 distribution tail의 더 작은 부분을 분석하며, κ∗는 AMS criterion을 최소화하여 선택된다.
Estimator convergence: regularly varying distribution에서 추출한 small sample의 경우, estimator convergence는 “nice”한 slowly varying function ℓ(k)과 “not so nice”한 slowly varying function ℓ(k) 사이에서 달라질 수 있다.estimator는 infinite-sample limit n →∞에서만 임의의 ℓ(k)에 대해 true ξ로 수렴하며, convergence speed는 ℓ(k)의 알려지지 않은 성질에 좌우될 수 있다.
실용적 권고: real-world network data에는 가능한 한 많은 consistent estimator를 적용하는 것이 권장 전략이다.이는 estimator가 distribution의 서로 다른 영역을 분석하면서 발생하는 finite-sample 차이와 불확실한 convergence behavior에서 비롯된 권고다.

Appendix D: 합성 수열 및 네트워크 모델에 대한 평가

Appendix D에서는 합성 degree sequence와 네트워크 모델에 extreme-value-theory estimator를 적용하고, 이를 PLFit과 비교한다.

평가 설정: Hill, Moments, Kernel estimator는 double-bootstrap procedure와 함께 극값이론을 사용한다.Appendix에서는 의 코드를 사용한다.
평가 설정: 이 estimator들은 기대한 결과를 산출하는지 평가하기 위해 합성 degree sequence와 네트워크 모델에 적용된다.
추정량 비교: 부록에서는 maximum-likelihood-inspired 기법과 Kolmogorov-Smirnov distance 최소화를 결합한 PLFit 과 이들의 추정값을 비교한다.

1. 합성 시퀀스

깨끗한 분포, 혼합 분포, cutoff 분포, double-power-law 분포를 아우르는 합성 시퀀스로 표본 크기와 tail exponent에 따른 estimator 정확도를 검증한다. EV estimator는 regularly varying 데이터에서 수렴하고 고정된 non-regularly-varying 데이터에서는 실패하며, PLFit은 깨끗한 zeta 데이터에서 가장 우수하지만 그 외에는 대체로 비슷한 성능을 보인다.

1. 합성 시퀀스: 벤치마크는 zeta, Pareto-mixed Poisson, exponential-cutoff Pareto, double power law family를 비롯해 네트워크와 관련된 다양한 분포에서 생성한 합성 시퀀스를 다룬다.분포에 degree zero가 포함된 경우 시퀀스에서 0인 원소를 제외하며, 시퀀스 길이, tail exponent, 분포 형태를 변화시킨다.
1. 합성 시퀀스: Double power law는 exponent γ를 갖는 regularly varying 분포지만, 작은 표본에서는 estimator가 대신 lower-tail exponent γ0를 식별할 수 있다.실험에서는 γ0 = 1.5, c = 500, r = 0.1로 설정하고 γ를 변화시킨다.
1. 합성 시퀀스: EV estimator는 regularly varying 시퀀스와 cutoff가 발산하는 분포에서 수렴하지만, 고정된 non-regularly-varying cutoff에서는 어떤 estimator도 수렴하지 않는다.실험에서는 각 분포, exponent, 표본 크기 조합마다 100개 시퀀스를 사용하고 relative root-mean-squared error를 평가한다.
1. 합성 시퀀스: 깨끗한 zeta 분포에서는 PLFit의 estimation error가 더 낮지만, 충분히 양호한 regularly varying 분포에서는 EV와 PLFit의 정확도 및 수렴 속도가 비슷하다.Zeta 분포는 상수 slowly varying function ℓ(k)를 가지며, ℓ(k)가 빠르게 수렴하면 두 estimator의 성능이 비슷해진다.

2. 네트워크 모델

이 연구는 여러 지수와 네트워크 크기에서 세 가지 비-i.i.d. 네트워크 모델의 degree sequence에 EV 기반 tail-exponent estimator를 적용해 평가한다. 모든 EV estimator가 수렴하며, γ = 2.1과 γ = 3인 preferential attachment에서는 PLFit보다 우수하다.

네트워크 모델: 실험에는 degree distribution이 regularly varying limit으로 수렴하는 erased configuration, preferential attachment, hyperbolic random graph model을 사용한다.이 모델들은 dependence의 영향을 받아 EV-estimator 성능이 달라지는지 검증할 수 있는 비-i.i.d. degree sequence를 제공한다.
실험 설계: 각 모델에서 γ ∈ {2.1, 2.5, 3.0}와 네트워크 크기 n을 10^3에서 10^6까지 변화시키고, 각 조합마다 100개의 random network를 생성한다.생성된 degree sequence는 RRMSE (D7)를 사용해 모든 고려 대상 estimator로 분석한다.
결과: degree sequence가 비-i.i.d.임에도 모든 EV estimator가 수렴하지만, 유한 네트워크의 degree distribution이 limiting distribution에 느리게 접근할 때는 수렴이 느리다.γ = 2에 가까워질수록 Pareto-mixed Poisson limit에 더 느리게 접근하기 때문에, γ = 2.1인 HRG에서는 수렴이 특히 느리다.
결과: preferential attachment에서는 γ = 2.1과 γ = 3일 때 EV estimator가 PLFit보다 명확히 우수하며, γ = 2.5에서는 모든 estimator의 성능이 비슷하다.성능은 Fig. 9에 제시된 네트워크 모델, 지수, 크기 전반에서 relative root mean squared error (RRMSE)로 측정한다.

3. PLFit의 해부

PLFit는 후보 지수에 대한 likelihood maximization과 degree threshold에 대한 KS-distance minimization을 결합하며, 선택된 threshold 이상에서 순수 power-law tail을 가정한다. KS minimization이 지나치게 작은 threshold를 선택하고, 그 결과 MLE가 점근적 tail exponent가 아니라 국소 PDF slope를 추정하기 때문에 오차가 발생한다.

알고리즘: PLFit는 후보 γ 값에 대한 generalized-zeta likelihood를 maximization하고 관측된 degree threshold 전반에서 KS distance를 minimization하여 exponent와 threshold를 함께 선택한다.반환되는 추정값은 가장 작은 KS distance에 대응하는 γ와 k_min이다.
결과: double power law와 preferential attachment에서는 PLFit가 검토한 extreme-value estimator보다 더 느리게 수렴하며, 국소 slope가 실제 tail exponent와 다를 때 그 추정값이 상당히 틀릴 수 있다.이처럼 부정확한 추정값으로 KS testing을 적용하면 추정 exponent와 실제 exponent가 다르기 때문에 순수 power-law 가설을 기각할 수 있다.
KS distance minimization: regularly varying distribution에는 더 작은 degree 부근의 관측값이 더 많이 포함되어 국소 empirical-CDF deviation이 감소하므로, KS minimization은 PLFit를 잘못되게 낮은 k_min 값으로 이끈다.Figure 10은 double power-law sample에서 이 메커니즘을 보여준다.
Likelihood maximization: 작은 k_min에서는 PLFit의 MLE component가 점근적 tail exponent보다 해당 threshold 부근의 log-log PDF slope를 주로 fit한다.이는 국소 slope와 tail slope가 다를 때 PLFit가 어떤 경우에는 정확하지만 상당히 벗어날 수 있는 이유를 설명한다.