Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Video Pandemics: Worldwide Viral Spreading of Psy’s Gangnam Style Video Kapitel lesen Erstes Kapitel lesen

2017 | Supplement | Buchkapitel

Local Diffusion Versus Random Relocation in Random Walks

verfasst von : Viktor Stojkoski, Tamara Dimitrova, Petar Jovanovski, Ana Sokolovska, Ljupco Kocarev

Erschienen in: ICT Innovations 2017

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We study a class of random walks on graphs with two mechanisms: local diffusion and random relocation. Such mechanisms are common in search algorithms, an example being the PageRank. The rate with which two mechanisms are mixed is called damping factor. It determines the first-passage time, defined as the time required for a walker starting from a source node to find a given target node. We provide bounds on the stationary distribution of random walks. Global mean first-passage time as a function of the damping factor is computed in closed form for a simple example. The results provide new insights on the search engines.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Internet of Things Based Solutions for Road Safety and Traffic Management in Intelligent Transportation Systems
Nächstes Kapitel Network-Dependent Server Performance Analysis of HTTP Adaptive Streaming
Anhänge
Nur mit Berechtigung zugänglich
Literatur
1.
Lovasz, L.: Random walks on graphs: a survey. In: Combinatorics, Paul Erdos in Eighty, vol. 2 (1993)
2.
Noh, J.D., Rieger, H.: Random walks on complex networks. Phys. Rev. Lett. 92(11), 118701 (2004)CrossRef
3.
4.
Berkhout, J., Heidergott, B.F.: Ranking nodes in general networks: a markov multi-chain approach. Discret. Event Dyn. Syst. 1–31 (2017). Special Issue on Performance Analysis and Optimization of Discrete Event Systems
5.
Pedroche, F., García, E., Romance, M., Criado, R.: Sharp estimates for the personalized multiplex pagerank. J. Comput. Appl. Math. (2017, in press)
6.
Pan, J.Y., Yang, H.J., Faloutsos, C., Duygulu, P.: Automatic multimedia cross-modal correlation discovery. In: Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 653–658. ACM (2004)
7.
Zhou, D., Bousquet, O., Lal, T.N., Weston, J., Schölkopf, B.: Learning with local and global consistency. In: Advances in Neural Information Processing Systems, pp. 321–328 (2004)
8.
Garnerone, S., Zanardi, P., Lidar, D.A.: Adiabatic quantum algorithm for search engine ranking. Phys. Rev. Lett. 108(23), 230506 (2012)CrossRef
9.
Singh, R., Xu, J., Berger, B.: Global alignment of multiple protein interaction networks with application to functional orthology detection. Proc. Natl Acad. Sci. 105(35), 12763–12768 (2008)CrossRef
10.
Mooney, B.L., Corrales, L.R., Clark, A.E.: Molecularnetworks: an integrated graph theoretic and data mining tool to explore solvent organization in molecular simulation. J. Comput. Chem. 33(8), 853–860 (2012)CrossRef
11.
Zuo, X.N., Ehmke, R., Mennes, M., Imperati, D., Castellanos, F.X., Sporns, O., Milham, M.P.: Network centrality in the human functional connectome. Cereb. Cortex 22(8), 1862–1875 (2011)CrossRef
12.
Leskovec, J., Lang, K.J., Dasgupta, A., Mahoney, M.W.: Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters. Internet Math. 6(1), 29–123 (2009)MathSciNetCrossRefMATH
13.
14.
Jasch, F., Blumen, A.: Target problem on small-world networks. Phys. Rev. E 63(4), 041108 (2001)CrossRef
15.
Bénichou, O., Loverdo, C., Moreau, M., Voituriez, R.: Intermittent search strategies. Rev. Mod. Phys. 83(1), 81 (2011)CrossRefMATH
16.
Tejedor, V., Bénichou, O., Voituriez, R.: Global mean first-passage times of random walks on complex networks. Phys. Rev. E 80(6), 065104 (2009)CrossRef
17.
Agliari, E., Burioni, R., Manzotti, A.: Effective target arrangement in a deterministic scale-free graph. Phys. Rev. E 82(1), 011118 (2010)CrossRef
18.
Meyer, B., Agliari, E., Bénichou, O., Voituriez, R.: Exact calculations of first-passage quantities on recursive networks. Phys. Rev. E 85(2), 026113 (2012)CrossRef
19.
Lin, Y., Julaiti, A., Zhang, Z.: Mean first-passage time for random walks in general graphs with a deep trap. J. Chem. Phys. 137(12), 124104 (2012)CrossRef
20.
Hwang, S., Lee, D.S., Kahng, B.: First passage time for random walks in heterogeneous networks. Phys. Rev. Lett. 109(8), 088701 (2012)CrossRef
21.
Wu, B., Zhang, Z.: Controlling the efficiency of trapping in treelike fractals. J. Chem. Phys. 139(2), 024106 (2013)CrossRef
22.
Yang, Y., Zhang, Z.: Random walks in unweighted and weighted modular scale-free networks with a perfect trap. J. Chem. Phys. 139(23), 234106 (2013)CrossRef
23.
Fronczak, A., Fronczak, P.: Biased random walks in complex networks: the role of local navigation rules. Phys. Rev. E 80(1), 016107 (2009)MathSciNetCrossRef
24.
Bonaventura, M., Nicosia, V., Latora, V.: Characteristic times of biased random walks on complex networks. Phys. Rev. E 89(1), 012803 (2014)CrossRef
25.
Boldi, P., Santini, M., Vigna, S.: Pagerank: functional dependencies. ACM Trans. Inf. Syst. (TOIS) 27(4), 19 (2009)CrossRef
26.
Kamvar, S., Haveliwala, T.: The condition number of the pagerank problem. Technical report, Stanford InfoLab (2003)
27.
Ben-Israel, A., Greville, T.N.: Generalized Inverses: Theory and Applications, vol. 15. Springer Science & Business Media, New York (2003)MATH
Metadaten
Titel
Local Diffusion Versus Random Relocation in Random Walks
verfasst von
Viktor Stojkoski
Tamara Dimitrova
Petar Jovanovski
Ana Sokolovska
Ljupco Kocarev
Copyright-Jahr
2017
Buch
ICT Innovations 2017

Print ISBN: 978-3-319-67596-1

Electronic ISBN: 978-3-319-67597-8

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-67597-8_6

Premium Partner

    Bildnachweise