An efficiency measure for dynamic networks modeled as evolutionary variational inequalities with application to the Internet and vulnerability analysis
Tóm tắt
In this paper, we propose an efficiency/performance measure for dynamic networks, which have been modeled as evolutionary variational inequalities. Such applications include the Internet. The measure, which captures demands, flows, and costs/latencies over time, allows for the identification of the importance of the nodes and links and their rankings. We provide both continuous time and discrete time versions of the efficiency measure. We illustrate the efficiency measure for the time-dependent (demand-varying) Braess paradox and demonstrate how it can be used to assess the most vulnerable nodes and links in terms of the greatest impact of their removal on the efficiency/performance of the dynamic network over time.
Tài liệu tham khảo
Barbagallo, A. (2007). Regularity results for time-dependent variational inequalities and quasi-variational inequalities and application to the calculation of dynamic traffic network. Mathematical Models and Methods in Applied Sciences, 17, 277–304.
Beckmann, M. J. (1967). On the theory of traffic flows in networks. Traffic Quarterly, 21, 109–116.
Beckmann, M. J., McGuire, C. B., & Winsten, C. B. (1956). Studies in the economics of transportation. New Haven: Yale University Press.
Bertsekas, D. P., & Gallager, R. G. (1992). Data networks (2nd ed.) Englewood Cliffs: Prentice-Hall.
Bertsekas, D. P., & Tsitsiklis, J. N. (1989). Parallel and distributed computation: Numerical methods. Englewood Cliffs: Prentice-Hall.
Bienenstock, E. J., & Bonacich, P. (2003). Balancing efficiency and vulnerability in social networks. In Dynamic social network modeling and analysis: Workshop summary and papers (pp. 253–264). Washington, DC: The National Academy of Sciences.
Boyce, D. E., Mahmassani, H. S., & Nagurney, A. (2005). A retrospective of Beckmann, McGuire, and Winsten’s. Studies in the Economics of Transportation, Papers in Regional Science, 84, 85–103.
Braess, D. (1968). Uber ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung, 12, 258–268.
Braess, D., Nagurney, A., & Wakolbinger, T. (2005). On a paradox of traffic planning, translation of the 1968 article by Braess. Transportation Science, 39, 446–450.
Cantor, D. G., & Gerla, M. (1974). Optimal routing in a packet-switched computer network. IEEE Transactions on Computers, 23, 1062–1069.
Cojocaru, M.-G., Daniele, P., & Nagurney, A. (2005). Projected dynamical systems and evolutionary variational inequalities. Journal of Optimization Theory and Applications, 27, 1–15.
Cojocaru, M.-G., Daniele, P., & Nagurney, A. (2006). Double-layered dynamics: A unified theory of projected dynamical systems and evolutionary variational inequalities. European Journal of Operational Research, 175, 494–507.
Dafermos, S. (1980). Traffic equilibrium and variational inequalities. Transportation Science, 14, 42–54.
Daganzo, C. F. (1977). On the traffic assignment problem with flow dependent costs-I. Transportation Research, 11, 433–437.
Daganzo, C. F. (1977). On the traffic assignment problem with flow dependent costs-II. Transportation Research, 11, 439–441.
Dafermos, S. C., & Sparrow, F. T. (1969). The traffic assignment problem for a general network. Journal of Research of the National Bureau of Standards, 73B, 91–118.
Daniele, P. (2003). Evolutionary variational inequalities and economic models for demand supply markets. Mathematical Models and Methods in Applied Sciences, 4, 471–489.
Daniele, P. (2004). Time-dependent spatial price equilibrium problem: Existence and stability results for the quantity formulation model. Journal of Global Optimization, 28, 283–295.
Daniele, P. (2006). Dynamic networks and evolutionary variational inequalities. Cheltenham: Edward Elgar Publishing.
Daniele, P., Maugeri, A., & Oettli, W. (1999). Time-dependent variational inequalities. Journal of Optimization Theory and its Applications, 103, 543–555.
Gallager, R. G. (1977). A minimum delay routing algorithm using distributed computation. IEEE Transaction on Communications, 25, 73–85.
Jenelius, E., Petersen, T., & Mattsson, L.-G. (2006). Road network vulnerability: Identifying important links and exposed regions. Transportation Research A, 40, 537–560.
Kinderlehrer, D., & Stampacchia, G. (1980). An introduction to variational inequalities and their applications. New York: Academic Press.
Korilis, Y. A., Lazar, A. A., & Orda, A. (1999). Avoiding the Braess paradox in non-cooperative networks. Journal of Applied Probability, 36, 211–222.
Latora, V., & Marchiori, M. (2001). Efficient behavior of small-world networks. Physical Review Letters, 87, (Article No. 198701).
Latora, V., & Marchiori, M. (2003). Economic small-world behavior in weighted networks. The European Physical Journal B, 32, 249–263.
Latora, V., & Marchiori, M. (2004). How the science of complex networks can help developing strategies against terrorism. Chaos, Solitons and Fractals, 20, 69–75.
Nagurney, A. (1993). Network economics: A variational inequality approach. Dordrecht: Kluwer Academic Publishers.
Nagurney, A. (2006). Supply chain network economics: Dynamics of prices, flows, and profits. Cheltenham: Edward Elgar Publishing.
Nagurney, A., & Dong, J. (2002). Supernetworks: Decision-making for the information age. Cheltenham: Edward Elgar Publishing.
Nagurney, A., Liu, Z., Cojocaru, M.-G., & Daniele, P. (2007). Static and dynamic transportation network equilibrium reformulations of electric power supply chain networks with known demands. Transportation Research E, 43, 624–646.
Nagurney, A., Parkes, D., & Daniele, P. (2007). The internet, evolutionary variational inequalities, and the time-dependent Braess paradox. Computational Management Science, 4, 355–375.
Nagurney, A., & Qiang, Q. (2007). A transportation network efficiency measure that captures flows, behavior, and costs with applications to network component importance identification and vulnerability. In Proceedings of the 18th annual POMS conference, Dallas, Texas. May 2007
Nagurney, A., & Qiang, Q. (2007). A network efficiency measure for congested networks. Europhysics Letters, 79, 38005, p1–p5.
Nagurney, A., & Siokos, S. (1997). Financial networks: Statics and dynamics. Heidelberg: Springer.
Pas, E. I., & Principio, S. L. (1997). Braess paradox: Some new insights. Transportation Research B, 31, 265–276.
Patriksson, M. (1994). The traffic assignment problem. Utrecht: VSP.
Qiang, Q., & Nagurney, A. (2008). A unified network performance measure with importance identification and the ranking of network components. Optimization Letters, 2, 127–142.
Ran, B., & Boyce, D. E. (1996). Modeling dynamic transportation networks. Berlin: Springer.
Resende, M. G. C., & Pardalos, P. M., (Eds.) (2006). Handbook of optimization in telecommunications. New York: Springer Science and Business Media.
Roughgarden, T. (2005). Selfish routing and the price of anarchy. Cambridge: MIT Press.
Smith, M. (1979). Existence, uniqueness, and stability of traffic equilibria. Transportation Research B, 13, 259–304.
Wardrop, J. G. (1952). Some theoretical aspects of road traffic research. In Proceedings of the institute of civil engineers, Part II (p. 325–378).