×

Farey graphs as models for complex networks. (English) Zbl 1206.68245

Summary: Farey sequences of irreducible fractions between 0 and 1 can be related to graph constructions known as Farey graphs. These graphs were first introduced by Matula and Kornerup in 1979 and further studied by Colbourn in 1982, and they have many interesting properties: they are minimally 3-colorable, uniquely Hamiltonian, maximally outerplanar and perfect. In this paper, we introduce a simple generation method for a Farey graph family, and we study analytically relevant topological properties: order, size, degree distribution and correlation, clustering, transitivity, diameter and average distance. We show that the graphs are a good model for networks associated with some complex systems.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68M10 Network design and communication in computer systems
11B57 Farey sequences; the sequences \(1^k, 2^k, \dots\)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Albert, R.; Barabási, A.-L., Statistical mechanics of complex networks, Rev. Modern Phys., 74, 47 (2002) · Zbl 1205.82086
[2] Andrade, J. S.; Herrmann, H. J.; Andrade, R. F.S.; da Silva, L. R., Apollonian networks: simultaneously scale-free, small world, Euclidean, space filling, and with matching graphs, Phys. Rev. Lett., 94, 018702 (2005)
[3] D. Austin, Trees, teeth, and time: the mathematics of clock making, American Mathematical Society, Feature Column, Monthly Essays on Mathematical Topics, December 2008. http://www.ams.org/featurecolumn/archive/stern-brocot.html; D. Austin, Trees, teeth, and time: the mathematics of clock making, American Mathematical Society, Feature Column, Monthly Essays on Mathematical Topics, December 2008. http://www.ams.org/featurecolumn/archive/stern-brocot.html
[4] Barabási, A.-L.; Albert, R., Emergence of scaling in random networks, Science, 286, 509-512 (1999) · Zbl 1226.05223
[5] Barrat, A.; Weigt, M., On the properties of small-world network models, Eur. Phys. J. B, 13, 547-560 (2000)
[6] Biggs, N. L., Graphs with large girth, Ars Combin., 25-C, 73-80 (1988) · Zbl 0649.05042
[7] Boccaletti, S.; Latora, V.; Moreno, Y.; Chavez, M.; Hwang, D.-U., Complex networks: structure and dynamics, Phys. Rep., 424, 175 (2006) · Zbl 1371.82002
[8] A. Brandstaedt, V.B. Le, P.J. Spinrad, Graph classes: a survey, in: SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, PA, 1999.; A. Brandstaedt, V.B. Le, P.J. Spinrad, Graph classes: a survey, in: SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, PA, 1999.
[9] Colbourn, C. J., Farey series and maximal outerplanar graphs, SIAM J. Algebr. Discrete Methods, 3, 187-189 (1982) · Zbl 0499.05025
[10] Comellas, F.; Fertin, G.; Raspaud, A., Recursive graphs with small-world scale-free properties, Phys. Rev. E, 69, 037104 (2004)
[11] Dorogovtsev, S. N.; Mendes, J. F.F., Evolution of networks, Adv. Phys., 51, 1079 (2002)
[12] Dorogovtsev, S. N.; Goltsev, A. V.; Mendes, J. F.F., Pseudofractal scale-free web, Phys. Rev. E, 65, 066122 (2002)
[13] Ferrer i. Cancho, R.; Janssen, C.; Solé, R. V., Topology of technology graphs: small world patterns in electronic circuits, Phys. Rev. E, 64, 046119 (2001)
[14] Graham, R. L.; Knuth, D. E.; Patashnik, O., Concrete Mathematics: A Foundation for Computer Science (1985), Addison-Wesley Pub. Co.: Addison-Wesley Pub. Co. Reading, MA
[15] Hardy, G. H.; Wright, E. M., An Introduction to the Theory of Numbers (1979), Oxford University Press · Zbl 0423.10001
[16] Jung, S.; Kim, S.; Kahng, B., Geometric fractal growth model for scale-free networks, Phys. Rev. E, 65, 056101 (2002)
[17] Matula, D. W.; Kornerup, P., A graph theoretic interpretation of fractions, continued fractions and the GCD algorithm, (Mullin, R. C.; Stanton, R. G., Proc. 10th Southeastern Conference on Combinatorics, Graph Theory, and Computing (1979), Utilitas Mathematica Publishing, Inc.), 932
[18] Maslov, S.; Sneppen, K., Specificity and stability in topology of protein networks, Science, 296, 910-913 (2002)
[19] Newman, M. E.J., Models of small-world, J. Stat. Phys., 101, 819 (2000) · Zbl 1049.82520
[20] Newman, M. E.J., Assortative mixing in networks, Phys. Rev. Lett., 89, 208701 (2002)
[21] Newman, M. E.J., The structure and function of complex networks, SIAM Rev., 45, 167-256 (2003) · Zbl 1029.68010
[22] Newman, M. E.J.; Watts, D. J.; Strogatz, S. H., Random graph models of social networks, Proc. Natl. Acad. Sci. USA, 99, 2566-2572 (2002) · Zbl 1114.91362
[23] Ozik, J.; Hunt, B.-R.; Ott, E., Growing networks with geographical attachment preference: emergence of small worlds, Phys. Rev. E, 69, 026108 (2004)
[24] Pastor-Satorras, R.; Vázquez, A.; Vespignani, A., Dynamical and correlation properties of the Internet, Phys. Rev. Lett., 87, 258701 (2001)
[25] Ravasz, E.; Barabási, A.-L., Hierarchical organization in complex networks, Phys. Rev. E, 67, 026112 (2003)
[26] Watts, D. J.; Strogatz, S. H., Collective dynamics of ‘small-world’ networks, Nature, 393, 440-442 (1998) · Zbl 1368.05139
[27] E.W. Weisstein, Farey sequence. From MathWorld-A Wolfram Web Resource. http://mathworld.wolfram.com/FareySequence.html; E.W. Weisstein, Farey sequence. From MathWorld-A Wolfram Web Resource. http://mathworld.wolfram.com/FareySequence.html
[28] Zhang, Z.; Rong, L.; Comellas, F., Evolving small-world networks with geographical attachment preference, J. Phys. A: Math. Gen., 39, 3253-3261 (2006) · Zbl 1088.93003
[29] Zhang, Z. Z.; Rong, L. L.; Guo, C. H., A deterministic small-world network created by edge iterations, Physica A, 363, 567-572 (2006)
[30] Zhang, Z.; Zhou, S.; Wang, Z.; Shen, Z., A geometric growth model interpolating between regular and small-world networks, J. Phys. A: Math. Theor., 40, 11863-11876 (2007) · Zbl 1189.91187
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.