導(dǎo)語

復(fù)雜系統(tǒng)通�？山楦呔S非線性動(dòng)力學(xué)系統(tǒng)，其宏觀行為由大量異質(zhì)成分之間的相互作用共同決定。為了獲得可解釋的宏觀描述，研究中常隱含地假設(shè)：這些相互作用可以由一個(gè)有效低秩的網(wǎng)絡(luò)矩陣來刻畫，從而使系統(tǒng)動(dòng)力學(xué)具備可降維的結(jié)構(gòu)——這一假設(shè)被稱為低秩假說。

本文系統(tǒng)闡明了低秩假說的數(shù)學(xué)內(nèi)涵，并檢驗(yàn)了其在隨機(jī)網(wǎng)絡(luò)與真實(shí)網(wǎng)絡(luò)中的適用性�；谄娈愔捣纸猓⊿VD）的基本理論，作者一方面分析了多類隨機(jī)圖模型中低秩結(jié)構(gòu)出現(xiàn)的機(jī)制，另一方面通過大量真實(shí)網(wǎng)絡(luò)數(shù)據(jù)驗(yàn)證了奇異值的快速衰減現(xiàn)象。進(jìn)一步地，文章評(píng)估了低秩結(jié)構(gòu)對(duì)網(wǎng)絡(luò)上非線性動(dòng)力學(xué)降維的影響，證明了包括循環(huán)神經(jīng)網(wǎng)絡(luò)在內(nèi)的一類動(dòng)力系統(tǒng)可以實(shí)現(xiàn)精確或近似的低維描述，并揭示了高階相互作用在降維過程中自然涌現(xiàn)的機(jī)制。

關(guān)鍵詞：低秩假設(shè)（Low-rank hypothesis）、奇異值分解（Singular value decomposition，SVD）、維度約簡(jiǎn)（Dimension reduction）、動(dòng)力學(xué)系統(tǒng)、高階相互作用（Higher-order interactions）

來源：集智俱樂部

作者： 王璇

審校： 趙思怡

論文題目：The low-rank hypothesis of complex systems 論文鏈接：https://www.nature.com/articles/s41567-023-02303-0 發(fā)表時(shí)間：2024 年 1 月 10 日 論文來源：Nature Physics

目錄

引言

網(wǎng)絡(luò)模型假說的證據(jù)

真實(shí)網(wǎng)絡(luò)假說的驗(yàn)證

誘導(dǎo)的低維假說

高階相互作用的涌現(xiàn)

結(jié)論與展望

方法

真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集

引言

理解復(fù)雜系統(tǒng)中的涌現(xiàn)行為，關(guān)鍵在于建立微觀相互作用與宏觀集體現(xiàn)象之間的聯(lián)系。與其試圖窮盡系統(tǒng)中所有組成成分的細(xì)節(jié)，降維方法關(guān)注的是能否找到一組有限的宏觀變量，使其既足以描述系統(tǒng)行為，又不會(huì)掩蓋關(guān)鍵動(dòng)力學(xué)機(jī)制。

然而，這一目標(biāo)在復(fù)雜系統(tǒng)中尤為困難。現(xiàn)實(shí)系統(tǒng)往往具有極高的維度，其動(dòng)力學(xué)狀態(tài)空間隨系統(tǒng)規(guī)模迅速膨脹，這種現(xiàn)象通常被稱為維數(shù)災(zāi)難[1-3]。在許多領(lǐng)域中，如何在保留系統(tǒng)本質(zhì)行為的同時(shí)實(shí)現(xiàn)有效降維，仍是一個(gè)懸而未決的問題。

在多者異也（More is different）的思想框架下，試圖用簡(jiǎn)潔模型刻畫復(fù)雜系統(tǒng)，表面上看似矛盾。然而，簡(jiǎn)化結(jié)構(gòu)并不意味著行為簡(jiǎn)單。許多低維或規(guī)則明確的模型，同樣可以展現(xiàn)出混沌、突變等高度復(fù)雜的動(dòng)力學(xué)現(xiàn)象。

這表明，關(guān)鍵不在于系統(tǒng)的形式是否簡(jiǎn)單，而在于所選描述是否抓住了主導(dǎo)動(dòng)力學(xué)的核心自由度。正是在這一意義上，低秩結(jié)構(gòu)為理解復(fù)雜系統(tǒng)提供了一種可能的橋梁。

在網(wǎng)絡(luò)科學(xué)中，復(fù)雜系統(tǒng)組成成分之間相互作用的拓?fù)浣Y(jié)構(gòu)通常被簡(jiǎn)化為圖，由一組頂點(diǎn)和一組邊定義 (Figs. 1a-b)。這種表示法有助于提取復(fù)雜網(wǎng)絡(luò)的主導(dǎo)特性，例如其模塊化組織結(jié)構(gòu)[13]。目前正在發(fā)生的一種范式轉(zhuǎn)變是使用超圖或單純復(fù)形（simplicial complex）來代替圖，以考慮在某些真實(shí)系統(tǒng)中觀察到的重要高階相互作用[14, 15]。除了尋找描述復(fù)雜系統(tǒng)的合適維度，人們還需要揭示其相互作用的階數(shù)。正如后文所示，這兩個(gè)問題是相互交織的。

一個(gè)圖總可以表示為一個(gè)矩陣，這一事實(shí)為利用線性代數(shù)刻畫網(wǎng)絡(luò)結(jié)構(gòu)提供了最基本、也最有力的切入點(diǎn)。基于這種表示，譜理論（spectral theory）通過對(duì)矩陣進(jìn)行分解，使人們能夠識(shí)別網(wǎng)絡(luò)中起主導(dǎo)作用的結(jié)構(gòu)成分。長(zhǎng)期以來，特征值分解被廣泛用于提取圖的關(guān)鍵性質(zhì)，例如網(wǎng)絡(luò)不變量[16]、模塊化結(jié)構(gòu)[17]、節(jié)點(diǎn)中心性[18]，以及網(wǎng)絡(luò)上動(dòng)力系統(tǒng)的分岔行為[19]。

然而，如何將譜理論有效推廣到有向、加權(quán)以及帶符號(hào)（如興奮–抑制）等更一般的網(wǎng)絡(luò)，仍然是網(wǎng)絡(luò)科學(xué)中的一項(xiàng)關(guān)鍵挑戰(zhàn)。在這些情形下，特征值分解往往會(huì)產(chǎn)生復(fù)特征值和復(fù)特征向量，從而在解釋和應(yīng)用上帶來困難。更重要的是，從數(shù)學(xué)上講，網(wǎng)絡(luò)的矩陣表示甚至并不總是可對(duì)角化的。例如，僅由一條有向邊連接的最簡(jiǎn)單有向圖，或任何其（實(shí)）矩陣表示W(wǎng)為矩形矩陣的網(wǎng)絡(luò)（如關(guān)聯(lián)矩陣、多層網(wǎng)絡(luò)中的層間耦合矩陣），都不存在特征值分解意義下的對(duì)角化表示。

然而，矩陣 WW? 和 W?W 總是方陣且對(duì)稱，因此是可對(duì)角化的，這為奇異值分解（singular value decomposition, SVD）奠定了基礎(chǔ)。有趣的是，SVD 對(duì)任何矩陣都存在，奇異向量是實(shí)值的，奇異值 σ1,...,σN 是非負(fù)實(shí)數(shù)。值得注意的是，非零奇異值的個(gè)數(shù)等于W的秩。此外，SVD 繼承了特征值分解的許多定理[20]，例如 Weyl 定理[21, 22]，但它也產(chǎn)生新的基本結(jié)果。特別地，SVD 是降維的核心工具：Schmidt-Eckart-Young-Mirsky 定理保證，截?cái)?SVD 能給出一個(gè)矩陣的最佳低秩近似 (Fig. 1c 和引理 S13)。

圖 1：真實(shí)網(wǎng)絡(luò)低秩假設(shè)的實(shí)驗(yàn)驗(yàn)證。

SVD的顯著特性及其與矩陣（有效）秩之間的密切關(guān)系，在網(wǎng)絡(luò)科學(xué)和譜圖理論中尚未得到充分的認(rèn)識(shí)，相比之下，它在數(shù)據(jù)科學(xué)（例如矩陣補(bǔ)全[23]、動(dòng)態(tài)模式分解[24]和最優(yōu)奇異值收縮[25]）、控制理論（例如Kalman準(zhǔn)則[26, 27]）、隨機(jī)矩陣?yán)碚摚ɡ鏜arcenko-Pastur's定律[28]）以及線性代數(shù)（例如矩陣范數(shù)[20]）等領(lǐng)域卻極為常見。在許多網(wǎng)絡(luò)科學(xué)或譜圖理論的主要入門教材中，甚至都沒有提及SVD。

在整個(gè)論文中，利用SVD的關(guān)鍵屬性來定義和評(píng)估復(fù)雜系統(tǒng)的低秩假設(shè)的影響。在處理復(fù)雜系統(tǒng)作為高維非線性動(dòng)力系統(tǒng)的情況之前，首先揭示了隨機(jī)圖假設(shè)的理論證據(jù)，然后對(duì)真實(shí)網(wǎng)絡(luò)的假設(shè)進(jìn)行了經(jīng)驗(yàn)驗(yàn)證。

網(wǎng)絡(luò)模型假說的證據(jù)

首先，考慮隨機(jī)圖是頗具啟發(fā)性的。隨機(jī)圖通常由一組頂點(diǎn)及其間連接的概率分布構(gòu)成，這些概率依賴于諸如頂點(diǎn)度、模塊結(jié)構(gòu)或頂點(diǎn)在度量空間中的距離等屬性。從數(shù)學(xué)上講，任意隨機(jī)圖的權(quán)重矩陣都可以表示為

W=〈W〉+R

其中〈W〉是期望權(quán)重矩陣，R 是均值為 0 的隨機(jī)矩陣。

通過研究眾多廣泛使用的隨機(jī)圖，發(fā)現(xiàn)其期望矩陣包含低秩矩陣。實(shí)際上，強(qiáng)調(diào)了一個(gè)通常隱含的假設(shè)，即〈W〉等于低秩矩陣L的函數(shù)Φ（圖 2a，方法部分表 I）。在很多情況下，Φ(L)=L，因此很容易看出〈W〉的低秩，因?yàn)樗梢詫懗芍确纸獾男问�。一個(gè)特定的魏爾不等式已經(jīng)確立了該假設(shè)的一個(gè)預(yù)期但重要的結(jié)果：一個(gè)較小的隨機(jī)部分R確保W的每個(gè)奇異值都接近〈W〉的奇異值，即

