Decision Sciences Seminar
Wednesday September 04, 2013
11:00AM - 12:30PM
Shankar Bhamidi UNC, Department of Statistics and Operations Research
Some statistical problems in models for complex networks
The last few years have seen an explosion in the amount of data on many real world networks. This has resulted in an interdisciplinary eff ort in formulating models to understand the data. We explore various theoretical questions arising from such data, including: 1. Reconstruction of routing trees (Network Tomography): In a number of problems that arise from trying to discover the underlying structure of the Internet, it is often impossible to take direct measurements at the routers. We shall describe progress in trying to reconstruct the "Multicast" tree exactly using only "end-to-end" measurements. We show that this can be done using very few samples. 2. MCMC simulation of exponential random graphs: Exponential random graphs are one of the most used models in social network theory. The basic intuition is as follows: In social networks we see more triangles cliques etc than we would expect in a random graph, since if A is a friend of B and A is a friend of C then it is quite likely that B and C are friends. One way to model such a phenomenon is to attach, for every graph G,a Hamiltonian given by say H(G) = β#E(G) + γ#T(G) where E(G) and T(G) are the number of edges and triangles respectively and then looking at the Gibbs distribution induced by this Hamiltonian. Simulating from these models is of paramount interest. 3. Modeling retweet networks and Non-local preferential attachment: A wide array of real world networks exhibit a "superstar" phenomenon, including twitter event networks, where one vertex contains a finite fraction of the edges of the network. We describe a variant of preferential attachment which seems to perform much better on empirical data than the standard model. We will describe mathematical techniques from continuous time branching processes required to analyze this model.