The random-walks tag has no wiki summary.
2
votes
0answers
68 views
Graph conductance - program/code/library
Technical question: is there any open source program/code/library which can compute (minimal) conductance of a given graph, probably by some simulated annealing?
Think it is quite well-known problem, ...
2
votes
1answer
66 views
Increasing entropy of random walk
Let $P$ be a transition matrix of a random walk in an undirected (may not regular) graph $G$. Let $\pi$ be a distribution on $V(G)$. The Shannon entropy of $\pi$ is defined by
$$H(\pi)=-\sum_{v \in ...
3
votes
1answer
131 views
How many random walks to start from each node?
Assume that we are given a real life graph, DBLP network in my case, where degree distribution of nodes follows a power law (many nodes have 1, 2 neighbors, and only a few nodes have hundreds of ...
8
votes
0answers
155 views
On “The Average Height of Planted Plane Trees” by Knuth, de Bruijn and Rice (1972)
I am trying to derive the classic paper in the title only by elementary means (no generating functions, no complex analysis, no Fourier analysis) although with much less precision. In short, I "only" ...
1
vote
1answer
112 views
Prove: cover time for directed graph is exponential
How can I prove that the cover time for a directed graph G can be exponential in the size of G?
