  This paper considers a Markov-modulated duplication-deletion random graph
where at each time instant, one node can either join or leave the network; the
probabilities of joining or leaving evolve according to the realization of a
finite state Markov chain. The paper comprises of 2 results. First, motivated
by social network applications, we analyze the asymptotic behavior of the
degree distribution of the Markov-modulated random graph. Using the asymptotic
degree distribution, an expression is obtained for the delay in searching such
graphs. Second, a stochastic approximation algorithm is presented to track
empirical degree distribution as it evolves over time. The tracking performance
of the algorithm is analyzed in terms of mean square error and a functional
central limit theorem is presented for the asymptotic tracking error.
