ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Mathematics 15 January 2024

Distances in a geographical attachment network model

  • Department of Statistics and Finance, School of Management, University of Science and Technology of China, Hefei 230026, China

Cite this:
https://doi.org/10.52396/JUSTC-2023-0082
More Information
  • Author Bio:

    Ziling Xu is a postgraduate student of the University of Science and Technology of China. Her research mainly focuses on random network

    Qunqiang Feng is currently an Associate Professor at the University of Science and Technology of China (USTC). He received his Ph.D. degree from USTC in 2006. His research mainly focuses on applied probability, random network models, and network data analysis

  • Corresponding author: E-mail: fengqq@ustc.edu.cn
  • Received Date: 06 May 2023
  • Accepted Date: 03 July 2023
    • Available Online: 15 January 2024
    Abstract

  • Abstract

    Distances between nodes are one of the most essential subjects in the study of complex networks. In this paper, we investigate the asymptotic behaviors of two types of distances in a model of geographic attachment networks (GANs): the typical distance and the flooding time. By generating an auxiliary tree and using a continuous-time branching process, we demonstrate that in this model the typical distance is asymptotically normal, and the flooding time converges to a given constant in probability as well.

    Graphical abstract

    Distances in a geographical attachment network model.

    Abstract

    Distances between nodes are one of the most essential subjects in the study of complex networks. In this paper, we investigate the asymptotic behaviors of two types of distances in a model of geographic attachment networks (GANs): the typical distance and the flooding time. By generating an auxiliary tree and using a continuous-time branching process, we demonstrate that in this model the typical distance is asymptotically normal, and the flooding time converges to a given constant in probability as well.

    • Public Summary

    • The asymptotic properties of the typical distance and the flooding time in a geographic attachment network (GAN) model are studied.
    • The typical distance of GAN is asymptotically normal.
    • The flooding time of GAN converges to a given constant in probability.

    FullText(HTML)
  • loading
    • References(25)
  • [1]
    Wasserman S, Faust K. Social Network Analysis: Methods and Applications. Cambridge, UK: Cambridge University Press, 1994.
    [2]
    Wu J, Tse C K, Lau F C M, et al. Analysis of communication network performance from a complex network perspective. IEEE Transactions on Circuits and Systems, 2013, 60: 3303–3316. doi: 10.1109/TCSI.2013.2264697
    [3]
    Newman M E J. The structure of scientific collaboration networks. Proceedings of the National Academy of Sciences of the United States of America, 2001, 98: 404–409. doi: 10.1073/pnas.98.2.404
    [4]
    Alm E, Arkin A P. Biological networks. Current Opinion in Structural Biology, 2003, 13: 193–202. doi: 10.1016/S0959-440X(03)00031-9
    [5]
    Ozik J, Hunt B R, Ott E. Growing networks with geographical attachment preference: Emergence of small worlds. Physical Review E, 2004, 69: 026108. doi: 10.1103/PhysRevE.69.026108
    [6]
    Feng Q, Wang Y, Hu Z. Small-world effect in geographical attachment networks. Probability in the Engineering and Informational Sciences, 2021, 35: 276–296. doi: 10.1017/S0269964819000342
    [7]
    Hayashi Y. A review of recent studies of geographical scale-free networks. Information and Media Technologies, 2006, 1: 1136–1145. doi: 10.11185/imt.1.1136
    [8]
    Zhang Z, Rong L, Comellas F. Evolving small-world networks with geographical attachment preference. Journal of Physics A: Mathematical and General, 2006, 39: 3253. doi: 10.1088/0305-4470/39/13/005
    [9]
    Zhang Z, Rong L, Guo C. A deterministic small-world network created by edge iterations. Physica A: Statistical Mechanics and its Applications, 2006, 363: 567–572. doi: 10.1016/j.physa.2005.08.020
    [10]
    Barabási A L, Albert R. Emergence of scaling in random networks. Science, 1999, 286: 509–512. doi: 10.1126/science.286.5439.509
    [11]
    Kolossváry I, Komjáthy J, Vágó L. Degrees and distances in random and evolving Apollonian networks. Advances in Applied Probability, 2016, 48: 865–902. doi: 10.1017/apr.2016.32
    [12]
    Zhou T, Yan G, Wang B. Maximal planar networks with large clustering coefficient and power-law degree distribution. Physical Review E, 2005, 71: 046141. doi: 10.1103/PhysRevE.71.046141
    [13]
    Andrade Jr J S, Herrmann H J, Andrade R F, et al. Apollonian networks: simultaneously scale-free, small world, Euclidean, space filling, and with matching graphs. Physical Review Letters, 2005, 94: 018702. doi: 10.1103/PhysRevLett.94.018702
    [14]
    Zhang Z, Rong L, Zhou S. Evolving Apollonian networks with small-world scale-free topologies. Physical Review E, 2006, 74: 046105. doi: 10.1103/PhysRevE.74.046105
    [15]
    Abdullah M A, Bode M, Fountoulakis N. Typical distances in a geometric model for complex networks. arXiv: 1506.07811, 2015
    [16]
    Dereich S, Mönch C, Mörters P. Typical distances in ultrasmall random networks. Advances in Applied Probability, 2012, 44: 583–601. doi: 10.1239/aap/1339878725
    [17]
    Bhamidi S, van der Hofstad R, Hooghiemstra G. First passage percolation on the Erdös–Rényi random graph. Combinatorics, Probability and Computing, 2011, 20: 683–707. doi: 10.1017/S096354831100023X
    [18]
    Bhamidi S, van der Hofstad R. Weak disorder asymptotics in the stochastic mean-field model of distance. Advances in Applied Probability, 2012, 22: 29–69. doi: 10.1214/10-AAP753
    [19]
    van der Hofstad R, Hooghiemstra G, van Mieghem P. The flooding time in random graphs. Extremes, 2002, 5: 111–129. doi: 10.1023/A:1022175620150
    [20]
    Camargo D, Popov S. Total flooding time and rumor propagation on graphs. Journal of Statistical Physics, 2017, 166: 1558–1571. doi: 10.1007/s10955-017-1731-0
    [21]
    Amini H, Draief M, Lelarge M. Flooding in weighted sparse random graphs. SIAM Journal on Discrete Mathematics, 2013, 27: 1–26. doi: 10.1137/120865021
    [22]
    Mountford T, Saliba J. Flooding and diameter in general weighted random graphs. Journal of Applied Probability, 2020, 57: 956–980. doi: 10.1017/jpr.2020.45
    [23]
    Athreya K B, Ney P E. Branching Processes. Berlin: Springer, 1972.
    [24]
    Bühler W J. Generations and degree of relationship in supercritical Markov branching processes. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 1971, 18: 141–152. doi: 10.1007/BF00569184
    [25]
    Feller W. An Introduction to Probability Theory and Its Applications, Vol. 1. 3rd Edition. New York: Wiley, 2008.
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML

    Figure  1.  Illustration of the growing GAN model with potential nodes for time $ n = 0 $, 1, and 2, where points $ \bullet $ represent nodes in the network, points $ \circ $ are potential nodes, and red dashed lines are potential edges.

    Figure  2.  Initial internode internals in GAN(0).

    Figure  3.  (a) is the subnetwork $ {{\rm{GAN}}}_1 $ after adding several nodes without marking potential nodes where the nodes labeled 0 and 1 are the initial nodes. By redrawing the network, we can obtain (b). The nodes marked as black circles and the nodes marked as blue squares are actual nodes and potential nodes, respectively. Except for the blue dotted line, the solid lines and the dotted lines represent the ancestral line of each node and shortcuts, respectively. Furthermore, the black lines and red lines represent existing edges and potential edges, respectively. $ u_0 $ is one of the potential nodes of this subnetwork.

    [1]
    Wasserman S, Faust K. Social Network Analysis: Methods and Applications. Cambridge, UK: Cambridge University Press, 1994.
    [2]
    Wu J, Tse C K, Lau F C M, et al. Analysis of communication network performance from a complex network perspective. IEEE Transactions on Circuits and Systems, 2013, 60: 3303–3316. doi: 10.1109/TCSI.2013.2264697
    [3]
    Newman M E J. The structure of scientific collaboration networks. Proceedings of the National Academy of Sciences of the United States of America, 2001, 98: 404–409. doi: 10.1073/pnas.98.2.404
    [4]
    Alm E, Arkin A P. Biological networks. Current Opinion in Structural Biology, 2003, 13: 193–202. doi: 10.1016/S0959-440X(03)00031-9
    [5]
    Ozik J, Hunt B R, Ott E. Growing networks with geographical attachment preference: Emergence of small worlds. Physical Review E, 2004, 69: 026108. doi: 10.1103/PhysRevE.69.026108
    [6]
    Feng Q, Wang Y, Hu Z. Small-world effect in geographical attachment networks. Probability in the Engineering and Informational Sciences, 2021, 35: 276–296. doi: 10.1017/S0269964819000342
    [7]
    Hayashi Y. A review of recent studies of geographical scale-free networks. Information and Media Technologies, 2006, 1: 1136–1145. doi: 10.11185/imt.1.1136
    [8]
    Zhang Z, Rong L, Comellas F. Evolving small-world networks with geographical attachment preference. Journal of Physics A: Mathematical and General, 2006, 39: 3253. doi: 10.1088/0305-4470/39/13/005
    [9]
    Zhang Z, Rong L, Guo C. A deterministic small-world network created by edge iterations. Physica A: Statistical Mechanics and its Applications, 2006, 363: 567–572. doi: 10.1016/j.physa.2005.08.020
    [10]
    Barabási A L, Albert R. Emergence of scaling in random networks. Science, 1999, 286: 509–512. doi: 10.1126/science.286.5439.509
    [11]
    Kolossváry I, Komjáthy J, Vágó L. Degrees and distances in random and evolving Apollonian networks. Advances in Applied Probability, 2016, 48: 865–902. doi: 10.1017/apr.2016.32
    [12]
    Zhou T, Yan G, Wang B. Maximal planar networks with large clustering coefficient and power-law degree distribution. Physical Review E, 2005, 71: 046141. doi: 10.1103/PhysRevE.71.046141
    [13]
    Andrade Jr J S, Herrmann H J, Andrade R F, et al. Apollonian networks: simultaneously scale-free, small world, Euclidean, space filling, and with matching graphs. Physical Review Letters, 2005, 94: 018702. doi: 10.1103/PhysRevLett.94.018702
    [14]
    Zhang Z, Rong L, Zhou S. Evolving Apollonian networks with small-world scale-free topologies. Physical Review E, 2006, 74: 046105. doi: 10.1103/PhysRevE.74.046105
    [15]
    Abdullah M A, Bode M, Fountoulakis N. Typical distances in a geometric model for complex networks. arXiv: 1506.07811, 2015
    [16]
    Dereich S, Mönch C, Mörters P. Typical distances in ultrasmall random networks. Advances in Applied Probability, 2012, 44: 583–601. doi: 10.1239/aap/1339878725
    [17]
    Bhamidi S, van der Hofstad R, Hooghiemstra G. First passage percolation on the Erdös–Rényi random graph. Combinatorics, Probability and Computing, 2011, 20: 683–707. doi: 10.1017/S096354831100023X
    [18]
    Bhamidi S, van der Hofstad R. Weak disorder asymptotics in the stochastic mean-field model of distance. Advances in Applied Probability, 2012, 22: 29–69. doi: 10.1214/10-AAP753
    [19]
    van der Hofstad R, Hooghiemstra G, van Mieghem P. The flooding time in random graphs. Extremes, 2002, 5: 111–129. doi: 10.1023/A:1022175620150
    [20]
    Camargo D, Popov S. Total flooding time and rumor propagation on graphs. Journal of Statistical Physics, 2017, 166: 1558–1571. doi: 10.1007/s10955-017-1731-0
    [21]
    Amini H, Draief M, Lelarge M. Flooding in weighted sparse random graphs. SIAM Journal on Discrete Mathematics, 2013, 27: 1–26. doi: 10.1137/120865021
    [22]
    Mountford T, Saliba J. Flooding and diameter in general weighted random graphs. Journal of Applied Probability, 2020, 57: 956–980. doi: 10.1017/jpr.2020.45
    [23]
    Athreya K B, Ney P E. Branching Processes. Berlin: Springer, 1972.
    [24]
    Bühler W J. Generations and degree of relationship in supercritical Markov branching processes. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 1971, 18: 141–152. doi: 10.1007/BF00569184
    [25]
    Feller W. An Introduction to Probability Theory and Its Applications, Vol. 1. 3rd Edition. New York: Wiley, 2008.
    Recommended articles
    TrendMD
    Volume 53 Issue 11 page: 1104
    Cover

    Article Metrics

    Article views (119) PDF downloads(324)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return