Random walks and diffusion on networks. (English) Zbl 1377.05180
Phys. Rep. 716-717, 1-58 (2017); corrigendum ibid. 745, 96 (2018); corrigendum ibid. 851, 37-39 (2020).
Summary: Random walks are ubiquitous in the sciences, and they are interesting from both theoretical and practical perspectives. They are one of the most fundamental types of stochastic processes; can be used to model numerous phenomena, including diffusion, interactions, and opinions among humans and animals; and can be used to extract information about important entities or dense groups of entities in a network. Random walks have been studied for many decades on both regular lattices and (especially in the last couple of decades) on networks with a variety of structures. In the present article, we survey the theory and applications of random walks on networks, restricting ourselves to simple cases of single and non-adaptive random walkers. We distinguish three main types of random walks: discrete-time random walks, node-centric continuous-time random walks, and edge-centric continuous-time random walks. We first briefly survey random walks on a line, and then we consider random walks on various types of networks. We extensively discuss applications of random walks, including ranking of nodes (e.g., PageRank), community detection, respondent-driven sampling, and opinion models such as voter models.
MSC:
| 05C81 | Random walks on graphs |
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
| 60J60 | Diffusion processes |
| 76R50 | Diffusion |
| 82B41 | Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics |
References:
| [1] | D. Aldous, J.A. Fill, Reversible Markov chains and random walks on graphs, unfinished monograph, recompiled 2014, 2002, available at http://www.stat.berkeley.edu/ aldous/RWG/book.html; D. Aldous, J.A. Fill, Reversible Markov chains and random walks on graphs, unfinished monograph, recompiled 2014, 2002, available at http://www.stat.berkeley.edu/ aldous/RWG/book.html |
| [2] | Feller, W., An Introduction to Probability Theory and its Applications, Volume I (1968), John Wiley & Sons: John Wiley & Sons Hoboken, NJ, USA · Zbl 0155.23101 |
| [3] | Feller, W., An Introduction to Probability Theory and its Applications, Volume II (1971), John Wiley & Sons: John Wiley & Sons Hoboken, NJ, USA · Zbl 0219.60003 |
| [4] | Hughes, B. D., Random Walks and Randon Environments, Volume 1: Random Walks (1995), Oxford University Press: Oxford University Press Oxford, UK · Zbl 0820.60053 |
| [5] | Kutner, R.; Masoliver, J., The continuous time random walk, still trendy: Fifty-year history, state of art, and outlook, Eur. Phys. J. B, 90, 50 (2017) |
| [6] | Pearson, K., The problem of the random walk, Nature, 72, 294 (1905) · JFM 36.0303.02 |
| [7] | Ore, O., Pascal and the invention of probability theory, Amer. Math. Monthly, 67, 409-419 (1960) · Zbl 0092.24503 |
| [8] | Einstein, A., Über die von der molekularkinetischen Theorie der Wärme geforderte Bewegung von in ruhenden Flüssigkeiten suspendierten Teilchen, Ann. Phys., 322, 549-560 (1905) · JFM 36.0975.01 |
| [9] | Viswanathan, G. M.; Buldyrev, S. V.; Havlin, S.; da Luz, M. G.E.; Raposo, E. P.; Stanley, H. E., Optimizing the success of random searches, Nature, 401, 911-914 (1999) |
| [10] | Codling, E. A.; Plank, M. J.; Benhamou, S., Random walk models in biology, J. R. Soc. Interface, 5, 813-834 (2008) |
| [11] | Humphries et al., N. E., Environmental context explains Lévy and Brownian movement patterns of marine predators, Nature, 465, 1066-1069 (2010) |
| [12] | Okubo, A.; Levin, S. A., Diffusion and Ecological Problems: Modern Perspectives (2001), Springer: Springer New York, NY, USA · Zbl 1027.92022 |
| [13] | Tuckwell, H. C., Introduction to Theoretical Neurobiology: Volume 2, Nonlinear and Stochastic Theories (1988), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 0647.92009 |
| [14] | Gabbiani, F.; Cox, S. J., Mathematics for Neuroscientists (2010), Academic Press: Academic Press Amsterdam, The Netherlands · Zbl 1309.92003 |
| [15] | Usher, M.; McClelland, J. L., The time course of perceptual choice: The leaky, competing accumulator model, Psychol. Rev., 108, 550-592 (2001) |
| [16] | Gold, J. I.; Shadlen, M. N., The neural basis of decision making, Annu. Rev. Neurosci., 30, 535-574 (2007) |
| [17] | Ewens, W. J., Mathematical Population Genetics I. Theoretical Introduction (2010), Springer: Springer New York, NY, USA · Zbl 1060.92046 |
| [18] | Fisher, M. E., Shape of a self-avoiding walk or polymer chain, J. Chem. Phys., 44, 616-622 (1966) |
| [19] | Isichenko, M. B., Percolation, statistical topography, and transport in random media, Rev. Modern Phys., 64, 961-1043 (1992) |
| [20] | Campbell, J. Y.; Lo, A. W.; MacKinlay, A. C., The Econometrics of Financial Markets (1996), Princeton University Press: Princeton University Press Princeton, NJ, USA · Zbl 0927.62113 |
| [21] | Mantegna, R. N.; Stanley, H. E., An Introduction to Econophysics (1999), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 0958.76001 |
| [22] | Jia, Tao; Wang, Dashun; Szymanski, Boleslaw K., Quantifying patterns of research-interest evolution, Nat. Human Behav., 1, 0078 (2017) |
| [23] | Gleich, D. F., PageRank beyond the Web, SIAM Rev., 57, 321-363 (2015) · Zbl 1336.05122 |
| [24] | Coifman, R. R.; Lafon, S.; Lee, A. B.; Maggioni, M.; Nadler, B.; Warner, F.; Zucker, S. W., Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps, Proc. Natl. Acad. Sci. USA, 102, 7426-7431 (2005) · Zbl 1405.42043 |
| [25] | Coifman, R. R.; Lafon, S., Diffusion maps, Appl. Comput. Harmon. Anal., 21, 5-30 (2006) · Zbl 1095.68094 |
| [26] | Clauset, A.; Kogan, M.; Redner, S., Safe leads and lead changes in competitive team sports, Phys. Rev. E, 91, 062815 (2015) |
| [27] | Godrèche, C.; Majumdar, S. N.; Schehr, G., Record statistics of a strongly correlated time series: Random walks and Lévy flights, J. Phys. A, 50, 333001 (2017) · Zbl 1376.82074 |
| [28] | Iannelli, F.; Koher, A.; Brockmann, D.; Hövel, P.; Sokolov, I. M., Effective distances for epidemics spreading on complex networks, Phys. Rev. E, 95, 012313 (2017) |
| [29] | Spitzer, F., Principles of Random Walk (1976), Springer: Springer New York, NY, USA · Zbl 0119.34304 |
| [30] | Weiss, G. H., Aspects and Applications of the Random Walk (1994), North-Holland: North-Holland Amsterdam, The Netherlands · Zbl 0925.60079 |
| [31] | Redner, S., A Guide to First-Passage Processes (2001), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 0980.60006 |
| [32] | Burioni, R.; Cassi, D., Random walks on graphs: Ideas, techniques and results, J. Phys. A, 38, R45-R78 (2005) · Zbl 1076.82023 |
| [33] | Krapivsky, P. L.; Redner, S.; Ben-Naim, E., A Kinetic View of Statistical Physics (2010), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 1235.82040 |
| [34] | Klafter, J.; Sokolov, I. M., First Steps in Random Walks (2011), Oxford University Press: Oxford University Press Oxford, UK · Zbl 1242.60046 |
| [35] | Ibe, O. C., Elements of Random Walk and Diffusion Processes (2013), Wiley: Wiley Hoboken, NJ, USA · Zbl 1294.60002 |
| [36] | Rammal, R., Random-walk statistics on fractal structures, J. Stat. Phys., 36, 547-560 (1984) · Zbl 0587.60061 |
| [37] | Havlin, S.; ben-Avraham, D., Diffusion in disordered media, Adv. Phys., 36, 695-798 (1987) |
| [38] | Bouchaud, J. P.; Georges, A., Anomalous diffusion in disordered media: Statistical mechanisms, models and physical applications, Phys. Rep., 195, 127-293 (1990) |
| [39] | ben-Avraham, D.; Havlin, S., Diffusion and Reactions in Fractals and Disordered Systems (2000), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 1075.82001 |
| [40] | Bénichou, O.; Voituriez, R., From first-passage times of random walks in confinement to geometry-controlled kinetics, Phys. Rep., 539, 225-284 (2014) · Zbl 1358.60003 |
| [41] | Doyle, P. G.; Snell, J. L., Random Walks and Electric Networks (1984), Mathematical Association of America: Mathematical Association of America Washington, DC, USA · Zbl 0583.60065 |
| [42] | Lovász, L., Random walks on graphs: A survey, (Miklós, D.; Sós, V. T.; Szőnyi, T., Combinatorics, Paul Erdős Is Eighty, Volume 1 (1993), János Bolyai Math. Soc.: János Bolyai Math. Soc. Budapest, Hungary), 353-398 · Zbl 0782.00098 |
| [43] | Porter, M. A.; Bianconi, G., Editorial: Network analysis and modelling: Special issue of European Journal of Applied Mathematics, Eur. J. Appl. Math., 27, 807-811 (2016) · Zbl 1384.00084 |
| [44] | Newman, M. E.J., Networks: An Introduction (2010), Oxford University Press: Oxford University Press Oxford, UK · Zbl 1195.94003 |
| [45] | Barabási, A. L., Network Science (2016), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 1353.94001 |
| [46] | Boccaletti, S.; Latora, V.; Moreno, Y.; Chavez, M.; Hwang, D. U., Complex networks: structure and dynamics, Phys. Rep., 424, 175-308 (2006) · Zbl 1371.82002 |
| [47] | Strogatz, S. H., Exploring complex networks, Nature, 410, 268-276 (2001) · Zbl 1370.90052 |
| [48] | Barrat, A.; Barthélemy, M.; Vespignani, A., Dynamical Processes on Complex Networks (2008), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 1198.90005 |
| [49] | Porter, M. A.; Gleeson, J. P., Dynamical Systems on Networks: A Tutorial (2016), Springer: Springer Heidelberg, Germany · Zbl 1369.34001 |
| [50] | Dorogovtsev, S. N.; Mendes, J. F.F., Evolution of Networks: From Biological Nets to the Internet and WWW (2003), Oxford University Press: Oxford University Press Oxford, UK · Zbl 1109.68537 |
| [51] | Cohen, R.; Havlin, S., Complex Networks: Structure, Robustness and Function (2010), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 1196.05092 |
| [52] | Estrada, E., The Structure of Complex Networks: Theory and Applications (2012), Oxford University Press: Oxford University Press Oxford, UK · Zbl 1267.05001 |
| [53] | Newman, M. E.J., The structure and function of complex networks, SIAM Rev., 45, 167-256 (2003) · Zbl 1029.68010 |
| [54] | Arenas, A.; Díaz-Guilera, A.; Kurths, J.; Moreno, Y.; Zhou, C., Synchronization in complex networks, Phys. Rep., 469, 93-153 (2008) |
| [55] | Albert, R.; Barabási, A. L., Statistical mechanics of complex networks, Rev. Modern Phys., 74, 47-97 (2002) · Zbl 1205.82086 |
| [56] | Dorogovtsev, S. N.; Goltsev, A. V.; Mendes, J. F.F., Critical phenomena in complex networks, Rev. Modern Phys., 80, 1275-1335 (2008) |
| [57] | Holme, P.; Saramäki, J., Temporal networks, Phys. Rep., 519, 97-125 (2012) |
| [58] | Holme, P., Modern temporal network theory: A colloquium, Eur. Phys. J. B, 88, 234 (2015) |
| [59] | Masuda, N.; Lambiotte, R., A Guide to Temporal Networks (2016), World Scientific: World Scientific London, UK · Zbl 1376.60001 |
| [60] | Boccaletti, S.; Bianconi, G.; Criado, R.; del Genio, C. I.; Gómez-Gardeñes, J.; Romance, M.; Sendiña-Nadal, I.; Wang, Z.; Zanin, M., The structure and dynamics of multilayer networks, Phys. Rep., 544, 1-122 (2014) |
| [61] | Kivelä, M.; Arenas, A.; Barthelemy, M.; Gleeson, J. P.; Moreno, Y.; Porter, M. A., Multilayer Networks, J. Comput. Netw., 2, 203-271 (2014) |
| [62] | De Domenico, M.; Granell, C.; Porter, M. A.; Arenas, A., The physics of spreading processes in multilayer networks, Nat. Phys., 12, 901-906 (2016) |
| [63] | M.A. Porter, J.P. Onnela, P.J. Mucha, Communities in networks, Notices Amer. Math. Soc. 56 (2009) 1082-1097, 1164-1166.; M.A. Porter, J.P. Onnela, P.J. Mucha, Communities in networks, Notices Amer. Math. Soc. 56 (2009) 1082-1097, 1164-1166. · Zbl 1188.05142 |
| [64] | Fortunato, S., Community detection in graphs, Phys. Rep., 486, 75-174 (2010) |
| [65] | Fortunato, S.; Hric, D., Community detection in networks: A user guide, Phys. Rep., 659, 1-44 (2016) |
| [66] | S. Brin, L. Page, Anatomy of a large-scale hypertextual web search engine, in: Proceedings of the Seventh International World Wide Web Conference, 1998, pp. 107-117.; S. Brin, L. Page, Anatomy of a large-scale hypertextual web search engine, in: Proceedings of the Seventh International World Wide Web Conference, 1998, pp. 107-117. |
| [67] | Bonacich, P., Factoring and weighting approaches to status scores and clique identification, J. Math. Sociol., 2, 113-120 (1972) |
| [68] | Jeub, L. G.S.; Balachandran, P.; Porter, M. A.; Mucha, P. J.; Mahoney, M. W., Think locally, act locally: Detection of small, medium-sized, and large communities in large networks, Phys. Rev. E, 91, 012821 (2015) |
| [69] | Gillis, J., Correlated random walk, Math. Proc. Cambridge Philos. Soc., 51, 639-651 (1955) · Zbl 0068.12102 |
| [70] | Domb, C., From random to self-avoiding walks, J. Stat. Phys., 30, 425-436 (1983) |
| [71] | Madras, N.; Slade, G., The Self-Avoiding Walk (1993), Birkhäuser: Birkhäuser Boston, MA, USA · Zbl 0780.60103 |
| [72] | Evans, M. R.; Hanney, T., Nonequilibrium statistical mechanics of the zero-range process and related models, J. Phys. A, 38, R195-R240 (2005) · Zbl 1086.82012 |
| [73] | Schenzle, A.; Brand, H., Multiplicative stochastic processes in statistical physics, Phys. Rev. A, 20, 1628-1647 (1979) |
| [74] | Havlin, S.; Selinger, R. B.; Schwartz, M.; Stanley, H. E.; Bunde, A., Random multiplicative processes and transport in structures with correlated spatial disorder, Phys. Rev. Lett., 61, 1438-1441 (1988) |
| [75] | Pemantle, R., A survey of random processes with reinforcement, Probab. Surv., 4, 1-79 (2007) · Zbl 1189.60138 |
| [76] | Schinazi, R. B., Classical and Spatial Stochastic Processes (1999), Birkhäuser: Birkhäuser Boston, MA, USA · Zbl 0919.60002 |
| [77] | Schütz, G. M.; Trimper, S., Elephants can always remember: Exact long-range memory effects in a non-Markovian random walk, Phys. Rev. E, 70, 045101(R) (2004) |
| [78] | Kempe, J., Quantum random walks: An introductory overview, Contemp. Phys., 44, 307-327 (2003) |
| [79] | Mülken, O.; Blumen, A., Continuous-time quantum walks: Models for coherent transport on complex networks, Phys. Rep., 502, 37-87 (2011) |
| [80] | Bénichou, O.; Loverdo, C.; Moreau, M.; Voituriez, R., Intermittent search strategies, Rev. Modern Phys., 83, 81-130 (2011) |
| [81] | Tejedor, V.; Voituriez, R.; Bénichou, O., Optimizing persistent random searches, Phys. Rev. Lett., 108, 088103 (2012) |
| [82] | Bénichou, O.; Redner, S., Depletion-controlled starvation of a diffusing forager, Phys. Rev. Lett., 113, 238101 (2014) |
| [83] | Bénichou, O.; Chupeau, M.; Redner, S., Role of depletion on the dynamics of a diffusing forager, J. Phys. A, 49, 394003 (2016) · Zbl 1353.82030 |
| [84] | Bhat, U.; Redner, S.; Bénichou, O., Starvation dynamics of a greedy forager, J. Stat. Mech., 073213 (2017) · Zbl 1457.82349 |
| [85] | Grebenkov, D. S.; Rupprecht, J. F., The escape problem for mortal walkers, J. Chem. Phys., 146, 084106 (2017) |
| [86] | T. Schilling, T. Voigtmann, Clearing out a maze: The hungry random walker and its anomalous diffusion, 2016, https://arxiv.org/abs/1607.01123; T. Schilling, T. Voigtmann, Clearing out a maze: The hungry random walker and its anomalous diffusion, 2016, https://arxiv.org/abs/1607.01123 |
| [87] | Ghosh, R.; Lerman, K., Rethinking centrality: The role of dynamical processes in social network analysis, Discrete Contin. Dyn. Syst. Ser. B, 19, 1355-1372 (2014) · Zbl 1307.91153 |
| [88] | Yan, X.; Teng, S.h.; Lerman, K.; Ghosh, R., Capturing the interplay of dynamics and networks through parameterizations of Laplacian operators, PeerJ Comput. Sci., 2, e57 (2016) |
| [89] | Anderson, R. M.; May, R. M., Infectious Diseases of Humans (1991), Oxford University Press: Oxford University Press Oxford, UK |
| [90] | Pastor-Satorras, R.; Castellano, C.; Van Mieghem, P.; Vespignani, A., Epidemic processes in complex networks, Rev. Modern Phys., 87, 925-979 (2015) |
| [91] | Y. Wang, D. Chakrabarti, C. Wang, C. Faloutsos, Epidemic spreading in real networks: an eigenvalue viewpoint, in: Proc. 22nd International Symposium on Reliable Distributed Systems, SRDS’03, 2003, pp. 25-34.; Y. Wang, D. Chakrabarti, C. Wang, C. Faloutsos, Epidemic spreading in real networks: an eigenvalue viewpoint, in: Proc. 22nd International Symposium on Reliable Distributed Systems, SRDS’03, 2003, pp. 25-34. |
| [92] | Klemm, K.; Serrano, M.Á.; Eguíluz, V. M.; San Miguel, M., A measure of individual role in collective dynamics, Sci. Rep., 2, 292 (2012) |
| [93] | Godsil, C.; Royle, G., Algebraic Graph Theory (2001), Springer: Springer New York, NY, USA · Zbl 0968.05002 |
| [94] | Valente, T. W., Network Models of the Diffusion of Innovations (1995), Hampton Press: Hampton Press Cresskill, NJ, USA |
| [95] | Asllani, M.; Challenger, J. D.; Pavone, F. S.; Sacconi, L.; Fanelli, D., The theory of pattern formation on directed networks, Nat. Commun., 5, 4517 (2014) |
| [96] | Montroll, E. W.; Weiss, G. H., Random walks on lattices. II, J. Math. Phys., 6, 167-181 (1965) · Zbl 1342.60067 |
| [97] | Cox, D. R., Renewal Theory (1962), Methuen & Co. Ltd.: Methuen & Co. Ltd. Frome, UK · Zbl 0103.11504 |
| [98] | Grigolini, P.; Palatella, L.; Raffaelli, G., Asymmetric anomalous diffusion: An efficient way to detect memory in time series, Fractals, 9, 439-449 (2001) |
| [99] | Hoory, S.; Linial, N.; Wigderson, A., Expander graphs and their applications, Bull. Amer. Math. Soc., 43, 439-561 (2006) · Zbl 1147.68608 |
| [100] | Clauset, A.; Shalizi, C. R.; Newman, M. E.J., Power-law distributions in empirical data, SIAM Rev., 51, 661-703 (2009) · Zbl 1176.62001 |
| [101] | Eisler, Z.; Kertész, J., Random walks on complex networks with inhomogeneous impact, Phys. Rev. E, 71, 057104 (2005) |
| [102] | Wang, W. X.; Wang, B. H.; Yin, C. Y.; Xie, Y. B.; Zhou, T., Traffic dynamics based on local routing protocol on a scale-free network, Phys. Rev. E, 73, 026111 (2006) |
| [103] | Fronczak, A.; Fronczak, P., Biased random walks in complex networks: The role of local navigation rules, Phys. Rev. E, 80, 016107 (2009) |
| [104] | Lee, S.; Yook, S. H.; Kim, Y., Centrality measure of complex networks using biased random walks, Eur. Phys. J. B, 68, 277-281 (2009) |
| [105] | Baronchelli, A.; Pastor-Satorras, R., Mean-field diffusive dynamics on weighted networks, Phys. Rev. E, 82, 011111 (2010) |
| [106] | Bonaventura, M.; Nicosia, V.; Latora, V., Characteristic times of biased random walks on complex networks, Phys. Rev. E, 89, 012803 (2014) |
| [107] | Demetrius, L.; Manke, T., Robustness and network evolution—an entropic principle, Physica A, 346, 682-696 (2005) |
| [108] | Gómez-Gardeñes, J.; Latora, V., Entropy rate of diffusion processes on complex networks, Phys. Rev. E, 78, 065102(R) (2008) |
| [109] | Burda, Z.; Duda, J.; Luck, J. M.; Waclaw, B., Localization of the maximal entropy random walk, Phys. Rev. Lett., 102, 160602 (2009) |
| [110] | Delvenne, J. C.; Libert, A. S., Centrality measures and thermodynamic formalism for complex networks, Phys. Rev. E, 83, 046117 (2011) |
| [111] | Sinatra, R.; Gómez-Gardeñes, J.; Lambiotte, R.; Nicosia, V.; Latora, V., Maximal-entropy random walks in complex networks with limited information, Phys. Rev. E, 83, 030103(R) (2011) |
| [112] | Kemeny, J. G.; Snell, J. L., Finite Markov Chains (Second Printing) (1976), Springer-Verlag: Springer-Verlag New York, NY, USA |
| [113] | Papoulis, A.; Pillai, S. U., Probability, Random Variables, and Stochastic Processes (2002), McGraw-Hill: McGraw-Hill New York, NY, USA |
| [114] | Iosifescu, M., Finite Markov Processes and Their Applications (1980), Dover Publications: Dover Publications Mineola, NY, USA · Zbl 0436.60001 |
| [115] | Stewart, W. J., Introduction to the Numerical Solution of Markov Chains (1994), Princeton University Press: Princeton University Press Princeton, NJ, USA · Zbl 0821.65099 |
| [116] | Norris, J. R., Markov Chains (1997), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 0873.60043 |
| [117] | Taylor, H. M.; Karlin, S., An Introduction to Stochastic Modeling (1998), Academic Press: Academic Press San Diego, CA, USA · Zbl 0946.60002 |
| [118] | Levin, D. A.; Peres, Y.; Wilmer, E. L., Markov Chains and Mixing Times (2009), American Mathematical Society: American Mathematical Society Providence, RI, USA · Zbl 1160.60001 |
| [119] | Blanchard, P.; Volchenkov, D., Random Walks and Diffusions on Graphs and Databases: An Introduction (2011), Springer: Springer Heidelberg, Germany · Zbl 1242.05250 |
| [120] | Privault, N., Understanding Markov Chains: Examples and Applications (2013), Springer: Springer Singapore · Zbl 1305.60003 |
| [121] | Sethna, J. P., Statistical Mechanics: Entropy, Order Parameters and Complexity (2006), Oxford University Press: Oxford University Press Oxford, UK · Zbl 1140.82004 |
| [122] | B.K. Fosdick, D.B. Larremore, J. Nishimura, J. Ugander, Configuring random graph models with fixed degree sequences, SIAM Rev. (2017), (in press) https://arxiv.org/abs/1608.00607; B.K. Fosdick, D.B. Larremore, J. Nishimura, J. Ugander, Configuring random graph models with fixed degree sequences, SIAM Rev. (2017), (in press) https://arxiv.org/abs/1608.00607 · Zbl 1387.05235 |
| [123] | Colizza, V.; Vespignani, A., Epidemic modeling in metapopulation systems with heterogeneous coupling pattern: Theory and simulations, J. Theoret. Biol., 251, 450-467 (2008) · Zbl 1398.92233 |
| [124] | Lin, Y.; Zhang, Z., Random walks in weighted networks with a perfect trap: An application of Laplacian spectra, Phys. Rev. E, 87, 062140 (2013) |
| [125] | Zhang, Z.; Shan, T.; Chen, G., Random walks on weighted networks, Phys. Rev. E, 87, 012112 (2013) |
| [126] | Donato, D.; Laura, L.; Leonardi, S.; Millozzi, S., Large scale properties of the Webgraph, Eur. Phys. J. B, 38, 239-243 (2004) |
| [127] | Fortunato, S.; Flammini, A.; Menczer, F.; Vespignani, A., Topical interests and the mitigation of search engine bias, Proc. Natl. Acad. Sci. USA, 103, 12684-12689 (2006) |
| [128] | Restrepo, J. G.; Ott, E.; Hunt, B. R., Characterizing the dynamical importance of network nodes and links, Phys. Rev. Lett., 97, 094102 (2006) |
| [129] | Davis, P. M., Eigenfactor: Does the principle of repeated improvement result in better estimates than raw citation counts?, J. Amer. Soc. Info. Sci. Technol., 59, 2186-2188 (2008) |
| [130] | Fortunato, S.; Boguñá, M.; Flammini, A.; Menczer, F., Approximating pageRank from in-degree, Lecture Notes in Comput. Sci., 4936, 59-71 (2008) · Zbl 1142.68311 |
| [131] | Fersht, A., The most influential journals: Impact factor and Eigenfactor, Proc. Natl. Acad. Sci. USA, 106, 6883-6884 (2009) |
| [132] | Masuda, N.; Ohtsuki, H., Evolutionary dynamics and fixation probabilities in directed networks, New J. Phys., 11, 033012 (2009) |
| [133] | Ghoshal, G.; Barabási, A. L., Ranking stability and super-stable nodes in complex networks, Nature Commun., 2, 394 (2011) |
| [134] | Sandryhaila, A.; Moura, J. M.F., Discrete signal processing on graphs, IEEE Trans. Signal Process., 61, 1644-1656 (2013) · Zbl 1393.94424 |
| [135] | Tremblay, N.; Borgnat, P., Graph wavelets for multiscale community mining, IEEE Trans. Signal Process., 62, 5227-5239 (2014) · Zbl 1394.94602 |
| [136] | Samukhin, A. N.; Dorogovtsev, S. N.; Mendes, J. F.F., Laplacian spectra of, and random walks on, complex networks: Are scale-free architectures really important?, Phys. Rev. E, 77, 036115 (2008) |
| [137] | Chung, F. R.K., Spectral Graph Theory (1997), American Mathematical Society: American Mathematical Society Providence, RI, USA · Zbl 0867.05046 |
| [138] | Donetti, L.; Neri, F.; Muñoz, M. A., Optimal network topologies: expanders, cages, Ramanujan graphs, entangled networks and all that, J. Stat. Mech., 2006, P08007 (2006) · Zbl 1459.05169 |
| [139] | Cvetković, D.; Rowlinson, P.; Simić, S., An Introduction to the Theory of Graph Spectra (2010), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 1211.05002 |
| [140] | Van Mieghem, P., Graph Spectra for Complex Networks (2011), Cambridge University Press · Zbl 1232.05128 |
| [141] | Golub, G. H.; Van Loan, C. F., Matrix Computations (1996), The Johns Hopkins University Press: The Johns Hopkins University Press Baltimore, MD, USA · Zbl 0865.65009 |
| [142] | Estrada, E.; Hatano, N.; Benzi, M., The physics of communicability in complex networks, Phys. Rep., 514, 89-119 (2012) |
| [143] | Miekkala, U., Graph properties for splitting with grounded Laplacian matrices, BIT, 33, 485-495 (1993) · Zbl 0789.65021 |
| [144] | Noh, J. D.; Rieger, H., Random walks on complex networks, Phys. Rev. Lett., 92, 118701 (2004) |
| [145] | Wilf, H. S., generatingfunctionology (2005), A K Peters, Ltd.: A K Peters, Ltd. Wellesley, MA, USA · Zbl 0689.05001 |
| [146] | Kittas, A.; Carmi, S.; Havlin, S.; Argyrakis, P., Trapping in complex networks, Europhys. Lett., 84, 40008 (2008) |
| [147] | Perra, N.; Baronchelli, A.; Mocanu, D.; Gonçalves, B.; Pastor-Satorras, R.; Vespignani, A., Random walks and search in time-varying networks, Phys. Rev. Lett., 109, 238701 (2012) |
| [148] | Starnini, M.; Baronchelli, A.; Barrat, A.; Pastor-Satorras, R., Random walks on temporal networks, Phys. Rev. E, 85, 056115 (2012) |
| [149] | Almaas, E.; Kulkarni, R. V.; Stroud, D., Scaling properties of random walks on small-world networks, Phys. Rev. E, 68, 056105 (2003) |
| [150] | Masuda, N.; Konno, N., Return times of random walk on generalized random graphs, Phys. Rev. E, 69, 066113 (2004) |
| [151] | Hwang, S.; Lee, D. S.; Kahng, B., Effective trapping of random walkers in complex networks, Phys. Rev. E, 85, 046110 (2012) |
| [152] | Hwang, S.; Lee, D. S.; Kahng, B., Origin of the hub spectral dimension in scale-free networks, Phys. Rev. E, 87, 022816 (2013) |
| [153] | Peng, J.; Agliari, E.; Zhang, Z., Exact calculations of first-passage properties on the pseudofractal scale-free web, Chaos, 25, 073118 (2015) · Zbl 1374.82014 |
| [154] | Montroll, E. W., Random walks on lattices. III. Calculation of first-passage times with application to exciton trapping on photosynthetic units, J. Math. Phys., 10, 753-765 (1969) · Zbl 1368.60049 |
| [155] | Bollt, E. M.; ben-Avraham, D., What is special about diffusion on scale-free nets?, New J. Phys., 7, 26 (2005) |
| [156] | Sood, V.; Redner, S.; ben-Avraham, D., First-passage properties of the Erdős-Renyi random graph, J. Phys. A, 38, 109-123 (2005) · Zbl 1067.60001 |
| [157] | Löwe, M.; Torres, F., On hitting times for a simple random walk on dense Erdös-Rényi random graphs, Statist. Probab. Lett., 89, 81-88 (2014) · Zbl 1295.05214 |
| [158] | Tishby, I.; Biham, O.; Katzav, E., The distribution of first hitting times of random walks on directed Erdős-Rényi networks, J. Stat. Mech., 043402 (2017) · Zbl 1457.82162 |
| [159] | Jespersen, S.; Sokolov, I. M.; Blumen, A., Relaxation properties of small-world networks, Phys. Rev. E, 62, 4405-4408 (2000) |
| [160] | Pandit, S. A.; Amritkar, R. E., Random spread on the family of small-world networks, Phys. Rev. E, 63, 041104 (2001) |
| [161] | Lahtinen, J.; Kertész, J.; Kaski, K., Scaling of random spreading in small world networks, Phys. Rev. E, 64, 057105 (2001) |
| [162] | Jasch, F.; Blumen, A., Trapping of random walks on small-world networks, Phys. Rev. E, 64, 066104 (2001) |
| [163] | Parris, P. E.; Kenkre, V. M., Traversal times for random walks on small-world networks, Phys. Rev. E, 72, 056119 (2005) |
| [164] | Yang, S. J., Exploring complex networks by walking on them, Phys. Rev. E, 71, 016107 (2005) |
| [165] | Porter, M. A., Small-world network, Scholarpedia, 7, 2, 1739 (2012) |
| [166] | Hwang, S.; Lee, D. S.; Kahng, B., First passage time for random walks in heterogeneous networks, Phys. Rev. Lett., 109, 088701 (2012) |
| [167] | Condamin, S.; Bénichou, O.; Tejedor, V.; Voituriez, R.; Klafter, J., First-passage times in complex scale-invariant media, Nature, 450, 77-80 (2007) |
| [168] | Dorogovtsev, S. N.; Goltsev, A. V.; Mendes, J. F.F., Pseudofractal scale-free web, Phys. Rev. E, 65, 066122 (2002) |
| [169] | Ravasz, E.; Somera, A. L.; Mongru, D. A.; Oltvai, Z. N.; Barabási, A. L., Hierarchical organization of modularity in metabolic networks, Science, 297, 1551-1555 (2002) |
| [170] | Ravasz, E.; Barabási, A. L., Hierarchical organization in complex networks, Phys. Rev. E, 67, 026112 (2003) |
| [171] | Rozenfeld, H. D.; Havlin, S.; ben Avraham, D., Fractal and transfractal recursive scale-free nets, New J. Phys., 9, 175 (2007) |
| [172] | Song, C.; Havlin, S.; Makse, H. A., Self-similarity of complex networks, Nature, 433, 392-395 (2005) |
| [173] | Song, C. M.; Havlin, S.; Makse, H. A., Origins of fractality in the growth of complex networks, Nat. Phys., 2, 275-281 (2006) |
| [174] | Simon, H. A., The architecture of complexity, Proc. Am. Phil. Soc., 106, 467-482 (1962), http://www.jstor.org/stable/985254 |
| [175] | J. Leskovec, D. Huttenlocher, J. Kleinberg, Signed networks in social media, in: Proc. 28th International Conference on Human Factors in Computing Systems - CHI ’10, 2010, pp. 1361-1370.; J. Leskovec, D. Huttenlocher, J. Kleinberg, Signed networks in social media, in: Proc. 28th International Conference on Human Factors in Computing Systems - CHI ’10, 2010, pp. 1361-1370. |
| [176] | Karrer, B.; Newman, M. E.J., Random graph models for directed acyclic networks, Phys. Rev. E, 80, 046110 (2009) |
| [177] | Falconer, K., Fractals: A Very Short Introduction (2013), Oxford University Press: Oxford University Press Oxford, UK · Zbl 1279.28001 |
| [178] | Kozak, J. J.; Balakrishnan, V., Analytic expression for the mean time to absorption for a random walker on the Sierpinski gasket, Phys. Rev. E, 65, 021105 (2002) |
| [179] | Havlin, S.; Weissman, H., Mapping between hopping on hierarchical structures and diffusion on a family of fractals, J. Phys. A, 19, L1021-L1026 (1986) |
| [180] | Kahng, B.; Redner, S., Scaling of the first-passage time and the survival probability on exact and quasi-exact self-similar structures, J. Phys. A, 22, 887-902 (1989) |
| [181] | Agliari, E., Exact mean first-passage time on the T-graph, Phys. Rev. E, 77, 011128 (2008) |
| [182] | Vicsek, T., Fractal models for diffusion controlled aggregation, J. Phys. A, 16, L647-L652 (1983) |
| [183] | Blumen, A.; Jurjiu, A.; Koslowski, T.; von Ferber, C., Dynamics of Vicsek fractals, models for hyperbranched polymers, Phys. Rev. E, 67, 061103 (2003) |
| [184] | Zhang, Z.; Wu, B.; Zhang, H.; Zhou, S.; Guan, J.; Wang, Z., Determining global mean-first-passage time of random walks on Vicsek fractals using eigenvalues of Laplacian matrices, Phys. Rev. E, 81, 031118 (2010) |
| [185] | Matan, O.; Havlin, S., Mean first-passage time on loopless aggregates, Phys. Rev. A, 40, 6573-6579 (1989) |
| [186] | Berker, A. N.; Ostlund, S., Renormalization-group calculations of finite systems: Order parameter and specific heat for epitaxial ordering, J. Phys. C, 12, 4961-4975 (1979) |
| [187] | Tejedor, V.; Bénichou, O.; Voituriez, R., Global mean first-passage times of random walks on complex networks, Phys. Rev. E, 80, 065104(R) (2009) |
| [188] | Zhang, Z.; Lin, Y.; Ma, Y., Effect of trap position on the efficiency of trapping in treelike scale-free networks, J. Phys. A, 44, 075102 (2011) · Zbl 1210.05160 |
| [189] | Yun, C. K.; Kahng, B.; Kim, D., Annihilation of two-species reaction-diffusion processes on fractal scale-free networks, New J. Phys., 11, 063025 (2009) |
| [190] | Barabási, A. L.; Ravasz, E.; Vicsek, T., Deterministic scale-free networks, Physica A, 299, 559-564 (2001) · Zbl 0972.57003 |
| [191] | Jung, S.; Kim, S.; Kahng, B., Geometric fractal growth model for scale-free networks, Phys. Rev. E, 65, 056101 (2002) |
| [192] | 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) |
| [193] | Doye, J. P.K.; Massen, C. P., Self-similar disk packings as model spatial scale-free networks, Phys. Rev. E, 71, 016128 (2005) |
| [194] | Zhang, Z.; Qi, Y.; Zhou, S.; Xie, W.; Guan, J., Exact solution for mean first-passage time on a pseudofractal scale-free web, Phys. Rev. E, 79, 021127 (2009) |
| [195] | Zhang, Z.; Qi, Y.; Zhou, S.; Gao, S.; Guan, J., Explicit determination of mean first-passage time for random walks on deterministic uniform recursive trees, Phys. Rev. E, 81, 016114 (2010) |
| [196] | Zhang, Z.; Guo, X.; Lin, Y., Full eigenvalues of the Markov matrix for scale-free polymer networks, Phys. Rev. E, 90, 022816 (2014) |
| [197] | Agliari, E.; Burioni, R., Random walks on deterministic scale-free networks: Exact results, Phys. Rev. E, 80, 031125 (2009) |
| [198] | Zhang, Z.; Lin, Y.; Gao, S.; Zhou, S.; Guan, J.; Li, M., Trapping in scale-free networks with hierarchical organization of modularity, Phys. Rev. E, 80, 051120 (2009) |
| [199] | Zhang, Z.; Guan, J.; Xie, W.; Qi, Y.; Zhou, S., Random walks on the Apollonian network with a single trap, Europhys. Lett., 86, 10006 (2009) |
| [200] | Reuveni, S.; Granek, R.; Klafter, J., Vibrational shortcut to the mean-first-passage-time problem, Phys. Rev. E, 81, 040103(R) (2010) |
| [201] | Gallos, L. K.; Song, C.; Havlin, S.; Makse, H. A., Scaling theory of transport in complex biological networks, Proc. Natl. Acad. Sci. USA, 104, 7746-7751 (2007) |
| [202] | Baronchelli, A.; Loreto, V., Ring structures and mean first passage time in networks, Phys. Rev. E, 73, 026103 (2006) |
| [203] | Lau, H. W.; Szeto, K. Y., Asymptotic analysis of first passage time in complex networks, Europhys. Lett., 90, 40005 (2010) |
| [204] | Cooper, C.; Frieze, A., The cover time of sparse random graphs, Random Struct. Algorithms, 30, 1-16 (2007) · Zbl 1113.05089 |
| [205] | Cooper, C.; Frieze, A., The cover time of the preferential attachment graph, J. Combin. Theory Ser. B, 97, 269-290 (2007) · Zbl 1114.05095 |
| [206] | Chupeau, M.; Bénichou, O.; Voituriez, R., Cover times of random searches, Nat. Phys., 11, 844-847 (2015) |
| [207] | B.F. Maier, D. Brockmann, Cover time for random walks on arbitrary complex networks, 2017, https://arxiv.org/abs/1706.02356; B.F. Maier, D. Brockmann, Cover time for random walks on arbitrary complex networks, 2017, https://arxiv.org/abs/1706.02356 |
| [208] | G. Barnes, U. Feige, Short random walks on graphs, in: Proc. Twenty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’93, 1993, pp. 728-737.; G. Barnes, U. Feige, Short random walks on graphs, in: Proc. Twenty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’93, 1993, pp. 728-737. · Zbl 1310.05188 |
| [209] | Gallos, L. K., Random walk and trapping processes on scale-free networks, Phys. Rev. E, 70, 046116 (2004) |
| [210] | Stauffer, D.; Sahimi, M., Diffusion in scale-free networks with annealed disorder, Phys. Rev. E, 72, 046128 (2005) |
| [211] | da Fontoura Costa, L.; Travieso, G., Exploring complex networks through random walks, Phys. Rev. E, 75, 016102 (2007) |
| [212] | Baronchelli, A.; Catanzaro, M.; Pastor-Satorras, R., Random walks on complex trees, Phys. Rev. E, 78, 011114 (2008) |
| [213] | Asztalos, A.; Toroczkai, Z., Network discovery by generalized random walks, Europhys. Lett., 92, 50008 (2010) |
| [214] | Hoffmann, T.; Porter, M. A.; Lambiotte, R., Generalized master equations for non-Poisson dynamics on networks, Phys. Rev. E, 86, 046102 (2012) |
| [215] | Speidel, L.; Lambiotte, R.; Aihara, K.; Masuda, N., Steady state and mean recurrence time for random walks on stochastic temporal networks, Phys. Rev. E, 91, 012806 (2015) |
| [216] | Colizza, V.; Pastor-Satorras, R.; Vespignani, A., Reaction-diffusion processes and metapopulation models in heterogeneous networks, Nat. Phys., 3, 276-282 (2007) |
| [217] | Vespignani, A., Modelling dynamical processes in complex socio-technical systems, Nat. Phys., 8, 32-39 (2011) |
| [218] | Scardal, P. S.; Taylor, D.; Sun, J.; Arenas, A., Collective frequency variation in network synchronization and reverse PageRank, Phys. Rev. E, 93, 042314 (2016) |
| [219] | Biggs, N., Algebraic potential theory on graphs, Bull. Lond. Math. Soc., 29, 641-682 (1997) · Zbl 0892.05033 |
| [220] | R.P. Agaev, P.Y. Chebotarev, The matrix of maximum out forests of a digraph and its applications, Autom. Rem. Cont. 61 (2000) 1424-1450.; R.P. Agaev, P.Y. Chebotarev, The matrix of maximum out forests of a digraph and its applications, Autom. Rem. Cont. 61 (2000) 1424-1450. · Zbl 1057.05038 |
| [221] | Masuda, N.; Kawamura, Y.; Kori, H., Analysis of relative influence of nodes in directed networks, Phys. Rev. E, 80, 046114 (2009) |
| [222] | Masuda, N.; Kawamura, Y.; Kori, H., Impact of hierarchical modular structure on ranking of individual nodes in directed networks, New J. Phys., 11, 113002 (2009) |
| [223] | Ermentrout, G. B., Stable periodic solutions to discrete and continuum arrays of weakly coupled nonlinear oscillators, SIAM J. Appl. Math., 52, 1665-1687 (1992) · Zbl 0786.45005 |
| [224] | Merris, R., Laplacian matrices of graphs: A survey, Linear Algebra Appl., 197-198, 143-176 (1994) · Zbl 0802.05053 |
| [225] | Mohar, B., Some applications of Laplace eigenvalues of graphs, (Hahn, G.; Sabidussi, G., Graph Symmetry: Algebraic Methods and Applications (1997), Kluwer: Kluwer Dordrecht, The Netherlands), 225-275 · Zbl 0883.05096 |
| [226] | Pecora, L. M.; Carroll, T. L., Synchronization of chaotic systems, Chaos, 25, 097611 (2015) · Zbl 1374.34002 |
| [227] | Motter, A. E., Bounding network spectra for network design, New J. Phys., 9, 182 (2007) |
| [228] | Vázquez, A.; Oliveira, J. G.; Dezsö, Z.; Goh, K. I.; Kondor, I.; Barabási, A. L., Modeling bursts and heavy tails in human dynamics, Phys. Rev. E, 73, 036127 (2006) |
| [229] | Kivelä, M.; Porter, M. A., Estimating interevent time distributions from finite observation periods in communication networks, Phys. Rev. E, 92, 052813 (2015) |
| [230] | Delvenne, J. C.; Lambiotte, R.; Rocha, L. E.C., Diffusion on networked systems is a question of time or structure, Nat. Commun., 6, 7366 (2015) |
| [231] | De Nigris, S.; Hastir, A.; Lambiotte, R., Burstiness and fractional diffusion on complex networks, Eur. Phys. J. B, 89, 114 (2016) |
| [232] | Allen, A. O., Probability, Statistics, and Queueing Theory: With Computer Science Applications (1990), Academic Press: Academic Press Boston, MA, USA · Zbl 0703.62001 |
| [233] | DeFord, D. R.; Pauls, S. D., A new framework for dynamical models on multiplex networks, J. Compl. Netw. (2017) · Zbl 1460.90041 |
| [234] | Mucha, P. J.; Richardson, T.; Macon, K.; Porter, M. A.; Onnela, J. P., Community structure in time-dependent, multiscale, and multiplex networks, Science, 328, 876-878 (2010) · Zbl 1226.91056 |
| [235] | De Domenico, M.; Lancichinetti, A.; Arenas, A.; Rosvall, M., Identifying modular flows on multilayer networks reveals highly overlapping organization in interconnected systems, Phys. Rev. X, 5, 011027 (2015) |
| [236] | Jeub, L. G.S.; Mahoney, M. W.; Mucha, P. J.; Porter, M. A., A local perspective on community structure in multilayer networks, Netw. Sci., 5, 144-163 (2017) |
| [237] | Gómez, S.; Díaz-Guilera, A.; Gómez-Gardeñes, J.; Pérez-Vicente, C. J.; Moreno, Y.; Arenas, A., Diffusion dynamics on multiplex networks, Phys. Rev. Lett., 110, 028701 (2013) |
| [238] | Solé-Ribalta, A.; De Domenico, M.; Kouvaris, N. E.; Díaz-Guilera, A.; Gómez, S.; Arenas, A., Spectral properties of the Laplacian of multiplex networks, Phys. Rev. E, 88, 032807 (2013) |
| [239] | Radicchi, F.; Arenas, A., Abrupt transition in the structural formation of interconnected networks, Nat. Phys., 9, 717-720 (2013) |
| [240] | De Domenico, M.; Solé-Ribalta, A.; Gómez, S.; Arenas, A., Navigability of interconnected networks under random failures, Proc. Natl. Acad. Sci. USA, 111, 8351-8356 (2014) · Zbl 1355.90014 |
| [241] | L. Lacasa, I.P. Mariño, J. Miguez, V. Nicosia, J. Gómez-Gardeñes, Identifying the hidden multiplex architecture of complex systems, 2017, https://arxiv.org/abs/1705.04661; L. Lacasa, I.P. Mariño, J. Miguez, V. Nicosia, J. Gómez-Gardeñes, Identifying the hidden multiplex architecture of complex systems, 2017, https://arxiv.org/abs/1705.04661 |
| [242] | Perra, N.; Gonçalves, B.; Pastor-Satorras, R.; Vespignani, A., Activity driven modeling of time varying networks, Sci. Rep., 2, 469 (2012) |
| [243] | Bollobás, B., Random Graphs (2001), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 0979.05003 |
| [244] | Ribeiro, B.; Perra, N.; Baronchelli, A., Quantifying the effect of temporal resolution on time-varying networks, Sci. Rep., 3, 3006 (2013) |
| [245] | Alessandretti, L.; Sun, K.; Baronchelli, A.; Perra, N., Random walks on activity-driven networks with attractiveness, Phys. Rev. E, 95, 052318 (2017) |
| [246] | Masuda, N.; Klemm, K.; Eguíluz, V. M., Temporal networks: Slowing down diffusion by long lasting interactions, Phys. Rev. Lett., 111, 188701 (2013) |
| [247] | Lambiotte, R.; Salnikov, V.; Rosvall, M., Effect of memory on the dynamics of random walks on networks, J. Comput. Netw., 3, 177-188 (2015) |
| [248] | Scholtes, I.; Wider, N.; Pfitzner, R.; Garas, A.; Tessone, C. J.; Schweitzer, F., Causality-driven slow-down and speed-up of diffusion in non-Markovian temporal networks, Nat. Comm., 5, 5024 (2014) |
| [249] | Sousa da Mata, A.; Pastor-Satorras, R., Slow relaxation dynamics and aging in random walks on activity driven temporal networks, Eur. Phys. J. B, 88, 38 (2015) · Zbl 1516.82041 |
| [250] | Rosvall, M.; Esquivel, A. V.; Lancichinetti, A.; West, J. D.; Lambiotte, R., Memory in network flows and its effects on spreading dynamics and community detection, Nat. Comm., 5, 4630 (2014) |
| [251] | Rocha, L. E.C.; Masuda, N., Random walk centrality for temporal networks, New J. Phys., 16, 063023 (2014) · Zbl 1451.60083 |
| [252] | Saramäki, J.; Holme, P., Exploring temporal networks with greedy walks, Eur. Phys. J. B, 88, 334 (2015) |
| [253] | Harary, F.; Norman, R. Z., Some properties of line digraphs, Rend. Circ. Mat. Palermo, 9, 161-168 (1960) · Zbl 0099.18205 |
| [254] | Evans, T. S.; Lambiotte, R., Line graphs, link partitions, and overlapping communities, Phys. Rev. E, 80, 016105 (2009) |
| [255] | Salnikov, V.; Schaub, M. T.; Lambiotte, R., Using higher-order Markov models to reveal flow-based communities in networks, Sci. Rep., 6, 23194 (2016) |
| [256] | Xu, J.; Wickramarathne, T. L.; Chawla, N. V., Representing higher-order dependencies in networks, Sci. Adv., 2, e1600028 (2016) |
| [257] | Alon, N.; Benjamini, I.; Lubetzky, E.; Sodin, S., Non-backtracking random walks mix faster, Commun. Contemp. Math., 9, 585-603 (2007) · Zbl 1140.60301 |
| [258] | Fitzner, R.; van der Hofstad, R., Non-backtracking random walk, J. Stat. Phys., 150, 264-284 (2013) · Zbl 1259.82043 |
| [259] | Karrer, B.; Newman, M. E.J.; Zdeborová, L., Percolation on sparse networks, Phys. Rev. Lett., 113, 208702 (2014) |
| [260] | Hamilton, K. E.; Pryadko, L. P., Tight lower bound for percolation threshold on an infinite graph, Phys. Rev. Lett., 113, 208701 (2014) |
| [261] | Martin, T.; Zhang, X.; Newman, M. E.J., Localization and centrality in networks, Phys. Rev. E, 90, 052808 (2014) |
| [262] | Krzakala, F.; Moore, C.; Mossel, E.; Neeman, J.; Sly, A.; Zdeborová, L.; Zhang, P., Spectral redemption in clustering sparse networks, Proc. Natl. Acad. Sci. USA, 110, 20935-20940 (2013) · Zbl 1359.62252 |
| [263] | M.E.J. Newman, Spectral community detection in sparse networks, 2013, https://arxiv.org/abs/1308.6494; M.E.J. Newman, Spectral community detection in sparse networks, 2013, https://arxiv.org/abs/1308.6494 |
| [264] | C. Bordenave, M. Lelarge, L. Massoulié, Non-backtracking spectrum of random graphs: community detection and non-regular ramanujan graphs, in: Proc. IEEE 56th Annual Symp. Found. Comput. Sci., FOCS ’15, 2015, pp. 1347-1357.; C. Bordenave, M. Lelarge, L. Massoulié, Non-backtracking spectrum of random graphs: community detection and non-regular ramanujan graphs, in: Proc. IEEE 56th Annual Symp. Found. Comput. Sci., FOCS ’15, 2015, pp. 1347-1357. |
| [265] | Morone, F.; Makse, H. A., Influence maximization in complex networks through optimal percolation, Nature, 524, 65-68 (2015) |
| [266] | Takaguchi, T.; Nakamura, M.; Sato, N.; Yano, K.; Masuda, N., Predictability of conversation partners, Phys. Rev. X, 1, 011008 (2011) |
| [267] | Pfitzner, R.; Scholtes, I.; Garas, A.; Tessone, C. J.; Schweitzer, F., Betweenness preference: Quantifying correlations in the topological dynamics of temporal networks, Phys. Rev. Lett., 110, 198701 (2013) |
| [268] | Li, W.; Ng, M. K., On the limiting probability distribution of a transition probability tensor, Linear Multilinear Algebra, 62, 362-385 (2014) · Zbl 1301.60049 |
| [269] | Benson, A. R.; Gleich, D. F.; Lim, L. H., The spacey random walk: A stochastic process for higher-order data, SIAM Rev., 59, 321-345 (2017) · Zbl 1365.15033 |
| [270] | Kareiva, P.; Shigesada, N., Analyzing insect movement as a correlated random walk, Oecologia, 56, 234-238 (1983) |
| [271] | F. Chierichetti, R. Kumar, P. Raghavan, T. Sarlós, Are web users really Markovian?, in: Proc. 21st Intl. Conf. World Wide Web, WWW ’12, 2012, pp. 609-618.; F. Chierichetti, R. Kumar, P. Raghavan, T. Sarlós, Are web users really Markovian?, in: Proc. 21st Intl. Conf. World Wide Web, WWW ’12, 2012, pp. 609-618. |
| [272] | J. Kleinberg, Complex networks and decentralized search algorithms, in: Proc. Internat. Congress Math., 2006, pp. 1019-1044.; J. Kleinberg, Complex networks and decentralized search algorithms, in: Proc. Internat. Congress Math., 2006, pp. 1019-1044. · Zbl 1102.68514 |
| [273] | Q. Lv, P. Cao, E. Cohen, K. Li, S. Shenker, Search and replication in unstructured peer-to-peer networks, in: Proc. 16th Internat. Conf. Supercomputing, ICS ’02, 2002, pp. 84-95.; Q. Lv, P. Cao, E. Cohen, K. Li, S. Shenker, Search and replication in unstructured peer-to-peer networks, in: Proc. 16th Internat. Conf. Supercomputing, ICS ’02, 2002, pp. 84-95. |
| [274] | N. Bisnik, A. Abouzeid, Modeling and analysis of random walk search algorithms in P2P networks, in: Proc. Second International Workshop on Hot Topics in Peer-To-Peer Systems, 2005, pp. 95-103.; N. Bisnik, A. Abouzeid, Modeling and analysis of random walk search algorithms in P2P networks, in: Proc. Second International Workshop on Hot Topics in Peer-To-Peer Systems, 2005, pp. 95-103. |
| [275] | Tanenbaum, A. S.; Wetherall, D. J., Computer Networks (2011), Prentice Hall: Prentice Hall Boston, MA, USA |
| [276] | Adamic, L. A.; Lukose, R. M.; Puniyani, A. R.; Huberman, B. A., Search in power-law networks, Phys. Rev. E, 64, 046135 (2001) |
| [277] | Lü, L.; Chen, D.; Ren, X. L.; Zhang, Q. M.; Zhang, Y. C.; Zhou, T., Vital nodes identification in complex networks, Phys. Rep., 650, 1-63 (2016) |
| [278] | Katz, L., A new status index derived from sociometric analysis, Psychometrika, 18, 39-43 (1953) · Zbl 0053.27606 |
| [279] | Kleinberg, J. M., Authoritative sources in a hyperlinked environment, J. ACM, 46, 604-632 (1999) · Zbl 1065.68660 |
| [280] | Grindrod, P.; Parsons, M. C.; Higham, D. J.; Estrada, E., Communicability across evolving networks, Phys. Rev. E, 83, 046120 (2011) |
| [281] | Halu, A.; Mondragón, R. J.; Panzarasa, P.; Bianconi, G., Multiplex PageRank, PLoS One, 8, e78293 (2013) |
| [282] | De Domenico, M.; Solé-Ribalta, A.; Omodei, E.; Gómez, S.; Arenas, A., Ranking in interconnected multilayer networks reveals versatile nodes, Nat. Comm., 6, 6868 (2015) |
| [283] | Solé-Ribalta, A.; De Domenico, M.; Gómez, S.; Arenas, A., Random walk centrality in interconnected multilayer networks, Physica D, 323-324, 73-79 (2016) · Zbl 1365.90046 |
| [284] | Taylor, D.; Myers, S. A.; Clauset, A.; Porter, M. A.; Mucha, P. J., Eigenvector-based centrality measures for temporal networks, Multiscale Model. Simul., 15, 537-574 (2017) · Zbl 1386.91116 |
| [285] | Liao, H.; Mariani, M. S.; Medo, M.; Zhang, Y. C.; Zhou, M. Y., Ranking in evolving complex networks, Phys. Rep., 689, 1-54 (2017) · Zbl 1366.91124 |
| [286] | Page, L.; Brin, S.; Motwani, R.; Winograd, T., The PageRank citation ranking: Bringing order to the web, Technical Report 1999-66 (1999), Stanford InfoLab, http://ilpubs.stanford.edu:8090/422/ |
| [287] | Pinski, G.; Narin, F., Citation influence for journal aggregates of scientific publications: Theory, with application to literature of physics, Info. Proc. Manag., 12, 297-312 (1976) |
| [288] | Langville, A. N.; Meyer, C. D., Deeper inside PageRank, Internet Math., 1, 335-380 (2004) · Zbl 1098.68010 |
| [289] | Berkhin, P., A survey on PageRank computing, Internet Math., 2, 73-120 (2005) · Zbl 1100.68504 |
| [290] | Langville, A. N.; Meyer, C. D., Google’s PageRank and Beyond: The Science of Search Engine Rankings (2006), Princeton University Press: Princeton University Press Princeton, NJ, USA · Zbl 1104.68042 |
| [291] | Kamvar, S., Numerical Algorithms for Personalized Search in Self-organizing Information Networks (2010), Princeton University Press: Princeton University Press Princeton, NJ, USA · Zbl 1211.68004 |
| [292] | Ermann, L.; Frahm, K. M.; Shepelyansky, D. L., Google matrix analysis of directed networks, Rev. Modern Phys., 88, 039905 (2016) |
| [293] | Winter, C., Google goes cancer: Improving outcome prediction for cancer patients by network-based ranking of marker genes, PLOS Comput. Biol., 8, e1002511 (2012) |
| [294] | Radicchi, F., Who is the best player ever? A complex network analysis of the history of professional tennis, PLoS One, 6, e17249 (2011) |
| [295] | Callaghan, T.; Mucha, P. J.; Porter, M. A., Random walker ranking for NCAA division I-A football, Amer. Math. Monthly, 114, 761-777 (2007) · Zbl 1143.60036 |
| [296] | Park, J.; Newman, M. E.J., A network-based ranking system for US college football, J. Stat. Mech., P10014 (2005) |
| [297] | Saavedra, S.; Powers, S.; McCotter, T.; Porter, M. A.; Mucha, P. J., Mutually-antagonistic interactions in baseball networks, Physica A, 389, 1131-1141 (2010) |
| [298] | Lages, J.; Patt, A.; Shepelyansky, D. L., Wikipedia ranking of world universities, Eur. Phys. J. B, 89, 69 (2016) |
| [299] | Myers, S. A.; Mucha, P. J.; Porter, M. A., Mathematical genealogy and department prestige, Chaos, 21, 041104 (2011) |
| [300] | Folke Mitzlaff, Gerd Stumme, Recommending given names, 2013, https://arxiv.org/abs/1302.4412; Folke Mitzlaff, Gerd Stumme, Recommending given names, 2013, https://arxiv.org/abs/1302.4412 |
| [301] | Brin, S.; Motwani, R.; Page, L.; Winograd, T., What can you do with a Web in your Pocket?, Bull. IEEE Comput. Soc. Tech. Comm. Data Eng., 21, 37-47 (1998), http://sites.computer.org/debull/98june/webbase.ps |
| [302] | T.H. Haveliwala, Topic-sensitive PageRank, in: Proc. Eleventh Intl. Conf. World Wide Web, WWW ’02, 2002, pp. 517-526.; T.H. Haveliwala, Topic-sensitive PageRank, in: Proc. Eleventh Intl. Conf. World Wide Web, WWW ’02, 2002, pp. 517-526. |
| [303] | G. Jeh, J. Widom, Scaling personalized web search, in: Proc. Twelfth Intl. Conf. World Wide Web, WWW ’03, 2003, pp. 271-279.; G. Jeh, J. Widom, Scaling personalized web search, in: Proc. Twelfth Intl. Conf. World Wide Web, WWW ’03, 2003, pp. 271-279. |
| [304] | W. Xie, D. Bindel, A. Demers, J. Gehrke, Edge-weighted personalized PageRank: Breaking a decade-old performance barrier, in: Proc. 21st ACM SIGKDD Intl. Conf. Knowledge Disc. Data Mining, KDD ’15, 2015, pp. 1325-1334.; W. Xie, D. Bindel, A. Demers, J. Gehrke, Edge-weighted personalized PageRank: Breaking a decade-old performance barrier, in: Proc. 21st ACM SIGKDD Intl. Conf. Knowledge Disc. Data Mining, KDD ’15, 2015, pp. 1325-1334. |
| [305] | Lambiotte, R.; Rosvall, M., Ranking and clustering of nodes in networks with smart teleportation, Phys. Rev. E, 85, 056107 (2012) |
| [306] | P. Boldi, M. Santini, S. Vigna, PageRank as a function of the damping factor, in: Proc. 14th Internat. Conf. on World Wide Web, 2005, pp. 557-566.; P. Boldi, M. Santini, S. Vigna, PageRank as a function of the damping factor, in: Proc. 14th Internat. Conf. on World Wide Web, 2005, pp. 557-566. |
| [307] | Brinkmeier, M., PageRank revisited, ACM Trans. Internet Tech., 6, 282-301 (2006) |
| [308] | Chung, F., The heat kernel as the pagerank of a graph, Proc. Natl. Acad. Sci. USA, 104, 19735-19740 (2007) |
| [309] | Chung, F., A local graph partitioning algorithm using heat kernel pagerank, Internet Math., 6, 315-330 (2009) · Zbl 1238.05208 |
| [310] | D. Zhou, S.A. Orshanskiy, H. Zha, C.L. Giles, Co-ranking authors and documents in a heterogeneous network, in: Seventh IEEE Int. Conf. Data Mining (ICDM 2007), 2007, pp. 739-744.; D. Zhou, S.A. Orshanskiy, H. Zha, C.L. Giles, Co-ranking authors and documents in a heterogeneous network, in: Seventh IEEE Int. Conf. Data Mining (ICDM 2007), 2007, pp. 739-744. |
| [311] | M.K. Ng, X. Li, Y. Ye, MultiRank: Co-ranking for objects and relations in multi-relational data, in: Proc. 17th ACM SIGKDD Int. Conf. Knowledge Disc. Data Mining, KDD ’11, 2011, pp. 1217-1225.; M.K. Ng, X. Li, Y. Ye, MultiRank: Co-ranking for objects and relations in multi-relational data, in: Proc. 17th ACM SIGKDD Int. Conf. Knowledge Disc. Data Mining, KDD ’11, 2011, pp. 1217-1225. |
| [312] | Pedroche, F.; Romance, M.; Criado, R., A biplex approach to PageRank centrality: From classic to multiplex networks, Chaos, 26, 065301 (2016) · Zbl 1374.68136 |
| [313] | Daniels, H. E., Round-robin tournament scores, Biometrika, 56, 295-299 (1969) |
| [314] | Moon, J. W.; Pullman, N. J., On generalized tournament matrices, SIAM Rev., 12, 384-399 (1970) · Zbl 0198.03804 |
| [315] | Berman, K. A., A graph theoretical approach to handicap ranking of tournaments and paired comparisons, SIAM Alg. Discrete Methods, 1, 359-361 (1980) · Zbl 0499.05028 |
| [316] | Borm, N. E.; Brink, R. Van Den; Slikker, M., An iterative procedure for evaluating digraph competitions, Ann. Oper. Res., 109, 61-75 (2002) · Zbl 1007.91003 |
| [317] | Taylor, P. D., Allele-frequency change in a class-structured population, Am. Nat., 135, 95-106 (1990) |
| [318] | Taylor, P. D., Inclusive fitness arguments in genetic models of behaviour, J. Math. Biol., 34, 654-674 (1996) · Zbl 0845.92019 |
| [319] | Grindrod, P.; Higham, D. J., A matrix iteration for dynamic network summaries, SIAM Rev., 55, 118-128 (2013) · Zbl 1262.91121 |
| [320] | Freeman, L. C., A set of measures of centrality based on betweenness, Sociometry, 40, 35-41 (1977) |
| [321] | Newman, M. E.J., A measure of betweenness centrality based on random walks, Soc. Netw., 27, 39-54 (2005) |
| [322] | Ben-Akiva, M.; Lerman, S. R., Discrete Choice Analysis: Theory and Application to Travel Demand (1985), MIT Press: MIT Press Cambridge, MA |
| [323] | Train, K. E., Discrete Choice Methods with Simulation (2009), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 1269.62073 |
| [324] | C. Dwork, R. Kumar, M. Naor, D. Sivakumar, Rank aggregation methods for the Web, in: Proc. Tenth Intl. Conf. World Wide Web, WWW ’01, 2001, pp. 613-622.; C. Dwork, R. Kumar, M. Naor, D. Sivakumar, Rank aggregation methods for the Web, in: Proc. Tenth Intl. Conf. World Wide Web, WWW ’01, 2001, pp. 613-622. |
| [325] | Bradley, R. A.; Terry, M. E., Rank analysis of incomplete block designs: I. The method of paired comparisons, Biometrika, 39, 324-345 (1952) · Zbl 0047.12903 |
| [326] | Luce, R. D., Individual Choice Behavior: A Theoretical Analysis (1959), Wiley: Wiley New York, NY · Zbl 0093.31708 |
| [327] | Ragain, S.; Ugander, J., Pairwise choice Markov chains, (Lee, D. D.; Sugiyama, M.; Luxburg, U. V.; Guyon, I.; Garnett, R., Advances in Neural Information Processing Systems, vol. 29 (2016), Curran Associates, Inc.), 3198-3206, https://papers.nips.cc/paper/6287-pairwise-choice-markov-chains.pdf |
| [328] | Block, H. D.; Marschak, J., Random orderings and stochastic theories of responses, (Olkin, I.; Ghuyre, S. G.; Hoeffding, W.; Madow, W. G.; Mann, H. B., Contributions To Probability and Statistics: Essays in Honor of Harold Hotelling (1960), Stanford University Press: Stanford University Press Redwood City, CA), 97-132, https://econpapers.repec.org/paper/cwlcwldpp/66.htm · Zbl 0096.12104 |
| [329] | Plackett, R. L., The Analysis of permutations, J. R. Stat. Soc. Ser. C. Appl. Stat., 24, 193-202 (1975) |
| [330] | Maystre, L.; Grossglauser, M., Fast and accurate inference of Plackett-Luce models, (Cortes, C.; Lawrence, N. D.; Lee, D. D.; Sugiyama, M.; Garnett, R., Advances in Neural Information Processing Systems 28 (2015), Curran Associates, Inc.), 172-180, https://papers.nips.cc/paper/5681-fast-and-accurate-inference-of-plackettluce-models |
| [331] | Negahban, S.; Oh, S.; Shah, D., Iterative ranking from pair-wise comparisons, (Pereira, F.; Burges, C. J.C.; Bottou, L.; Weinberger, K. Q., Advances in Neural Information Processing Systems, vol. 25 (2012), Curran Associates, Inc.), 2474-2482, https://papers.nips.cc/paper/4701-iterative-ranking-from-pair-wise-comparisons |
| [332] | Negahban, S.; Oh, S.; Shah, D., Rank centrality: Ranking from pairwise comparisons, Oper. Res., 65, 266-287 (2017) · Zbl 1414.91133 |
| [333] | Shi, J.; Malik, J., Normalized cuts and image segmentation, IEEE Trans. Pattern Anal. Mach. Intell., 22, 888-905 (2000) |
| [334] | van Dongen, S. M., Graph Clustering by Flow Simulation (2001), University of Utrecht, https://dspace.library.uu.nl/handle/1874/848 |
| [335] | Eriksen, K. A.; Simonsen, I.; Maslov, S.; Sneppen, K., Modularity and extreme edges of the Internet, Phys. Rev. Lett., 90, 148701 (2003) |
| [336] | Zhou, H., Network landscape from a Brownian particle’s perspective, Phys. Rev. E, 67, 041908 (2003) |
| [337] | Arenas, A.; Díaz-Guilera, A.; Pérez-Vicente, C. J., Synchronization reveals topological scales in complex networks, Phys. Rev. Lett., 96, 114102 (2006) |
| [338] | Newman, M. E.J., Finding community structure in networks using the eigenvectors of matrices, Phys. Rev. E, 74, 036104 (2006) |
| [339] | Danon, L.; Arenas, A.; Díaz-Guilera, A., Impact of community structure on information transfer, Phys. Rev. E, 77, 036103 (2008) |
| [340] | Cheng, X. Q.; Shen, H. W., Uncovering the community structure associated with the diffusion dynamics on networks, J. Stat. Mech., 2010, P04024 (2010) |
| [341] | Lambiotte, R.; Sinatra, R.; Delvenne, J. C.; Evans, T. S.; Barahona, M.; Latora, V., Flow graphs: Interweaving dynamics and structure, Phys. Rev. E, 84, 017102 (2011) |
| [342] | Piccardi, C., Finding and testing network communities by lumped Markov chains, PLoS One, 6, e27028 (2011) |
| [343] | Sarzynska, M.; Leicht, E. A.; Chowell, G.; Porter, M. A., Null models for community detection in spatially embedded, temporal networks, J. Comput. Netw., 4, 363-406 (2016) |
| [344] | Bazzi, M.; Porter, M. A.; Williams, S.; McDonald, M.; Fenn, D. J.; Howison, S. D., Community detection in temporal multilayer networks, with an application to correlation networks, Multiscale Model. Simul., 14, 1-41 (2016) · Zbl 1328.90151 |
| [345] | Fortunato, S.; Barthélemy, M., Resolution limit in community detection, Proc. Natl. Acad. Sci. USA, 104, 36-41 (2007) |
| [346] | Good, B. H.; de Montjoye, Y. A.; Clauset, A., Performance of modularity maximization in practical contexts, Phys. Rev. E, 81, 046106 (2010) |
| [347] | M. Lambiotte, J.C. Delvenne, M. Barahona, Laplacian dynamics and multiscale modular structure in networks, 2008, arXiv:0812.1770v2; M. Lambiotte, J.C. Delvenne, M. Barahona, Laplacian dynamics and multiscale modular structure in networks, 2008, arXiv:0812.1770v2 |
| [348] | Schaub, M. T.; Delvenne, J. C.; Yaliraki, S. N.; Barahona, M., Markov dynamics as a zooming lens for multiscale community detection: Non clique-like communities and the field-of-view limit, PLoS One, 7, e32210 (2012) |
| [349] | Beguerisse-Díaz, M.; Garduño-Hernández, G.; Vangelov, B.; Yaliraki, S. N.; Barahona, M., Interest communities and flow roles in directed networks: The Twitter network of the UK riots, J. R. Soc. Interface, 11, 20140940 (2014) |
| [350] | Lambiotte, R.; Delvenne, J. C.; Barahona, M., Random walks, Markov processes and the multiscale modular organization of complex networks, IEEE Trans. Netw. Sci. Eng., 1, 76-90 (2014) |
| [351] | Delvenne, J. C.; Yaliraki, S. N.; Barahona, M., Stability of graph communities across time scales, Proc. Natl. Acad. Sci. USA, 107, 12755-12760 (2010) |
| [352] | Delvenne, J. C.; Schaub, M. T.; Yaliraki, S. N.; Barahona, M., The stability of a graph partition: A dynamics-based framework for community detection, (Mukherjee, A.; Choudhury, M.; Peruani, F.; Ganguly, N.; Mitra, B., Dynamics on and of Complex Networks, Volume 2: Applications To Time-Varying Dynamical Systems (2013), Springer: Springer New York, NY, USA), 221-242 |
| [353] | Reichardt, J.; Bornholdt, S., Statistical mechanics of community detection, Phys. Rev. E, 74, 016110 (2006) |
| [354] | Newman, M. E.J., Equivalence between modularity optimization and maximum likelihood methods for community detection, Phys. Rev. E, 94, 052315 (2016) |
| [355] | Bassett, D. S.; Porter, M. A.; Wymbs, N. F.; Grafton, S. T.; Carlson, J. M.; Mucha, P. J., Robust detection of dynamic community structure in networks, Chaos, 23, 013142 (2013) |
| [356] | Pons, P.; Latapy, M., Computing communities in large networks using random walks, J. Graph Algorithms Appl., 10, 191-218 (2006) · Zbl 1161.68694 |
| [357] | Zhou, H.; Lipowsky, R., Network Brownian motion: A new method to measure vertex-vertex proximity and to identify communities and subcommunities, Lecture Notes in Comput. Sci., 3038, 1062-1069 (2004) |
| [358] | Newman, M. E.J., Fast algorithm for detecting community structure in networks, Phys. Rev. E, 69, 066133 (2004) |
| [359] | Fouss, F.; Pirotte, A.; Renders, J. M.; Saerens, M., Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation, IEEE Trans. Knowl. Data Eng., 19, 355-369 (2007) |
| [360] | Barnett, S., Matrices: Methods and Applications (1990), Oxford University Press: Oxford University Press Oxford, UK · Zbl 0706.15001 |
| [361] | Rosvall, M.; Bergstrom, C. T., Maps of random walks on complex networks reveal community structure, Proc. Natl. Acad. Sci. USA, 105, 1118-1123 (2008) |
| [362] | Rosvall, M.; Bergstrom, C. T., Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems, PLoS One, 6, e18209 (2011) |
| [363] | Huffman, D. A., A method for the construction of minimum-redundancy codes, Proc. IRE, 40, 1098-1101 (1952) · Zbl 0137.13605 |
| [364] | M. Rosvall, MapDemo (demonstration of map equation), 2016, http://www.mapequation.org/apps/MapDemo.html; M. Rosvall, MapDemo (demonstration of map equation), 2016, http://www.mapequation.org/apps/MapDemo.html |
| [365] | D.A. Spielman, S.H. Teng, Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, in: Proc. Thirty-Sixth Annual ACM Symp. Theory of Comput., STOC ’04, 2004, pp. 81-90.; D.A. Spielman, S.H. Teng, Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, in: Proc. Thirty-Sixth Annual ACM Symp. Theory of Comput., STOC ’04, 2004, pp. 81-90. · Zbl 1192.65048 |
| [366] | R. Andersen, F. Chung, K. Lang, Local graph partitioning using PageRank vectors, in: Proc. IEEE 47th Annual Symp. Found. Comput. Sci., FOCS ’06, 2006, pp. 475-486.; R. Andersen, F. Chung, K. Lang, Local graph partitioning using PageRank vectors, in: Proc. IEEE 47th Annual Symp. Found. Comput. Sci., FOCS ’06, 2006, pp. 475-486. |
| [367] | Spielman, D. A.; Teng, S. H., A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning, SIAM J. Comput., 42, 1-26 (2013) · Zbl 1286.68244 |
| [368] | K. Kloster, D.F. Gleich, Heat kernel based community detection, in: Proc. 20th ACM SIGKDD Intl. Conf. Knowledge Disc. Data Mining, KDD ’14, 2014, pp. 1386-1395.; K. Kloster, D.F. Gleich, Heat kernel based community detection, in: Proc. 20th ACM SIGKDD Intl. Conf. Knowledge Disc. Data Mining, KDD ’14, 2014, pp. 1386-1395. |
| [369] | I.M. Kloumann, J.M. Kleinberg, Community membership identification from small seed sets, in: Proc. 20th ACM SIGKDD Intl. Conf. Knowledge Disc. Data Mining, KDD ’14, 2014, pp. 1366-1375.; I.M. Kloumann, J.M. Kleinberg, Community membership identification from small seed sets, in: Proc. 20th ACM SIGKDD Intl. Conf. Knowledge Disc. Data Mining, KDD ’14, 2014, pp. 1366-1375. |
| [370] | Kloumann, I. M.; Ugander, J.; Kleinberg, J., Block models and personalized PageRank, Proc. Natl. Acad. Sci. USA, 114, 33-38 (2017) |
| [371] | Mucha, P. J.; Porter, M. A., Communities in multislice voting networks, Chaos, 20, 041108 (2010) |
| [372] | Csermely, P.; London, A.; Wu, L. Y.; Uzzi, B., Structure and dynamics of core/periphery networks, J. Compl. Netw., 1, 93-123 (2013) |
| [373] | Rombach, M. P.; Porter, M. A.; Fowler, J. H.; Mucha, P. J., Core-periphery structure in networks, SIAM J. Appl. Math., 74, 167-190 (2014) · Zbl 1368.62169 |
| [374] | Della Rossa, F.; Dercole, F.; Piccardi, C., Profiling core-periphery network structure by random walkers, Sci. Rep., 3, 1467 (2013) |
| [375] | Lee, J. A.; Verleysen, M., Nonlinear Dimensionality Reduction (2007), Springer: Springer New York, NY · Zbl 1128.68024 |
| [376] | De Domenico, M., Diffusion geometry unravels the emergence of functional clusters in collective phenomena, Phys. Rev. Lett., 118, 168301 (2017) |
| [377] | Heckathorn, D. D., Respondent-driven sampling: A new approach to the study of hidden populations, Soc. Prob., 44, 174-199 (1997) |
| [378] | Salganik, M. J.; Heckathorn, D. D., Sampling and estimation in hidden populations using respondent-driven sampling, Sociol. Methodol., 34, 193-240 (2004) |
| [379] | Volz, E.; Heckathorn, D. D., Probability based estimation theory for respondent driven sampling, J. Official Stat., 24, 79-97 (2008), http://www.jos.nu/articles/abstract.asp?article=241079 |
| [380] | McCarty, C.; Killworth, P. D.; Bernard, H. R.; Johnsen, E. C.; Shelley, G. A., Comparing two methods for estimating network size, Human Organ., 60, 28-39 (2001) |
| [381] | Marsden, P. V., Recent developments in network measurement, (Models and Methods in Social Network Analysis (2005), Cambridge University Press: Cambridge University Press Cambridge, UK), 8-30 |
| [382] | Rocha, L. E.C.; Thorson, A. E.; Lambiotte, R.; Liljeros, F., Respondent-driven sampling bias induced by community structure and response rates in social networks, J. Roy. Statist. Soc. Ser. A, 180, 99-118 (2017) |
| [383] | J. Malmros, L.E.C. Rocha, Multiple seed structure and disconnected networks in respondent-driven sampling, 2016, arXiv.org arXiv:1603.04222; J. Malmros, L.E.C. Rocha, Multiple seed structure and disconnected networks in respondent-driven sampling, 2016, arXiv.org arXiv:1603.04222 |
| [384] | Lu, X.; Bengtsson, L.; Britton, T.; Camitz, M.; Kim, B. J.; Thorson, A.; Liljeros, F., The sensitivity of respondent-driven sampling, J. Roy. Statist. Soc. A, 175, 191-216 (2012) |
| [385] | Malmros, J.; Masuda, N.; Britton, T., Random walks on directed networks: Inference and respondent-driven sampling, J. Off. Stat., 32, 433-459 (2016) |
| [386] | Gile, K. J., Improved inference for respondent-driven sampling data with application to HIV prevalence estimation, J. Amer. Statist. Assoc., 106, 135-146 (2011) · Zbl 1396.62009 |
| [387] | Markov Chain Monte Carlo in Practice, (Gilks, W. R.; Richardson, S.; Spiegelhalter, D. J. (1996), Chapman & Hall: Chapman & Hall London, UK) · Zbl 0832.00018 |
| [388] | Stutzbach, D.; Rejaie, R.; Duffield, N.; Sen, S.; Willinger, W., On unbiased sampling for unstructured peer-to-peer networks, IEEE/ACM Trans. Netw., 17, 377-390 (2009) |
| [389] | M. Gjoka, M. Kurant, C.T. Butts, A. Markopoulou, Walking in facebook: A case study of unbiased sampling of OSNs, in: roc. 29th Conf. Info. Comm., 2010, INFOCOM ’10, pp. 2498-2506.; M. Gjoka, M. Kurant, C.T. Butts, A. Markopoulou, Walking in facebook: A case study of unbiased sampling of OSNs, in: roc. 29th Conf. Info. Comm., 2010, INFOCOM ’10, pp. 2498-2506. |
| [390] | Liggett, T. M., Interacting Particle Systems (1985), Springer: Springer New York, NY, USA · Zbl 0559.60078 |
| [391] | Durrett, D., Lecture Notes on Particle Systems and Percolation (1988), Belmont: Belmont Wadsworth, CA, USA · Zbl 0659.60129 |
| [392] | Castellano, C.; Fortunato, S.; Loreto, V., Statistical physics of social dynamics, Rev. Modern Phys., 81, 591-646 (2009) |
| [393] | Antal, T.; Redner, S.; Sood, V., Evolutionary dynamics on degree-heterogeneous graphs, Phys. Rev. Lett., 96, 188104 (2006) |
| [394] | Sood, V.; Antal, T.; Redner, S., Voter models on heterogeneous networks, Phys. Rev. E, 77, 041121 (2008) |
| [395] | Donnelly, P.; Welsh, D., Finite particle systems and infection models, Math. Proc. Cambridge Philos. Soc., 94, 167-182 (1983) · Zbl 0534.60095 |
| [396] | Griffeath, D., Annihilating and coalescing random walks on \(Z^d\), Z. Wahrscheinlichkeitstheor. Verwandte Geb., 46, 55-65 (1978) · Zbl 0373.60127 |
| [397] | Cooper, C.; Elsässer, R.; Ono, H.; Radzik, T., Coalescing random walks and voting on connected graphs, SIAM J. Discrete Math., 27, 1748-1758 (2013) · Zbl 1361.05120 |
| [398] | Masuda, N., Voter model on the two-clique graph, Phys. Rev. E, 90, 012802 (2014) |
| [399] | Iwamasa, Y.; Masuda, N., Networks maximizing the consensus time of voter models, Phys. Rev. E, 90, 012816 (2014) |
| [400] | Abelson, R. P., Mathematical models of the distribution of attitudes under controversy, (Frederiksen, N.; Gulliksen, H., Contributions To Mathematical Psychology (1964), Holt, Rinehart and Winston: Holt, Rinehart and Winston New York, NY, USA), 141-160 |
| [401] | DeGroot, M. H., Reaching a consensus, J. Amer. Statist. Assoc., 69, 118-121 (1974) · Zbl 0282.92011 |
| [402] | Jackson, M. O., Social and Economic Networks (2008), Princeton University Press: Princeton University Press Princeton, NJ, USA · Zbl 1149.91051 |
| [403] | Olfati-Saber, R.; Fax, J. A.; Murray, R. M., Consensus and cooperation in networked multi-agent systems, Proc. IEEE, 95, 215-233 (2007) · Zbl 1376.68138 |
| [404] | Friedkin, N. E.; Johnsen, E. C., Social Influence Network Theory: A Sociological Examination of Small Group Dynamics (2011), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 1228.91001 |
| [405] | Jia, P.; MirTabatabaei, A.; Friedkin, N. E.; Bullo, F., Opinion dynamics and the evolution of social power in influence networks, SIAM Rev., 57, 367-397 (2015) · Zbl 1339.91098 |
| [406] | Sznajd-Weron, K.; Sznajd, J., Opinion evolution in closed community, Internat. J. Modern Phys. C, 11, 1157-1165 (2000) |
| [407] | Krapivsky, P. L.; Redner, S., Dynamics of majority rule in two-state interacting spin systems, Phys. Rev. Lett., 90, 23, 238701 (2003) |
| [408] | Schweitzer, F.; Behera, L., Nonlinear voter models: The transition from invasion to coexistence, Eur. Phys. J. B, 67, 301-318 (2009) · Zbl 1188.91190 |
| [409] | Shao, J.; Havlin, S.; Stanley, H. E., Dynamic opinion model and invasion percolation, Phys. Rev. Lett., 103, 018701 (2009) |
| [410] | Rodrigues, F. A.; Peron, T. K.D.; Ji, P.; Kurths, J., The Kuramoto model in complex networks, Phys. Rep., 610, 1-98 (2016) · Zbl 1357.34089 |
| [411] | Gfeller, D.; De Los Rios, P., Spectral coarse graining of complex networks, Phys. Rev. Lett., 99, 038701 (2007) |
| [412] | Gfeller, D.; De Los Rios, P., Spectral coarse graining and synchronization in oscillator networks, Phys. Rev. Lett., 100, 174104 (2008) |
| [413] | O’Clery, N.; Yuan, Y.; Stan, G. B.; Barahona, M., Observability and coarse graining of consensus dynamics through the external equitable partition, Phys. Rev. E, 88, 042805 (2013) |
| [414] | Pecora, L. M.; Sorrentino, F.; Hagerstrom, A. M.; Murphy, T. E.; Roy, R., Cluster synchronization and isolated desynchronization in complex networks with symmetries, Nat. Comm., 5, 4079 (2014) |
| [415] | L. Li, W.M. Campbell, R.S. Caceres, Graph model selection via random walks, 2017, https://arxiv.org/abs/1704.05516; L. Li, W.M. Campbell, R.S. Caceres, Graph model selection via random walks, 2017, https://arxiv.org/abs/1704.05516 |
| [416] | K. Henderson, B. Gallagher, T. Eliassi-Rad, H. Tong, S. Basu, L. Akoglu, D. Koutra, C. Faloutsos, L. Li, RolX: Structural role extraction & mining in large graphs, in: Proc. 18th ACM SIGKDD Intl. Conf. Knowledge Disc. Data Mining, KDD ’12, 2012, pp. 1231-1239.; K. Henderson, B. Gallagher, T. Eliassi-Rad, H. Tong, S. Basu, L. Akoglu, D. Koutra, C. Faloutsos, L. Li, RolX: Structural role extraction & mining in large graphs, in: Proc. 18th ACM SIGKDD Intl. Conf. Knowledge Disc. Data Mining, KDD ’12, 2012, pp. 1231-1239. |
| [417] | Zhou, S.; Mondragón, R. J., The rich-club phenomenon in the Internet topology, IEEE Commun. Lett., 8, 180-182 (2004) |
| [418] | Colizza, V.; A. Flammini, M. A. Serrano; Vespignani, A., Detecting rich-club ordering in complex networks, Nat. Phys., 2, 110-115 (2006) |
| [419] | Newman, M. E.J.; Leicht, E. A., Mixture models and exploratory analysis in networks, Proc. Natl. Acad. Sci. USA, 104, 9564-9569 (2007) · Zbl 1155.91026 |
| [420] | Wu, T.; Benson, A. R.; Gleich, D. F., General tensor spectral co-clustering for higher-order data, (Lee, D. D.; Sugiyama, M.; Luxburg, U. V., Advances in Neural Information Processing Systems, vol. 29 (2016), Curran Associates, Inc.), 2559-2567, https://arxiv.org/abs/1603.00395 |
| [421] | Lu, L.; Peng, X., High-ordered random walks and generalized laplacians on hypergraphs, Lecture Notes in Comput. Sci., 6732, 14-25 (2011) · Zbl 1328.05106 |
| [422] | Mukherjee, S.; Steenbergen, J., Random walks on simplicial complexes and harmonics, Random Structures Algorithms, 49, 379-405 (2016) · Zbl 1346.05301 |
| [423] | Nicosia, V.; Skardal, P. S.; Arenas, A.; Latora, V., Collective phenomena emerging from the interactions between dynamical processes in multiplex networks, Phys. Rev. Lett., 118, 138302 (2017) |
| [424] | G. Han, H. Sethu, Waddling random walk: Fast and accurate mining of motif statistics in large graphs, in: Sixteenth IEEE Intl. Conf. Data Mining, ICDM 2016, 2016, pp. 181-190.; G. Han, H. Sethu, Waddling random walk: Fast and accurate mining of motif statistics in large graphs, in: Sixteenth IEEE Intl. Conf. Data Mining, ICDM 2016, 2016, pp. 181-190. |
| [425] | Tria, F.; Loreto, V.; Servedio, V. D.P.; Strogatz, S. H., The dynamics of correlated novelties, Sci. Rep., 4, 5890 (2014) |
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.
