2025年大學《數(shù)理基礎(chǔ)科學》專業(yè)題庫——大學數(shù)理基礎(chǔ)科學的復雜網(wǎng)絡(luò)分析考試時間：______分鐘總分：______分姓名：______一、1.定義無向圖G=(V,E)中的度序列。若一個無標度網(wǎng)絡(luò)的度分布服從冪律分布P(K)∝K^-γ，請解釋γ的含義及其對網(wǎng)絡(luò)特性的影響。2.描述并解釋Watts-Strogatz小世界模型的基本思想及其關(guān)鍵參數(shù)。說明該模型如何生成具有小世界特性的網(wǎng)絡(luò)。3.給出無向連通圖中網(wǎng)絡(luò)直徑D和平均路徑長度L的定義。證明對于任意n個節(jié)點的無向連通圖，必有D≥L。二、4.已知一個無向圖G的鄰接矩陣A如下：```A=[[0,1,0,1,0],[1,0,1,1,0],[0,1,0,0,1],[1,1,0,0,1],[0,0,1,1,0]]```請計算該圖每個節(jié)點的度。假設(shè)節(jié)點代表城市，邊代表直接的高速公路連接。請使用Dijkstra算法找出從節(jié)點1到節(jié)點5的最短路徑，并給出該路徑及其總長度。說明Dijkstra算法的基本思想。5.定義網(wǎng)絡(luò)節(jié)點度中心性、介數(shù)中心性和緊密度中心性。請簡述這三種中心性度量分別反映了節(jié)點在網(wǎng)絡(luò)中的哪種重要性或影響力。6.解釋網(wǎng)絡(luò)社群檢測的“模塊度”Q的概念。給定一個網(wǎng)絡(luò)劃分S={S1,S2,...,Sk}，請寫出模塊度Q的計算公式，并說明Q的取值范圍及其含義。三、7.解釋隨機網(wǎng)絡(luò)模型G(n,p)的生成過程。對于包含n個節(jié)點的隨機網(wǎng)絡(luò)，若連接概率p固定，當n趨于無窮大時，請分析平均路徑長度L(p)和聚類系數(shù)C(p)的漸近行為。8.什么是網(wǎng)絡(luò)的特征向量中心性（EigenvectorCentrality）？請解釋其計算原理，并說明該指標與節(jié)點度中心性有何不同。它如何衡量一個節(jié)點及其鄰居節(jié)點的重要性？9.描述圖論中“最小生成樹”的概念及其應用場景。給出Prim算法和Kruskal算法的基本思想。解釋為什么在生成樹中，任意加入一條不屬于生成樹的邊，必然形成唯一的環(huán)。四、10.考慮一個有向無環(huán)圖（DAG）G=(V,E)，其中V={1,2,3,4}，E={(1,2),(1,3),(2,4),(3,4)}。請給出該DAG的鄰接矩陣表示。對于節(jié)點1，請列出所有從它出發(fā)可以到達的節(jié)點，并給出所有到達節(jié)點4的路徑。11.什么是網(wǎng)絡(luò)嵌入？請簡述將圖結(jié)構(gòu)數(shù)據(jù)映射到低維向量空間的基本動機。介紹兩種不同的網(wǎng)絡(luò)降維方法（例如，主成分分析PCA或多維尺度分析MDS），并簡述其原理。12.請解釋圖神經(jīng)網(wǎng)絡(luò)（GNN）的基本工作原理。說明GNN如何通過消息傳遞機制聚合鄰居節(jié)點的信息來更新中心節(jié)點的表示。比較GNN與傳統(tǒng)神經(jīng)網(wǎng)絡(luò)在處理圖結(jié)構(gòu)數(shù)據(jù)方面的主要區(qū)別。五、13.設(shè)想你需要分析一個學術(shù)合作網(wǎng)絡(luò)，節(jié)點代表研究人員，邊代表共同發(fā)表過論文。請設(shè)計一個基于復雜網(wǎng)絡(luò)分析的方法論，用于識別該網(wǎng)絡(luò)中的核心研究群體（社群）以及最重要的研究人員（中心節(jié)點）。說明你將選擇哪些網(wǎng)絡(luò)指標和算法，并簡述分析步驟。14.什么是復雜網(wǎng)絡(luò)的“小世界”特性？“無標度”網(wǎng)絡(luò)又具有什么顯著特征？請分別解釋這兩種特性，并各舉一個可能出現(xiàn)的實際網(wǎng)絡(luò)例子。15.試述復雜網(wǎng)絡(luò)分析在生物信息學（如蛋白質(zhì)相互作用網(wǎng)絡(luò)）中的一個具體應用。說明通過網(wǎng)絡(luò)分析可以獲得哪些生物學insights，以及分析過程中可能遇到的主要挑戰(zhàn)。試卷答案一、1.節(jié)點v的度是其連接邊數(shù)。度序列是網(wǎng)絡(luò)所有節(jié)點的度組成的序列{d1,d2,...,dn}。γ值表示網(wǎng)絡(luò)的“重尾”程度：γ<2表示網(wǎng)絡(luò)中存在大量高連接度節(jié)點（樞紐），網(wǎng)絡(luò)具有較強的魯棒性但也可能存在傳播風險；γ=2表示無標度網(wǎng)絡(luò)，新節(jié)點傾向于連接到現(xiàn)有度數(shù)最高的節(jié)點，網(wǎng)絡(luò)效率高；γ>2表示網(wǎng)絡(luò)更像隨機網(wǎng)絡(luò)，節(jié)點度分布較為均勻。2.Watts-Strogatz模型通過引入少量隨機重連（re-wiring）來打破規(guī)則網(wǎng)絡(luò)（如環(huán)狀網(wǎng)絡(luò)）的高聚類系數(shù)，同時保持較短的平均路徑長度。關(guān)鍵參數(shù)是重連概率p：p=0時為規(guī)則網(wǎng)絡(luò)，p接近1時接近隨機網(wǎng)絡(luò)。隨著p增大，網(wǎng)絡(luò)直徑先減小后趨于穩(wěn)定，平均路徑長度持續(xù)減小，聚類系數(shù)顯著下降，最終呈現(xiàn)小世界特性。3.證明：設(shè)G的節(jié)點為V={v1,v2,...,vn}，任意取兩個節(jié)點vi,vj∈V(i≠j)。在圖G中，vi和vj之間存在至少一條路徑P。P的長度至少為1（即至少有一條邊）。考慮在P上任意插入一個中間節(jié)點vk∈V\{vi,vj}，得到新的路徑P'=vi,vk,vj。P'的長度比P長1。因此，G中任意兩節(jié)點間的最短路徑長度（即直徑D）總是大于或等于P的長度，而P的長度≤L+1(因為P只包含一條邊)。所以D≥L。二、4.度計算：節(jié)點1度=1+1=2；節(jié)點2度=1+1+1=3；節(jié)點3度=1+1=2；節(jié)點4度=1+1+1=3；節(jié)點5度=1+1=2。Dijkstra算法思想：從起點出發(fā)，維護到起點的最短路徑估計值，初始除起點外均為無窮大。每次從未訪問節(jié)點中選估計值最小的節(jié)點更新其估計值和父節(jié)點，直到所有節(jié)點訪問完畢。最短路徑：1-2-4-5，長度=3。過程簡述：起點1，訪問1，更新鄰居2(路徑1),4(路徑1)。未訪問中最小估計值1(節(jié)點2)，訪問2，更新鄰居3(路徑2+1=3),4(路徑1+1=2)。未訪問中最小估計值2(節(jié)點4)，訪問4，更新鄰居5(路徑2+1=3)。節(jié)點5已訪問。算法結(jié)束，路徑為1->2->4->5。5.度中心性：節(jié)點擁有的連接邊數(shù)，反映節(jié)點連接的廣度。介數(shù)中心性：節(jié)點出現(xiàn)在網(wǎng)絡(luò)中其他節(jié)點對之間最短路徑上的頻率，反映節(jié)點對信息流動的controlling能力。緊密度中心性：節(jié)點與網(wǎng)絡(luò)中所有其他節(jié)點的平均距離的倒數(shù)，反映節(jié)點在網(wǎng)絡(luò)中的“接近”程度。6.模塊度Q是衡量網(wǎng)絡(luò)社群劃分質(zhì)量的標準指標。公式Q=Σ_{i=1..k}[(|Si|*(|Si|-1)/2)/(|S|*(|S|-1)/2)]-(Σ_{j=1..k}|Sj|*(|Sj|-1)/2)/(|S|*(|S|-1)/2)，其中S是劃分，Si是第i個社群，|Si|是社群Si的節(jié)點數(shù)，|S|是網(wǎng)絡(luò)總節(jié)點數(shù)。Q的取值范圍通常在[-1,1]或[0,1](歸一化后)。Q越接近最大值（通常為1或ln|S|），表示社群內(nèi)部連接越緊密（密內(nèi)疏外），劃分質(zhì)量越高。三、7.G(n,p)生成：首先創(chuàng)建包含n個節(jié)點的空圖。然后對于圖中每對不同的節(jié)點vi,vj(i<j)，以概率p添加一條連接邊(vi,vj)。重復此過程n(n-1)/2次（所有可能的兩點對）。平均路徑長度L(p)隨n增大而增大，但在p較小時（p<1/n）近似為ln(n)/p。聚類系數(shù)C(p)在p較小時接近0，當p增大到一定程度（p>1/n）時，C(p)快速上升并趨于飽和，接近p。8.特征向量中心性衡量節(jié)點的重要性，不僅考慮其直接連接的節(jié)點數(shù)，還考慮其鄰居節(jié)點的重要性。計算原理：迭代更新節(jié)點v的特征向量得分x(v)：x'(v)=Σ_{u∈N(v)}x(u)，其中N(v)是v的鄰居集合。初始值可設(shè)為均值為1的向量。迭代直至收斂。得分x(v)與x(u)正相關(guān)，即重要節(jié)點的鄰居通常也重要。與度中心性不同，它區(qū)分了不同重要性鄰居的貢獻（通過特征向量特征值體現(xiàn)）。9.最小生成樹是連接圖中所有節(jié)點、邊權(quán)重總和最小的生成子圖。應用：網(wǎng)絡(luò)設(shè)計（如連接多個城市的通信網(wǎng)絡(luò)、公路網(wǎng)）、最小代價覆蓋問題等。Prim算法思想：從一個起點開始，每次從未訪問的鄰接節(jié)點中選擇最小邊權(quán)連接到已訪問集合，不斷擴展，直至所有節(jié)點加入。Kruskal算法思想：將所有邊按權(quán)重排序，按順序加入邊，若加入某邊不形成環(huán)，則保留并加入該邊，直至形成包含所有節(jié)點的樹。加入邊不形成環(huán)的保證依賴于邊的排序和并查集數(shù)據(jù)結(jié)構(gòu)（或按秩合并）。四、10.鄰接矩陣（以0表示無邊，1表示有邊，方向從行到列）：```[[0,1,1,0],[0,0,0,1],[0,0,0,1],[0,0,0,0]]```從節(jié)點1出發(fā)的可達節(jié)點：通過邊(1,2)可達2，通過邊(1,3)可達3。因此可達節(jié)點為{2,3}。到達節(jié)點4的路徑：1->2->4；1->3->4。11.網(wǎng)絡(luò)嵌入是將圖結(jié)構(gòu)數(shù)據(jù)映射到低維向量空間表示的過程，使得圖的結(jié)構(gòu)信息能在向量空間中得到保留或近似。動機：便于使用傳統(tǒng)機器學習算法處理；降低計算復雜度；可視化網(wǎng)絡(luò)結(jié)構(gòu)；捕捉節(jié)點間的相似性。方法一：多維尺度分析（MDS）-非監(jiān)督降維，通過保持距離或相似性度量在低維空間中的近似來嵌入節(jié)點。方法二：主成分分析（PCA）-適用于節(jié)點特征矩陣（如度向量、中心性向量），通過線性變換找到最能解釋數(shù)據(jù)方差的方向（主成分）作為低維表示。12.GNN原理：模仿大腦神經(jīng)元傳遞信息的方式。每個節(jié)點維護一個狀態(tài)（初始為特征向量或零向量）。通過“消息傳遞”步驟：節(jié)點聚合其鄰居的狀態(tài)信息（通常使用函數(shù)如求和、最大池化等），并可能結(jié)合自己的狀態(tài)，生成自己的新狀態(tài)。這個過程在圖上迭代多層，信息逐漸傳播。與傳統(tǒng)神經(jīng)網(wǎng)絡(luò)區(qū)別：GNN的參數(shù)通常只在節(jié)點或邊級別共享（對于整個圖共享），并且其計算依賴于圖的拓撲結(jié)構(gòu)（鄰居關(guān)系），能夠直接處理非歐幾里得的數(shù)據(jù)（圖）。五、13.分析方法設(shè)計：1.數(shù)據(jù)預處理：構(gòu)建合作網(wǎng)絡(luò)鄰接矩陣。2.計算網(wǎng)絡(luò)指標：計算度中心性、介數(shù)中心性、緊密度中心性、聚類系數(shù)等，初步識別度數(shù)高、連接緊密、控制關(guān)鍵路徑的節(jié)點。3.社群檢測：應用社群檢測算法（如Louvain方法、標簽傳播），將研究人員劃分為不同的合作群體。4.結(jié)果解釋：分析每個社群的特征（如平均合作強度、研究領(lǐng)域），識別核心研究群體。5.中心節(jié)點識別：根據(jù)中心性指標排序，識別最重要的研究人員。6.可視化與驗證：繪制網(wǎng)絡(luò)圖，可視化社群結(jié)構(gòu)和中心節(jié)點，與領(lǐng)域知識對比驗證結(jié)果。14.小世界特性：指許多真實世界網(wǎng)絡(luò)同時具有高聚類系數(shù)（節(jié)點及其鄰居之間連接緊密）和短平均路徑長度（網(wǎng)絡(luò)中任意兩節(jié)點間平均只需通過少數(shù)中間節(jié)點即可連接）的特性。無標度特性：指網(wǎng)絡(luò)節(jié)點的度分布服從冪律分布P(K)∝K^-γ，即少數(shù)節(jié)點擁有非常多的連接（度數(shù)極高），而絕大多數(shù)節(jié)點度數(shù)較低。實際例子：小世