×

Applying path-counting methods for measuring the robustness of the network-structured system. (English) Zbl 1171.90346

Summary: We consider the path-counting problem that asks how many paths exist between any two different nodes in a network after deleting an arbitrary number of edges or nodes from the original network. Using path-counting methods, we propose a quantitative method for measuring the robustness of the network-structured system. First we define the connectivity function and attempt to obtain the expected connectivity function for the network. Applying the Monte Carlo method, we estimate expected edge deletion and node deletion connectivity functions when an arbitrary number of edges or nodes are deleted from the original network. We attempt to approximate the expected edge deletion connectivity function using an appropriate nonlinear function with two parameters. We also show the numerical results of applying the path-counting method with their analysis in order to quantitatively evaluate the connectivity for some special types of networks.

MSC:

90B10 Deterministic network models in operations research
90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ashida, Operations Research and Its Applications, Lecture Notes in Operations Research 6, 6th International Symposium on Operations Research and Its Applications (ISORA 06), Xinjiang, China pp 22– (2006)
[2] Ball, Computing network reliability, Operations Research 27 pp 823– (1979) · Zbl 0412.90030
[3] Ball, Finding the most vital arcs in a network, Operations Research Letters 8 pp 73– (1989) · Zbl 0679.90086
[4] Bell, A game theoretic approach to measuring the performance reliability of transportation networks, Transportation Research Part B: Methodological 34 pp 533– (2000)
[5] Bell, Transportation Network Analysis (1997) · doi:10.1002/9781118903032
[6] Morohosi, Monte Carlo and Quasi-Monte Carlo Methods 2002 pp 357– (2004) · doi:10.1007/978-3-642-18743-8_22
[7] Oyama, Weight of shortest path analyses for the optimal location problem, Journal of the Operations Research Society of Japan 43 (1) pp 176– (2000) · Zbl 1138.90418
[8] Oyama, Quantitative method for evaluating stable connectedness of the network-structured system, Operations Research and Its Applications, Proceedings of the Fourth International Symposium, ISORA 4 (1) pp 54– (2002)
[9] Oyama, Operational Research and its Applications: Recent Trends, Proceedings of the APORS 2003, New Delhi, India pp 375– (2003)
[10] Oyama, Applying the shortest path counting problem to evaluate the importance of city road segments and the connectedness of the network-structured system, International Transactions in Operational Research 11 pp 555– (2004) · Zbl 1131.90457
[11] Oyama, T. , Taguchi, A. , 1992. Shortest path counting problem and evaluating the congestion of road segments. PAT News, The Institute of Statistical Research, No. 1, pp. 13-19 (in Japanese).
[12] Oyama, Perspectives of Advanced Technology Society 3: Urban Life and Traffic pp 3– (1996)
[13] Scott, Network robustness index, Journal of Transport Geography 14 pp 215– (2006)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.