Distinguishing subsampled power laws from other heavy-tailed distributions
Loading...
URL
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
2020-10-19
Department
Major/Subject
Complex Systems
Mcode
SCI3060
Degree programme
Master’s Programme in Life Science Technologies
Language
en
Pages
46+7
Series
Abstract
Distinguishing power law distributions from other heavy-tailed distributions is challenging, and this task is often further complicated by subsampling effects. In this Thesis, we assess how well two commonly used methods for detecting power law distributions - the methods of Clauset et al. and Voitalovet al. - succeed in distinguishing subsampled power laws from two other heavy-tailed distributions, the lognormal and the stretched exponential distributions, when the data is subsampled with a fairly common sampling scheme, the incident subgraph sampling. The overall aim of this Thesis is to understand the extent to which the results obtained for a subsample with very low sampling depth can be generalized to the original degree distribution. Our results show that the power law exponent of the original distribution can be estimated fairly accurately from subsamples, but classifying the distribution correctly is more challenging. Clauset's method mistakenly rejects the power law hypothesis for a large fraction of the subsamples from power law distributions. While Voitalov's method correctly recognizes subsampled power law distributions with all tested sampling depths, its capacity to distinguish power laws from the heavy-tailed alternatives is limited. However, these misclassifications tend to result not from the subsampling itself but from the estimators' inability to classify the original sample correctly. In fact, we show that Voitalov's method can often be excepted to perform better on subsamples than on the original samples from the lognormal and the stretched exponential distributions, while the contrary is true for Clauset's method. Both methods succeed in distinguishing subsampled exponential distributions from power laws. Finally, we apply the methods to a dataset from the field of immunology, more specifically the sampled clone size distribution of human T-cell receptors' alpha chains in the thymus, and draw tentative conclusions about the original clone size distribution.Potenssilakien tunnistaminen ja niiden erottaminen muista leveähäntäisistä jakaumista on tunnetusti haastavaa, ja tämä tehtävä muuttuu entistä vaikeammaksi, jos analyysi perustuu otoksiin. Tässä diplomityössä selvitetään, kuinka hyvin kaksi potenssilakien tunnistamiseen yleisesti käytettyä metodia - Clauset'n ja Voitalovin metodit - onnistuvat erottamaan otokset potenssilakijakaumasta ja kahdesta muusta leveähäntäisestä jakaumasta, log-normaalista ja leveähäntäisestä Weibull-jakaumasta. Otannassa käytetään menetelmää, jossa verkoston linkit valitaan satunnaisesti ja kaikki linkkeihin kiinnittyneet solmut valitaan mukaan otokseen. Työn tavoitteena on selvittää, missä määrin otoksista saadut tulokset ovat yleistettävissä verkoston alkuperäiseen astejakaumaan. Tulokset osoittavat, että alkuperäisen potenssilain eksponentti voidaan arvioida pienistäkin otoksista suhteellisen tarkasti, kun taas otosten jakaumatyypin luokittelu on haasteellisempaa. Clauset'n metodi hylkää potenssilakihypoteesin virheellisesti monien potenssilakijakaumasta simuloitujen otosten kohdalla. Voitalovin metodi puolestaan luokittelee oikein otokset potenssilakijakaumista, mutta erehtyy pitämään monia otoksia muista leveähäntäisistä jakaumista potenssilakeina. Virheelliset luokittelut eivät kuitenkaan johdu otannasta sinänsä vaan Voitalovin metodin kyvyttömyydestä tunnistaa alkuperäinen jakauma. Metodien odotusarvoisten tulosten tarkastelu osoittaa, että Voitalovin metodin voi odottaa onnistuvan paremmin otosten kuin alkuperäisten jakaumien luokittelussa otoskoon kasvaessa rajatta, kun taas Clauset'n metodin kyky erotella jakaumia heikkenee, mitä pienemmällä todennäköisyydellä verkoston linkit valitaan mukaan otokseen. Molemmat metodit luokittelevat otokset eksponentiaalisista jakaumista oikein. Lopuksi sovellamme metodeja immunologisen puolustusjärjestelmän kannalta keskeisten T-solujen TCR-alpha-ketjujen kloonikokojakaumaan ja esitämme alustavia johtopäätöksiä alkuperäisestä kloonikokojakaumasta.Description
Supervisor
Saramäki, JariThesis advisor
Saramäki, JariKeywords
power laws, scale-free networks, heavy-tailed distributions, sampling