×

Graph concatenations to derive weighted fractal networks. (English) Zbl 1444.05135

Summary: Given an initial weighted graph \(G_0\), an integer \(m>1\), and \(m\) scaling factors \(f_1,\ldots, f_m\in( 0,1)\), we define a sequence of weighted graphs \(\{ G_k\}_{k = 0}^\infty\) iteratively. Provided that \(G_{k - 1}\) is given for \(k\geq1\), we let \(G_{k - 1}^{( 1)},\dots,G_{k - 1}^{( m)}\) be \(m\) copies of \(G_{k - 1}\), whose weighted edges have been scaled by \(f_1,\dots, f_m\), respectively. Then, \( G_k\) is constructed by concatenating \(G_0\) with all the \(m\) copies. The proposed framework shares several properties with fractal sets, and the similarity dimension \(d_{\mathrm{fract}}\) has a great impact on the topology of the graphs \(G_k\) (e.g., node strength distribution). Moreover, the average geodesic distance of \(G_k\) increases logarithmically with the system size; thus, this framework also generates the small-world property.

MSC:

05C82 Small world graphs, complex networks (graph-theoretic aspects)
05C22 Signed and weighted graphs
05C72 Fractional graph theory, fuzzy graph theory
90B10 Deterministic network models in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Boccaletti, S.; Latora, V.; Moreno, Y.; Chavez, M.; Hwang, D., Complex networks: structure and dynamics, Physics Reports, 424, 4-5, 175-308 (2006) · Zbl 1371.82002 · doi:10.1016/j.physrep.2005.10.009
[2] Dorogovtsev, S., Lectures On Complex Networks (2010), Oxford, UK: Oxford University Press, Oxford, UK · Zbl 1200.94003
[3] Huang, R., A qd-type method for computing generalized singular values of BF matrix pairs with sign regularity to high relative accuracy, Mathematics of Computation, 89, 321, 229-252 (2020) · Zbl 1436.65037 · doi:10.1090/mcom/3444
[4] Newman, M. E. J., The structure and function of complex networks, SIAM Review, 45, 2, 167-256 (2003) · Zbl 1029.68010 · doi:10.1137/s003614450342480
[5] Barrat, A.; Barthelemy, M.; Pastor-Satorras, R.; Vespignani, A., The architecture of complex weighted networks, Proceedings of the National Academy of Sciences, 101, 11, 3747-3752 (2004) · doi:10.1073/pnas.0400087101
[6] Barabási, A.-L.; Ravasz, E.; Vicsek, T., Deterministic scale-free networks, Physica A: Statistical Mechanics and Its Applications, 299, 3-4, 559-564 (2001) · Zbl 0972.57003 · doi:10.1016/s0378-4371(01)00369-7
[7] Zhang, Z.-Z.; Zhou, S.-G.; Zou, T.; Chen, L.; Guan, J., Self-similarity, small-world, scale-free scaling, disassortativity, and robustness in hierarchical lattices, The European Physical Journal B, 56, 3, 259-271 (2007) · Zbl 1189.91188 · doi:10.1140/epjb/e2007-00344-7
[8] Zhang, Z.; Gao, S.; Chen, L.; Zhou, S.; Zhang, H.; Guan, J., Mapping koch curves into scale-free small-world networks, Journal of Physics A: Mathematical and Theoretical, 43, 39 (2010) · Zbl 1213.28004 · doi:10.1088/1751-8113/43/39/395101
[9] Carletti, T.; Righi, S., Weighted fractal networks, Physica A: Statistical Mechanics and Its Applications, 389, 10, 2134-2142 (2010) · doi:10.1016/j.physa.2010.01.019
[10] Hutchinson, J., Fractals and self-similarity, Indiana University Mathematics Journal, 30, 5, 713-747 (1981) · Zbl 0598.28011 · doi:10.1512/iumj.1981.30.30055
[11] Li, T.; Jiang, K.; Xi, L., Average distance of self-similar fractal trees, Fractals, 26, 1 (2018) · Zbl 1432.28007 · doi:10.1142/s0218348x18500160
[12] Xi, L.; Ye, Q., Average distances on substitution trees, Physica A: Statistical Mechanics and Its Applications, 529 (2019) · Zbl 07568590 · doi:10.1016/j.physa.2019.121556
[13] Xiao, Y.; Gu, J., Uniform Cantor sets as hyperbolic boundaries, Filomat, 28, 8, 1737-1745 (2014) · Zbl 1474.30169 · doi:10.2298/fil1408737x
[14] Schneider, J. E., A generalization of the von Koch curve, Mathematics Magazine, 38, 3, 144-147 (1965) · Zbl 0129.36901 · doi:10.2307/2688774
[15] Falconer, K., Fractal Geometry (1990), Chichester, UK: John Wiley & Sons, Chichester, UK
[16] Bondy, A.; Ram Murty, M., Graph Theory (2008), London, UK: Springer-Verlag London, London, UK · Zbl 1134.05001
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.