對(duì)于所有 i∈{1,...,N}，其中 σi(A) 表示矩陣 A 的第 i 個(gè)奇異值，||·||2 表示譜矩陣范數(shù)（見定理 S10 和推論 S12）。將 W=〈W〉+R，其中 〈W〉=L 且 rank(L)=r 視為一個(gè)帶尖峰的隨機(jī)矩陣[29-33]，能提供一個(gè)更精確的視角。對(duì)于此類矩陣，奇異值存在一個(gè)與 R 的奇異值相關(guān)的“主體”，并且奇異值的異常值的產(chǎn)生或消失在漸近意義上由 Baik-Ben Arous-Peche（BBP）相變[34]來表征。值得注意的是，W中存在 p≤r 個(gè)奇異值異常值僅取決于 W 的主導(dǎo)奇異值的閾值，即 σ1(〈W〉),...,σr(〈W〉）[32]。因此，〈W〉的低秩 r 以及溫和的閾值條件意味著 W 的最大奇異值位于σ1(〈W〉),...,σr(〈W〉）附近，這是低秩假設(shè)的一個(gè)初步指標(biāo)。

然而，〈W〉的低秩并非總是顯而易見的，比如在有向軟配置模型及其加權(quán)版本的情況中。實(shí)際上，它們的預(yù)期權(quán)重矩陣是秩為 1 的矩陣的非線性函數(shù)（見方法部分）。利用Weyl不等式，證明了這兩種模型中〈W〉的奇異值均被一個(gè)指數(shù)遞減項(xiàng)所上界（見方法部分中的定理 1，圖 2e 和 2i）。圖 2b - 2i 展示了在四種不同的加權(quán)隨機(jī)圖和兩種噪聲條件下，W的奇異值如何繼承了〈W〉主奇異值的遞減趨勢(shì)，而次主奇異值則與R相關(guān)。W 的主奇異值的迅速遞減暗示了網(wǎng)絡(luò)的近似低秩，從而構(gòu)成了低秩假設(shè)的第二個(gè)關(guān)鍵指標(biāo)。

然而，“迅速下降”和“接近低秩”這兩個(gè)屬性仍需進(jìn)行量化。為此，本文引入了有效秩的概念。例如，穩(wěn)定秩衡量了平方奇異值相對(duì)于 的相對(duì)重要性（見方法部分，表 II）。在圖 2j - 2m 中，展示了其隨著噪聲水平的增加在四個(gè)隨機(jī)圖中的持續(xù)性。通過 N→ ∞ 時(shí)的有效秩的漸近行為，可以更好地理解一個(gè)隨機(jī)圖的有效秩“低”的程度（見方法部分）。不同的奇異值下降會(huì)導(dǎo)致有效秩的漸近行為不同，從常數(shù) O(1) 和次線性增長(zhǎng) O(N1-?)（其中?∈ (0，1]）到線性增長(zhǎng) O(N)。值得注意的是，次線性增長(zhǎng)意味著有效秩與維度的比率在漸近情況下會(huì)下降到 O(N-?) 的形式：因此，研究者將說一個(gè)有效秩如果其增長(zhǎng)最多是次線性的，那么這個(gè)有效秩就是低的。例如，文章證明了任何具有指數(shù)遞減特征值的擴(kuò)展網(wǎng)絡(luò)模型（例如軟配置模型）都會(huì)導(dǎo)致穩(wěn)定秩以及另外兩個(gè)有效秩的漸近行為達(dá)到最低值 O(1)（見方法部分，推論 2）。然而，在處理隨機(jī)圖的單個(gè)實(shí)例或真實(shí)網(wǎng)絡(luò)時(shí)，應(yīng)保持 N 的值不變，上述漸近觀點(diǎn)就不適用了。不過，可以針對(duì)“到底低到什么程度？”這一問題給出一個(gè)更微妙、分級(jí)的回應(yīng)，即通過有效秩與維度比值來回答：比值遠(yuǎn)小于 1 的值表明在 SVD 中只有少數(shù)特征值有顯著貢獻(xiàn)，這意味著 W 可以很好地近似為低秩矩陣。因此，具有較小的有效秩與維度比值是低秩假設(shè)的第三個(gè)指標(biāo)，這次是定量的。綜上所述，對(duì)于隨機(jī)圖，低秩假設(shè)已通過三個(gè)指標(biāo)進(jìn)行了描述。第二個(gè)指標(biāo)，即特征值的快速遞減，是該假設(shè)的核心指標(biāo)：第一個(gè)指標(biāo)是導(dǎo)致遞減的理論原因，第三個(gè)指標(biāo)是其結(jié)果。第二和第三個(gè)指標(biāo)并不依賴于任何理論模型，可以應(yīng)用于任何類型的網(wǎng)絡(luò)數(shù)據(jù)。因此，本文采用了以下通用且可行的低秩假設(shè)定義：即假設(shè)網(wǎng)絡(luò)權(quán)重矩陣的奇異值迅速降低，這意味著其有效秩較低�，F(xiàn)在將這一假設(shè)進(jìn)行驗(yàn)證。

綜上所述，低秩假設(shè)在隨機(jī)圖中用三個(gè)指標(biāo)進(jìn)行了描述。第二個(gè)指標(biāo)，即奇異值的迅速下降，是該假設(shè)的核心指標(biāo)：第一個(gè)指標(biāo)是導(dǎo)致其下降的理論原因，第三個(gè)指標(biāo)則是其結(jié)果。第二個(gè)和第三個(gè)指標(biāo)與任何類型的網(wǎng)絡(luò)數(shù)據(jù)無關(guān)，并且可以應(yīng)用于此類數(shù)據(jù)中。因此，研究者采用了以下關(guān)于低秩假設(shè)的一般且可行的定義：它是假設(shè)網(wǎng)絡(luò)權(quán)重矩陣的奇異值迅速下降，這意味著有效秩較低。現(xiàn)在研究者將對(duì)這一假設(shè)進(jìn)行檢驗(yàn)。

真實(shí)網(wǎng)絡(luò)假說的驗(yàn)證

盡管低秩假說經(jīng)常被使用——通常是隱含的，但有時(shí)也非常明確[35, 36]——但對(duì)于各種類型的真實(shí)網(wǎng)絡(luò)，仍需通過實(shí)驗(yàn)來驗(yàn)證。

實(shí)驗(yàn)表明，真實(shí)網(wǎng)絡(luò)中奇異值的快速衰減是普遍現(xiàn)象。作為一個(gè)例子，在圖 1d 中展示了黑腹果蠅連接組的奇異值分布圖。圖 1e 展示了來自 10 個(gè)不同來源的 679 個(gè)真實(shí)網(wǎng)絡(luò)的奇異值分布的綜合視圖。為了幫助理解衰減趨勢(shì)，繪制了一條通用的奇異值包絡(luò)線，所有網(wǎng)絡(luò) 95% 的奇異值都位于該包絡(luò)線之下。

有了奇異值包絡(luò)線的顯式形式，就可以將穩(wěn)定秩解釋為曲線下的面積，進(jìn)而找到一個(gè)理論界限，大多數(shù)網(wǎng)絡(luò)的穩(wěn)定秩都低于此界限（見方法部分，定理3）。在圖 1f 中，展示了真實(shí)網(wǎng)絡(luò)的穩(wěn)定秩以及高于 96% 網(wǎng)絡(luò)的理論界限，這表明穩(wěn)定秩通常預(yù)期小于頂點(diǎn)數(shù)N的 10%。

為了確保這一觀察結(jié)果不僅限于穩(wěn)定秩，在圖 1g - 1m 中報(bào)告了其他有效秩的類似觀察結(jié)果（見方法部分）。對(duì)于 m 均值秩和 e 均值秩而言，其值大于 frank 是意料之中的事。實(shí)際上，很容易證明 frank≤nrank≤erank≤rank（見方法部分）。與有效秩不同的是，實(shí)網(wǎng)絡(luò)的秩通常與其維度相當(dāng)（圖 1n）。這一觀察結(jié)果是合理的，特別是對(duì)于具有真實(shí)權(quán)重的加權(quán)網(wǎng)絡(luò)而言，因?yàn)椴豢赡婢仃嚇?gòu)成了測(cè)度為 0 的集合。

所考慮的數(shù)據(jù)集均為具有固定節(jié)點(diǎn)數(shù) N 的真實(shí)網(wǎng)絡(luò)，但這些網(wǎng)絡(luò)的有效秩的漸近行為仍可以像存在一個(gè)相關(guān)的不斷增長(zhǎng)的圖那樣進(jìn)行評(píng)估，即當(dāng) N 增大時(shí)，該圖的奇異值仍處于實(shí)驗(yàn)奇異值范圍之內(nèi)。通過這種方法，研究者證明了如圖 1e 中所示的奇異值范圍對(duì)于 Frank、nrank 和 crank 來說具有恒定和次線性增長(zhǎng)（見方法部分）。

總之，研究者表明許多實(shí)際網(wǎng)絡(luò)的奇異值呈迅速遞減趨勢(shì)，從而導(dǎo)致有效秩較低。有趣的是，這種觀察結(jié)果似乎在大數(shù)據(jù)矩陣中普遍存在[37-39]，但這一現(xiàn)象仍令人困惑。特別是，這些觀察結(jié)果對(duì)于網(wǎng)絡(luò)上的高維非線性動(dòng)態(tài)的影響尚待厘清，這將在下一節(jié)中進(jìn)行探討。

圖 2：隨機(jī)圖低秩假設(shè)的三個(gè)指標(biāo)。

誘導(dǎo)的低維假說

從直覺上講，認(rèn)為具有低（有效）秩的網(wǎng)絡(luò)使得這些網(wǎng)絡(luò)上的動(dòng)態(tài)過程能夠進(jìn)行維度縮減�？紤]完整的動(dòng)態(tài)方程，其中 11是在時(shí)間 t 時(shí)系統(tǒng)的狀態(tài)，是一個(gè)連續(xù)可微的向量場(chǎng)，而 W 是一個(gè) N×N 的權(quán)重矩陣描述了該網(wǎng)絡(luò)（圖 3a - 3b）。更具體地說，給定和 W （此時(shí)x(t)未知），研究動(dòng)態(tài)方程的子類，其中 y=W。

考慮這個(gè)動(dòng)力學(xué)子類已經(jīng)突出了低秩假說的一個(gè)重要含義。g 中的線性函數(shù) 具有非常特殊的作用：即使 x 屬于一個(gè)N維流形，當(dāng) W 的秩較低時(shí)，其像空間中的向量也將屬于一個(gè)低維子流形。即使 W 是滿秩的，研究者在圖 1 中的實(shí)驗(yàn)觀察表明，它很可能具有低的有效秩。因此，研究者可以說 Wx 將屬于一個(gè)有效低維的子流形。

正如一些隨機(jī)圖模型是由低秩矩陣L的非線性函數(shù)Φ構(gòu)造而成一樣，向量場(chǎng) g 非線性地依賴于 Wx，這使得評(píng)估 g(x,y) 的低維性具有挑戰(zhàn)性。盡管最近有所進(jìn)展[40, 41]，但對(duì)于復(fù)雜網(wǎng)絡(luò)上的非線性動(dòng)力學(xué)，如何選擇降維后的維度以及如何量化降維誤差仍然不清楚。

對(duì)動(dòng)力系統(tǒng)的降維處理可以理解為將低維向量場(chǎng)與高維對(duì)應(yīng)場(chǎng)進(jìn)行對(duì)齊的問題（圖 3c ）。這涉及選擇一個(gè) n×N的降維矩陣 M，它將整個(gè)系統(tǒng)的元素映射到降維系統(tǒng)中，同時(shí)還需要一個(gè)向量場(chǎng) F，用于描述一組可觀測(cè)量 在 中的演化過程。在 中，對(duì)于 x∈處的對(duì)齊誤差，記為 ，可以定義為向量場(chǎng) M o f 與 F o M 之間的誤差（見方法部分）。

