Graphs over Time Densification Laws, Shrinking

How do real graphs evolve over time? What are “normal” growth patterns in social, technological, and information networks? Many studies have discovered patterns in sta- tic graphs, identifying properties in a single snapshot of a large network, or in a very small number of snapshots; these include heavy tails for in- and out-degree distributions, com- munities, small-world phenomena, and others. However, given the lack of information about network evolution over long periods, it has been hard to convert these findin gs into statements about trends over time. gs into statements about trends over time.