{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:35:42Z","timestamp":1772120142815,"version":"3.50.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,11,17]],"date-time":"2023-11-17T00:00:00Z","timestamp":1700179200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,11,17]],"date-time":"2023-11-17T00:00:00Z","timestamp":1700179200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Netw Sci"],"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Often, due to prohibitively large size or to limits to data collecting APIs, it is not possible to work with a complete network dataset and sampling is required. A type of sampling which is consistent with Twitter API restrictions is uniform edge sampling. In this paper, we propose a methodology for the recovery of two fundamental network properties from an edge-sampled network: the degree distribution and the triangle count (we estimate the totals for the network and the counts associated with each edge). We use a Bayesian approach and show a range of methods for constructing a prior which does not require assumptions about the original network. Our approach is tested on two synthetic and three real datasets with diverse sizes, degree distributions, degree-degree correlations and triangle count distributions.<\/jats:p>","DOI":"10.1007\/s41109-023-00574-3","type":"journal-article","created":{"date-parts":[[2023,11,17]],"date-time":"2023-11-17T09:03:02Z","timestamp":1700211782000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Using a Bayesian approach to reconstruct graph statistics after edge sampling"],"prefix":"10.1007","volume":"8","author":[{"given":"Naomi A.","family":"Arnold","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ra\u00fal J.","family":"Mondrag\u00f3n","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard G.","family":"Clegg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,11,17]]},"reference":[{"key":"574_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2601438","volume":"8","author":"NK Ahmed","year":"2013","unstructured":"Ahmed NK, Neville J, Kompella R (2013) Network sampling: from static to streaming graphs. ACM Trans Knowl Discov Data 8:1\u201356","journal-title":"ACM Trans Knowl Discov Data"},{"key":"574_CR2","doi-asserted-by":"publisher","first-page":"S134","DOI":"10.1017\/nws.2021.2","volume":"9","author":"N Antunes","year":"2021","unstructured":"Antunes N, Guo T, Pipiras V (2021) Sampling methods and estimation of triangle count distributions in large networks. Netw Sci 9:S134\u2013S156","journal-title":"Netw Sci"},{"key":"574_CR3","unstructured":"Arnold N (2021) Studying evolving complex networks. Ph.D. thesis, Queen Mary University of London"},{"key":"574_CR4","doi-asserted-by":"crossref","unstructured":"Arnold NA, Mondrag\u00f3n RJ, Clegg RG (2023) Reconstructing degree distribution and triangle counts from edge-sampled graphs. In: Complex networks and their applications XI: proceedings of the eleventh international conference on complex networks and their applications: COMPLEX NETWORKS 2022\u2013Vol 2. Springer, pp 297\u2013309","DOI":"10.1007\/978-3-031-21131-7_23"},{"key":"574_CR5","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"A-L Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si A-L, Albert R (1999) Emergence of scaling in random networks. Science 286:509\u2013512","journal-title":"Science"},{"issue":"2","key":"574_CR6","doi-asserted-by":"publisher","first-page":"987","DOI":"10.1214\/21-AOS2134","volume":"50","author":"BB Bhattacharya","year":"2022","unstructured":"Bhattacharya BB, Das S, Mukherjee S (2022) Motif estimation via subgraph sampling: the fourth-moment phenomenon. Ann Stat 50(2):987\u20131011","journal-title":"Ann Stat"},{"key":"574_CR7","doi-asserted-by":"publisher","first-page":"633","DOI":"10.3390\/e24050633","volume":"24","author":"G Bianconi","year":"2022","unstructured":"Bianconi G (2022) Grand canonical ensembles of sparse networks and Bayesian inference. Entropy 24:633","journal-title":"Entropy"},{"key":"574_CR8","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.71.066116","volume":"71","author":"G Bianconi","year":"2005","unstructured":"Bianconi G, Caldarelli G, Capocci A (2005) Loops structure of the internet at the autonomous system level. Phys Rev E 71:066116","journal-title":"Phys Rev E"},{"key":"574_CR9","unstructured":"Chen Q, Chang H, Govindan R, Jamin S (2002) The origin of power laws in internet topologies revisited. In: Proc. IEEE comp. and comm. societies"},{"issue":"1","key":"574_CR10","doi-asserted-by":"publisher","first-page":"P51","DOI":"10.37236\/2093","volume":"19","author":"T DuBois","year":"2012","unstructured":"DuBois T, Eubank S, Srinivasan A (2012) The effect of random edge removal on network degree sequence. Electron J Comb 19(1):P51","journal-title":"Electron J Comb"},{"key":"574_CR11","first-page":"17","volume":"5","author":"P Erd\u0151s","year":"1960","unstructured":"Erd\u0151s P, R\u00e9nyi A (1960) On the evolution of random graphs. Publ Math Inst Hung Acad Sci 5:17\u201360","journal-title":"Publ Math Inst Hung Acad Sci"},{"key":"574_CR12","doi-asserted-by":"publisher","first-page":"1464","DOI":"10.1086\/229693","volume":"96","author":"SL Feld","year":"1991","unstructured":"Feld SL (1991) Why your friends have more friends than you do. Am J Sociol 96:1464\u20131477","journal-title":"Am J Sociol"},{"key":"574_CR13","unstructured":"Frank O (1971) Statistical inference in graphs. Ph.D. thesis, Foa Repro Stockholm"},{"key":"574_CR14","doi-asserted-by":"crossref","unstructured":"Ganguly A, Kolaczyk ED (2017) Estimation of vertex degrees in a sampled network. In: Asilomar conference on signals, systems, and computers","DOI":"10.1109\/ACSSC.2017.8335492"},{"key":"574_CR15","doi-asserted-by":"crossref","unstructured":"Katzir L, Liberty E, Somekh O (2011) Estimating sizes of social networks via biased sampling. In: Proc. int. conf. on world wide web","DOI":"10.1145\/1963405.1963489"},{"key":"574_CR16","unstructured":"Klusowski JM, Wu Y (2018) Counting motifs with graph sampling. In: Conference on learning theory. PMLR, pp 1966\u20132011"},{"key":"574_CR17","doi-asserted-by":"crossref","unstructured":"Leskovec J, Faloutsos C (2006) Sampling from large graphs. In: Proceedings of the international conference on knowledge discovery and data mining","DOI":"10.1145\/1150402.1150479"},{"key":"574_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3022186","volume":"12","author":"Y Lim","year":"2018","unstructured":"Lim Y, Jung M, Kang U (2018) Memory-efficient and accurate sampling for counting local triangles in graph streams: from simple to multigraphs. ACM Trans Knowl Discov Data 12:1\u201328","journal-title":"ACM Trans Knowl Discov Data"},{"key":"574_CR19","unstructured":"Morstatter F, Pfeffer J, Liu H, Carley K (2013) Is the sample good enough? Comparing data from Twitter\u2019s streaming API with Twitter\u2019s firehose. In: Proc. of the international AAAI conference on web and social media"},{"key":"574_CR20","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1073\/pnas.98.2.404","volume":"98","author":"ME Newman","year":"2001","unstructured":"Newman ME (2001) The structure of scientific collaboration networks. Proc Natl Acad Sci 98:404\u2013409","journal-title":"Proc Natl Acad Sci"},{"issue":"6","key":"574_CR21","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1038\/s41567-018-0076-1","volume":"14","author":"ME Newman","year":"2018","unstructured":"Newman ME (2018) Network structure from rich but noisy data. Nat Phys 14(6):542\u2013545","journal-title":"Nat Phys"},{"key":"574_CR22","doi-asserted-by":"crossref","unstructured":"Paranjape A, Benson AR, Leskovec J (2017) Motifs in temporal networks. In: Proceedings of the tenth ACM international conference on web search and data mining, pp 601\u2013610","DOI":"10.1145\/3018661.3018731"},{"key":"574_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3059194","volume":"11","author":"LD Stefani","year":"2017","unstructured":"Stefani LD, Epasto A, Riondato M, Upfal E (2017) Triest: counting local and global triangles in fully dynamic streams with fixed memory size. ACM Trans Knowl Discov Data (TKDD) 11:1\u201350","journal-title":"ACM Trans Knowl Discov Data (TKDD)"},{"key":"574_CR24","doi-asserted-by":"publisher","first-page":"4221","DOI":"10.1073\/pnas.0501179102","volume":"102","author":"MP Stumpf","year":"2005","unstructured":"Stumpf MP, Wiuf C, May RM (2005) Subnets of scale-free networks are not scale-free: sampling properties of networks. PNAS 102:4221\u20134224","journal-title":"PNAS"},{"key":"574_CR25","doi-asserted-by":"crossref","unstructured":"Tsourakakis CE, Kang U, Miller GL, Faloutsos C (2009) Doulion: counting triangles in massive graphs with a coin. In: Proceedings international conference on knowledge discovery and data mining","DOI":"10.1145\/1557019.1557111"},{"key":"574_CR26","unstructured":"Twitter (2022) Stream tweets in real-time: developer documentation. https:\/\/developer.twitter.com\/en\/docs\/tutorials\/stream-tweets-in-real-time"},{"key":"574_CR27","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"DJ Watts","year":"1998","unstructured":"Watts DJ, Strogatz SH (1998) Collective dynamics of \u2018small-world\u2019 networks. Nature 393:440\u2013442","journal-title":"Nature"},{"issue":"6","key":"574_CR28","doi-asserted-by":"publisher","first-page":"cnaa046","DOI":"10.1093\/comnet\/cnaa046","volume":"8","author":"J-G Young","year":"2020","unstructured":"Young J-G, Cantwell GT, Newman M (2020) Bayesian inference of network structure from unreliable data. J Complex Netw 8(6):cnaa046","journal-title":"J Complex Netw"},{"key":"574_CR29","doi-asserted-by":"crossref","unstructured":"Zhang Y, Kolaczyk ED, Spencer BD (2015) Estimating network degree distributions under sampling: An inverse problem, with applications to monitoring social media networks. Ann Appl Stat","DOI":"10.1214\/14-AOAS800"},{"issue":"6","key":"574_CR30","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1088\/1367-2630\/9\/6\/173","volume":"9","author":"S Zhou","year":"2007","unstructured":"Zhou S, Mondrag\u00f3n R (2007) Structural constraints in complex networks. New J Phys 9(6):173","journal-title":"New J Phys"}],"container-title":["Applied Network Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-023-00574-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41109-023-00574-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-023-00574-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,17]],"date-time":"2023-11-17T09:03:50Z","timestamp":1700211830000},"score":1,"resource":{"primary":{"URL":"https:\/\/appliednetsci.springeropen.com\/articles\/10.1007\/s41109-023-00574-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,17]]},"references-count":30,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,12]]}},"alternative-id":["574"],"URL":"https:\/\/doi.org\/10.1007\/s41109-023-00574-3","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-2640432\/v1","asserted-by":"object"}]},"ISSN":["2364-8228"],"issn-type":[{"value":"2364-8228","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,17]]},"assertion":[{"value":"28 February 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 July 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 November 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"No ethical approval is applicable for this work.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"The authors have no competing interests as defined by Springer, or other interests that might be perceived to influence the results and\/or discussion reported in this paper.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"80"}}