通常情況下，要將對(duì)齊誤差降至最低以找到最優(yōu)的配對(duì)方案 (M,F) 是一項(xiàng)極具挑戰(zhàn)性的任務(wù)（參見附錄 III.1），而最佳選擇則取決于建模者的具體目標(biāo)。例如，選擇 M 以確保 F 的時(shí)間演變?cè)谌魏螘r(shí)候都具有可解釋性（例如，同步可觀測(cè)量 [41]），這可能會(huì)使優(yōu)化問題變得更加復(fù)雜。

圖 3：復(fù)雜系統(tǒng)的低秩假設(shè)以及更高階相互作用的出現(xiàn)。

先專注于確定 F 的值，暫時(shí)不考慮 M 。通過最小二乘法，證明了 在中能最小化一種對(duì)齊誤差，其中 +$ 表示偽逆（見方法部分）。這樣做能夠證明，對(duì)于 ，由最小二乘向量場(chǎng)引起的對(duì)齊誤差 滿足

其中 和是雅可比矩陣 (方法)。

有趣的是，上述不等式提出了一種非任意選擇降維矩陣的方法。實(shí)際上，

該方法將與系統(tǒng)中相互作用相關(guān)的因子 ||W(I-M+M)||2 降至最低，從而通常能使每個(gè)可觀測(cè)量 Xμ 成為全局量，即包含關(guān)于大多數(shù)頂點(diǎn)的信息（見方法部分說明）。

在式（3）中所做出的選擇促使研究者推導(dǎo)出另一個(gè)不等式，該不等式揭示了網(wǎng)絡(luò)奇異值對(duì)對(duì)齊誤差的貢獻(xiàn)（見方法部分，定理 4）：

其中 。值得注意的是，該不等式為精確的維度縮減提供了一個(gè)判據(jù)：若（其中 且 n = rank(W），則上界會(huì)趨于零，此時(shí)維度縮減就是精確的（見方法部分）。

圖 4：在真實(shí)復(fù)雜網(wǎng)絡(luò)上進(jìn)行非線性動(dòng)力學(xué)分析時(shí)的維度縮減誤差與它們的奇異值和有效秩的關(guān)系。

因此，一類通用的動(dòng)力學(xué)模型，包括RNN和Wilson-Cowan神經(jīng)動(dòng)力學(xué)模型，都可以被精確地簡(jiǎn)化（見方法部分部分）。上限（4）旨在具有直觀性（不一定嚴(yán)格）：它將網(wǎng)絡(luò)奇異值的迅速衰減與維度縮減誤差聯(lián)系起來。作為一個(gè)基本的例子，對(duì)于線性系統(tǒng) ，相對(duì)對(duì)齊誤差 只能簡(jiǎn)單地用 來上界表示，這意味著網(wǎng)絡(luò)矩陣 W 的奇異值的迅速減小（無論其權(quán)重如何）都會(huì)直接導(dǎo)致對(duì)齊誤差的迅速減小。

圖 4a - d 展示了隨著參數(shù) n 的變化，對(duì)齊誤差的降低情況——后者與上界值和奇異值的迅速衰減相一致——在四個(gè)真實(shí)網(wǎng)絡(luò)的動(dòng)態(tài)系統(tǒng)中均有體現(xiàn)。研究者展示了如何通過調(diào)整 n 來預(yù)測(cè)流行病在流行病學(xué)動(dòng)態(tài)中的情況（圖 4e）、神經(jīng)元?jiǎng)討B(tài)中的滯后現(xiàn)象（圖 4f）、微生物動(dòng)態(tài)中的穩(wěn)定分支（圖 4g）或RNN中的極限循環(huán)（圖 4h）。雖然有效秩有助于選擇合適的維度 n 來描述集體現(xiàn)象，但僅將其用作一種指示： n 應(yīng)根據(jù)模型者對(duì)定性（例如，滯后現(xiàn)象是否保持不變？）或定量（例如，預(yù)測(cè)的轉(zhuǎn)變是否準(zhǔn)確？）誤差的容忍度來選擇。因此，很明顯，描述復(fù)雜網(wǎng)絡(luò)的低（有效）秩矩陣為這些網(wǎng)絡(luò)上的非線性動(dòng)態(tài)的降維提供了基礎(chǔ)。

簡(jiǎn)化后的系統(tǒng)類似于發(fā)生在一個(gè)更小結(jié)構(gòu)上的低維動(dòng)力學(xué)，該結(jié)構(gòu)的性質(zhì)仍有待明確（見圖 3c ）。將在下一節(jié)展示，降維最終導(dǎo)致了高階相互作用的涌現(xiàn)，如圖 3d 所示。

高階相互作用的涌現(xiàn)

關(guān)于各種復(fù)雜系統(tǒng)中存在更高階相互作用的理論和實(shí)驗(yàn)證據(jù)已有報(bào)道，其結(jié)果——例如對(duì)爆發(fā)性轉(zhuǎn)變[42]或介觀定位[43]的影響——也已得到了廣泛研究[44]。然而，這些相互作用的起源仍在積極研究之中，特別是對(duì)于振蕩系統(tǒng)[45，46]。

使用研究者的框架，一個(gè)簡(jiǎn)單的例子很容易提供對(duì)高階交互出現(xiàn)的見解。用i∈{1,...,N}考慮流行病學(xué)動(dòng)態(tài)，其中xi為頂點(diǎn)i被感染的概率，y=Wx而di和γ分別為頂點(diǎn)i的恢復(fù)率和感染率。簡(jiǎn)化后的動(dòng)力學(xué)由

對(duì)于所有 μ∈{1,...,n}，其中 是一個(gè)具有 n×n 規(guī)模的簡(jiǎn)化恢復(fù)率矩陣，其 D = diag(d1，...，dN}，而 是一個(gè)具有 n×n 規(guī)模的簡(jiǎn)化權(quán)重矩陣。

讓研究者更仔細(xì)地研究一下式（5）中的最后一項(xiàng)。為了簡(jiǎn)化計(jì)算，假設(shè) M+=M?，即 M 的各行是正交的。那么，Mμi 表示頂點(diǎn) i 對(duì)第 μ 個(gè)可觀測(cè)值的影響，是第 ν 個(gè)可觀測(cè)值對(duì)其在頂點(diǎn) i 上的依賴程度的加權(quán)影響，而 是第 κ 個(gè)可觀測(cè)值對(duì)其連接到頂點(diǎn) i 的頂點(diǎn)的依賴程度的加權(quán)影響。總之，這些因素形成了可觀測(cè)值 Xμ、Xν 和 Xκ 之間的三階相互作用，通過將式（5）重新排列可以更清晰地體現(xiàn)這一點(diǎn)：

其中三階相互作用被編碼在一個(gè)三階張量 中，其元素為

對(duì)于所有 μ, ν, κ∈ {1,...,n} 。因此，簡(jiǎn)化系統(tǒng)所形成的結(jié)構(gòu)是一個(gè)具有 n 個(gè)頂點(diǎn)的超圖（圖 3c-d），該超圖通常是有向的[47]、加權(quán)的、帶符號(hào)的，并由 和 構(gòu)成。

除了諸如權(quán)重矩陣W 等動(dòng)態(tài)參數(shù)的影響之外，式（7）還強(qiáng)調(diào)了縮減矩陣 M 在塑造高階相互作用方面所起的關(guān)鍵作用。實(shí)際上， M部分決定了超圖的有向、加權(quán)和有符號(hào)性質(zhì)。此外，如果可觀測(cè)量分別取決于不相交的頂點(diǎn)組，即 ，其中δ是克羅內(nèi)克符號(hào)， s 將每個(gè)頂點(diǎn) i 映射到其所屬的組，那么式（7）中元素構(gòu)成的張量可以精確地映射為一個(gè)矩陣。換句話說，在流行病學(xué)動(dòng)態(tài)中，高階相互作用源自取決于頂點(diǎn)重疊組的可觀測(cè)量（例如，一般情況下）。有趣的是，這種重疊是復(fù)雜網(wǎng)絡(luò)（如社交網(wǎng)絡(luò)）中非常常見的特征[48]。

這些觀察結(jié)果促使研究者去探尋這種涌現(xiàn)現(xiàn)象的通用條件。對(duì)于 （其中 對(duì)于所有 i∈{1,...，N} 都是一個(gè)解析標(biāo)量場(chǎng)），證明了最小二乘最優(yōu)向量場(chǎng)取決于可觀測(cè)量 X1，...，Xn 之間的高階相互作用（見方法部分，命題 5）。然后推導(dǎo)出了兩個(gè)富有啟發(fā)性的結(jié)論。首先，如果標(biāo)量場(chǎng)在 xi 和 yi上是 xi 和 yi 的總次數(shù)為 δ 的多項(xiàng)式，那么簡(jiǎn)化系統(tǒng)的超圖具有最高階 δ+1 的相互作用（見方法部分，推論 S70）。其次，具有分別依賴于不同組頂點(diǎn)的可觀測(cè)量并不足以避免一般情況下的高階相互作用： yi 中的非線性也起到了作用（見方法部分，推論 S71）。微生物和振蕩器動(dòng)力學(xué)的其他計(jì)算示例在擴(kuò)展數(shù)據(jù)表 1 中給出，以補(bǔ)充之前關(guān)于流行病學(xué)動(dòng)力學(xué)的觀察結(jié)果。

總之，研究者的研究結(jié)果表明，許多高階相互作用的情況可能是由于選擇了低維（宏觀）表示來模擬各種復(fù)雜系統(tǒng)所導(dǎo)致的副產(chǎn)品。這些結(jié)果闡明了描述維度以及原始系統(tǒng)的非線性在塑造后續(xù)簡(jiǎn)化系統(tǒng)中的相互作用方面所起的關(guān)鍵作用。

結(jié)論與展望

在本文中，闡述了低秩假設(shè)在復(fù)雜系統(tǒng)中的普遍性及其所產(chǎn)生的影響，涵蓋了從網(wǎng)絡(luò)上高維非線性動(dòng)態(tài)的降維處理到更高階相互作用的產(chǎn)生等方面的內(nèi)容。

實(shí)驗(yàn)結(jié)果表明，低秩假設(shè)或許不僅是一種假設(shè)，而且可能是許多真實(shí)復(fù)雜系統(tǒng)所固有的特性。發(fā)現(xiàn)暗示了某些涌現(xiàn)的集體現(xiàn)象可能是由遠(yuǎn)少于先驗(yàn)預(yù)期的變量所導(dǎo)致的，這得益于其復(fù)雜網(wǎng)絡(luò)的低秩特性。然而，低秩假設(shè)的使用應(yīng)當(dāng)非常謹(jǐn)慎：實(shí)際網(wǎng)絡(luò)的有效秩通常在 N 的相當(dāng)大的比例范圍內(nèi)，若不加留意地采用低秩假設(shè)，可能會(huì)導(dǎo)致對(duì)給定復(fù)雜系統(tǒng)的一種過于簡(jiǎn)化的模型。因此，基于實(shí)際網(wǎng)絡(luò)的觀測(cè)奇異值來設(shè)計(jì)新的隨機(jī)圖似乎是很有意義的。網(wǎng)絡(luò)的奇異值并非僅僅是譜理論的抽象：就像度、聚類系數(shù)或互惠性一樣，它們具有直觀的解釋，可作為復(fù)雜網(wǎng)絡(luò)/系統(tǒng)的有效維度的指標(biāo)。

