General
Graphons of Line Graphs
arXiv stat.ML0 views
arXiv:2409.01656v4 Announce Type: replace Abstract: We consider the problem of estimating graph limits, known as graphons, from observations of sequences of sparse finite graphs. In this paper we show a simple method that can shed light on a subset of sparse graphs. The method involves mapping the original graphs to their line graphs. We show that graphs satisfying a particular property, which we call the square-degree property are sparse, but give rise to dense line graphs. This enables the use of results on graph limits of dense graphs to derive convergence. In particular, star graphs satisfy the square-degree property resulting in dense line graphs and non-zero graphons of line graphs. We demonstrate empirically that we can distinguish different numbers of stars (which are sparse) by the graphons of their corresponding line graphs. Whereas in the original graphs, the different number of stars all converge to the zero graphon due to sparsity. Similarly, superlinear preferential attachment graphs give rise to dense line graphs almost surely. In contrast, dense graphs, including Erdos-Renyi graphs make the line graphs sparse, resulting in the zero graphon.
Source:https://arxiv.org/abs/2409.01656PreviousBilevel optimization for data-driven learning of Koopman embeddings using kernel-based autoencodersNextNetworks with Finite VC Dimension: Pro and Contra
Related posts
Adventurer returns home to Hull after 28-year walk from South America
0Hacker News New
Vending machine has terms and conditions you must accept before using [video]
0Hacker News New
Tomorrow Corporation Tech Demo [video]
0Hacker News New
Does Social Status Run in Families?
0Hacker News New
Show HN: Svoxx – A multilingual freelance marketplace with social features
0Hacker News New
433MHz TUI scanner: using a FT232H connected to a CC1101
0Hacker News New