Perhaps this review http://journals.aps.org/rmp/abstract/10.1103/RevModPhys.80.1275 could be one of possible starting points.   Also  see this paper  https://www.researchgate.net/publication/1902212_Dynamical_replica_analysis_of_processes_on_finitely_connected_random_graphs_I_Vertex_covering for more references to studies of stochastic processes on graphs. 

Article Dynamical replica analysis of processes on finitely connecte...

Dear Colleague Sudev,

Although it's not my domain, I believe that there is a connection between graph theory and probability. I agree with colleague Stoica that could  be useful  to you the book

Geoffrey Grimmett, Probability on Graphs (Random Processes on Graphs and Lattices), Cambridge University Press, 4th printing 2013.

I hope that helps, Mirjana

Well I am on application plane, I guess some proofs by Paul Erdos are remarkable .

https://en.wikipedia.org/wiki/Random_graph

https://en.wikipedia.org/wiki/Stochastic_block_model

http://mathworld.wolfram.com/RandomGraph.html

http://mathworld.wolfram.com/PercolationTheory.html

Dear Sudev, the earlier persons on this page have already presented some relevant references, so that in the following I restrict myself to some complementary issues.

Graph theory pervades mathematics, pure and applied, and physics. There is virtually nowhere where graph theory is not encountered. For instance, it plays a significant role in the theory of sparse matrices; some of the best algorithms (for instance the Nested-Dissection Algorithm by George, and George and Liu) cannot have been devised without reliance on the methods of graph theory. One of the earliest comprehensive texts on graph theory is by Frank Harary (Graph Theory, Addison-Wesley, 1969), which I highly recommend. Harary has also edited a book with the title Graph Theory and Theoretical Physics (Academic Press, 1967), which is not widely known, however is extremely useful. It contains contributions by a number of luminaries, including one by Pieter Kasteleyn, the person who solved the dimer problem on a two-dimensional planar lattice in terms of Pfaffians. I note in passing that Pfaffians are also encountered in a specific formulation of the Wick theorem for fermions, the latter theorem directly relating to Feynman graphs / diagrams in the many-body perturbation expansions for systems of fermions (see below).

Earliest physical applications of graph theory have been in the area of statistical physics. The linked-cluster expansion, and the associated high-temperature expansion, which is dealt with in graduate texts on statistical mechanics, has direct root in graph theory. The standard text in this area is Vol. 3 of the series Phase Transitions and Critical Phenomena, edited by C. Domb and M.S. Green (Academic Press, 1974).  The first Chapter of this volume, by C. Domb, is on Graph Theory. The third chapter, by Michael Wortis, deals with Linked Cluster Expansion. Etc. In recent years, in particular Rajiv R.P. Singh (UC Davis) and his collaborators have extensively used high-temperature expansion to study correlated fermion and boson systems.

Graph theory plays also a prominent role in the study of Feynman diagrams. The standard text in this area is the one by N. Nakanishi (Graph Theory and Feynman Integrals, Gordon & Breach, 1971).

A field where graph theory plays a significant role, is network theory. The field is replete with stochastic models. A good book in this area, which you may wish to consult, is the one edited by Pastor-Satorras et al., with the title Statistical Mechanics of Complex Networks (Springer, 2003).

Regarding stochastic processes, one very important area concerns the stochastic processes associated with Monte Carlo sampling methods, where the Metropolis algorithm is combined with construction of one or several (depending on the problem) Markov processes. A Markov process is best described in terms of graphs. But aside from this, in recent years the quantum Monte Carlo technique has also been used for evaluating the weak-coupling perturbation series expansion of the partition function, as well as of those of various correlation functions (for example, the one-particle Green function and the associated self-energy). The diagrammatic Monte Carlo technique (to which amongst others N.V. Prokof'ev and S. Svistunov have made significant contributions) involves two Markov processes whereby relevant Feynman diagrams of various order are stochastically sampled and evaluated. For a relatively brief review of this approach, I refer you to the article by Van Houcke et al., with the title Diagrammatic Monte Carlo, the link to which I attach below.

http://www.sciencedirect.com/science/article/pii/S1875389210006498

Dear @Sudev, I am attaching link to a Ph.D thesis Stochastic processes on graphs with cycles: geometric and variational approaches by Martin Wainwright.

The influence of this scientific work is especially treated in the areas like Network information theory, Analysis of iterative decoding, Application to large deviations analysis...

http://ssg.mit.edu/ssg_theses/ssg_theses_2000_2009/Wainwright_PhD_1_02.PDF

This is also very interesting resource: Graph theory and stochastic processes! 

The next reference is fine example of application : Interest communities and flow roles in directed networks: the Twitter network of the UK riots!

http://rsif.royalsocietypublishing.org/keyword/graph-theory-and-stochastic-processes

http://rsif.royalsocietypublishing.org/content/11/101/20140940

A point of view : every element of a graph dynamical systems can be made by mathematicians  / analysis / processes in so called " STOCHASTIC " models in serving 

Hi,

Graphs can be used for motion planning for automated vehicles. Motion planning is done considering various uncertainties in the possible responses of the subject vehicle and surrounding vehicles. Hence,I see the possible application of graph theory in stochastic process of motion planning. I have cited few interesting documents in this direction.

Bry, Adam, and Nicholas Roy. "Rapidly-exploring random belief trees for motion planning under uncertainty." Robotics and Automation (ICRA), 2011 IEEE International Conference on. IEEE, 2011.

Katrakazas, Christos, et al. "Real-time motion planning methods for autonomous on-road driving: State-of-the-art and future research directions."Transportation Research Part C: Emerging Technologies 60 (2015): 416-442.

@Sudev: You can also have a look on the attached paper. This explain in details how can we apply graphs (in this case rooted trees) to Stochastic Differential equations (SPDEs in this case !)