  Weighted graphs are commonly used to model various complex systems, including
social networks, power grids, transportation networks, and biological systems.
In many applications, the connectivity of these networks can be expressed
through the Mean First Passage Times (MFPTs) of a Markov chain modeling a
random walker on the graph. In this paper, we generalize the network metrics
based on Markov chains' MFPTs and extend them to networks affected by
uncertainty, in which edges may fail and hence not be present according to a
pre-determined stochastic model. To find optimally connected graphs, we present
a parameterization-free method for optimizing the MFPTs of the underlying
Markov chain. More specifically, we show how to extend the Simultaneous
Perturbation Stochastic Approximation (SPSA) algorithm in the context of Markov
chain optimization. The proposed algorithm is suitable for both fixed and
random networks. Using various numerical experiments, we demonstrate
scalability compared to established benchmarks. Importantly, our algorithm
finds an optimal solution without requiring prior knowledge of edge failure
probabilities, allowing for an online optimization approach.
