通过线图转换，让稀疏图的极限可分析，突破传统零图子瓶颈。
Graphons of Line Graphs
- 将原图映射为线图，利用其稠密性突破稀疏限制
- 星图和超线性优先连接图的线图产生非零图子
- 适合研究稀疏网络结构演化与可区分性
本文研究从稀疏有限图序列中估计图极限（图子）的问题。提出一种方法：将原图映射到其线图。若图满足特定的平方度性质，则虽本身稀疏，但其线图是稠密的，从而可应用稠密图图子理论推导收敛性。星图满足该性质，其线图稠密且对应非零图子；实验表明，不同数量的星图可通过其线图图子被区分，而原图因稀疏性均收敛至零图子。类似地，超线性优先连接图几乎必然产生稠密线图。相反，稠密图（如Erdos-Renyi图）的线图仍稀疏，导致零图子。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。