All Questions
8 questions
16
votes
5
answers
3k
views
Simple random walk on a locally finite graph: when is it recurrent?
I'm giving a talk tomorrow about a result in computer science which I recently proved. It's a recurrence-transience result on a random process which is related in spirit to a simple random walk. My ...
- 30.3k
12
votes
3
answers
552
views
Estimate on currents in Cayley graphs
Take a Cayley graph $\Gamma$ (thought of as an electrical network with all edges having equal resistance) and break one edge $e$ and put a battery there. (Assume the graph has only one end* so that ...
- 4,432
6
votes
1
answer
644
views
Random path in a graph
Consider a finite graph $G$. I would like to define a random path between two vertices $s$ and $t$ of the graph $G$ by looking at a measure $\mu$ on all spanning trees. Then the probability of a given ...
- 4,432
5
votes
2
answers
943
views
Methods to approximate the betweenness centrality on large networks
To calculate the between centrality wiki def:
$g(v) = \sum_{s\neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}$
of a node in a graph/network;$\sigma_{st}$ is the ...
- 197
4
votes
2
answers
139
views
References studying properties of a graph which are stable under finite perturbation
Let's say two locally finite, connected, undirected, infinite graphs are "finite perturbations" of each other if one can remove a finite subset from each and obtain isomorphic graphs (which are now ...
- 4,304
3
votes
2
answers
478
views
Random spanning trees probability problem
We are given a simple connected graph $G(V,E)$ with vertex and edge set $V$ and $E$ respectively. For any vertex $v\in V$, let $D_T(v)$ the degree of $v$ in a uniformly generated random spanning tree $...
- 1,677
3
votes
1
answer
109
views
Has this random process been studied on grid graphs?
As an offshoot of a different discussion I got curious about (uniform) random spanning trees on grid graphs (torus graphs in particular, to avoid having to think about edge effects) and what their ...
- 1,951
2
votes
2
answers
312
views
Random walk and isoperimetric constant
I assume that a result of the following kind is known, and I would really appreciate a reference for it... Or at least, some hints as to where to start looking.
Theorem(?): Let $\varepsilon>0$ ...
- 11.2k