节点的中介度(Betweenness Centrality)是度量节点在复杂网络中重要程度的一种重要指标;计算节点中介度在社交网络分析、交通网络治理、网络安全管理等广泛应用中起着关键性作用。传统节点中介度计算方法大多数仅关注小规模和静态图,然而在实际应用中网络规模巨大且具有动态特征,因此如何在这样的网络上计算中介度受到了研究界的关注。本文研究动态图中介度和Top-k节点中介度的计算方法,包含针对动态图的节点中介度增量计算方法、针对静态图的Top-k节点近似中介度计算方法,以及针对动态图Top-k节点近似中介度计算方法。论文主要研究的内容如下:(1)动态图中节点中介度计算的增量式算法。为精确计算动态图中各节点中介度,基于经典的针对静态图的Brandes算法,提出了一种增量式算法。该算法利用增量式单源最短路径计算技术,维护中间结果,快速计算发生改变的中介度。在Email-Eu-core、Facebook和bitcoin-alpha等数据集上的实验结果验证了所提出算法的高效性;相比其他算法,所提出算法速度提升10倍左右;在不同稀疏度和不同规模的图上,所提出算法的速度比传统静态算法快2倍以上。(2)静态图中Top-k节点近似中介度获取算法。为计算静态网络中Top-k节点近似中介度,本文采用抽样自适应技术,提出了一种近似中介度计算方法。该算法将原有的单向计算枢轴的过程分为双向前后轴同时计算,减少抽样过程某些节点被高估的情况,通过保证极少部分的节点近似中介度的准确性,快速获得以近似中介度排序前Top-k节点。在 CollegeMsg、p2p-Gnutella05/06、Soc-sign-bitcoinapla 和 Wiki-Vote 五个数据集上的实验结果表明,在保证前Top-k节点近似中介度的情况下,所提出算法和其他算法相比,运算速度平均提高2.4倍以上,排序几何平均值提高数10倍以上。(3)动态图中Top-k节点近似中介度获取算法。为计算动态网络中Top-k节点近似中介度,本文采用抽样自适应技术,提出了一种在动态网络上维护Top-k节点近似中介度的算法。该算法通过维护抽样结果、实时更新前后枢轴数量和排序近似中介度,动态更新 Top-k 节点。在 CollegeMsg、p2p-Gnutella05/06、Soc-sign-bitcoinapla 和 Wiki-Vote五个数据集中实验结果表明,所提出相比其他算法运算速度平均提高10倍以上。