Spectral classes of regular, random, and empirical graphs

被引：15

作者：

Gu, Jiao ^{[1
,2
,3
,4
]}

Jost, Juergen ^{[1
,5
]}

Liu, Shiping ^{[6
]}

Stadler, Peter F. ^{[1
,2
,3
,5
,7
]}

机构：

[1] Max Planck Inst Math Sci, D-04103 Leipzig, Germany

[2] Univ Leipzig, Dept Comp Sci, Bioinformat Grp, D-04107 Leipzig, Germany

[3] Univ Leipzig, Interdisciplinary Ctr Bioinformat, D-04107 Leipzig, Germany

[4] Jiangnan Univ, Sch Sci, Wuxi 214122, Peoples R China

[5] Santa Fe Inst, Santa Fe, NM 87501 USA

[6] Univ Durham, Dept Math Sci, Durham DH1 3LE, England

[7] Univ Vienna, Inst Theoret Chem, A-1090 Vienna, Austria

来源：

LINEAR ALGEBRA AND ITS APPLICATIONS | 2016年 / 489卷

基金：

英国工程与自然科学研究理事会;

关键词：

Quasimetric; Laplacian spectrum; Radon measure; Graph families; NETWORKS;

D O I：

10.1016/j.laa.2015.08.038

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We define a (pseudo-)distance between graphs based on the spectrum of the normalized Laplacian. Since this quantity can be computed easily, or at numerically estimated, it is suitable for comparing in particular large graphs. Numerical experiments demonstrate that the spectral distance provides a practically useful measure of graph dissimilarity. The asymptotic behavior of the Laplacian spectrum furthermore yields a tool for classifying families of graphs in such a way that the distance of two graphs from the same family is bounded by O(1/n) in terms of size n of their vertex sets. (C) 2015 Elsevier Inc. All rights reserved.

引用

页码：30 / 49

页数：20

共 45 条

[1] Processes on unimodular random networks [J].