理論框架還表明，從較粗粒度分辨率下觀測(cè)到的時(shí)間序列中推斷復(fù)雜系統(tǒng)中的相互關(guān)系（例如，大腦中的局部場(chǎng)電位[49] 或植物群落中的豐度[50]），很可能會(huì)揭示出顯著的高階相互作用。研究者推測(cè)，通過實(shí)驗(yàn)在不同尺度上監(jiān)測(cè)復(fù)雜系統(tǒng)將有助于闡明測(cè)量所處維度對(duì)高階相互作用出現(xiàn)的作用。對(duì)高階網(wǎng)絡(luò)上的動(dòng)態(tài)進(jìn)行維度縮減[14, 51] 也是值得探索的方向，或許可以通過塔克分解[52] 來實(shí)現(xiàn)。

然而，確定驅(qū)動(dòng)復(fù)雜系統(tǒng)行為的主要可觀測(cè)量的確切形式仍是一個(gè)未解決的問題。盡管關(guān)注的是線性可觀測(cè)量，但可能存在一組適用于特定高維動(dòng)態(tài)的少量非線性可觀測(cè)量[53]。然而，找到合適的、直觀的非線性可觀測(cè)量要困難得多[54]。研究者對(duì)真實(shí)網(wǎng)絡(luò)的有效秩的觀察也促使研究者進(jìn)一步研究從時(shí)間序列中推斷出可解釋的低秩模型的課題[55]。

最后，尚未探討的復(fù)雜系統(tǒng)的一個(gè)關(guān)鍵特性是其適應(yīng)能力[56]。研究者的初步研究結(jié)果表明，復(fù)雜網(wǎng)絡(luò)的低有效秩在控制[57, 58]以及評(píng)估復(fù)雜適應(yīng)系統(tǒng)的恢復(fù)能力方面起著核心作用[59]。此外，有跡象表明成熟或?qū)W習(xí)能夠降低網(wǎng)絡(luò)的有效秩[60]。

方法

隨機(jī)圖

一個(gè)隨機(jī)圖可以用一個(gè)隨機(jī)矩陣描述為

其中 〈W〉 是期望權(quán)重矩陣，R 是零均值隨機(jī)矩陣。即使在典型模型中，單個(gè)實(shí)例通常是滿秩 N 的，期望權(quán)重矩陣〈W〉也常被定義為一個(gè)低秩矩陣 L 的逐元素函數(shù)，即

其中 φ 是一個(gè)實(shí)變量的實(shí)值函數(shù)。這是對(duì)正文中 〈W〉=Φ(L) 的另一種等價(jià)寫法。在表 1 中，研究者列出了一些經(jīng)典隨機(jī)圖的例子及其對(duì)應(yīng)的低秩矩陣。

表 I：低秩矩陣 L，其表征了具有 N 個(gè)頂點(diǎn)的不同隨機(jī)圖的預(yù)期鄰接矩陣。SBM：隨機(jī)塊模型，CL：鐘-盧模型，MD：元度模型，DSCM：有向軟配置模型，RDPG：隨機(jī)點(diǎn)積圖，RGM：隨機(jī)幾何模型，RPG：秩擾動(dòng)高斯模型，DCSBM：度校正隨機(jī)塊模型，縮寫前的“W”表示“加權(quán)”。對(duì)于 SD RGM，L 的秩更確切地說是 D、D + 1 或 D + 2，這是由參考文獻(xiàn) [61， 定理 7] 以及不等式 rank(A o B) ≤ rank(A) rank(B) 所導(dǎo)致的。參數(shù)q、r、d 和 D 通常假定與 N 相比很小。

評(píng)估 L 的低秩是簡(jiǎn)單的，但當(dāng) φ 是非線性時(shí)，評(píng)估〈W〉的低秩則更困難。例如，在有向軟配置模型中，Φ=ΦFD，是一個(gè)費(fèi)米-狄拉克分布；在其加權(quán)版本中，Φ=ΦBE，是一個(gè)Bose-Einstein分布。對(duì)于這兩個(gè)模型，下面的定理表明它們期望權(quán)重矩陣的奇異值被一個(gè)指數(shù)衰減項(xiàng)從上界限制。

在圖 2 中，展示了 RPG、DCSBM、S1 RGM 和 WDSCM 中 W、〈W〉和 R 的奇異值。圖 2e 和 i 中顯示的上界由公式 (10) 給出，該公式通過累加常數(shù) n_{i+1}>..."},"displayMode":"inline","viewType":"inline"}}">ni>ni+1>.. 直到 ni 小于 10-12 來計(jì)算。對(duì)于 RPG，向量 mμ 和 nμ 是不同高斯分布的實(shí)例，且 r=5。使用截?cái)嗯晾弁蟹植嫉膶?shí)例來生成期望度（DCSBM 和 S1 RGM）以及 （WDSCM）。DCSBM 的塊數(shù) q 設(shè)為 5，并且定義期望邊數(shù)的塊矩陣 ∧，使得塊內(nèi)的期望邊數(shù)多于塊間。為了獲得隨機(jī)權(quán)重矩陣中隨機(jī)部分 R 的范數(shù)（RPG 除外，其 R 已設(shè)為均值為 0 的高斯分布），研究者生成了 100 個(gè) W 的實(shí)例，計(jì)算了每個(gè)實(shí)例的 R=W-〈W〉 及其范數(shù)。通過改變 RPG 中 R 各高斯元素的方差、DCSBM 中的期望邊數(shù)、S1 RGM 中的溫度 1/β 以及 WDSCM 中 和 的最小值，來增加 R 的譜范數(shù)。

表 II: 維度為 N×N、秩為 r 的矩陣的不同有效秩，以其奇異值 σ1≥ ... ≥σN 表示。對(duì)于 energy，常數(shù) Τ 是一個(gè)需在 0 到 1 之間設(shè)置的閾值。對(duì)于 thrank，σmed 是中位數(shù)奇異值，μmed 是 Mar?enko-Pastur 概率密度函數(shù)的中位數(shù) [62]。對(duì)于 shrank，s* 表示一個(gè)最優(yōu)奇異值收縮函數(shù) [25, 63]。

有效秩

從矩陣分解中提取顯著分量數(shù)量這一想法是一個(gè)古老的主題（例如，在因子分析[64,65]或主成分分析[66-71]中），但仍在隨機(jī)矩陣?yán)碚�、�?shù)據(jù)科學(xué)[29,62]以及網(wǎng)絡(luò)科學(xué)（其中超幾何幾何[57]和信息理論[68]被使用）等領(lǐng)域有著新的有趣發(fā)展。由于SVD與秩有著密切的關(guān)系，許多有效的秩是通過奇異值來定義的。直觀地說，這些有效的秩是表示在分解矩陣時(shí)哪些奇異值是顯著的數(shù)字。表 2 展示了所整理的不同有效秩的列表。有效秩 thrank 和 shrink 是從諸如 Refs. [65,66,25] 中介紹的矩陣去噪技術(shù)中定義的，這些技術(shù)依賴于無限隨機(jī)矩陣的譜理論[32]來確定收縮奇異值的最優(yōu)方法。在圖 11 中，使用了弗羅貝尼烏斯范數(shù)來獲得收縮，并且在圖 1j 中使用了能量比的閾值為 0.9 。

動(dòng)力系統(tǒng)的降維

高維非線性動(dòng)力學(xué)的降維是獲得復(fù)雜系統(tǒng)分析和數(shù)值見解的基本方法。低維動(dòng)力學(xué)可以通過優(yōu)化問題獲得，在一組約束下最小化某種誤差，以保留原始系統(tǒng)的顯著特性。對(duì)于動(dòng)力系統(tǒng)，一個(gè)自然的優(yōu)化變量是簡(jiǎn)化向量場(chǎng) F 本身，它被選擇來近似表示完整的向量場(chǎng) f。然而，找出不同向量場(chǎng)誤差之間的關(guān)系以及哪一個(gè)可以解析地最小化是相當(dāng)令人困惑的。

動(dòng)力學(xué)的積分與性質(zhì)

圖 4 中展示的真實(shí)網(wǎng)絡(luò)上的動(dòng)力學(xué)軌跡是使用 scipy.integrate 的 solve_ivp 獲得的。使用了后向微分公式（BDF），這是一種具有可變步長(zhǎng)和階數(shù)的隱式方法，已知非常適合剛性問題，例如腸道微生物組上的微生物動(dòng)力學(xué)。研究者觀察到，對(duì)于完整的微生物動(dòng)力學(xué)，相對(duì)容差 rtol=10-8 和絕對(duì)容差 atol=10-12（對(duì)于簡(jiǎn)化動(dòng)力學(xué)為 rtol=10-6 和 atol=10-10）在合理的積分時(shí)間內(nèi)給出了可靠的結(jié)果，并且與最近的基準(zhǔn)測(cè)試結(jié)果一致。此外，研究者按照 solve_ivp 文檔對(duì) BDF 方法的建議，向積分器提供了完整和簡(jiǎn)化動(dòng)力學(xué)的雅可比矩陣。研究者還使用相對(duì)容差 10-8 和絕對(duì)容差 10-12 的 BDF 方法積分了其他動(dòng)力學(xué)。

對(duì)于流行病學(xué)動(dòng)力學(xué)，出現(xiàn)了臨界慢化現(xiàn)象，但可以通過在跨臨界分岔點(diǎn)附近增加時(shí)間步數(shù)來輕松處理，正如在圖 4e 插圖中所做的那樣。注意，增加維度可以提高對(duì)更高感染率的預(yù)測(cè)。在圖 4f 中，觀察到神經(jīng)元?jiǎng)恿W(xué)的全局可觀測(cè)量相對(duì)于突觸權(quán)重存在滯回現(xiàn)象。在圖 4e-f 中，均方根誤差（RMSE）簡(jiǎn)單地計(jì)算為完整動(dòng)力學(xué)和簡(jiǎn)化動(dòng)力學(xué)在不同 n 下的全局平衡點(diǎn)之間的誤差。

如圖 4g 所示，微生物動(dòng)力學(xué)的全局可觀測(cè)量出現(xiàn)了多個(gè)穩(wěn)定的平衡點(diǎn)分支。按照以下步驟進(jìn)行，以獲得一個(gè)僅涉及部分平衡點(diǎn)分支的簡(jiǎn)化圖景。專注于使用從 0 到 1 的均勻分布中采樣的初始條件 x0 獲得的一個(gè)前向分支，并在圖 4g 中展示了當(dāng)逐漸增加微生物相互作用權(quán)重時(shí)其穩(wěn)定性的喪失。為了獲得一個(gè)后向分支，從 0 到 z 的均勻分布中采樣初始條件 x0，其中 z 是 1 到 15 之間的隨機(jī)整數(shù)，然后積分動(dòng)力學(xué)以獲得平衡點(diǎn)，接著降低微生物相互作用權(quán)重，并將最后一個(gè)平衡點(diǎn)用作下一次積分的初始條件，重復(fù)最后這兩個(gè)步驟，直到達(dá)到最小耦合值。重復(fù)所有這些步驟 100 次以生成不同的初始條件和穩(wěn)定分支。在每次迭代中，確保在平衡點(diǎn)處評(píng)估的向量場(chǎng)得到的向量其元素低于容差 10-7，并且平衡點(diǎn)是正的。在這種情況下，RMSE 計(jì)算為完整動(dòng)力學(xué)和簡(jiǎn)化動(dòng)力學(xué)的平均上分支和下分支之間的誤差。

