All Questions
Tagged with network-theory random-graphs
4 questions
0
votes
1
answer
115
views
Sources of information on algorithms for finding Hamiltonian cycles (Pósa)
I research various algorithms in complex networks and I am quite new in this field. I am currently focusing on random geometric graphs - Pósa's algorithm for finding a hamiltonian cycle. Can you ...
- 1
12
votes
1
answer
542
views
Distribution of degree in graphs: when is the friendship paradox the paradox it wants to be?
$\DeclareMathOperator\deg{deg}\DeclareMathOperator\ndeg{ndeg}\newcommand\abs[1]{\lvert#1\rvert}$The friendship paradox goes most people have fewer friends than their friends have on average. The ...
- 343
4
votes
1
answer
158
views
Almost all simple graphs are small world networks
Two days ago it occurred to me that almost all simple graphs are small world networks in the sense that if $G_N$ is a simple graph with $N$ nodes sampled from the Erdös-Rényi random graph distribution ...
- 3,871
2
votes
0
answers
64
views
Transversal deviation in first passage percolation
Take the lattice $\mathbb{L}^{2}=(\mathbb{Z}^{2},\mathbb{E}^{2})$ with i.i.d. $\text{U}[0,1]$ weights on the edges, and the random variable $D$ giving the maximal transversal deviation of the geodesic ...
- 640