## January 29, 2016:

#
Algorithmic Complexity of Power Law Networks

##
Timothy Johnson

It was experimentally observed that the majority of real-world networks
are scale-free and follow power law degree distribution. The aim of this
paper is to study the algorithmic complexity of such “typical”
networks. The contribution of this work is twofold.

First, we define a deterministic condition for checking whether a graph
has a power law degree distribution and experimentally validate it on
real-world networks. This definition allows us to derive interesting
properties of power law networks.

Secondly, we give a novel theoretical explanation why many algorithms
run faster on real-world data than what is predicted by algorithmic
worst-case analysis. We show how to exploit the power law degree
distribution to design faster algorithms for a number of classic
$\mathsf{P}$-time
problems including transitive closure, maximum matching, determinant,
PageRank and matrix inverse. Moreover, we deal with the problems of
counting triangles and finding maximum clique.

In contrast to previously done average-case analyses, we believe that
this is the first “waterproof” argument that explains why many
real-world networks are easier.

(Based on a
paper by Paweł Brach, Marek Cygan, Jakub Łącki, and
Piotr Sankowski at SODA 2016.)