Abstract
Complex networks are everywhere. They appear for example in the form of biological networks, social networks, or computer networks and have been studied extensively. Efficient algorithms to solve problems on complex networks play a central role in today’s society. Algorithmic metatheorems show that many problems can be solved efficiently. Since logic is a powerful tool to model problems, it has been used to obtain very general metatheorems. In this work, we consider all problems definable in firstorder logic and analyze which properties of complex networks allow them to be solved efficiently.
The mathematical tool to describe complex networks are random graph models. We define a property of random graph models called αpowerlawboundedness. Roughly speaking, a random graph is αpowerlawbounded if it does not admit strong clustering and its degree sequence is bounded by a powerlaw distribution with exponent at least α (i.e. the fraction of vertices with degree k is roughly O(k^{α})).
We solve the firstorder modelchecking problem (parameterized by the length of the formula) in almost linear FPT time on random graph models satisfying this property with α ≥ 3. This means in particular that one can solve every problem expressible in firstorder logic in almost linear expected time on these random graph models. This includes for example preferential attachment graphs, ChungLu graphs, configuration graphs, and sparse ErdősRényi graphs. Our results match known hardness results and generalize previous tractability results on this topic.
BibTeX  Entry
@InProceedings{dreier_et_al:LIPIcs:2020:12906,
author = {Jan Dreier and Philipp Kuinke and Peter Rossmanith},
title = {{FirstOrder ModelChecking in Random Graphs and Complex Networks}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {40:140:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771627},
ISSN = {18688969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12906},
URN = {urn:nbn:de:0030drops129068},
doi = {10.4230/LIPIcs.ESA.2020.40},
annote = {Keywords: random graphs, average case analysis, firstorder modelchecking}
}
Keywords: 

random graphs, average case analysis, firstorder modelchecking 
Collection: 

28th Annual European Symposium on Algorithms (ESA 2020) 
Issue Date: 

2020 
Date of publication: 

26.08.2020 