Sayan Banerjee’s contribution to the Discussion of ‘Root and community inference on the latent growth process of a network’ by Crane and Xu

原文摘要

I congratulate the authors on their elegant and computationally tractable approach to inference problems in network archaeology. This is one of the few papers which rigorously analyses inference for noisy temporal networks. The key idea is to compute the distribution of the possible arrival orders of vertices given an unlabelled network realization (online detection) and construct the confidence set for the root by sorting vertices according to their probability of arriving first given the observed unlabelled network. A Gibbs-type algorithm is provided to compute the above distribution in O(m+nlogn) time (⁠m,n are, respectively, the number of edges and vertices). Finally, some theoretical guarantees are provided for the size of the confidence set provided the noise is not too large. I have the following comments. (i) Community structure for dynamic networks: The community structure conceived in the paper by looking at a K-forest and then adding noise is rather restrictive as the individual trees in the forest are ‘decoupled’: they can be generated by running independent continuous-time branching processes from K ancestors till the total population size hits n. A more realistic model should comprise individual vertices exerting community-specific influences, in addition to their degrees, in the growth of the network. One such model has been recently explored in Antunes et al. (2023) under the name of attribute network models. In addition to obtaining local weak limits and other asymptotics, some network sampling and ranking algorithms have been explored in these papers. It would be interesting to extend the current approach to community detection problems for these networks. (ii) Comparison with other root finding algorithms: The authors mention several other works where root detection algorithms are presented. They are said to be more conservative as the guarantees are asymptotic as the network size grows, and there are some non-explicit constants involved in the associated bounds. However, no direct comparison is provided for these algorithms on the PAPER model for fixed large n. It would be instructive to compare these methods computationally. To my knowledge, some of the asymptotic guarantees for these other algorithms can be made quantitative and it would be interesting to compare them to the theoretical results in this paper. (iii) Non-local centrality measures: In Theorem 12 of the paper, it is shown, by ‘upper bounding’ the confidence set with that obtained via a degree-based criterion, that the size of the confidence set is O(nγ) for some γ≤0.8 if the noise level θ=o(logn/n)⁠. Moreover, a conjecture is made that the actual size of the confidence set should be O(1) in this case. I believe that to prove this conjecture, one needs to analyse ‘non-local’ centrality measures that look beyond one-step neighbourhoods of vertices (like Jordan centrality Bubeck et al., 2017). This is because, as shown in Banerjee and Bhamidi (2021), the degree centrality lacks persistence, that is, the identities of the highest degree vertices keep changing infinitely often as the network grows, unlike the APA model (see also Dereich & Mörters, 2009). However, Jordan centrality exhibits persistence (Banerjee & Bhamidi, 2022). This could be interesting future work.

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