Abstract: Empirical findings have shown that many real-world networks are scale-free in the sense that there is a high variability in the number of connections of the elements of the networks. Spurred by these empirical findings, models have been proposed for such networks. In this talk, we describe a particular class of random graphs in which edges are present independently but with unequal edge occupation probabilities, that are moderated by appropriate vertex weights. For such models, it is known precisely when there is a giant component, meaning that a positive proportion of the vertices is connected to one another. Empirical studies show that many real-world networks have degree sequences with diverging second moment, where the vertices with largest degrees or `hubs' play a profound role in the network's functionality.

Percolation on networks is one of the simplest models for network functionality. It can be interpreted as describing the effect of random attacks on the network, where edges are removed independently with a fixed probability. Interestingly, networks with diverging second moment degree tend to be robust to such random attacks, in the sense that a giant component remains after percolation for any
fixed positive retention probability.

We investigate the critical behavior for two popular models of complex networks with diverging second moments, the configuration model and the generalized random graph. We identify what the critical values are, and how they scale with the graph size. Interestingly, this scaling turns out to be rather different for the configuration model, where hubs share many edges between them, and the generalized random graph, for which hubs are connected by at most one edge. Thus, the single-edge constraint plays a significant role. This clears up part of the confusion in the physics literature.

[This is joint work with Shankar Bhamidi, Souvik Dhara, Johan van Leeuwaarden and Sanchayan Sen.]