Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Probability on trees and networks
Lyons R., Peres Y., Cambridge University Press, New York, NY, 2016. Type: Book (9781107160156)
Date Reviewed: Jul 19 2017

Information and communications technology (ICT) specialists might be interested in this tough mathematical book. For sure, this is not a work that can be easily read to relax in the evening, since a lot of background knowledge is necessary to understand the material. Additionally, due to the character of the material and the way it is presented, the book is not easy to follow. Obviously, the authors’ goal is not to present a popular book, but rather a serious treatise on relationships between probability theory and infinite graphs.

A short summary of the chapters of this very dense text follows. I must admit that even producing a short description of the contents would involve a short treatise on the material for a layman. Therefore, I will only stress some notions that may be familiar to a reader with some background in probability and graph theory.

Chapter 1 concisely presents the most important notions and theorems covered in the book. Chapter 2 shows the relationship between random walks and so-called electric networks, where we have the parallelism between current flows as well as resistance and some graph-related entities. Chapter 3 elaborates on infinite graphs, where random walks are also studied. For an ICT engineer acquainted with graph theory, it might be interesting to see the well-known Ford-Fulkerson theorem (max-flow min-cut) proven in a way that is different from what one can see in networking or computer science textbooks. Chapter 4 again deals with a familiar notion: spanning trees; however, here they are treated from the randomness viewpoint. The next chapter introduces the very important idea of percolation. Chapter 6 describes some properties of graphs with so-called expansion constants. A notable fact is that the well-known information theory concept of entropy is used to prove some of the theorems of this chapter. Then, chapter 7 analyzes percolation properties on a selected type of graph (transitive). Chapter 8 relates the percolation theory and the so-called mass-transport technique that is used for probabilistic calculations on graphs. In chapter 9, Lyons and Peres come back to the “electric networks” and present how Dirichlet functions can be used for their description if we deal with infinite graphs. Analogously, chapter 10 revisits spanning trees, dealing with random spanning forests. The topic is extended with the familiar notion of a minimal spanning forest in chapter 11. Chapter 12 elaborates on the speed of some specific branching processes. Chapter 13 is devoted to the escape rate of a random walk. The subsequent chapter studies the properties of transitive Markov chains. Chapter 15 deals with the so-called Hausdorff dimension. Chapter 16 relates capacity and percolation, and closes with a chapter on random walks as a distinguished type of tree.

The book is likely to be interesting for a specialist in theoretical computer science, at least as a source enriching one’s erudition. It is also likely to be a source of scientific inspiration since the authors present some relationships that can be used in network science. Effective application of the information in exercises requires a lot of mathematical competence and imagination. Nevertheless, the work can be recommended to all readers that are willing to extend their knowledge on the topics, which are much more advanced than those typically dealt with in the ICT graduate school curriculum.

Reviewer:  Piotr Cholda Review #: CR145433 (1709-0586)
Bookmark and Share
  Featured Reviewer  
 
Probability And Statistics (G.3 )
 
 
Network Problems (G.2.2 ... )
 
 
Probabilistic Computation (F.1.2 ... )
 
 
Trees (G.2.2 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Probability And Statistics": Date
Probabilities from fuzzy observations
Yager R. (ed) Information Sciences 32(1): 1-31, 1984. Type: Article
Mar 1 1985
Randomness conservation inequalities; information and independence in mathematical theories
Levin L. Information and Control 61(1): 15-37, 1984. Type: Article
Sep 1 1985
The valuing of management information. Part I: the Bayesian approach
Carter M. Journal of Information Science 10(1): 1-9, 1985. Type: Article
May 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy