Graph-Theoretic Analysis of Complex Stochastic Networks

• Activity Number: 463
• Type: Invited
• Date/Time: Wednesday, August 7, 2013 : 8:30 AM to 10:20 AM
• Sponsor: Section on Statistical Graphics
• Author(s): David H. Collins*+ and Aparna V. Huzurbazar
• Companies: Los Alamos National Laboratory and Statistical Sciences Group, Los Alamos National Laboratory
• Keywords: Graph theory ; Stochastic networks ; Flowgraphs ; Markov process ; Semi-Markov process

Abstract

We describe the use of graphs to represent Markovian and semi-Markovian stochastic networks, and how the interplay of visual and algebraic properties of the graphs aids in the determination of quantities such as first passage times. We also show how Markovian stochastic processes are special cases of generalized flowgraphs, with other special cases ranging from transportation networks to representations of finite automata. This leads to the formulation of general algorithms for graph reduction that can be expressed in terms of either visual or matrix-algebraic properties of the graph.