In the past decade, several examples of complex networks have been found that are small worlds and are scale-free. The small-world property means that distances in networks are small, while the scale-free property means that the degree sequence obeys a power law.
In this talk, I will describe real networks satisfying these properties, as well as some of the proposed models for them. I focus on a recent model that uses the preferential attachement paradigm: new vertices are more likely to attach to older vertices already having a high degree. Preferential attachment graphs turn out to be scale free, but it is less clear how their distances behave.
(This is joint work with Henri van den Esker, Gerard Hooghiemstra, Dmitri Znamenski and Piet Van Mieghem.)