构建了军事信息栅格(military information grid,MIG)级联失效模型,深入分析MIG级联失效特性,并在此基础上提出了鲁棒性建设策略。基于相互依存网络理论分析模型,将MIG划分为通信基础网和信息服务网,改进了节点介数计算方法,突出了服务...构建了军事信息栅格(military information grid,MIG)级联失效模型,深入分析MIG级联失效特性,并在此基础上提出了鲁棒性建设策略。基于相互依存网络理论分析模型,将MIG划分为通信基础网和信息服务网,改进了节点介数计算方法,突出了服务关系对通信流量的影响,并定义了节点失效判定准则,研究了失效节点通信负荷和信息服务负荷重分配规律及因此造成的失效传播原理。通过引入成本惩罚函数和砥柱节点的概念,构建数学模型,研究并提出了兼顾投入成本和抗毁效益的建设策略。仿真实验结果表明,少量砥柱节点能力的加强,即可有效提高全栅格体系的抗级联失效特性。展开更多
Edge closeness and betweenness centralities are widely used path-based metrics for characterizing the importance of edges in networks.In general graphs,edge closeness centrality indicates the importance of edges by th...Edge closeness and betweenness centralities are widely used path-based metrics for characterizing the importance of edges in networks.In general graphs,edge closeness centrality indicates the importance of edges by the shortest distances from the edge to all the other vertices.Edge betweenness centrality ranks which edges are significant based on the fraction of all-pairs shortest paths that pass through the edge.Nowadays,extensive research efforts go into centrality computation over general graphs that omit time dimension.However,numerous real-world networks are modeled as temporal graphs,where the nodes are related to each other at different time instances.The temporal property is important and should not be neglected because it guides the flow of information in the network.This state of affairs motivates the paper’s study of edge centrality computation methods on temporal graphs.We introduce the concepts of the label,and label dominance relation,and then propose multi-thread parallel labeling-based methods on OpenMP to efficiently compute edge closeness and betweenness centralities w.r.t.three types of optimal temporal paths.For edge closeness centrality computation,a time segmentation strategy and two observations are presented to aggregate some related temporal edges for uniform processing.For edge betweenness centrality computation,to improve efficiency,temporal edge dependency formulas,a labeling-based forward-backward scanning strategy,and a compression-based optimization method are further proposed to iteratively accumulate centrality values.Extensive experiments using 13 real temporal graphs are conducted to provide detailed insights into the efficiency and effectiveness of the proposed methods.Compared with state-ofthe-art methods,labeling-based methods are capable of up to two orders of magnitude speedup.展开更多
文摘构建了军事信息栅格(military information grid,MIG)级联失效模型,深入分析MIG级联失效特性,并在此基础上提出了鲁棒性建设策略。基于相互依存网络理论分析模型,将MIG划分为通信基础网和信息服务网,改进了节点介数计算方法,突出了服务关系对通信流量的影响,并定义了节点失效判定准则,研究了失效节点通信负荷和信息服务负荷重分配规律及因此造成的失效传播原理。通过引入成本惩罚函数和砥柱节点的概念,构建数学模型,研究并提出了兼顾投入成本和抗毁效益的建设策略。仿真实验结果表明,少量砥柱节点能力的加强,即可有效提高全栅格体系的抗级联失效特性。
基金supported by the National Natural Science Foundation of China(Grant Nos.62302451 and 62276233)the Natural Science Foundation of Zhejiang Province of China(No.LQ22F020018)the Key Research Project of Zhejiang Province of China(No.2023C01048).
文摘Edge closeness and betweenness centralities are widely used path-based metrics for characterizing the importance of edges in networks.In general graphs,edge closeness centrality indicates the importance of edges by the shortest distances from the edge to all the other vertices.Edge betweenness centrality ranks which edges are significant based on the fraction of all-pairs shortest paths that pass through the edge.Nowadays,extensive research efforts go into centrality computation over general graphs that omit time dimension.However,numerous real-world networks are modeled as temporal graphs,where the nodes are related to each other at different time instances.The temporal property is important and should not be neglected because it guides the flow of information in the network.This state of affairs motivates the paper’s study of edge centrality computation methods on temporal graphs.We introduce the concepts of the label,and label dominance relation,and then propose multi-thread parallel labeling-based methods on OpenMP to efficiently compute edge closeness and betweenness centralities w.r.t.three types of optimal temporal paths.For edge closeness centrality computation,a time segmentation strategy and two observations are presented to aggregate some related temporal edges for uniform processing.For edge betweenness centrality computation,to improve efficiency,temporal edge dependency formulas,a labeling-based forward-backward scanning strategy,and a compression-based optimization method are further proposed to iteratively accumulate centrality values.Extensive experiments using 13 real temporal graphs are conducted to provide detailed insights into the efficiency and effectiveness of the proposed methods.Compared with state-ofthe-art methods,labeling-based methods are capable of up to two orders of magnitude speedup.
