Proposers of the vote of thanks to Crane and Xu and contribution to the Discussion of ‘Root and community inference on the latent growth process of a network’

原文摘要

We commend the authors on an illuminating article which significantly extends the state of the art in network archaeology. Notably, whereas most other literature in the area has provided methods for root inference which are theoretically grounded only in the case of random trees, the techniques in this paper have been designed to model nontree-structured networks, as well. This has important practical implications, as many real-world networks contain one or more cycles. The main challenge faced by the probability and statistics community—for the better part of the last decade—was that it was difficult to concoct a model that was simple enough to analyse rigorously, yet complex enough to comprise a sufficiently interesting family of random graph structures. By introducing their PAPER model, Crane and Xu have proposed a model achieving an ideal balance, accompanied by a variety of attractively useful and strikingly intuitive theoretical results. The simulation results are also very impressive, in that the algorithms can be efficiently run on a single laptop even for networks with millions of nodes. The fact that the PAPER model achieves such versatility with only three parameters is a major strength of the work. This makes parameter estimation plausible (the authors suggest several methods for parameter estimation in the appendices, based on EM and Bayesian methods). From our reading, we wondered how one might decide in practice to use a more complicated model for a given network, e.g. sequential PAPER vs. nonsequential PAPER, or fixed-K vs. random K, as the more complicated networks would of course lead to more complicated inference procedures. For instance, is anything known about degree profiles of random-K networks, and are they qualitatively different from the degree profiles of fixed-K networks? (Which would be more reasonable for specific problems such as the coauthor networks studied in this paper?) We are also curious to understand better, in practice, what the confidence sets look like for K>1 (does the algorithm output K connected components?). How might the algorithm be modified if the goal is to output a set of K-tuples such that the K-tuple containing the K root nodes is contained in this set, with a certain high probability? Section 5 of the paper presents theoretical results concerning confidence sets for the root node (or root nodes, when K>1⁠) of a random network. Along the lines of some of our previous work (Jog & Loh, 2018), we wondered how much the theory could extend to the case of constructing a confidence set for the first M>1 nodes (say, for simplicity, in the case when K=1⁠). Also, can reasonable conditions be imposed under which confidence sets are proven to ‘persist’ when the number of nodes n tends to infinity? Finally, if the random network were initialized with a ‘seed graph’ (Lugosi & Pereira, 2019), could confidence sets for the seed graph be constructed by an extension of the techniques in this paper, with corresponding theoretical results? Although several variants of the PAPER model are introduced in Section 2 of the paper, the core theoretical results seem to only cover the vanilla and fixed-K cases. Thus, we wondered whether results such as the fact that credible sets have the correct frequentist coverage (Theorems 7 and 8) also holds for sequential and random-K models. Does the minimality property of confidence sets based on posterior root probabilities (Remark 6/Theorem S5) also hold for K>1? If any of the answers are negative, can the authors comment on the technical difficulties involved in extending their results to these cases? Lastly, we found the results of the paper to be rather thought-provoking in terms of their potential for opening new avenues for studying more complicated random growth models. Some examples include sequential models with a ‘vertex retirement’ feature, e.g. motivated by the study of coauthorship networks. Another idea is to model in deletion noise which is time-dependent, in contrast to the versions of PAPER presented in the paper, which assume that once connections are formed in the sequential model, they remain fixed forever. Other worthwhile models to study in conjunction with PAPER might be the sublinear preferential attachment model, which also exhibits persistence properties analogous to the linear preferential attachment model (Jog & Loh, 2016), and the ‘superstar model’, which purportedly provides a better fit to empirical data in social networks than the standard preferential attachment model (Bhamidi et al., 2015).

摘要来源：OpenAlex 索引摘要（稿件版本未注明）