  We prove almost sure convergence of the maximum degree in an evolving graph
model combining a growing number of local choices with sublinear preferential
attachment. At each step in the growth of the graph, a new vertex is
introduced. Then we draw a random number of edges from it to existing vertices,
chosen independently by the following rule. For each edge, we consider a sample
of the growing size of vertices chosen with probabilities proportional to the
sublinear function of their degrees. Then new vertex attaches to the vertex
with the highest degree from the sample. Depending on the growth rate of the
sample and the sublinear function, the maximum degree could be of the sublinear
order, of the linear order or having almost all edges drawing to it. The prove
using various stochastic approximation processes and a large deviation
approach.
