Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
On the Estimation of Network Complexity: Dimension of Graphons
Authors: Yann Issartel
JMLR 2021 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this paper, we develop a statistical theory of graph complexity in a general model of random graphs, the so-called graphon model. From a single observation of the graph, we construct an estimator of the neighborhood-distance and show universal non-asymptotic bounds for its risk, matching minimax lower bounds. Based on this estimated distance, we compute the corresponding covering number and Minkowski dimension and we provide optimal non-asymptotic error bounds for these two plug-in estimators. Section 6.2: "We shortly illustrate the empirical performance of our algorithm on the random geometric graph, introduced in Section 3.2. Consider the latent space [0, 1], endowed with the uniform measure and the function W(x, y) = I||x y||2 0.1, which has a Minkowski dimension 2 and satisfies the assumptions of Theorem 12. We sample n = 1000 points uniformly on [0, 1] and plot the outputs log b N(ap.c) Ω (ϵ) log ϵ over the range of radii ϵ n 0.005 + k 0.005 ; k {0, . . . , 100} o ." |
| Researcher Affiliation | Academia | Yann Issartel EMAIL Universit e Paris-Saclay, Laboratoire de Math ematiques d Orsay, 91405 Orsay, France. CREST, Ensae, Institut Polytechnique de Paris, 91120 Palaiseau, France. |
| Pseudocode | Yes | Covering Number Algorithm Input: A = [Aij] adjacency matrix of size n n, a radius ϵ. Step 1 : constructing the distance-estimator br 1. Compute the nearest neighbor s index of each sampled point ωi: i {1, . . . , n}, bm(i) = argmin j: j =i max k: k =i,j Ak, Ai Aj n . 2. Compute all the distances: i, j {1, . . . , n}, br(i, j) = Ai, A bm(i) n + Aj, A bm(j) n 2 Ai, Aj n. Step 2 : computing an approximation of the ϵ-covering number 3. In the space S0 = {1, . . . , n} endowed with the distance function br, consider B0 = {Bj}j n the set of all the balls of radius ϵ. 4. Obtain a cover of {1, . . . , n} as follows: Set i = 0. While Si = , do: (a) Select a ball B in Bi that contains the largest number of elements of Si. (b) Set Si+1 = Si B to remove the elements covered by B, (c) Set Bi+1 = Bi {B} to update the set of available balls, (d) Set i = i + 1 to continue the algorithm. Output: the number i of selected balls, denoted by b N(ap.c) Ω (ϵ). |
| Open Source Code | No | No explicit statement about code availability or repository link is found in the paper. |
| Open Datasets | No | No concrete access information for a publicly available or open dataset is provided. The paper discusses theoretical models like the W-random graph model and illustrates empirical performance on a simulated random geometric graph by sampling points. |
| Dataset Splits | No | The paper does not use external datasets, but rather theoretical models and simulated data for illustration, thus specific dataset split information is not applicable or provided. |
| Hardware Specification | No | Section 6.2 describes an empirical illustration but does not provide any specific hardware details used for running the computations. |
| Software Dependencies | No | The paper does not provide specific ancillary software details with version numbers. The empirical illustration in Section 6.2 does not mention any software dependencies. |
| Experiment Setup | Yes | We sample n = 1000 points uniformly on [0, 1] and plot the outputs log b N(ap.c) Ω (ϵ) log ϵ over the range of radii ϵ n 0.005 + k 0.005 ; k {0, . . . , 100} o . |