Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, April 29, 2010, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Ueli Peter
Random graph processes are widely used to model the evolution of complex weblike networks. We consider the following simple process that has been proposed to model the dynamics of non-growing networks.
Input: a multigraph on $n$ vertices and $m$ edges and a preference function $f$.
Repeat the following steps:
1. Choose an edge $(v_i, v_j)$ uniformly at random.
2. Select a vertex $v_l$ at random proportional to f(deg(v_l)).
3. Rewire $(v_i, v_j)$ to $(v_i, v_l)$.
We show that the process converges in $O(m\log m)$ steps and present a framework that simplifies the calculation of graph properties in its stationary distribution.
Automatic MiSe System Software Version 1.4803M | admin login