文章基本信息

标题：First-Order Model-Checking in Random Graphs and Complex Networks
本地全文：下载
作者：Jan Dreier ; Philipp Kuinke ; Peter Rossmanith 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：173
页码：40:1-40:23
DOI：10.4230/LIPIcs.ESA.2020.40
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 meta-theorems 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 meta-theorems. In this work, we consider all problems definable in first-order 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 Î±-power-law-boundedness. Roughly speaking, a random graph is Î±-power-law-bounded if it does not admit strong clustering and its degree sequence is bounded by a power-law distribution with exponent at least Î± (i.e. the fraction of vertices with degree k is roughly O(k^{-Î±})). We solve the first-order model-checking 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 first-order logic in almost linear expected time on these random graph models. This includes for example preferential attachment graphs, Chung-Lu graphs, configuration graphs, and sparse ErdÅ's-RÃ©nyi graphs. Our results match known hardness results and generalize previous tractability results on this topic.
关键词：random graphs; average case analysis; first-order model-checking