On the Estimation of Network Complexity: Dimension of Graphons
Authors: Yann Issartel
JMLR 2021 | Venue PDF | Archive PDF | Plain Text | 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 . |