Birth and death processes in graphs and networks

The study of the evolution of graphs and networks with time has developed enormously in recent years – see Dorogovtsev & Mendes (2001). Many models for the evolution of graphs have been proposed to reflect  various properties of real world graphs such as the Web, citation graphs, and biological and social networks.

Recently, Fayolle, Krikun & Lasgouttes (2004) and Deo & Cami (2005, 2007) have studied the evolution of graphs and networks via birth and death processes.

The aim of this research project is to build and analyze models of evolution of graphs and networks using continuous and discrete time birth and death processes, in which both edges and vertices can be born or die at each time .

References & readings

• M.E.J. Newman (2003) The structure and function of complex networks (the_structure_and_function_of_complex_networks)
• Réka Albert &Albert-László Barabási (2002) Statistical mechanics of complex networks.Rev. Mod. Phys.74,47-97.(statistical_mechanics_of_complex_networks)
• S.N. Dorogovtsev and J.F.F. Mendes (2001) Evolution of networks. Advances in Physics (evolution_of_networks)
• Jurij Leskovec, Jon Kleinberg & Christos Faloutsos (2005) Graphs over time: Densification laws, shrinking diameters and possible explanations. (graphs_over_time)
• Fan Chung & Linyuan Lu (2006) Complex Graphs and Networks. CBMS Regional conference Series, Number 107. American Mathematical Society.
• Romualdo Pastor-Satorras, Miguel Rubi & Albert Diaz-Guilera (Eds) (2003) Statistical Mechanics of Complex Networks (Lecture Notes in Physics). Springer-Verlag.
• Remco van der Hofstad (2008 )Random Graphs and Complex Networks (random_graphs_and_complex_networks)
• Roger Guimerà & Marta Sales-Pardo (2006) Form follows function: the architecture of complex networks. Molecular Systems Biology 2:42, Published online: 1 August 2006.
• Jure Leskovec , Jon Kleinberg & Christos Faloutsos (2007) Graph evolution: Densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data (TKDD) archive, Volume 1(1), Article No. 2. (graph_evolution)
• Narsingh Deo & Aurel Cami (2005) A birth-death dynamic model of scale-free networks. ACM Southeast Regional Conference archive. Proceedings of the 43rd annual Southeast regional conference – Volume 2, pp. 26 – 27. ISBN: 1-59593-059-0
• Narsingh Deo & Aurel Cami (2007) Preferential deletion in dynamic models of web-like networks. Information Processing Letters archive,102(4),156-162
• Guy Fayolle, Maxim Krikun & Jean-Marc Lasgouttes (2004) Birth and death processes on certain random trees: Classification and stationary Laws. Probability Theory and Related Fields, Volume 128(3), 386-418. (birth_and_death_processes_on_certain_random_trees)