Stochastic approximation techniques, continuum scaling limits of high dimensional networks, and bias of network sampling algorithms

The last few years have seen an explosion in the development and use of network models in a host of real world applications. Canonical examples include the understanding of bias of network sampling algorithms in measuring and promoting individuals in a network with multiple types, and the use of objects such as the single linkage clustering tree (i.e. the Minimal spanning tree(MST)) in understanding unsupervised learning problems.
 
Dynamic network models arise naturally either in studying the evolution of real world networks or for inherent algorithmic pipelines to analyze data (e.g. Kruskal's algorithm for constructing the MST). In this talk, we will describe the use of stochastic approximation techniques to understand two major themes in dynamic networks, where stochastic approximation techniques play a key role:
 
a) We will described ideas building up to understanding the following conjecture from the early 2000s from statistical physics: for network models where edges are given iid random edge weights, the minimal spanning tree with edges properly rescaled should converge in the limit to compact random fractals. Further if the degree exponent of the model \tau > 4, then graph distances in the MST scale like n^{1/3} while for \tau \in (3,4) graph distances scale like n^{(\tau-3)/(\tau-1)}. 
 
b) We will describe ideas for studying the bias of network centrality algorithms in measuring popularity of individuals in a canonical model in social networks with vertices of different attribute types (e.g. minorities and majorities),  in particular showing that while the degree exponent can depend on the attribute type, more global measures such as the Page-rank do not depend on the attribute type. A surprising by-product of this analysis is the efficacy of Page-rank driven sampling in settings of rare minorities.