Visiting Speaker
Péter L. Erdos
A. Rényi Institute of Mathematics, Budapest, Hungary
How to sample scale-free degree sequence's realizations uniformly and fast
Friday
Apr 26, 2019
Watch video
3:30 pm
177 Huntington Ave
11th floor

Because of the important roles of the Internet and social networks in modern society, much attention has been paid to analyzing graphs with real-world network properties. One of the most prominent traits of many real-world networks is that their degree distribution follows the so-called power-law, usually with parameter \gamma between 2 and 3. Graphs with such degree distributions are sparse but have vertices with very large degrees. There are peculiarly few available methods to sample the realizations of exact degree distribution uniformly. One of them a newly developed exact uniform sampler by Gao and Wormald (SODA, 2018), based on the configuration model. This works when the parameter \gamma is > 2.8810. Another approach is a newly developed version of the switch Markov chains, which suitable to sample power-law degree sequences with parameter \gamma >2.

In this talk we will survey these results.

About the speaker
Péter L. Erdos received his Ms. C. in 1980 and earned his Ph. D. in 1982 at the Eˆtvˆs University, Budapest. He became the Doctor of the Hungarian Academy of Science in 2008. He joined the A. RÈnyi Institute of Mathematics, Hungarian Academy of Sciences in 1997, working now as a scientific advisor of the Institute. His main research interest lays in Combinatorics, Phylogenetics and Theoretical Computer Science
Visiting Speaker
Péter L. Erdos
A. Rényi Institute of Mathematics, Budapest, Hungary
How to sample scale-free degree sequence's realizations uniformly and fast
Fri
Apr 26, 2019
3:30 pm
177 Huntington Ave
11th floor
ADD to calendar

Because of the important roles of the Internet and social networks in modern society, much attention has been paid to analyzing graphs with real-world network properties. One of the most prominent traits of many real-world networks is that their degree distribution follows the so-called power-law, usually with parameter \gamma between 2 and 3. Graphs with such degree distributions are sparse but have vertices with very large degrees. There are peculiarly few available methods to sample the realizations of exact degree distribution uniformly. One of them a newly developed exact uniform sampler by Gao and Wormald (SODA, 2018), based on the configuration model. This works when the parameter \gamma is > 2.8810. Another approach is a newly developed version of the switch Markov chains, which suitable to sample power-law degree sequences with parameter \gamma >2.

In this talk we will survey these results.

about the speaker
Péter L. Erdos received his Ms. C. in 1980 and earned his Ph. D. in 1982 at the Eˆtvˆs University, Budapest. He became the Doctor of the Hungarian Academy of Science in 2008. He joined the A. RÈnyi Institute of Mathematics, Hungarian Academy of Sciences in 1997, working now as a scientific advisor of the Institute. His main research interest lays in Combinatorics, Phylogenetics and Theoretical Computer Science
10/2/19
Jaime Settle
Title TBA
10/16/19
Helder Nakaya
Title TBA