2025年大學《數(shù)學與應用數(shù)學》專業(yè)題庫——復雜網(wǎng)絡結構及其動力學行為考試時間：______分鐘總分：______分姓名：______一、填空題（每空3分，共30分）1.連通無向圖G中，任意兩個節(jié)點之間存在一條路徑，則稱G為______圖。無向圖中，若存在經(jīng)過每個節(jié)點恰好一次的路徑，則稱該路徑為______。2.設網(wǎng)絡G有n個節(jié)點，m條邊，其鄰接矩陣為A，則矩陣A中第i行（列）元素之和等于節(jié)點i的______。若節(jié)點i和節(jié)點j之間存在邊，則鄰接矩陣A中a_ij通常取值為______。3.網(wǎng)絡度分布函數(shù)P(k)描述了網(wǎng)絡中______值為k的節(jié)點的比例。無標度網(wǎng)絡（scale-freenetwork）的度分布通常服從______分布。4.網(wǎng)絡的聚類系數(shù)C表征了網(wǎng)絡的______程度，數(shù)值越接近1，表示節(jié)點與其鄰居之間連接越緊密。小世界網(wǎng)絡的一個重要特征是具有較小的______和較大的______。5.在SIR模型中，節(jié)點狀態(tài)S表示______，I表示______，R表示______。該模型的傳播過程通常用______方程組來描述。6.圖論中，求網(wǎng)絡中節(jié)點u和節(jié)點v之間最短路徑長度的問題，通?？梢杂胈_____算法或______算法來解決。二、選擇題（每題3分，共15分）1.下列哪一項不是無標度網(wǎng)絡的典型特征？(A)度分布遵循冪律分布P(k)~k^-γ(B)平均路徑長度隨節(jié)點數(shù)n線性增長(C)聚類系數(shù)較大(D)網(wǎng)絡中存在少量度值極高的Hub節(jié)點2.對于一個包含n個節(jié)點的完全圖K_n，其平均路徑長度d(A)等于：(A)1(B)n-1(C)n(n-1)/2(D)n/23.介數(shù)中心性（BetweennessCentrality）較高的節(jié)點通常意味著：(A)該節(jié)點連接的邊數(shù)最多(B)該節(jié)點在網(wǎng)絡中容易受到攻擊(C)該節(jié)點是網(wǎng)絡中信息傳播或資源流動的關鍵路徑上的樞紐(D)該節(jié)點的鄰居節(jié)點數(shù)最多4.在隨機網(wǎng)絡模型G(n,p)中，隨著節(jié)點數(shù)n趨于無窮大，當連接概率p保持不變時，若p<<n^-1，則該網(wǎng)絡更傾向于表現(xiàn)為：(A)小世界網(wǎng)絡(B)無標度網(wǎng)絡(C)完全圖(D)獨立圖5.以下哪種模型通常用于模擬意見的緩慢變化或信念的融合過程？(A)SIR傳染病模型(B)閾值模型（ThresholdModel）(C)網(wǎng)絡覆蓋模型（NetworkCovering）(D)優(yōu)先連接模型（PreferentialAttachment）三、簡答題（每題5分，共20分）1.簡述小世界網(wǎng)絡模型（WS模型）的基本思想及其與隨機網(wǎng)絡（ER模型）的主要區(qū)別。2.解釋網(wǎng)絡直徑和網(wǎng)絡平均路徑長度這兩個指標的含義，并說明它們在衡量網(wǎng)絡連通性方面的不同側重。3.請列舉三種常用的網(wǎng)絡中心性指標，并簡要說明其中任意一種指標的計算意義。4.簡述社區(qū)結構的概念及其在網(wǎng)絡分析中的重要性。四、計算題（每題10分，共30分）1.給定一個包含4個節(jié)點和5條邊的無向網(wǎng)絡G，其鄰接矩陣為：A=|0110||1011||1100||0100|（1）計算節(jié)點2和節(jié)點4之間的最短路徑長度（假設存在路徑）。（2）計算該網(wǎng)絡的平均路徑長度（假設網(wǎng)絡是連通的）。2.假設一個簡單隨機網(wǎng)絡G(n,p)包含n=100個節(jié)點，連接概率p=0.03。試計算該網(wǎng)絡中平均每個節(jié)點的度值k?。如果該網(wǎng)絡是連通的，根據(jù)np>=1的規(guī)則，p值大約需要多大？（不考慮重邊和自環(huán)）3.考慮一個包含5個節(jié)點的閾值模型網(wǎng)絡，每個節(jié)點的初始閾值θ均勻分布在[0,1]區(qū)間內。假設有一個初始狀態(tài)為“激活”的種子節(jié)點（設其閾值為0），激活閾值為0.2。試描述該模型的一次典型更新過程，并解釋在此參數(shù)設置下，激活狀態(tài)可能如何擴散。五、綜合應用題（15分）假設你正在研究一個信息傳播網(wǎng)絡，網(wǎng)絡中的節(jié)點代表個體，邊代表個體間的直接溝通渠道。你收集到了該網(wǎng)絡的結構數(shù)據(jù)，并觀察到其度分布大致符合P(k)~k^-2.5的冪律分布。請基于你所學的復雜網(wǎng)絡知識：1.分析該網(wǎng)絡的拓撲特性（至少指出兩個關鍵特性）。2.提出至少兩種可能的動力學模型（例如傳播模型）來模擬信息在該網(wǎng)絡中的傳播過程，并簡要說明選擇這些模型的原因。3.在選擇模型或分析傳播過程時，需要考慮哪些網(wǎng)絡結構特征或參數(shù)？試卷答案一、填空題1.連通，歐拉2.度，13.度值，冪律4.局部聚集，平均路徑長度，聚類系數(shù)5.易感者，感染者，移除者，常微分6.Dijkstra，F(xiàn)loyd-Warshall二、選擇題1.B2.B3.C4.D5.B三、簡答題1.解析思路：WS模型在小世界模型中引入了重連（re-wiring）概率p?；舅枷胧牵簭囊粋€初始的規(guī)則網(wǎng)絡（如環(huán)狀圖）開始，隨機選擇一部分邊并將其刪除，然后在隨機選擇的兩節(jié)點之間建立一條新的邊。WS模型允許節(jié)點保持部分初始鄰居關系（通過1-p的概率保留），同時引入了短程連接的可能性（通過p的概率重連）。與ER隨機網(wǎng)絡模型相比，WS模型通常具有更小的平均路徑長度和更大的聚類系數(shù)，體現(xiàn)了“六度分隔”現(xiàn)象，但保留了部分社區(qū)結構。2.解析思路：網(wǎng)絡直徑是指網(wǎng)絡中任意兩個節(jié)點之間可能存在的最長路徑的長度。它衡量的是網(wǎng)絡中節(jié)點間通信的最壞情況下的距離，反映了網(wǎng)絡的“最大”連通范圍。網(wǎng)絡平均路徑長度是指網(wǎng)絡中所有節(jié)點對之間最短路徑長度的平均值。它衡量的是網(wǎng)絡中節(jié)點間的“平均”距離，反映了信息或信號在網(wǎng)絡中傳播的平均速度。兩者都用于衡量網(wǎng)絡的連通性，但直徑關注極端情況，而平均路徑長度關注整體情況。3.解析思路：常用的網(wǎng)絡中心性指標包括：度中心性（DegreeCentrality）、介數(shù)中心性（BetweennessCentrality）、緊密度中心性（ClosenessCentrality）、特征向量中心性（EigenvectorCentrality）。選擇其中一種，如度中心性，其計算意義在于衡量一個節(jié)點的連接數(shù)多少。度值高的節(jié)點通常被認為是網(wǎng)絡中“更重要”或“更中心”的節(jié)點，因為它們直接連接到更多的其他節(jié)點，在信息傳播、資源流動等方面可能扮演關鍵角色。4.解析思路：社區(qū)結構（CommunityStructure）是指網(wǎng)絡中節(jié)點傾向于聚集形成緊密子群（社區(qū)）的現(xiàn)象，社區(qū)內節(jié)點間的連接比社區(qū)間節(jié)點間的連接更為密集。其重要性在于：①反映了網(wǎng)絡中隱藏的分組或層次結構，有助于理解網(wǎng)絡的形成機制和組織原則；②社區(qū)結構可以簡化網(wǎng)絡表示，降低復雜度，有助于分析網(wǎng)絡功能和動態(tài)行為；③識別社區(qū)有助于發(fā)現(xiàn)網(wǎng)絡中的關鍵節(jié)點或模塊。四、計算題1.解析思路：（1）利用鄰接矩陣，從節(jié)點2出發(fā)，查看其可達節(jié)點（矩陣第2行非零元素對應的節(jié)點：1,3,4）。從節(jié)點4出發(fā)，查看其可達節(jié)點（矩陣第4行非零元素對應的節(jié)點：2）。因此，節(jié)點2和節(jié)點4之間存在路徑2-4，長度為1。如果需要更復雜的路徑，則繼續(xù)擴展搜索。（2）計算平均路徑長度需要考慮所有節(jié)點對的最短路徑長度，并求平均值。對于小網(wǎng)絡，可以枚舉所有節(jié)點對，利用Floyd-Warshall或Dijkstra算法計算它們的最短路徑長度，然后求和再除以n*(n-1)/2。根據(jù)鄰接矩陣，節(jié)點間的最短路徑長度如下：d(1,2)=1,d(1,3)=1,d(1,4)=2,d(2,3)=1,d(2,4)=1,d(3,4)=2。平均路徑長度d(A)=(1+1+2+1+1+2)/6=8/6=4/3。2.解析思路：（1）在隨機網(wǎng)絡G(n,p)中，每個節(jié)點有p的概率與n-1個其他節(jié)點相連，因此平均度k?=np=100*0.03=3。（2）根據(jù)小世界網(wǎng)絡的連通性規(guī)則之一np>=1，需要p*100>=1，即p>=1/100=0.01。因此，p值至少需要為0.01才能保證網(wǎng)絡大概率是連通的。3.解析思路：初始狀態(tài)：節(jié)點1（種子節(jié)點）狀態(tài)為“I”（激活），閾值θ1=0；其他節(jié)點S（易感），閾值θj~[0,1]。更新過程：在每一步，檢查所有S節(jié)點。對于節(jié)點j，計算其鄰居中“I”狀態(tài)節(jié)點的“激活投票”總和（例如，投票值為1）。如果該總和>=節(jié)點j的閾值θj，則節(jié)點j狀態(tài)變?yōu)椤癐”。在此例中，只有節(jié)點1是“I”狀態(tài)，其閾值為0。因此，它會為所有鄰居S節(jié)點提供1的投票。由于θj>=0，任何S節(jié)點j都會接收到>=1的投票，從而其狀態(tài)將變?yōu)椤癐”。因此，所有節(jié)點最終都會被激活。這個模型在這種參數(shù)設置下表現(xiàn)出快速的全局激活。五、綜合應用題1.解析思路：根據(jù)度分布P(k)~k^-2.5，可以判斷該網(wǎng)絡是無標度網(wǎng)絡（scale-freenetwork），因為其度分布指數(shù)γ=2.5，屬于冪律分布（γ>=3）。拓撲特性分析：①無標度性：網(wǎng)絡中存在少量度值極高的Hub節(jié)點，這些節(jié)點連接數(shù)遠超平均，是信息傳播的關鍵。②小世界性（通常冪律分布的網(wǎng)絡也表現(xiàn)出小世界性，除非連接概率p非常?。浩骄窂介L度相對較短，節(jié)點之間可以通過較短的路徑相互連接，即使網(wǎng)絡規(guī)模很大。2.解析思路：模型選擇：①SIR模型：適合模擬具有長期恢復期或免疫期的信息傳播，如謠言、科學知識等。選擇原因：可以區(qū)分信息接收者（易感者S）、已接收并傳播者（感染者I）、已接收不再傳播者（移除者R）。②閾值模型：適合模擬基于社會影響或群體互動的信息采納過程，特別是當信息采納需要達到一定局部共識時。選擇原因：閾值模型允許節(jié)點根據(jù)鄰居狀態(tài)和自身閾值決定是否采納信息，能反映社會網(wǎng)絡中的影響結構。根據(jù)網(wǎng)絡無標度特性，SIR模型中的Hub節(jié)點可能成為快速傳播源頭，閾值模型中高閾值節(jié)點或處于高聚類系數(shù)社區(qū)中心的節(jié)點可能成為關鍵采納者。3.解析思路：在選擇模型或分析傳播時需要考慮：①網(wǎng)絡結構參數(shù)：平均路徑長度、聚類系數(shù)、度分