The network diameter is an important characteristic parameter of a complex network. Calculation for a large-scale complex network’s diameter has been an important subject in the study of complex networks. If the netw...The network diameter is an important characteristic parameter of a complex network. Calculation for a large-scale complex network’s diameter has been an important subject in the study of complex networks. If the network diameter is calculated directly, the problem mainly exists in efficiency for searching and counting the shortest paths. If the network diameter is calculated indirectly by studying the statistical function about the relationship between the network diameter and parameters affecting the diameter, the problems not only exist in the efficiency of statistic, but also exist in the function which may be not applicable to all kinds of networks. An algorithm for the complex network diameter based on the k order distance matrix is proposed with a matrix multiplication approach, and a mathematical proof for the algorithm correctness is given as well. Furthermore, some relevant propositions and deductions for reducing the complexity of this algorithm are put forward. With a good theoretical basis and a simple calculation process, this algorithm can be used to calculate the diameter of a large-scale complex network with small-world effect more accurately and efficiently. Two cases about the advanced research projects agency(ARPA) network model and the Chinese airline network model are adopted to verify the effect of this algorithm.展开更多
Based on Petersen graph, a new interconnection network, the RP(k) network, is devel-oped and the properties of the RP(k) network are investigated. The diameter of the RP(k) network is [ k/2] + 2 and its degree is 5. W...Based on Petersen graph, a new interconnection network, the RP(k) network, is devel-oped and the properties of the RP(k) network are investigated. The diameter of the RP(k) network is [ k/2] + 2 and its degree is 5. We prove that the diameter of the RP(k) network is much smaller than that of the 2-D Torus network when the number of nodes in interconnection networks is less than or equal to 300. In order to analyze the communication performance in a group of nodes, we propose the concepts of the optimal node groups and the diameter of the optimal node groups. We also show that the diameter of the optimal node groups in the RP(k) network is less than that in the 2-D Torus net-work. Especially when the number of nodes in an optimal node group is between 6 and 100, the diam-eter of the optimal node groups in the RP(k) network is half of that in the 2-D Torus network. Further-more based on the RP(k) network we design a set of routing algorithms which are point-to-point rout-ing, permutation routing, one-to-all routing and all-to-all routing. Their communication efficiencies are [ k/2] +2, k + 5, [k/2] + 2, and k + 5 respectively. The RP(k) network and the routing algorithms can provide efficient communication means for parallel and distributed computer system.展开更多
基金supported by the National Natural Science Foundation of China(61273210)
文摘The network diameter is an important characteristic parameter of a complex network. Calculation for a large-scale complex network’s diameter has been an important subject in the study of complex networks. If the network diameter is calculated directly, the problem mainly exists in efficiency for searching and counting the shortest paths. If the network diameter is calculated indirectly by studying the statistical function about the relationship between the network diameter and parameters affecting the diameter, the problems not only exist in the efficiency of statistic, but also exist in the function which may be not applicable to all kinds of networks. An algorithm for the complex network diameter based on the k order distance matrix is proposed with a matrix multiplication approach, and a mathematical proof for the algorithm correctness is given as well. Furthermore, some relevant propositions and deductions for reducing the complexity of this algorithm are put forward. With a good theoretical basis and a simple calculation process, this algorithm can be used to calculate the diameter of a large-scale complex network with small-world effect more accurately and efficiently. Two cases about the advanced research projects agency(ARPA) network model and the Chinese airline network model are adopted to verify the effect of this algorithm.
基金This work was supported by the National Natural Science Foundation of China (Grant No. 69933020) National High Performance Computing Fund.
文摘Based on Petersen graph, a new interconnection network, the RP(k) network, is devel-oped and the properties of the RP(k) network are investigated. The diameter of the RP(k) network is [ k/2] + 2 and its degree is 5. We prove that the diameter of the RP(k) network is much smaller than that of the 2-D Torus network when the number of nodes in interconnection networks is less than or equal to 300. In order to analyze the communication performance in a group of nodes, we propose the concepts of the optimal node groups and the diameter of the optimal node groups. We also show that the diameter of the optimal node groups in the RP(k) network is less than that in the 2-D Torus net-work. Especially when the number of nodes in an optimal node group is between 6 and 100, the diam-eter of the optimal node groups in the RP(k) network is half of that in the 2-D Torus network. Further-more based on the RP(k) network we design a set of routing algorithms which are point-to-point rout-ing, permutation routing, one-to-all routing and all-to-all routing. Their communication efficiencies are [ k/2] +2, k + 5, [k/2] + 2, and k + 5 respectively. The RP(k) network and the routing algorithms can provide efficient communication means for parallel and distributed computer system.
