×

Typical distances in the directed configuration model. (English) Zbl 1393.05101

Summary: We analyze the distribution of the distance between two nodes, sampled uniformly at random, in digraphs generated via the directed configuration model, in the supercritical regime. Under the assumption that the covariance between the in-degree and out-degree is finite, we show that the distance grows logarithmically in the size of the graph. In contrast with the undirected case, this can happen even when the variance of the degrees is infinite. The main tool in the analysis is a new coupling between a breadth-first graph exploration process and a suitable branching process based on the Kantorovich-Rubinstein metric. This coupling holds uniformly for a much larger number of steps in the exploration process than existing ones, and is therefore of independent interest.

MSC:

05C12 Distance in graphs
05C20 Directed graphs (digraphs), tournaments
05C80 Random graphs (graph-theoretic aspects)
60B10 Convergence of probability measures

Software:

WebGraph
PDF BibTeX XML Cite
Full Text: DOI arXiv Euclid

References:

[1] Arratia, R. and Liggett, T. M. (2005). How likely is an i.i.d. degree sequence to be graphical? Ann. Appl. Probab.15 652-670. · Zbl 1079.05023
[2] Athreya, K. B. and Ney, P. E. (2004). Branching Processes. Dover Publications, Mineola, NY. · Zbl 1070.60001
[3] Biggins, J. D. and Bingham, N. H. (1993). Large deviations in the supercritical branching process. Adv. in Appl. Probab.25 757-772. · Zbl 0796.60090
[4] Boldi, P., Rosa, M. and Vigna, S. (2011). HyperANF: Approximating the neighbourhood function of very large graphs on a budget. In Proceedings of the 20th International Conference on World Wide Web 625-634. ACM, New York.
[5] Boldi, P. and Vigna, S. (2004). The webgraph framework I: Compression techniques. In Proceedings of the 13th International Conference on World Wide Web 595-602. ACM, New York.
[6] Boldi, P. and Vigna, S. (2013). In-core computation of geometric centralities with hyperball: A hundred billion nodes and beyond. In Data Mining Workshops (ICDMW), 2013 IEEE 13th International Conference on 621-628. IEEE, New York.
[7] Bollobás, B. (1980). A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European J. Combin.1 311-316.
[8] Bollobás, B. (2001). Random Graphs, 2nd ed. Cambridge Studies in Advanced Mathematics73. Cambridge Univ. Press, Cambridge.
[9] Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A. and Wiener, J. (2000). Graph structure in the web. Comput. Netw.33 309-320.
[10] Chen, N., Litvak, N. and Olvera-Cravioto, M. (2017). Generalized PageRank on directed configuration networks. Random Structures Algorithms51 237-274. · Zbl 1370.05199
[11] Chen, N. and Olvera-Cravioto, M. (2013). Directed random graphs with given degree distributions. Stoch. Syst.3 147-186. · Zbl 1297.05212
[12] Chen, N. and Olvera-Cravioto, M. (2015). Efficient simulation for branching linear recursions. In Proceedings of the 2015 Winter Simulation Conference 1-12.
[13] Cooper, C. and Frieze, A. (2004). The size of the largest strongly connected component of a random digraph with a given degree sequence. Combin. Probab. Comput.13 319-337. · Zbl 1065.05085
[14] del Barrio, E., Giné, E. and Matrán, C. (1999). Central limit theorems for the Wasserstein distance between the empirical and the true distributions. Ann. Probab.27 1009-1071. · Zbl 0958.60012
[15] Durrett, R. (2010). Random Graph Dynamics, 1st ed. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge Univ. Press, Cambridge. · Zbl 1223.05002
[16] Goh, K.-I., Oh, E., Kahng, B. and Kim, D. (2003). Betweenness centrality correlation in social networks. Phys. Rev. E67 017101.
[17] Grandell, J. (1997). Mixed Poisson Processes. Springer, Berlin. · Zbl 0922.60005
[18] Miller, J. C. (2009). Percolation and epidemics in random clustered networks. Phys. Rev. E (3) 80 020901, 4.
[19] Newman, M. E. J. (2002). Spread of epidemic disease on networks. Phys. Rev. E (3) 66 016128, 11.
[20] Norros, I., Reittu, H. et al. (2006). On a conditionally Poissonian graph process. Adv. in Appl. Probab.38 59-75. · Zbl 1096.05047
[21] Penrose, M. D. (2016). The strong giant in a random digraph. J. Appl. Probab.53 57-70. · Zbl 1335.05164
[22] Serge Dubuc, M. (1971). La densité de la loi-limite d’un processus en cascade expansif. Probab. Theory Related Fields19 281-290. · Zbl 0208.44203
[23] Timár, G., Goltsev, A., Dorogovtsev, S. and Mendes, J. (2017). Mapping the structure of directed networks: Beyond the “bow-tie” diagram. Physics Review Letters118.
[24] Van Der Hofstad, R. (2016). Random Graphs and Complex Networks1. Cambridge Univ. Press, Cambridge. · Zbl 1361.05002
[25] van den Esker, H., van der Hofstad, R. and Hooghiemstra, G. (2008). Universality for the distance in finite variance random graphs. J. Stat. Phys.133 169-202. · Zbl 1152.82008
[26] van den Esker, H., van der Hofstad, R., Hooghiemstra, G. and Znamenski, D. (2005). Distances in random graphs with infinite mean degrees. Extremes8 111-141. · Zbl 1120.05086
[27] van der Hofstad, R., Hooghiemstra, G. and Van Mieghem, P. (2005). Distances in random graphs with finite variance degrees. Random Structures Algorithms27 76-123. · Zbl 1074.05083
[28] van der Hofstad, R., Hooghiemstra, G. and Znamenski, D. (2007). Distances in random graphs with finite mean and infinite variance degrees. Electron. J. Probab.12 703-766. · Zbl 1126.05090
[29] Villani, C.
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.