Algorithmic Complexity of Power Law Networks

DOI10.1137/1.9781611974331.CH91zbMATH Open1394.68010arXiv1507.02426OpenAlexW2952995998MaRDI QIDQ4575673FDOQ4575673

Jakub Łącki, Paweł Brach, Marek Cygan, Piotr Sankowski

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: It was experimentally observed that the majority of real-world networks 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. We observe that for exponents of the degree distribution in the range $[1,2]$ such networks exhibit double power law phenomenon that was observed for several real-world networks. Our observation indicates that this phenomenon could be explained by just pure graph theoretical properties. The second aim of our work is to 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 classical 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. Previously, it has been only shown that these problems can be solved very efficiently on power law graphs when these graphs are random, e.g., drawn at random from some distribution. However, it is unclear how to relate such a theoretical analysis to real-world graphs, which are fixed. Instead of that, we show that the randomness assumption can be replaced with a simple condition on the degrees of adjacent vertices, which can be used to obtain similar results. As a result, in some range of power law exponents, we are able to solve the maximum clique problem in polynomial time, although in general power law networks the problem is NP-complete.

Full work available at URL: https://arxiv.org/abs/1507.02426

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Network design and communication in computer systems (68M10)

Cited In (6)

• Finding Cliques in Social Networks: A New Distribution-Free Model
• Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection
• Finding Induced Subgraphs in Scale-Free Inhomogeneous Random Graphs
• The complexity of computations by networks
• Title not available (Why is that?)
• Greed is good for deterministic scale-free networks

This page was built for publication: Algorithmic Complexity of Power Law Networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575673)