對(duì)于（有限尺寸的）RNN，與參考文獻(xiàn)[71]結(jié)論中的觀察類似，在較低耦合時(shí)零點(diǎn)是穩(wěn)定平衡點(diǎn)，增加耦合最終會(huì)導(dǎo)致復(fù)雜性增加的極限環(huán)。研究者展示了當(dāng)維度n 接近學(xué)習(xí)網(wǎng)絡(luò)的秩時(shí)，完整動(dòng)力學(xué)中這個(gè)高維極限環(huán)的 3 維投影，以及簡(jiǎn)化動(dòng)力學(xué)中的極限環(huán)。RMSE 計(jì)算為完整循環(huán)神經(jīng)動(dòng)力學(xué)的極限環(huán)上的點(diǎn)與簡(jiǎn)化動(dòng)力學(xué)極限環(huán)上最近點(diǎn)之間的誤差。

真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集

本節(jié)列出本文使用的真實(shí)網(wǎng)絡(luò)，并給出兩幅補(bǔ)充圖。 表中所有網(wǎng)絡(luò)都來自 Netzschleuder，只有其中 31 個(gè)例外，列在下面。

? ‘celegans signed’：該網(wǎng)絡(luò)由開源數(shù)據(jù)庫 EleganSign [284] 的連接組 NT+R 方法預(yù)測(cè)結(jié)果補(bǔ)全得到，補(bǔ)全時(shí)遵循 Dale 原則（見 GitHub 倉庫中的 graphs/get real networks.py，函數(shù) get connectome weight matrix）。

? ‘drosophila’：取自文獻(xiàn) [12]。

? ‘cintestinalis’：Ciona intestinalis 的連接組來自文獻(xiàn) [285]，并保存在研究者的 Github 倉庫：graphs/graph data/connectome/ciona intestinalis lavaire elife-16962-fig16-data1-v1 modified.xlsx。

? ‘pdumerilii neuronal’：Platynereis dumerilii 的神經(jīng)連接組來自文獻(xiàn) [286]。 該版本為更新版，由作者 G. Jékely 私下分享給 V. Thibeault。 連接組文件在研究者的 Github 倉庫：graphs/graph data/connectome/pdumerilii neuronal.xml。

? ‘pdumerilii desmosomal’：Platynereis dumerilii 的橋粒（desmosomal）連接組來自文獻(xiàn) [287]。 該版本為更新版，由作者 G. Jékely 私下分享給 V. Thibeault。 連接組文件在研究者的 Github 倉庫：graphs/graph data/connectome/pdumerilii desmosomal.xml。

? ‘mouse meso’：小鼠介觀（mesoscopic）連接組來自文獻(xiàn) [288]，并保存在研究者的 Github 倉庫：graphs/graph data/connectome/mouse connectome-Oh Nature 2014.csv。

? ‘zebrafish meso’：斑馬魚介觀連接組由文獻(xiàn) [202] 改編得到，處理過程見本文 GitHub 倉庫 low-rank-hypothesis-complex-systems。

? ‘mouse voxel’：體素（voxel）尺度的小鼠連接組可在 Mendeley 數(shù)據(jù)集 mouse connectome voxelwise [289] 獲取。

? ‘mouse control rnn’、‘mouse rnn’、‘zebrafish rnn’：來自 Hadjiabadi 等人 [281] 的遞歸神經(jīng)網(wǎng)絡(luò)。

? ‘fully connected layer cnn XXXXX’（其中 XXXXX ∈ {00100, 00200, ..., 01000}）：來自倉庫 NWS [183] 中卷積神經(jīng)網(wǎng)絡(luò)的全連接層[183]。

? ‘gut’：人類腸道微生物組網(wǎng)絡(luò)來自文獻(xiàn) [282]，其構(gòu)造方式與文獻(xiàn) [58] 的補(bǔ)充材料一致（見 GitHub 倉庫 graphs/get real networks.py 中的函數(shù) get microbiome weight matrix）。

? ‘AT 2008’、‘CY 2015’、‘EE 2010’、‘PT 2009’、‘SI 2016’：來自文獻(xiàn) [290] 的經(jīng)濟(jì)網(wǎng)絡(luò)。

? ‘financial institution07-Apr-1999’、‘non financial institution04-Jan-2001’、‘households 04-Sep-1998’、‘households 09-Jan-2002’：Dryad 上文獻(xiàn) [291] 的經(jīng)濟(jì)網(wǎng)絡(luò)。

從 Github 提取各網(wǎng)絡(luò)的代碼在 graphs/get real networks 中。 關(guān)于數(shù)據(jù)集里真實(shí)網(wǎng)絡(luò)的更多信息，也可在 Github 倉庫 low-rank-hypothesis-complex-systems 中找到。 具體來說，可以查看 graphs/graph data 中的 real networks and their effective ranks.pdf，以獲得每個(gè)網(wǎng)絡(luò)的來源信息；或等價(jià)地查看補(bǔ)充表 1（supplementary table 1 real networks.pdf）。 需要說明的是，在計(jì)算有效秩之前，研究者做過一次預(yù)處理：為避免某些網(wǎng)絡(luò)類型被過度代表，研究者從包含 1145 個(gè)網(wǎng)絡(luò)的更大數(shù)據(jù)集中刪去了許多 Netzschleuder 網(wǎng)絡(luò)（例如 ‘board directors net1m...’、‘edit wikibooks...’、‘ego social gplus...’）。

