Fair and Biased Random Walks on Undirected Graphs and Related Entropies

Philippe Blanchard and Dimitri Volchenkov ()
Additional contact information
Philippe Blanchard: University of Bielefeld, Bielefeld – Bonn Stochastic Research Center (BiBoS)
Dimitri Volchenkov: University of Bielefeld, The Center of Excellence Cognitive Interaction Technology (CITEC)

Chapter Chapter 13 in Towards an Information Theory of Complex Networks, 2011, pp 365-395 from Springer

Abstract: Abstract The entropy rates of Markov chains (random walks) defined on connected undirected graphs are well studied in many surveys. We study the entropy rates related to the first-passage time probability distributions of fair random walks, their relative (Kullback–Leibler) entropies, and the entropy related to two biased random walks – with the random absorption of walkers and the shortest paths random walks. We show that uncertainty of first-passage times quantified by the entropy rates characterizes the connectedness of the graph. The relative entropy derived for the biased random walks estimates the level of uncertainty between connectivity and connectedness – the local and global properties of nodes in the graph.

Keywords: Entropy of graphs; First-passage times; Random walks on graphs (search for similar items in EconPapers)
Date: 2011
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-0-8176-4904-3_13

Ordering information: This item can be ordered from
http://www.springer.com/9780817649043

DOI: 10.1007/978-0-8176-4904-3_13

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().