{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T16:05:42Z","timestamp":1778601942907,"version":"3.51.4"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2021,5,19]],"date-time":"2021-05-19T00:00:00Z","timestamp":1621382400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000183","name":"U. S. Army Research Office","doi-asserted-by":"crossref","award":["W911NF-19-1-0365"],"award-info":[{"award-number":["W911NF-19-1-0365"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Science Foundation","award":["CCF-1714180"],"award-info":[{"award-number":["CCF-1714180"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2021,6,28]]},"abstract":"<jats:p>\n            This article considers the problem of estimating a power-law degree distribution of an undirected network using sampled data. Although power-law degree distributions are ubiquitous in nature, the widely used parametric methods for estimating them\u00a0(e.g.,\u00a0linear regression on double-logarithmic axes and maximum likelihood estimation with uniformly sampled nodes) suffer from the large variance introduced by the lack of data-points from the tail portion of the power-law degree distribution. As a solution, we present a novel maximum likelihood estimation approach that exploits the\n            <jats:italic>friendship paradox<\/jats:italic>\n            to sample more efficiently from the tail of the degree distribution. We analytically show that the proposed method results in a smaller bias, variance and a Cram\u00e8r\u2013Rao lower bound compared to the vanilla maximum likelihood estimate obtained with uniformly sampled nodes\u00a0(which is the most commonly used method in literature). Detailed numerical and empirical results are presented to illustrate the performance of the proposed method under different conditions and how it compares with alternative methods. We also show that the proposed method and its desirable properties (i.e.,\u00a0smaller bias, variance, and Cram\u00e8r\u2013Rao lower bound compared to vanilla method based on uniform samples) extend to parametric degree distributions other than the power-law such as exponential degree distributions as well. All the numerical and empirical results are reproducible and the code is publicly available on Github.\n          <\/jats:p>","DOI":"10.1145\/3451166","type":"journal-article","created":{"date-parts":[[2021,5,19]],"date-time":"2021-05-19T17:08:53Z","timestamp":1621444133000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Maximum Likelihood Estimation of Power-law Degree Distributions via Friendship Paradox-based Sampling"],"prefix":"10.1145","volume":"15","author":[{"given":"Buddhika","family":"Nettasinghe","sequence":"first","affiliation":[{"name":"Cornell University, Ithaca, New York"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vikram","family":"Krishnamurthy","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, New York"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,5,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335326"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-020-14394-x"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Ioannis E. Antoniou and E.T. Tsompa. 2008. Statistical analysis of weighted networks. Discrete Dynamics in Nature and Society 2008 4 (2008).  Ioannis E. Antoniou and E.T. Tsompa. 2008. Statistical analysis of weighted networks. Discrete Dynamics in Nature and Society 2008 4 (2008).","DOI":"10.1155\/2008\/375452"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3110025.3110027"},{"key":"e_1_2_1_5_1","volume-title":"Emergence of scaling in random networks. Science 286, 5439","author":"Barab\u00e1si Albert-L\u00e1szl\u00f3","year":"1999","unstructured":"Albert-L\u00e1szl\u00f3 Barab\u00e1si and R\u00e9ka Albert . 1999. Emergence of scaling in random networks. Science 286, 5439 ( 1999 ), 509\u2013512. Albert-L\u00e1szl\u00f3 Barab\u00e1si and R\u00e9ka Albert. 1999. Emergence of scaling in random networks. Science 286, 5439 (1999), 509\u2013512."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0400087101"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1140\/epjb\/e2007-00219-y"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/644108.644133"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-019-08746-5"},{"key":"e_1_2_1_10_1","first-page":"61","article-title":"The friendship paradox","volume":"41","author":"Cao Yang","year":"2016","unstructured":"Yang Cao and Sheldon M. Ross . 2016 . The friendship paradox . Mathematical Scientist 41 , 1 (2016), 61 \u2013 64 . Yang Cao and Sheldon M. Ross. 2016. The friendship paradox. Mathematical Scientist 41, 1 (2016), 61\u201364.","journal-title":"Mathematical Scientist"},{"key":"e_1_2_1_11_1","volume-title":"Berger","author":"Casella George","year":"2002","unstructured":"George Casella and Roger L . Berger . 2002 . Statistical Inference. Vol. 2 . Duxbury Pacific Grove, CA. George Casella and Roger L. Berger. 2002. Statistical Inference. Vol. 2. Duxbury Pacific Grove, CA."},{"key":"e_1_2_1_12_1","volume-title":"Chassin and Christian Posse","author":"David","year":"2005","unstructured":"David P. Chassin and Christian Posse . 2005 . Evaluating North American electric grid reliability using the Barab\u00e1si\u2013Albert network model. Physica A: Statistical Mechanics and its Applications 355, 2-4 (2005), 667\u2013677. David P. Chassin and Christian Posse. 2005. Evaluating North American electric grid reliability using the Barab\u00e1si\u2013Albert network model. Physica A: Statistical Mechanics and its Applications 355, 2-4 (2005), 667\u2013677."},{"key":"e_1_2_1_13_1","volume-title":"Evaluating stochastic seeding strategies in networks. arXiv preprint arXiv:1809.09561","author":"Chin Alex","year":"2018","unstructured":"Alex Chin , Dean Eckles , and Johan Ugander . 2018. Evaluating stochastic seeding strategies in networks. arXiv preprint arXiv:1809.09561 ( 2018 ). Alex Chin, Dean Eckles, and Johan Ugander. 2018. Evaluating stochastic seeding strategies in networks. arXiv preprint arXiv:1809.09561 (2018)."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0012948"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/070710111"},{"key":"e_1_2_1_16_1","unstructured":"Aaron Clauset Ellen Tucker and Matthias Sainz. [n.d.]. The Colorado Index of Complex Networks. Retrieved from https:\/\/icon.colorado.edu\/#!\/.  Aaron Clauset Ellen Tucker and Matthias Sainz. [n.d.]. The Colorado Index of Complex Networks. Retrieved from https:\/\/icon.colorado.edu\/#!\/."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.85.4626"},{"key":"e_1_2_1_18_1","volume-title":"Nehemia Schwartz, Daniel Ben-Avraham, and Shlomo Havlin.","author":"Cohen Reuven","year":"2003","unstructured":"Reuven Cohen , Alejandro Fabian Rozenfeld , Nehemia Schwartz, Daniel Ben-Avraham, and Shlomo Havlin. 2003 . Directed and non-directed scale-free networks. In Statistical Mechanics of Complex Networks. Springer , 23\u201345. Reuven Cohen, Alejandro Fabian Rozenfeld, Nehemia Schwartz, Daniel Ben-Avraham, and Shlomo Havlin. 2003. Directed and non-directed scale-free networks. In Statistical Mechanics of Complex Networks. Springer, 23\u201345."},{"key":"e_1_2_1_19_1","volume-title":"Wang","author":"Deng Weibing","year":"2011","unstructured":"Weibing Deng , Wei Li , Xu Cai , and Qiuping A . Wang . 2011 . The exponential degree distribution in complex networks: Non-equilibrium network theory, numerical simulation and empirical data. Physica A: Statistical Mechanics and its Applications 390, 8 (2011), 1481\u20131485. Weibing Deng, Wei Li, Xu Cai, and Qiuping A. Wang. 2011. The exponential degree distribution in complex networks: Non-equilibrium network theory, numerical simulation and empirical data. Physica A: Statistical Mechanics and its Applications 390, 8 (2011), 1481\u20131485."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1869916"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.66.035103"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.94.018102"},{"key":"e_1_2_1_23_1","first-page":"1","article-title":"Generalized friendship paradox in complex networks: The case of scientific collaboration","volume":"4","author":"Eom Young-Ho","year":"2014","unstructured":"Young-Ho Eom and Hang-Hyun Jo . 2014 . Generalized friendship paradox in complex networks: The case of scientific collaboration . Scientific Reports 4 , 1 (April 2014), 4603. Young-Ho Eom and Hang-Hyun Jo. 2014. Generalized friendship paradox in complex networks: The case of scientific collaboration. Scientific Reports 4, 1 (April 2014), 4603.","journal-title":"Scientific Reports"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1038\/srep09752"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/316194.316229"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1086\/229693"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.economics.050708.142940"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0092413"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1140\/epjb\/e2004-00316-5"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2086737.2086741"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2346183"},{"key":"e_1_2_1_32_1","article-title":"Centrality-friendship paradoxes: When our friends are more important than us","volume":"7","author":"Higham Desmond J.","year":"2018","unstructured":"Desmond J. Higham . 2018 . Centrality-friendship paradoxes: When our friends are more important than us . Journal of Complex Networks 7 , 4 (11 2018), 515\u2013528. Desmond J. Higham. 2018. Centrality-friendship paradoxes: When our friends are more important than us. Journal of Complex Networks 7, 4 (11 2018), 515\u2013528.","journal-title":"Journal of Complex Networks"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 7th International AAAI Conference on Weblogs and Social Media.","author":"Hodas Nathan O.","year":"2013","unstructured":"Nathan O. Hodas , Farshad Kooti , and Kristina Lerman . 2013 . Friendship paradox redux: Your friends are more interesting than you . In Proceedings of the 7th International AAAI Conference on Weblogs and Social Media. Nathan O. Hodas, Farshad Kooti, and Kristina Lerman. 2013. Friendship paradox redux: Your friends are more interesting than you. In Proceedings of the 7th International AAAI Conference on Weblogs and Social Media."},{"key":"e_1_2_1_34_1","volume-title":"Adamic","author":"Huberman Bernardo A.","year":"1999","unstructured":"Bernardo A. Huberman and Lada A . Adamic . 1999 . Internet : Growth dynamics of the world-wide web. Nature 401, 6749 (1999), 131. Bernardo A. Huberman and Lada A. Adamic. 1999. Internet: Growth dynamics of the world-wide web. Nature 401, 6749 (1999), 131."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1086\/701031"},{"key":"e_1_2_1_36_1","volume-title":"Oltvai","author":"Jeong Hawoong","year":"2001","unstructured":"Hawoong Jeong , Sean P. Mason , A.-L. Barab\u00e1si , and Zoltan N . Oltvai . 2001 . Lethality and centrality in protein networks. Nature 411, 6833 (2001), 41. Hawoong Jeong, Sean P. Mason, A.-L. Barab\u00e1si, and Zoltan N. Oltvai. 2001. Lethality and centrality in protein networks. Nature 411, 6833 (2001), 41."},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 8th International AAAI Conference on Weblogs and Social Media.","author":"Kooti Farshad","year":"2014","unstructured":"Farshad Kooti , Nathan O. Hodas , and Kristina Lerman . 2014 . Network weirdness: Exploring the origins of network paradoxes . In Proceedings of the 8th International AAAI Conference on Weblogs and Social Media. Farshad Kooti, Nathan O. Hodas, and Kristina Lerman. 2014. Network weirdness: Exploring the origins of network paradoxes. In Proceedings of the 8th International AAAI Conference on Weblogs and Social Media."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSIPN.2017.2697940"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2684822.2685293"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.99.052302"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0147617"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150479"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217299.1217301"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129088"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0143633"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1177\/0008068319570303"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2013.130604"},{"key":"e_1_2_1_48_1","unstructured":"Buddhika Nettasinghe and Vikram Krishnamurthy. [n.d.]. Simulation Code Repository. Retrieved from https:\/\/github.com\/ComplexInfo\/Powerlaw_Estimation.  Buddhika Nettasinghe and Vikram Krishnamurthy. [n.d.]. Simulation Code Repository. Retrieved from https:\/\/github.com\/ComplexInfo\/Powerlaw_Estimation."},{"key":"e_1_2_1_49_1","first-page":"1291","article-title":"What do your friends think?\u201d: Efficient polling methods for networks using friendship paradox","volume":"33","author":"Nettasinghe Buddhika","year":"2021","unstructured":"Buddhika Nettasinghe and Vikram Krishnamurthy . 2021 . \u201c What do your friends think?\u201d: Efficient polling methods for networks using friendship paradox . IEEE Transactions on Knowledge & Data Engineering 33 , 03 (2021), 1291 \u2013 1305 . Buddhika Nettasinghe and Vikram Krishnamurthy. 2021. \u201cWhat do your friends think?\u201d: Efficient polling methods for networks using friendship paradox. IEEE Transactions on Knowledge & Data Engineering 33, 03 (2021), 1291\u20131305.","journal-title":"IEEE Transactions on Knowledge & Data Engineering"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2019.2909015"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450342480"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1080\/00107510500052444"},{"key":"e_1_2_1_53_1","volume-title":"Piet Van Mieghem, and Alessandro Vespignani","author":"Pastor-Satorras Romualdo","year":"2015","unstructured":"Romualdo Pastor-Satorras , Claudio Castellano , Piet Van Mieghem, and Alessandro Vespignani . 2015 . Epidemic processes in complex networks. Reviews of modern physics 87, 3 (2015), 925. Romualdo Pastor-Satorras, Claudio Castellano, Piet Van Mieghem, and Alessandro Vespignani. 2015. Epidemic processes in complex networks. Reviews of modern physics 87, 3 (2015), 925."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.86.3200"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1879141.1879192"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2012.6425857"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1214\/13-AOAS710"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1088\/0256-307X\/26\/11\/118901"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0110121"},{"key":"e_1_2_1_60_1","first-page":"79","article-title":"Computing the distribution of a linear combination of inverted gamma variables","volume":"37","author":"Witkovsk\u1ef3 Viktor","year":"2001","unstructured":"Viktor Witkovsk\u1ef3 . 2001 . Computing the distribution of a linear combination of inverted gamma variables . Kybernetika 37 , 1 (2001), 79 \u2013 90 . Viktor Witkovsk\u1ef3. 2001. Computing the distribution of a linear combination of inverted gamma variables. Kybernetika 37, 1 (2001), 79\u201390.","journal-title":"Kybernetika"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3451166","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3451166","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3451166","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:25Z","timestamp":1750268965000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3451166"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,19]]},"references-count":60,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,6,28]]}},"alternative-id":["10.1145\/3451166"],"URL":"https:\/\/doi.org\/10.1145\/3451166","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,19]]},"assertion":[{"value":"2020-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-05-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}