A novel use of stochastic approximation algorithms for estimating degree of each node in social networks

A duplication-deletion random graph is presented in this paper to model social networks which change over time. The paper analyzes the dynamics of this duplication-deletion random graph where at each time instant, one node can either join or leave the network. A degree distribution analysis is provided for this graph and an expression is derived to compute the power law component. Also a Markov-modulated random graph is analyzed where the the growth of the network evolves according to a slow Markov chain. An upper bound is derived for the mean square error between the estimated degree distribution and the asymptotic one. Using the fact that the duplication-deletion graph satisfies a power law, an upper bound is presented for the most significant singular value of the adjacency matrix of the graph.