论文部分内容阅读
介度中心（betweenness centrality ，BC）是衡量网络节点重要程度的一个广泛使用的指标，最快的介度中心算法需要计算 n次单源最短路径，时间复杂度是 O（V × E）．介度中心算法的瓶颈就在于计算量太大，导致运行时间太长，无法在实际中应用，因此需要从近似算法的角度降低介度中心算法的计算量．目前介度中心近似算法在计算自然图时对计算量的降低并不显著．为了进一步降低介度中心算法的计算量，提出了一种基于顶点加权的介度中心近似算法，该算法采用顶点加权的方式将多次重复计算过程累加到一次计算