Dissertation > Excellent graduate degree dissertation topics show

Some Problems of Random Walks on Graphs

Author: ChenHaiYan
Tutor: Zhang??
School: Xiamen University
Course: Basic mathematics
Keywords: Random Walks Markov Chain Average first time Fast convergence
CLC: O157.5
Type: PhD thesis
Year: 2004
Downloads: 314
Quote: 5
Read: Download Dissertation


Nearly two decades of random walks on finite graph (ie, finite Markov chain ) approximation algorithm design , and subject it to more and more attention . At this time most of the effectiveness of the algorithm depends on the performance quality of the design of random walks , random swimming performance is mainly determined by several important parameters such as the average first time , with an average coverage time , the convergence rate and so on. This paper studies a finite graph random walks on two important parameters : the average first- time and convergence rate . Here are some new results of this paper : 1 . Strongly connected aperiodic using algebraic methods to Graphs ( irreducible aperiodic Markov chain ) average the first time a new expression , and the use of this expression to the de Bruijn graph , there are some graphs to Kautz graph and strongly regular graph related random walks on the mean first passage time between any two points . 2. No random swimming ( reversible Markov chain ) and the relationship between the electric network , trees and unicyclic graphs on simple random walks between any two points of the average first time the expression ; cut vertex graph and its subgraph random swimming between the average first- time relationship . 3. By solving the recurrence relation gives an expression of the average first- time simple random walks between any two points in the cycle diagram of types ; dual method to calculate the new trigonometric identities . 4. Hypercube Q_n constructed a fully weighted graph G P G random walks on ( the background mutation operator in the genetic algorithm ) transition matrix using orthogonal polynomials obtained the P eigenvalues ??; G on the exact value of the random walks conductance , thus proving its rapid convergence .

Related Dissertations

  1. Researches on Urban Rail Transportation Operation Management System Test and Evaluation Method,TP311.52
  2. Research on Emergency Plan Business Process Modeling and Analysis Based on Colored Petri Nets,TP301.1
  3. Risk-based entropy and Markov chain approach MANET Security Risk Assessment and System Implementation,TN929.5
  4. Detection and Tracking of Moving Object in Complex Background,TP391.41
  5. The Credit Risk of Financial Leasing Based on Markov Chain,F832.49
  6. The Studying on the Finite-step Random Walk,O211.6
  7. The Optimal Investment-consumption Model with Reference Dependent Utility,F830.59
  8. The Research of Backoff Algorithm in IEEE 802.11 DCF Cooperative MAC,TN925.93
  9. An Econometric Analysis of the Asymmetry and Persistence of the Industry Index Fluctuation in China’s Stock Market,F832.51
  10. Study on Discrete-time Ruin Problem with Interest,O211.62
  11. Study on Channel Assignment Strategy for Cellular Mobile Telecommunication System,TN929.5
  12. Research on Mixed Service Capacity in Multi-User Wireless Network,TN92
  13. Research of Multiplexing Technology of Variable-length Packet in Digital Multimedia System,TN934.3
  14. Research of Fire Artillery Central Controller Hot Standby Application System,TP273
  15. Research on the Computational Method Based on Markov Chain for Road Weight of Traffic Network,U491
  16. Study on Deterioration Prediction Based on Degradation Integral Model of Hydraulic Concrete,TV431
  17. Strong Limit Theorems for Countable Nonhomogenous Mth-order Markov Chains and Application,O211.62
  18. Research on the Construction of Wuhan Bonded Port Area on MSFLB Model,F224
  19. Convergence analysis of China 's regional energy efficiency of its space,F206
  20. Dynamic Comparative Advantage and Upgrading of China’s Foreign Trade Industries,F752
  21. Markov switching type numerical stability of stochastic differential equations,O211.63

CLC: > Mathematical sciences and chemical > Mathematics > Algebra,number theory, portfolio theory > Combinatorics ( combinatorics ) > Graph Theory
© 2012 www.DissertationTopic.Net  Mobile