研究者針對(duì)不同的奇異值衰減形式，給出了圖模型有效秩的漸近結(jié)果。 這些結(jié)果展示了多種可能行為：從常數(shù)增長(zhǎng) O(1），到次線性增長(zhǎng) O(N1-?}（其中 0 <?<1< pan>），再到線性增長(zhǎng) O(N）（當(dāng) N→∞）。 雖然研究者并不期望用單一圖模型來描述數(shù)據(jù)集中所有網(wǎng)絡(luò)（否則就能做統(tǒng)一的漸近分析），但研究者仍然可以問：有效秩如何隨網(wǎng)絡(luò)規(guī)模 N 分布。 在圖 S11 中，研究者給出了這樣的分布并做了非線性回歸。 回歸結(jié)果提示：隨著 N 增大，有效秩呈現(xiàn)次線性上升。 正如 II E 小節(jié)所說，進(jìn)一步研究增長(zhǎng)圖與真實(shí)增長(zhǎng)網(wǎng)絡(luò)中的有效秩行為，將有助于驗(yàn)證這種次線性增長(zhǎng)是否普遍存在。

此外，許多真實(shí)網(wǎng)絡(luò)與合成網(wǎng)絡(luò)都呈現(xiàn)稀疏矩陣結(jié)構(gòu)。 在 II C 小節(jié)研究者也指出，稀疏矩陣模型會(huì)給出較低的穩(wěn)定秩。 但是圖 S12 表明：真實(shí)網(wǎng)絡(luò)的有效秩與權(quán)重矩陣的密度反而呈現(xiàn)負(fù)相關(guān)。 這暗示，研究者在圖 1 中觀察到的有效秩現(xiàn)象，更關(guān)鍵的原因可能是奇異值的快速衰減，而不是單純的稀疏性。

參考文獻(xiàn)

[1] R. Bellman, Dynamic Programming (Princeton University Press, Princeton, 1957).

[2] S. Ganguli and H. Sompolinsky, "Compressed sensing, sparsity, and dimensionality in neuronal information processing and data analysis," Annu. Rev. Neurosci. 35, 485 (2012).

[3] L. F. Abbott et al., "The Mind of a Mouse," Cell 182, 1372 (2020).

[4] P. W. Anderson, "More is different," Science 177, 393 (1972).

[5] S. Strogatz, S. Walker, J. M. Yeomans, C. Tarnita, E. Arcaute, M. De Domenico, O. Artime, and K.-I. Goh, "Fifty years of 'More is different'," Nat. Rev. Phys. 4, 508 (2022).

[6] R. M. May, "Simple mathematical models with very complicated dynamics," Nature 261, 459 (1976).

[7] J. von Neumann, "The general and logical theory of automata," in John von Neumann Collected Work, Vol. V, edited by A. H. Taub (Bergamon Press, 1963) p. 288.

[8] S. Wolfram, "Cellular automata as models of complexity," Nature 311, 419 (1984).

[9] G. Parisi, "Statistical Physics and biology," Phys. World 6, 42 (1993).

[10] D. L. Stein and C. M. Newman, Spin Glasses and Complexity (Princeton University Press, New Jersey, 2013).

[11] K. I. Funahashi and Y. Nakamura, "Approximation of dynamical systems by continuous time recurrent neural networks," Neural Netw. 6, 801 (1993).

[12] L. K. Scheffer et al., "A connectome and analysis of the adult Drosophila central brain," eLife 9, 1 (2020).

[13] S. Fortunato and M. E. J. Newman, "20 years of network community detection," Nat. Phys. 18, 848 (2022).

[14] G. Bianconi, Higher-Order Networks (Cambridge University Press, Cambridge, 2021).

[15] F. Battiston, E. Amico, A. Barrat, G. Bianconi, G. F. de Arruda, B. Franceschiello, I. Iacopini, and S. Kéfi, "The physics of higher-order interactions in complex systems," Nat. Phys. 17, 1093 (2021).

[16] H. S. Wilf, "The eigenvalues of a graph and its chromatic number," J. Lond. Math. Soc. 1, 330 (1967).

[17] W. E. Donath and A. J. Hoffman, "Lower Bounds for the Partitioning of Graphs," IBM J. Res. Dev. 17, 420 (1973).

[18] P. Bonacich, "Factoring and weighting approaches to status scores and clique identification," J. Math. Sociol. 2, 113 (1972).

[19] J. G. Restrepo, E. Ott, and B. R. Hunt, "Onset of synchronization in large networks of coupled oscillators," Phys. Rev. E 71, 036151 (2005).

[20] R. A. Horn and C. R. Johnson, Matrix Analysis (Cambridge University Press, 2013).

[21] H. Weyl, "Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differentialgleichungen (mit einer Anwendung auf die Theorie der Hohlraumstrahlung)," Math. Ann. 71, 441 (1912).

[22] K. Fan, "Maximum properties and inequalities for the eigenvalues of completely continuous operators," Proc. Natl. Acad. Sci. U.S.A. 37, 760 (1951).

[23] J.-F. Cai, E. J. Candès, and Z. Shen, "A singular value thresholding algorithm for matrix completion," SIAM J. Optim. 46, 1956 (2010).

[24] J. N. Kutz, S. L. Brunton, and B. W. Brunton, Dynamic Mode Decomposition (SIAM, 2016).

[25] M. Gavish and D. L. Donoho, "Optimal Shrinkage of Singular Values," IEEE Trans. Inf. Theory 63, 2137 (2017).

[26] R. E. Kalman, "On the general theory of control systems," in 1st International IFAC Congress on Automatic and Remote Control (1960) p. 491; "Contributions to the theory of time-optimal control," Bol. Soc. Mat. Mex. 5, 102 (1960).

[27] G. Yan, P. E. Vértes, E. K. Towlson, Y. L. Chew, D. S. Walker, W. R. Schafer, and A.-L. Barabási, "Network control principles predict neuron function in the Caenorhabditis elegans connectome," Nature 550, 519 (2017).

[28] V. A. Mar?enko and L. A. Pastur, "Distribution of eigenvalues for some sets of random matrices," Math. USSR-Sbornik 1, 457 (1967).

[29] D. Féral and S. Péché, "The largest eigenvalue of rank one deformation of large wigner matrices," Commun. Math. Phys. 272, 185 (2007).

[30] M. Capitaine, C. Donati-Martin, and D. Féral, "The largest eigenvalues of finite rank deformation of large wigner matrices: convergence and nonuniversality of the fluctuation," Ann. Probab. 37, 1 (2009).

[31] F. Benaych-Georges and R. R. Nadakuditi, "The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices," Adv. Math. 227, 494 (2011).

[32] F. Benaych-Georges and R. R. Nadakuditi, "The singular values and vectors of low rank perturbations of large rectangular random matrices," J. Multivar. Anal. 111, 120 (2012).

[33] A. Pizzo, D. Renfrew, and A. Soshnikov, "On finite rank deformations of wigner matrices," in Ann. I. H. Poincaré - PR, Vol. 49 (2013) p. 64.

[34] J. Baik, G. Ben Arous, and S. Péché, "Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices," Ann. Probab. 33, 1643 (2005).

[35] E. Valdano and A. Arenas, "Exact rank reduction of network models," Phys. Rev. X 9, 031050 (2019).

[36] M. Beiran, A. Dubreuil, A. Valente, F. Mastrogiuseppe, and S. Ostojic, "Shaping dynamics with multiple populations in low-rank recurrent networks," Neural Comput. 33, 1572 (2021).

[37] P. Gao and S. Ganguli, "On simplicity and complexity in the brave new world of large-scale neuroscience," Curr. Opin. Neurobiol. 32, 148 (2015).

[38] B. Beckermann and A. Townsend, "On the singular values of matrices with displacement structure," SIAM J. Matrix Anal. Appl. 38, 1227 (2017).

[39] M. Udell and A. Townsend, "Why are big data matrices approximately low rank?" SIAM J. Math. Data Sci. 1, 14459 (2019).

[40] J. Gao, B. Barzel, and A.-L. Barabási, "Universal resilience patterns in complex networks," Nature 530, 307 (2016); C. Tu, J. Grilli, F. Schuessler, and S. Suweis, "Collapse of resilience patterns in generalized Lotka-Volterra dynamics and beyond," Phys. Rev. E 95, 062307 (2017); J. Jiang, Z.-G. Huang, T. P. Seager, W. Lin, C. Grebogi, A. Hastings, and Y.-C. Lai, "Predicting tipping points in mutualistic networks through dimension reduction," Proc. Natl. Acad. Sci. U.S.A. 115, E639 (2018); E. Laurence, N. Doyon, L. J. Dubé, and P. Desrosiers, "Spectral dimension reduction of complex dynamical networks," Phys. Rev. X 9, 011042 (2019); M. Vegué, V. Thibeault, P. Desrosiers, and A. Allard, "Dimension reduction of dynamics on modular and heterogeneous directed networks," PNAS Nexus, pgad150 (2023); P. Kundu, H. Kori, and N. Masuda, "Accuracy of a one-dimensional reduction of dynamical systems on networks," Phys. Rev. E 105, 024305 (2022).

[41] V. Thibeault, G. St-Onge, L. J. Dubé, and P. Desrosiers, "Threefold way to the dimension reduction of dynamics on networks: An application to synchronization," Phys. Rev. Research 2, 043215 (2020).

[42] C. Kuehn and C. Bick, "A universal route to explosive phenomena," Sci. Adv. 7, 1 (2021).

[43] G. St-Onge, V. Thibeault, A. Allard, L. J. Dubé, and L. Hébert-Dufresne, "Social confinement and mesoscopic localization of epidemics on networks," Phys. Rev. Lett. 126, 098301 (2021).

[44] F. Battiston, G. Cencetti, I. Iacopini, V. Latora, M. Lucas, A. Patania, J.-G. Young, and G. Petri, "Networks beyond pairwise interactions: Structure and dynamics," Phys. Rep. 874, 1 (2020).

[45] M. H. Matheny, J. Emenheiser, W. Fon, A. Chapman, A. Salova, M. Rohden, J. Li, M. Hudoba De Badyn, M. Pósfai, L. Duenas-Osorio, M. Mesbahi, J. P. Crutchfield, M. C. Cross, R. M. D'Souza, and M. L. Roukes, "Exotic states in a simple network of nanoelectromechanical oscillators," Science 363, 1057 (2019).

[46] E. Nijholt, J. L. Ocampo-Espindola, D. Eroglu, I. Z. Kiss, and T. Pereira, "Emergent hypernetworks in weakly coupled oscillators," Nat. Commun. 13, 4849 (2022).

[47] G. Gallo, G. Longo, S. Pallottino, and S. Nguyen, "Directed hypergraphs and applications," Discret. Appl. Math. 42, 177 (1993).

[48] G. Palla, I. Derényi, I. Farkas, and T. Vicsek, "Uncovering the overlapping community structure of complex networks in nature and society," Nature 435, 814 (2005).

[49] S. Yu, H. Yang, H. Nakahara, D. Plenz, G. S. Santos, and D. Nikolic, "Higher-order interactions characterized in cortical activity," J. Neurosci. 31, 17514 (2011).

[50] M. M. Mayfield and D. B. Stouffer, "Higher-order interactions capture unexplained complexity in diverse communities," Nat. Ecol. Evol. 1, 1 (2017).

[51] G. Ferraz de Arruda, M. Tizzani, and Y. Moreno, "Phase transitions and stability of dynamical processes on hypergraphs," Commun. Phys. 4, 24 (2021).

[52] L. Qi and Z. Luo, Tensor analysis (SIAM, 2017).

[53] S. Watanabe and S. H. Strogatz, "Constants of motion for superconducting Josephson arrays," Physica D 74, 197 (1994).

[54] S. L. Brunton, M. Budi?i?, E. Kaiser, and J. N. Kutz, "Modern Koopman theory for dynamical systems," SIAM Rev. 64, 229 (2022).

[55] A. Valente, J. W. Pillow, and S. Ostojic, "Extracting computational mechanisms from neural data using low-rank RNNs," (Curran Associates, Inc., 2022, 2022) p. 24072.

[56] J. H. Holland, Hidden Order: How Adaptation Builds Complexity (Addison-Wesley, 1995).

[57] A. N. Montanari, C. Duan, L. A. Aguirre, and A. E. Motter, "Functional observability and target state estimation in large-scale networks," Proc. Natl. Acad. Sci. U.S.A. 119, e2113750119 (2022).

[58] H. Sanhedrai, J. Gao, A. Bashan, M. Schwartz, S. Havlin, and B. Barzel, "Reviving a failed network through microscopic interventions," Nat. Phys. 18, 338 (2022).

[59] P. Desrosiers and X. Roy-Pomerleau, "One for all," Nat. Phys. 18, 238 (2022).

[60] C. H. Martin and M. W. Mahoney, "Implicit self-regularization in deep neural networks: Evidence from random matrix theory and implications for learning," J. Mach. Learn. Res. 22, 1 (2021).

[61] J. Gower, "Properties of Euclidean and non-Euclidean distance matrices," Linear Algebra Appl. 67, 81 (1985).

[62] M. Gavish and D. L. Donoho, "The optimal hard threshold for singular values is 4/√3," IEEE Trans. Inf. Theory 60, 5040 (2014).

[63] D. Donoho, M. Gavish, and I. Johnstone, "Optimal shrinkage of eigenvalues in the spiked covariance model," Ann. Statis. 46, 1742 (2018).

[64] E. R. Malinowski, "Theory of error in factor analysis," Anal. Chem. 49, 606 (1977).

[65] E. Sánchez and B. R. Kowalski, "Generalized rank annihilation factor analysis," Anal. Chem. 58, 496 (1986).

[66] H. Abdi and L. J. Williams, "Principal component analysis," WIREs Comput. Stat. 2, 433 (2010).

[67] P. Almagro, M. Bogu?á, and M. Angeles Serrano, "Detecting the ultra low dimensionality of real networks," Nat. Commun. 13, 6096 (2022).

[68] C. W. Lynn and D. S. Bassett, "Compressibility of complex networks," Proc. Natl. Acad. Sci. U.S.A. 118, e2023473118 (2021).

[69] P. O. Perry, Cross-Validation for Unsupervised Learning, Ph.D. thesis, Stanford University (2009).

[70] P. St?dter, Y. Sch?lte, L. Schmiester, J. Hasenauer, and P. L. Stapor, "Benchmarking of numerical integration methods for ODE models of biological systems," Sci. Rep. 11, 2696 (2021).

[71] H. Sompolinsky, A. Crisanti, and H.-J. Sommers, "Chaos in random neural networks," Phys. Rev. Lett. 61, 259 (1988).

[72] E. Schmidt, "Zur Theorie der linearen und nichtlinearen Integralgleichungen," Math. Ann. 63, 433 (1907).

[73] C. Eckart and G. Young, "The approximation of one matrix by another of lower rank," Psychometrika 1, 211 (1936).

[74] G. W. Stewart, "On the early history of singular value decomposition," SIAM Rev. 35, 551 (1993).

[75] S. L. Brunton and J. N. Kutz, Data-Driven Science and Engineering: Machine Learning, Dynamical Systems, and Control (Cambridge University Press, 2019).

[76] J. J. Gerbrands, "On the relationships between SVD, KLT and PCA," Pattern Recognit. 14, 375 (1981).

[77] H. Hotelling, "Analysis of a complex of statistical variables into principal components," J. Educ. Psych. 24, 417 (1933).

[78] H. Hotelling, "Analysis of a complex of statistical variables into principal components," J. Educ. Psych. 24, 498 (1933).

[79] S. Wold, K. Esbensen, and P. Geladi, "Principal component analysis," Chemom. Intell. Lab. Syst. 2, 37 (1987).

[80] L. Ferré, "Selection of components in principal component analysis: A comparison of methods," Comput. Stat. Data Anal. 19, 669 (1995).

[81] I. M. Johnstone and D. Paul, "PCA in High Dimensions: An Orientation," Proc. IEEE 106, 1277 (2018).

[82] R. D. Cook, "A slice of multivariate dimension reduction," J. Multivar. Anal. 188, 104812 (2022).

[83] K. Karhunen, Uber lineare Methoden in der Wahrscheinlichkeitsrechnung, Ph.D. thesis, University of Helsinki (1947).

[84] M. Loève, Probability theory: foundations, random sequences (Springer, 1955).

[85] R. Everson and L. Sirovich, "Karhunen-Loève procedure for gappy data," J. Opt. Soc. Am. A 12, 1657 (1995).

[86] G. Kerschen, J.-C. Golinval, A. F. Vakakis, and L. A. Bergman, "The method of proper orthogonal decomposition for dynamical characterization and order reduction of mechanical systems: An overview," Nonlinear Dyn. 41, 147 (2005).

[87] S. Volkwein, "Proper Orthogonal Decomposition: Theory and Reduced-Order Modelling," (2013).

[88] E. Lorenz, Empirical Orthogonal Functions and Statistical Weather Prediction, Tech. Rep. (Massachusetts Institute of Technology, 1956).

[89] A. H. Monahan, J. C. Fyfe, M. H. P. Ambaum, D. B. Stephenson, and G. R. North, "Empirical orthogonal functions: The medium is the message," J. Clim. 22, 6501 (2009).

[90] H. Bourlard and Y. Kamp, "Auto-association by multilayer perceptrons and singular value decomposition," Biol. Cybern. 59, 291 (1988).

[91] H. Bourlard and S. H. Kabil, "Autoencoders reloaded," Biol. Cybern. 116, 389 (2022).

[92] Z. Bai and J. W. Silverstein, Spectral Analysis of Large Dimensional Random Matrices, 2nd ed. (Springer, New York, 2010).

[93] T. Tao, Topics in Random Matrix Theory, Vol. 132 (American Mathematical Society, 2012).

[94] T. Tao and V. Vu, "Random covariance matrices: Universality of local statistics of eigenvalues," Ann. Probab. 40, 1285 (2012).

[95] A. Bloemendal and B. Virág, "Limits of spiked random matrices ii," Ann. Probab. 44, 2726 (2016).

[96] P. J. Forrester, Log-Gases and Random Matrices (Princeton University Press, 2010).

[97] R. A. Horn and C. R. Johnson, Topics in matrix analysis (Cambridge University Press, 1991).

[98] A. W. Marshall, I. Olkin, and B. C. Arnold, Inequalities: Theory of Majorization and its Application, 2nd ed. (Springer, 2011).

[99] H. Wittmeyer, "Einflu? der ?nderung einer Matrix auf die L?sung des zugeh?rigen Gleichungssystems, sowie auf die charakteristischen Zahlen und die Eigenvektoren," Z. Angew. Math. Mech. 16, 287 (1936).

[100] L. Mirsky, "Symmetric gauge functions and unitarily invariant norms," Q. J. Math. 11, 50 (1960).

[101] A. Ben-Israel and T. N. E. Greville, Generalized Inverses: Theory and Applications, 2nd ed. (Springer, New York, 2003).

[102] A. C. Antoulas, Approximation of Large-Scale Dynamical System (SIAM, 2005).

[103] G. H. Golub and C. F. Van Loan, Matrix Computations, 4th ed. (John Hopkins University Press, 2013).

[104] I. Markovsky, Low-Rank Approximations: Algorithms, Implementation, Applications, 2nd ed. (Springer, 2019).

[105] N. Harvey, "Low-rank approximation of matrices," (2011), Lecture 15, Section 1, University of British Columbia.

[106] R. Penrose, "Generalized inverse matrices," Math. Proc. Camb. Philos. Soc. 51, 406 (1955).

[107] R. Vershynin, High-Dimensional Probability: An Introduction with Applications in Data Science (Cambridge University Press, New York, 2018).

[108] M. Rudelson and R. Vershynin, "Sampling from large matrices: An approach through geometric functional analysis," J. ACM 54, 1 (2007).

[109] M. B. Cohen, J. Nelson, and D. P. Woodruff, "Optimal approximate matrix product in terms of stable rank," in 43rd Int. Colloq. Autom. Lang. Program. (ICALP 2016), Vol. 55 (2016) p. 11.

[110] B. Désy, P. Desrosiers, and A. Allard, "Dimension matters when modeling network communities in hyperbolic spaces," arXiv:2209.09201 (2023).

[111] A. Kyrillidis, M. Vlachos, and A. Zouzias, "Approximate matrix multiplication with application to linear embeddings," IEEE Int. Symp. Inf. Theory, 2182 (2014).

[112] I. Gutman, "The energy of a graph: Old and new results," Algebr. Comb. Appl., 196 (2001).

[113] V. Nikiforov, "The energy of graphs and matrices," J. Math. Anal. Appl. 326, 1472 (2007); B. Nica, A Brief Introduction to Spectral Graph Theory (European Mathematical Society, Zurich, 2018).

[114] A. A. Shabalin and A. B. Nobel, "Reconstruction of a low-rank matrix in the presence of Gaussian noise," J. Multivar. Anal. 118, 67 (2013).

[115] O. Roy and M. Vetterli, "The effective rank: A measure of effective dimensionality," in Eur. Signal Process. Conf. (2007) p. 606.

[116] R. Cangelosi and A. Goriely, "Component retention in principal component analysis with application to cDNA microarray data," Biol. Direct 2, 1 (2007).

[117] O. Alter, P. O. Brown, and D. Botstein, "Singular value decomposition for genome-Wide expression data processing and modeling," Proc. Natl. Acad. Sci. U.S.A. 97, 10101 (2000).

[118] L. L. Campbell, "Minimum coefficient rate for stationary random processes," Inf. Control 3, 360 (1960).

[119] W. Leeb, "Optimal singular value shrinkage for operator norm loss: Extending to non-square matrices," Stat. Probab. Lett. 186, 109472 (2022).

[120] M. W. Mahoney, "Randomized algorithms for matrices and data," Found. Trends Mach. Learn. 3, 123 (2011).

[121] P. D. Killworth and H. R. Bernard, "Informant accuracy in social network data," Hum. Organ. 35, 269 (1976).

[122] T. P. Peixoto, "Reconstructing networks with unknown and heterogeneous errors," Phys. Rev. X 8, 041011 (2018).

[123] M. E. J. Newman, "Network structure from rich but noisy data," Nat. Phys. 14, 542 (2018).

[124] J.-G. Young, G. T. Cantwell, and M. E. Newman, "Bayesian inference of network structure from unreliable data," J. Complex Netw. 8, 1 (2020).

[125] J.-G. Young, F. S. Valdovinos, and M. E. J. Newman, "Reconstruction of plant–pollinator networks from observational data," Nat. Commun. 12, 1 (2021).

[126] Z. Füredi and J. Komlós, "The eigenvalues of random symmetric matrices," Combinatorica 1, 233 (1981).

[127] P. Bonacich, "Power and Centrality: A Family of Measures," Am. J. Sociol. 92, 1170 (1987); F. Chung, Spectral Graph Theory (CBMS, Rhode Island, 1994).

[128] F. Chung, L. Lu, and V. Vu, "Spectra of random graphs with given expected degrees," Proc. Natl. Acad. Sci. U.S.A. 100, 6313 (2003).

[129] S. N. Dorogovtsev, A. V. Goltsev, J. F. F. Mendes, and A. N. Samukhin, "Spectra of complex networks," Phys. Rev. E 68, 046109 (2003).

[130] P. Van Mieghem, Graph Spectra for Complex Networks (Cambridge University Press, 2011).

[131] F. Chung and M. Radcliffe, "On the spectra of general random graphs," Electron. J. Comb. 18, P215 (2011).

[132] R. R. Nadakuditi and M. E. J. Newman, "Graph Spectra and the Detectability of Community Structure in Networks," Phys. Rev. Lett. 108, 188701 (2012).

[133] T. P. Peixoto, "Eigenvalue Spectra of Modular Networks," Phys. Rev. Lett. 111, 098701 (2013).

[134] C. Castellano and R. Pastor-Satorras, "Topological determinants of complex networks spectral properties: structural and dynamical effects," Phys. Rev. X 7, 041024 (2017).

[135] M. E. J. Newman, X. Zhang, and R. R. Nadakuditi, "Spectra of random networks with arbitrary degrees," Phys. Rev. E 99, 042309 (2019).

[136] A. Athreya, J. Cape, and M. Tang, "Eigenvalues of stochastic blockmodel graphs and random graphs with low-rank edge probability matrices," Sankhya A 84, 36 (2022).

[137] E. Estrada and P. Knight, A first course on network science (Oxford University Press, 2015); A.-L. Barabási, Network science (Cambridge University Press, 2016); V. Latora, V. Nicosia, and G. Russo, Complex Networks: Principles, Methods and Applications (Cambridge University Press, 2017); M. E. J. Newman, Networks (Oxford University Press, 2018).

[138] D. M. Cvetkovic, M. Doob, and H. Sachs, "Spectra of graphs. Theory and application," (1980).

[139] R. Solomonoff and A. Rapoport, "Connectivity of random nets," Bull. Math. Biophys. 13, 59 (1951).

[140] E. N. Gilbert, "Random graphs," Ann. Math. Stat. 30, 1141 (1959).

[141] P. Erd?s and A. Rényi, "On the evolution of random graphs," Publ. Math. Inst. Hung. Acad. Sci 5, 17 (1960).

[142] M. E. J. Newman, "The structure and function of complex networks," SIAM Rev. 45, 167 (2003).

[143] A. Guionnet, "Bernoulli Random Matrices," arXiv:2112.05506 (2021).

[144] A. Perry, A. S. Wein, A. S. Bandeira, and A. Moitra, "Optimality and sub-optimality of PCA I: Spiked random matrix models," Ann. Statis. 46, 2416 (2018).

[145] P. W. Holland, K. B. Laskey, and S. Leinhardt, "Stochastic blockmodels: First steps," Soc. Netw. 5, 109 (1983).

[146] J.-G. Young, G. St-Onge, P. Desrosiers, and L. J. Dubé, "Universality of the stochastic block model," Phys. Rev. E 98, 032309 (2018).

[147] F. Chung and L. Lu, "Connected Components in Random Graphs with Given Expected Degree Sequences," Ann. Comb. 6, 125 (2002).

[148] F. Chung and L. Lu, "The average distances in random graphs with given expected degrees," Proc. Natl. Acad. Sci. U.S.A. 99, 15879 (2002).

[149] W. Wang, M. Tang, E. H. Stanley, and L. A. Braunstein, "Unification of theoretical approaches for epidemic spreading on complex networks," Rep. Prog. Phys. 80, 036603 (2017).

[150] S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes, "Critical phenomena in complex networks," Rev. Mod. Phys. 80, 1275 (2008).

[151] D. Krioukov, F. Papadopoulos, M. Kitsak, A. Vahdat, and M. Boguná, "Hyperbolic geometry of complex networks," Phys. Rev. E 82, 036106 (2010).

[152] A. Allard, M. A. Serrano, and M. Bogu?á, "Geometric description of clustering in directed networks," arXiv:2302.09055 (2023).

[153] A.-L. Barabási and R. Albert, "Emergence of scaling in random networks," Science 289, 509 (1999).

[154] D. de Solla Price, "A general theory of bibliometric and other cumulative advantage processes," J. Am. Soc. Inf. Sci. 27, 292 (1976).

[155] C. Aicher, A. Z. Jacobs, and A. Clauset, "Learning latent block structure in weighted networks," J. Complex Netw. 3, 221 (2015).

[156] T. L. J. Ng and T. B. Murphy, "Weighted stochastic block model," Statistical Methods & Applications 30, 1365 (2021).

[157] U. Brandes, J. Lerner, U. Nagel, and B. Nick, "Structural trends in network ensembles," in Complex Networks: Results of the 2009 International Workshop on Complex Networks (CompleNet 2009) (2009) p. 83.

[158] M. Porfiri, D. J. Stilwell, and E. M. Bollt, "Synchronization in random weighted directed networks," IEEE Transactions on Circuits and Systems I 55, 3170 (2008).

[159] K. Rajan and L. F. Abbott, "Eigenvalue spectra of random matrices for neural networks," Phys. Rev. Lett. 97, 188104 (2006).

[160] J. Kadmon and H. Sompolinsky, "Transition to chaos in random neuronal networks," Phys. Rev. X 5, 041030 (2015).

[161] T. Tao and V. Vu, "Random matrices: the circular law," Communications in Contemporary Mathematics 10, 261 (2008).

[162] F. G?tze and A. Tikhomirov, "The circular law for random matrices," Ann. Probab. 38, 1444 (2010).

[163] K. P. Costello and V. Vu, "On the rank of random sparse matrices," Combinatorics, Probability and Computing 19, 321 (2010).

[164] P. M. Wood, "Universality and the circular law for sparse random matrices," Ann. Appl. Probab. 22, 1266 (2012).

[165] N. Cook, "The circular law for random regular digraphs with random edge weights," Random Matrices: Theory and Applications 6, 1750012 (2017).

[166] A. Allard, M. A. Serrano, G. García-Pérez, and M. Bogu?á, "The geometric nature of weights in real complex networks," Nat. Commun. 8, 14103 (2017).

[167] B. Karrer and M. E. J. Newman, "Stochastic blockmodels and community structure in networks," Phys. Rev. E 83, 016107 (2011).

[168] T. P. Peixoto, "Nonparametric weighted stochastic block models," Phys. Rev. E 97, 012306 (2018).

[169] A. Athreya, D. E. Fishkind, M. Tang, C. E. Priebe, Y. Park, J. T. Vogelstein, K. Levin, V. Lyzinski, Y. Qin, and D. L. Sussman, "Statistical inference on random dot product graphs: A survey," J. Mach. Learn. Res. 18, 1 (2018).

[170] D. Garlaschelli and M. I. Loffredo, "Generalized bose-fermi statistics and structural correlations in weighted networks," Phys. Rev. Lett. 102, 038701 (2009).

[171] D. Garlaschelli, "The weighted random graph model," New J. Phys. 11, 073005 (2009).

[172] M. A. Serrano and M. Bogu?á, "Weighted configuration model," in AIP conference proceedings, Vol. 776 (American Institute of Physics, 2005) p. 101.

[173] D. J. Watts and S. H. Strogatz, "Collective dynamics of 'small-world' networks," Nature 393, 440 (1998).

[174] D. Sherrington and S. Kirkpatrick, "Solvable model of a spin-glass," Phys. Rev. Lett. 35, 1792 (1975).

[175] P. Desrosiers and P. Forrester, "Asymptotic correlations for Gaussian and Wishart matrices with external source," Int. Math. Res. Not. 2006, 27395 (2006).

[176] A. Bloemendal and B. Virág, "Limits of spiked random matrices i," Probab. Theory Relat. Fields 156, 795 (2013).

[177] J. J. Hopfield, "Neural networks and physical systems with emergent collective computational abilities," Proc. Natl. Acad. Sci. U.S.A. 79, 2554 (1982).

[178] M. Luko?evi?ius and H. Jaeger, "Reservoir computing approaches to recurrent neural network training," Comput. Sci. Rev. 3, 127 (2009).

[179] D. Sussillo and L. F. Abbott, "Generating coherent patterns of activity from chaotic neural networks," Neuron 63, 544 (2009).

[180] F. Mastrogiuseppe and S. Ostojic, "Linking Connectivity, Dynamics, and Computations in Low-Rank Recurrent Neural Networks," Neuron 99, 609 (2018).

[181] F. Schuessler, A. Dubreuil, F. Mastrogiuseppe, S. Ostojic, and O. Barak, "Dynamics of random recurrent networks with correlated low-rank structure," Phys. Rev. Research 2, 013111 (2020).

[182] F. Schuessler, F. Mastrogiuseppe, A. Dubreuil, S. Ostojic, and O. Barak, "The interplay between randomness and structure during learning in RNNs," in Adv. Neural Inf. Process. Syst. 34 (2020) p. 1.

[183] G. Eilertsen, D. J?nsson, T. Ropinski, J. Unger, and A. Ynnerman, "Classifying the classifier: dissecting the weight space of neural networks," Proceedings of the European Conference on Artificial Intelligence (ECAI 2020) 325, 1119 (2020).

[184] E. T. Jaynes, "Information Theory and Statistical Mechanics," The Phys. Rev. 106, 620 (1957).

[185] J. Park and M. E. J. Newman, "Statistical mechanics of networks," Phys. Rev. E 70, 066117 (2004).

[186] G. Bianconi, "Entropy of network ensembles," Phys. Rev. E 79, 036114 (2009).

[187] T. Squartini and D. Garlaschelli, Maximum-Entropy Networks: Pattern Detection, Network Reconstruction and Graph Combinatorics (Springer, 2017).

[188] G. Cimini, T. Squartini, F. Saracco, D. Garlaschelli, A. Gabrielli, and G. Caldarelli, "The statistical physics of real-world networks," Nat. Rev. Phys. 1, 58 (2019).

[189] C. Carathéodory, "The beginning of research in the calculus of variations," Osiris 3, 224 (1937).

[190] G. Giorgi and T. H. Kjeldsen, eds., Traces and emergence of nonlinear programming (Birkhauser, New York, 2014).

[191] C. Carathéodory, Calculus of Variations and Partial Differential Equations of the first order, 3rd ed. (Chelsea Publishing Company, 1989).

[192] B. H. Pourciau, "Modern Multiplier Rules," Am. Math. Mon. 87, 433 (1980).

[193] E. K. P. Chong and S. H. Zak, An Introduction to Optimization, 4th ed. (Wiley, New Jersey, 2013).

[194] DLMF, "NIST Digital Library of Mathematical Functions," https://dlmf.nist.gov/, Release 1.1.9 of 2023-03-15, f. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller, B. V. Saunders, H. S. Cohl, and M. A. McClain, eds.

[195] J. Gao, Y. Cao, and J.-M. Lee, "Principal component analysis of 1/fα noise," Phys. Lett. A 314, 392–400 (2003).

[196] M. Sánchez-Islas, J. C. Toledo-Roy, and A. Frank, "Criticality in a multisignal system using principal component analysis," Phys. Rev. E 103, 042111 (2021).

[197] C. Stringer, M. Pachitariu, N. Steinmetz, M. Carandini, and K. D. Harris, "High-dimensional geometry of population responses in visual cortex," Nature 571, 361 (2019).

[198] C. Stringer, M. Pachitariu, N. Steinmetz, C. B. Reddy, M. Carandini, and K. D. Harris, "Spontaneous behaviors drive multidimensional, brainwide activity," Science 364, eaav7893 (2019).

[199] N. C. L. Kong, E. Margalit, J. L. Gardner, and A. M. Norcia, "Increasing neural network robustness improves match to macaque v1 eigenspectrum, spatial frequency preference and predictivity," PLoS Comput. Biol. 18, e1009739 (2022).

[200] J. M. Kleinberg, "Authoritative sources in a hyperlinked environment," in SODA '98: Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms (1998) p. 668.

[201] M. E. J. Newman, Networks (Oxford University Press, 2018).

[202] M. Kunst, E. Laurell, N. Mokayes, A. Kramer, F. Kubo, A. M. Fernandes, D. F?rster, M. Dal Maschio, and H. Baier, "A Cellular-Resolution Atlas of the Larval Zebrafish Brain," Neuron 103, 21 (2019).

[203] M. Mitchell, Complexity: A Guided Tour (Oxford University Press, 2009).

[204] D. Witvliet, B. Mulcahy, J. K. Mitchell, Y. Meirovitch, D. R. Berger, Y. Wu, Y. Liu, W. X. Koh, R. Parvathala, D. Holmyard, R. L. Schalek, N. Shavit, A. D. Chisholm, J. W. Lichtman, A. D. T. Samuel, and M. Zhen, "Connectomes across development reveal principles of brain maturation," Nature 596, 257 (2021).

[205] K. Fujimoto, "What are singular values of nonlinear operators?" in 43rd IEEE Conf. Decis. Control (2004) p. 1623.

[206] O. Koch and C. Lubich, "Dynamical low-rank approximation," SIAM J. Matrix Anal. Appl. 29, 434 (2007).

[207] P. Holme and J. Saram?ki, "Temporal networks," Phys. Rep. 519, 97 (2012).

[208] V. Thibeault, G. St-Onge, L. J. Dubé, and P. Desrosiers, "Threefold way to the dimension reduction of dynamics on networks: An application to synchronization," Phys. Rev. Research 2, 043215 (2020).

[209] V. Thibeault, Réduire la dimension des systèmes complexes : un regard sur l'émergence de la synchronisation, Master's thesis, Université Laval (2020).

[210] X. Wang and I. H. Sloan, "Why are high-dimensional finance problems often of low effective dimension?" SIAM J. Comput 27, 159 (2005).

[211] P. Espa?ol, "Statistical Mechanics of Coarse-graining," in Nov. Methods Soft Matter Simulations, Vol. 140, edited by M. Karttunen, I. Vattulainen, and A. Lukkarinen (Springer, Berlin, 2003) p. 69.

[212] P. Castiglione, M. Falcioni, A. Lesne, and A. Vulpiani, Chaos and Coarse Graining in Statistical Mechanics (Cambridge University Press, 2008).

[213] Y. S. Cho, T. Nishikawa, and A. E. Motter, "Stable chimeras and independently synchronizable clusters," Phys. Rev. Lett. 119, 084101 (2017).

[214] L. D. Smith and G. A. Gottwald, "Model reduction for the collective dynamics of globally coupled oscillators: From finite networks to the thermodynamic limit," Chaos 30, 093107 (2020).

[215] J. Wei and J. C. W. Kuo, "A lumping analysis in monomolecular reaction systems: Analysis of the exactly lumpable system," Ind. Eng. Chem. Fundamen. 8, 114 (1969).

[216] J. Tóth, G. Li, H. Rabitz, and A. S. Tomlin, "The effect of lumping and expanding on kinetic differential equations," SIAM J. Appl. Math. 57, 1531 (1997).

[217] I. Z. Kiss, J. C. Miller, and P. L. Simon, Mathematics of epidemics on networks: From exact to approximate models (Springer, Cham, 2017).

[218] B. B. Machta, R. Chachra, M. K. Transtrum, and J. P. Sethna, "Parameter Space Compression Underlies Emergent Theories and Predictive Models," Science 342, 604 (2013).

[219] T. Hoefler, D. Alistarh, T. Ben-Nun, N. Dryden, and A. Peste, "Sparsity in Deep Learning : Pruning and growth for efficient inference and training in neural networks," J. Mach. Learn. Res. 23, 1 (2021).

[220] F. Forni and R. Sepulchre, "Differential Dissipativity Theory for Dominance Analysis," IEEE Trans. Autom. Control 64, 2340 (2019).

[221] M. Faccin, M. T. Schaub, and J. C. Delvenne, "State Aggregations in Markov Chains and Block Models of Networks," Phys. Rev. Lett. 127, 078301 (2021).</...