2025年大学《数理基础科学》专业题库-大学数理基础科学的复杂网络分析

2025年大学《数理基础科学》专业题库——大学数理基础科学的复杂网络分析考试时间：______分钟总分：______分姓名：______一、1.定义无向图G=(V,E)中的度序列。若一个无标度网络的度分布服从幂律分布P(K)∝K^-γ，请解释γ的含义及其对网络特性的影响。2.描述并解释Watts-Strogatz小世界模型的基本思想及其关键参数。说明该模型如何生成具有小世界特性的网络。3.给出无向连通图中网络直径D和平均路径长度L的定义。证明对于任意n个节点的无向连通图，必有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]]```请计算该图每个节点的度。假设节点代表城市，边代表直接的高速公路连接。请使用Dijkstra算法找出从节点1到节点5的最短路径，并给出该路径及其总长度。说明Dijkstra算法的基本思想。5.定义网络节点度中心性、介数中心性和紧密度中心性。请简述这三种中心性度量分别反映了节点在网络中的哪种重要性或影响力。6.解释网络社群检测的“模块度”Q的概念。给定一个网络划分S={S1,S2,...,Sk}，请写出模块度Q的计算公式，并说明Q的取值范围及其含义。三、7.解释随机网络模型G(n,p)的生成过程。对于包含n个节点的随机网络，若连接概率p固定，当n趋于无穷大时，请分析平均路径长度L(p)和聚类系数C(p)的渐近行为。8.什么是网络的特征向量中心性（EigenvectorCentrality）？请解释其计算原理，并说明该指标与节点度中心性有何不同。它如何衡量一个节点及其邻居节点的重要性？9.描述图论中“最小生成树”的概念及其应用场景。给出Prim算法和Kruskal算法的基本思想。解释为什么在生成树中，任意加入一条不属于生成树的边，必然形成唯一的环。四、10.考虑一个有向无环图（DAG）G=(V,E)，其中V={1,2,3,4}，E={(1,2),(1,3),(2,4),(3,4)}。请给出该DAG的邻接矩阵表示。对于节点1，请列出所有从它出发可以到达的节点，并给出所有到达节点4的路径。11.什么是网络嵌入？请简述将图结构数据映射到低维向量空间的基本动机。介绍两种不同的网络降维方法（例如，主成分分析PCA或多维尺度分析MDS），并简述其原理。12.请解释图神经网络（GNN）的基本工作原理。说明GNN如何通过消息传递机制聚合邻居节点的信息来更新中心节点的表示。比较GNN与传统神经网络在处理图结构数据方面的主要区别。五、13.设想你需要分析一个学术合作网络，节点代表研究人员，边代表共同发表过论文。请设计一个基于复杂网络分析的方法论，用于识别该网络中的核心研究群体（社群）以及最重要的研究人员（中心节点）。说明你将选择哪些网络指标和算法，并简述分析步骤。14.什么是复杂网络的“小世界”特性？“无标度”网络又具有什么显著特征？请分别解释这两种特性，并各举一个可能出现的实际网络例子。15.试述复杂网络分析在生物信息学（如蛋白质相互作用网络）中的一个具体应用。说明通过网络分析可以获得哪些生物学insights，以及分析过程中可能遇到的主要挑战。试卷答案一、1.节点v的度是其连接边数。度序列是网络所有节点的度组成的序列{d1,d2,...,dn}。γ值表示网络的“重尾”程度：γ<2表示网络中存在大量高连接度节点（枢纽），网络具有较强的鲁棒性但也可能存在传播风险；γ=2表示无标度网络，新节点倾向于连接到现有度数最高的节点，网络效率高；γ>2表示网络更像随机网络，节点度分布较为均匀。2.Watts-Strogatz模型通过引入少量随机重连（re-wiring）来打破规则网络（如环状网络）的高聚类系数，同时保持较短的平均路径长度。关键参数是重连概率p：p=0时为规则网络，p接近1时接近随机网络。随着p增大，网络直径先减小后趋于稳定，平均路径长度持续减小，聚类系数显著下降，最终呈现小世界特性。3.证明：设G的节点为V={v1,v2,...,vn}，任意取两个节点vi,vj∈V(i≠j)。在图G中，vi和vj之间存在至少一条路径P。P的长度至少为1（即至少有一条边）。考虑在P上任意插入一个中间节点vk∈V\{vi,vj}，得到新的路径P'=vi,vk,vj。P'的长度比P长1。因此，G中任意两节点间的最短路径长度（即直径D）总是大于或等于P的长度，而P的长度≤L+1(因为P只包含一条边)。所以D≥L。二、4.度计算：节点1度=1+1=2；节点2度=1+1+1=3；节点3度=1+1=2；节点4度=1+1+1=3；节点5度=1+1=2。Dijkstra算法思想：从起点出发，维护到起点的最短路径估计值，初始除起点外均为无穷大。每次从未访问节点中选估计值最小的节点更新其估计值和父节点，直到所有节点访问完毕。最短路径：1-2-4-5，长度=3。过程简述：起点1，访问1，更新邻居2(路径1),4(路径1)。未访问中最小估计值1(节点2)，访问2，更新邻居3(路径2+1=3),4(路径1+1=2)。未访问中最小估计值2(节点4)，访问4，更新邻居5(路径2+1=3)。节点5已访问。算法结束，路径为1->2->4->5。5.度中心性：节点拥有的连接边数，反映节点连接的广度。介数中心性：节点出现在网络中其他节点对之间最短路径上的频率，反映节点对信息流动的controlling能力。紧密度中心性：节点与网络中所有其他节点的平均距离的倒数，反映节点在网络中的“接近”程度。6.模块度Q是衡量网络社群划分质量的标准指标。公式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的节点数，|S|是网络总节点数。Q的取值范围通常在[-1,1]或[0,1](归一化后)。Q越接近最大值（通常为1或ln|S|），表示社群内部连接越紧密（密内疏外），划分质量越高。三、7.G(n,p)生成：首先创建包含n个节点的空图。然后对于图中每对不同的节点vi,vj(i<j)，以概率p添加一条连接边(vi,vj)。重复此过程n(n-1)/2次（所有可能的两点对）。平均路径长度L(p)随n增大而增大，但在p较小时（p<1/n）近似为ln(n)/p。聚类系数C(p)在p较小时接近0，当p增大到一定程度（p>1/n）时，C(p)快速上升并趋于饱和，接近p。8.特征向量中心性衡量节点的重要性，不仅考虑其直接连接的节点数，还考虑其邻居节点的重要性。计算原理：迭代更新节点v的特征向量得分x(v)：x'(v)=Σ_{u∈N(v)}x(u)，其中N(v)是v的邻居集合。初始值可设为均值为1的向量。迭代直至收敛。得分x(v)与x(u)正相关，即重要节点的邻居通常也重要。与度中心性不同，它区分了不同重要性邻居的贡献（通过特征向量特征值体现）。9.最小生成树是连接图中所有节点、边权重总和最小的生成子图。应用：网络设计（如连接多个城市的通信网络、公路网）、最小代价覆盖问题等。Prim算法思想：从一个起点开始，每次从未访问的邻接节点中选择最小边权连接到已访问集合，不断扩展，直至所有节点加入。Kruskal算法思想：将所有边按权重排序，按顺序加入边，若加入某边不形成环，则保留并加入该边，直至形成包含所有节点的树。加入边不形成环的保证依赖于边的排序和并查集数据结构（或按秩合并）。四、10.邻接矩阵（以0表示无边，1表示有边，方向从行到列）：```[[0,1,1,0],[0,0,0,1],[0,0,0,1],[0,0,0,0]]```从节点1出发的可达节点：通过边(1,2)可达2，通过边(1,3)可达3。因此可达节点为{2,3}。到达节点4的路径：1->2->4；1->3->4。11.网络嵌入是将图结构数据映射到低维向量空间表示的过程，使得图的结构信息能在向量空间中得到保留或近似。动机：便于使用传统机器学习算法处理；降低计算复杂度；可视化网络结构；捕捉节点间的相似性。方法一：多维尺度分析（MDS）-非监督降维，通过保持距离或相似性度量在低维空间中的近似来嵌入节点。方法二：主成分分析（PCA）-适用于节点特征矩阵（如度向量、中心性向量），通过线性变换找到最能解释数据方差的方向（主成分）作为低维表示。12.GNN原理：模仿大脑神经元传递信息的方式。每个节点维护一个状态（初始为特征向量或零向量）。通过“消息传递”步骤：节点聚合其邻居的状态信息（通常使用函数如求和、最大池化等），并可能结合自己的状态，生成自己的新状态。这个过程在图上迭代多层，信息逐渐传播。与传统神经网络区别：GNN的参数通常只在节点或边级别共享（对于整个图共享），并且其计算依赖于图的拓扑结构（邻居关系），能够直接处理非欧几里得的数据（图）。五、13.分析方法设计：1.数据预处理：构建合作网络邻接矩阵。2.计算网络指标：计算度中心性、介数中心性、紧密度中心性、聚类系数等，初步识别度数高、连接紧密、控制关键路径的节点。3.社群检测：应用社群检测算法（如Louvain方法、标签传播），将研究人员划分为不同的合作群体。4.结果解释：分析每个社群的特征（如平均合作强度、研究领域），识别核心研究群体。5.中心节点识别：根据中心性指标排序，识别最重要的研究人员。6.可视化与验证：绘制网络图，可视化社群结构和中心节点，与领域知识对比验证结果。14.小世界特性：指许多真实世界网络同时具有高聚类系数（节点及其邻居之间连接紧密）和短平均路径长度（网络中任意两节点间平均只需通过少数中间节点即可连接）的特性。无标度特性：指网络节点的度分布服从幂律分布P(K)∝K^-γ，即少数节点拥有非常多的连接（度数极高），而绝大多数节点度数较低。实际例子：小世