Research On Computation Of Resistance Distance Of Networks And Its Applications

Network science is a new interdisciplinary subject,and is a branch of computer science,which plays more and more important role in modern science.Topological structures and metric properties of networks are important research contents in network science.In order to study topological structures and metric properties of networks,many different metric indices are proposed.The research on metric indices of networks has important significance for net-work security and network optimization.The resistance distance is a new type of metric index for networks,which has extensive applications in centrality of networks,randomized algo-rithm,connectivity and robustness of networks.Compared with traditional metric indices,the advantage of the resistance distance is that it can reflect global properties of networks.How to compute resistance distance is the key problem in the research on resistance distance,which attracts extensive attentions.In this dissertation,we investigate formulas for the resistance dis-tance and related indices,and use these formulas to study centrality,community and structure analysis of networks.The main work of this dissertation is summarized as follows.1.We give new formulas and block algorithm for the resistance distances of networks via principal submatrix and Schur complement of the Laplacian matrix,and use these new formulas to obtain expressions for resistance distances of some composite networks.The advantage of our formula is that the computation can be reduced order,and is very effective for the research on resistance distance of composite networks.We also use the theory of resistance distance to study line star sets,bipartiteness,isomorphism problems and strongly regularity of networks.2.The Kirchhoff index and degree Kirchhoff index are robustness indices of networks based on resistance distance.We give generalized inverse formulas for the Kirchhoff index and degree Kirchhoff index of networks,and use these formulas to obtain block algorithm for the Kirchhoff index and expressions for Kirchhoff indices of some composite networks.Some known formulas for the Kirchhoff index follow from our results immediately.3.The resistance centrality is a new centrality measure of networks based on resistance distance.We give the formula and algorithm for the resistance centrality of networks,obtain arrangement method for the importance of vertices based on resistance centrality,and discuss the advantage of resistance centrality via a real social network.4.We pose new algorithm for discovering communities of networks,and use it to obtain processor allocation scheme of computer programs in parallel computing.The advantage of our algorithm is that we can partition the network into multiple communities without knowing the size of the network,which overcomes the shortcomings of existing algorithms.5.In 2011,A.Leon-Garcia posed a network optimization problem about the resistance distance and Kirchhoff index.We solve this problem for star network and ring network.