Hatékony tulajdonságtesztelés sűrű gráfokban = Efficient property testing for dense graphs

Fekete, Panna Tímea (2026) Hatékony tulajdonságtesztelés sűrű gráfokban = Efficient property testing for dense graphs. SCIENTIA ET SECURITAS, 6 (4). pp. 328-335. ISSN 3057-9759

Preview

Text 112-article-p328.pdf - Published Version Available under License Creative Commons Attribution. Download (1MB) | Preview

Abstract

Nagy, sűrű hálózatok számos tudományterületen jelen vannak, így általános vizsgálatuk kiemelt jelentőséggel bír. Méretüknél fogva teljes egészében nehezen vizsgálhatók, emiatt mintavételezéssel kapott kisebb hálózatok tulajdonságaiból következtethetünk az eredeti hálózat struktúrájára. Jelen dolgozatban a hálózatokat a gráfelmélet segítségével formalizáljuk. Bizonyítjuk, hogy részbenrendezett halmazok monoton tulajdonságai könnyen tesztelhetők kis minták alapján. Továbbá kiterjesztünk két mintavételezési lemmát nemkorlátos magfüggvényekre, igazolva egy majdnem biztos konvergenciát a vágástávolságra. Összességében jelen dolgozat hozzájárul újabb komplex hálózatcsaládok globális tulajdonságainak feltárásához lokális minták segítségével. | Large-scale networks are ubiquitous in nature and technology, spanning domains such as neuroscience, epidemiology, transportation, and social sciences. Their analysis often requires the study of their graph counterparts, whose complex global behavior is often computationally prohibitively expensive to study directly. A common strategy is to analyze smaller substructures or simplified models of these graphs. However, this raises a fundamental question: to what extent do these smaller samples retain the key properties of the original network? This current research focuses on dense graphs, where the number of edges grows quadratically with the number of vertices. We further develop efficient tools for understanding their structure through sampling and removal lemmas. Building on Szemerédi’s regularity lemma—a cornerstone in the field of graph theory—we address its limitations by constructing more practical approaches that require significantly fewer computational resources. We investigate monotone classes of finite posets (that is, partially ordered sets closed under taking subposets) and prove that these are easily testable. This means that their structural properties can be reliably inferred by sampling only a number of vertices polynomial in the error parameter, a substantial improvement over earlier approaches relying on tower-type bounds. We prove this via a polynomial removal lemma for posets. Furthermore, we show that for every monotone class of posets, there exists an h such that the class is indistinguishable with strong testing from the class of Ch-free posets, where Ch is a chain of length h. Using this, we also obtain a two-sided test, with sampling size O(ε–1). Moreover, the test is essentially one-sided. We examine the sampling method from a graph limit point of view. The Counting Lemma and the Inverse Counting Lemma establish a connection for comparing two dense large graphs by relating homomorphism densities and cut distance. It has been shown that while the Counting Lemma holds for unbounded kernels (i.e., limits of multigraphs), the Inverse Counting Lemma does not. The Inverse Counting Lemma is built on the First and SecondSampling Lemmas, which we demonstrate also hold for unbounded kernels. The First Sampling Lemma gives bounds on the difference between the cut norms of the original and the sampled kernel. The main feature of the cut norm is that it emphasizes structure over randomness, and “filters out noise”. The Second Sampling Lemma gives an upper bound on the so-called ‘cut-metric’ of the original and the sampled kernel, i.e., the cut norm of the difference of the original and the sampled kernel where one can use any measure preserving transformation on the sample. We also derive that for any kernel in Lp (p > 4), the samples converge almost surely in the cut metric to the original kernel. Overall, the presented methods and theorems contribute to the more efficient and accurate study of the structure of large networks.

Actions (login required)

Edit Item