本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2024-03-12
摘要
在多個領域都是必不可少的。最簡單的方法是計算 O(n3) 中的所有特徵值（其中 n 是網路中的節點數），然後對屬於區間 [a,b] 的特徵值進行計數。另一種方法是使用西爾維斯特慣性定律，這也需要 O(n3)。儘管這兩種方法都提供了 [a,b] 中特徵值的確切數量，但它們在大型網路中的應用在計算上是不可行的。有時，μ[a,b] 的近似值就足夠了。在這種情況下，切比雪夫方法在 O(|E|) 中近似 μ[a,b]（其中 |E| 是邊數）。本研究提出了兩種計算局部樹狀網路 μ[a,b] 的替代方案：基於邊緣和度數的演算法。前者比切比雪夫方法有更好的精度。它的運行時間為 O(d|E|)，其中 d 是迭代次數。後者的精度稍低，但線性運行 (O(n))。