On terminal nodes and the degree profile of preferential dynamic attachment circuits
Published in Proceedings of the Thirteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), 2016
Recommended citation: Zhang, P. (2016). "On terminal nodes and the degree profile of preferential dynamic attachment circuits." In 2016 Proceedings of the Thirteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), Arlington, VA, 80--92. SIAM, Philadelphia, PA. https://doi.org/10.1137/1.9781611974324.9
We investigate terminal nodes and the degree profile in preferential dynamic attachment circuits. We study the distribution of the number of terminal nodes, which are the nodes that have not recruited other nodes, as the circuit ages. The expectation and variance of the number of terminal nodes are both linear with respect to the age of the circuit. We show via martingale that the number of terminal nodes asymptotically follows a Gaussian law. We also study the exact distribution of the degree of a specific node as the circuit grows. The exact expectation and variance of the degree of a node are determined via a series of Pólya-Eggenberger urn models with “hiccups” in between and recurrence methods. Phase transitions of these degrees are discussed briefly.