Remco van der Hofstad, TU Eindhoven: Critical percolation on scale-free random graphs
Thursday, 23.03.2023 16:30 im Raum M2
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.
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, or the result of a simple epidemic on the network.
We investigate the percolation critical behavior for a popular models of complex networks, the Poisson random graph, which can be interpreted as a model with multi-edges, or single edges by collapsing the multi-edges. 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 multi-edge case compared to the single-edge case in the scale-free regime.
This clears up part of the confusion in the physics literature. Furthermore, the single-edge case has an unexpected phase transition at the appropriate scale of the percolation parameter, where the size of the largest component jumps from a random value to a much larger almost deterministic value that is proportional to the root of the graph size.