×

Matrix analysis of a Markov chain small-world model. (English) Zbl 1075.60095

The authors present a direct matrix-theoretic method which produces exact results for the Markov chain of the small-world model, recently introduced by D. Higham. Their method extends Higham’s original one to any number of nodes and any value of the \(\varepsilon\)-parameter of the Markov chain model.

MSC:

60J27 Continuous-time Markov processes on discrete state spaces
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15B51 Stochastic matrices
60J20 Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
65C40 Numerical analysis or methods applied to Markov chains
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albert, R.; Jeong, H.; Barabási, A.-L., The Internet’s Achilles’ heel: error and attack tolerance of complex networks, Nature, 406, 378-382 (2000)
[2] Amaral, L. A.N.; Scala, A.; Barthélémy, M.; Stanley, H. E., Classes of small-world networks, Proc. Natl. Acad. Sci. USA, 97, 11149-11152 (2000)
[3] Barabási, A.-L.; Ravasz, E.; Vicsek, T., Deterministic scale-free networks, Physica A, 299, 559-564 (2001) · Zbl 0972.57003
[4] Barbour, A. D.; Reinert, G., Small worlds, Random Struct. Algorith., 19, 54-74 (2001) · Zbl 0988.60100
[5] Comellas, F.; Sampels, M., Deterministic small-world networks, Physica A, 309, 231-235 (2002) · Zbl 0995.60103
[6] Dow, M., Explicit inverses of Toeplitz and associated matrices, ANZIAM J., 44, E, 185-215 (2003)
[7] Higham, D. J., A matrix perturbation view of the small world phenomenon, SIAM J. Matrix Anal. Appl., 25, 4, 429-444 (2003) · Zbl 1050.65004
[8] S.D. Kamvar, T.H. Haveliwala, C.D. Manning, G.H. Golub, Extrapolation methods for accelerating PageRank computations, in: Proceedings of the 12th International World Wide Web Conference, Budapest, Hungary, 2003, pp. 261-270.; S.D. Kamvar, T.H. Haveliwala, C.D. Manning, G.H. Golub, Extrapolation methods for accelerating PageRank computations, in: Proceedings of the 12th International World Wide Web Conference, Budapest, Hungary, 2003, pp. 261-270.
[9] Kemeny, J. G.; Snell, J. L., Finite Markov Chains (1960), Van Nostrand: Van Nostrand Princeton, New Jersey · Zbl 0112.09802
[10] J. Kleinberg, The small-world phenomenon: an algorithmic perspective, in: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, Portland, Oregon, USA, 2000, pp. 163-170.; J. Kleinberg, The small-world phenomenon: an algorithmic perspective, in: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, Portland, Oregon, USA, 2000, pp. 163-170. · Zbl 1296.05181
[11] Montoya, J. M.; Solé, R. V., Small world patterns in food webs, J. Theor. Biol., 214, 405-412 (2002)
[12] Newman, M. E.J., The structure of scientific collaboration networks, Proc. Natl. Acad. Sci. USA, 98, 404-409 (2001) · Zbl 1065.00518
[13] Newman, M. E.J.; Moore, C.; Watts, D. J., Mean-field solution of the small-world network model, Phys. Rev. Lett., 84, 3201-3204 (2000)
[14] Pastor-Satorras, R.; Vespignani, A., Epidemic spreading in scale-free networks, Phys. Rev. Lett., 86, 3200-3203 (2001)
[15] Wagner, A.; Fell, D. A., The small world inside large metabolic networks, Proc. Roy. Soc. London Ser. B., 268, 1803-1810 (2001)
[16] Watts, D. J.; Strogatz, S. H., Collective dynamics of “small-world” networks, Nature, 393, 440-442 (1998) · Zbl 1368.05139
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.