zbMATH — the first resource for mathematics

Finding the seed of uniform attachment trees. (English) Zbl 1466.60013
Summary: A uniform attachment tree is a random tree that is generated dynamically. Starting from a fixed “seed” tree, vertices are added sequentially by attaching each vertex to an existing vertex chosen uniformly at random. Upon observing a large (unlabeled) tree, one wishes to find the initial seed. We investigate to what extent seed trees can be recovered, at least partially. We consider three types of seeds: a path, a star, and a random uniform attachment tree. We propose and analyze seed-finding algorithms for all three types of seed trees.

60C05 Combinatorial probability
05C05 Trees
05C80 Random graphs (graph-theoretic aspects)
62H12 Estimation in multivariate analysis
Full Text: DOI Euclid arXiv
[1] Christian Borgs, Michael Brautbar, Jennifer Chayes, Sanjeev Khanna, and Brendan Lucier: The power of local information in social networks. In Internet and Network Economics, 406-419. Springer, 2012.
[2] S. Boucheron, G. Lugosi, and P. Massart: Concentration inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013. · Zbl 1279.60005
[3] Michael Brautbar and Michael J. Kearns: Local algorithms for finding interesting individuals in large networks. In Innovations in Theoretical Computer Science (ITCS), 2010.
[4] Sebastien Bubeck, Luc Devroye, and Gábor Lugosi: Finding Adam in random growing trees. Random Structures & Algorithms, 50(2): 158-172, 2017. · Zbl 1359.05110
[5] Sebastien Bubeck, Ronen Eldan, Elchanan Mossel, and Miklós Rácz: From trees to seeds: on the inference of the seed from large trees in the uniform attachment model. Bernoulli, 23(4A):2887-2916, 2017. · Zbl 1381.60026
[6] Sebastien Bubeck, Elchanan Mossel, and Miklós Z Rácz: On the influence of the seed graph in the preferential attachment model. IEEE Transactions on Network Science and Engineering, 2(1):30-39, 2015.
[7] Nicolas Curien, Thomas Duquesne, Igor Kortchemski, and Ioan Manolescu: Scaling limits and influence of the seed graph in preferential attachment trees. Journal de l’Ecole Polytechnique-Mathématiques, 2:1-34, 2015. · Zbl 1320.05110
[8] Luc Devroye: Limit laws for local counters in random binary search trees. Random Structures & Algorithms, 2(3):303-315, 1991. · Zbl 0728.60027
[9] Luc Devroye and Tommy Reddad: On the discovery of the seed in uniform attachment trees. arXiv:1810.00969, 2018. · Zbl 1429.62126
[10] Michael Drmota: Random trees: an interplay between combinatorics and probability. Springer Science & Business Media, 2009. · Zbl 1170.05022
[11] Alan Frieze and Wesley Pegden: Looking for vertex number one. The Annals of Applied Probability, 27(1):582-630, 2017 · Zbl 1381.60027
[12] Wassily Hoeffding and Herbert Robbins: The central limit theorem for dependent random variables. Duke Mathematical Journal, 15(3):773-780, 1948. · Zbl 0031.36701
[13] Svante Janson: Large deviations for sums of partly dependent random variables. Random Structures & Algorithms, 24(3):234-248, 2004. · Zbl 1044.60021
[14] Varun Jog and Po-Ling Loh: Analysis of centrality in sublinear preferential attachment trees via the CMJ branching process. IEEE Transactions on Network Science and Engineering, 2017. · Zbl 1386.05176
[15] Varun Jog and Po-Ling Loh: Persistence of centrality in random growing trees. Random Structures & Algorithms, 2017 · Zbl 1386.05176
[16] C. McDiarmid: On the method of bounded differences. In Surveys in Combinatorics 1989, pages 148-188. Cambridge University Press, Cambridge, 1989. · Zbl 0712.05012
[17] Saket Navlakha and Carl Kingsford: Network archaeology: uncovering ancient networks from present-day interactions. PLoS Computational Biology, 7(4):e1001119, 2011.
[18] Yosef Rinott: On normal approximation rates for certain sums of dependent random variables. Journal of Computational and Applied Mathematics, 55(2):135-143, 1994. · Zbl 0821.60037
[19] Devavrat Shah and Tauhid Zaman: Finding rumor sources on random trees. Operations Research, 64(3):736-755, 2016. · Zbl 1348.90166
[20] Devavrat Shah and Tauhid R. Zaman: Rumors in a network: Who’s the culprit? IEEE Transactions on Information Theory, 57(8):5163-5181, 2011 · Zbl 1366.91126
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.