Random graph process models of large networks

It is observed empirically that the World Wide Web and many other large networks have degree sequences which can be considered to exhibit a power law. Thus the proportion nk, of vertices of degree k is of the form nk  ∼ Ck-x when k is large. Here x > 0 constant is the parameter of the power law. This polynomial decrease is in contrast to classical Erdos-Renyi random graphs where nk drops off exponentially fast above the expected degree.

We consider a random graph model, the web-graph, for constructing net- works as discrete processes; and which produce a power law degree sequence. For web-graphs we give an explanation of some methods which can be used to obtain the power law of degree sequence, and the distribution of vertex degree. We study this for a generalized undirected model, and for a directed model, the Hub-Authority model.

For undirected web-graph process, we show that as the degree k tends to in nity, the expected proportion of vertices of degree k has power law parameter 1+1/η where η is the limiting ratio of the expected number of edge endpoints inserted by preferential attachment to the expected total degree.