Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-09T21:51:31.770Z Has data issue: false hasContentIssue false

Distribution of Vertex Degree in Web-Graphs

Published online by Cambridge University Press:  31 July 2006

COLIN COOPER
Affiliation:
Department of Computer Science, King's College, University of London, London WC2R 2LS, UK (e-mail: colin.cooper@kcl.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We give results for the age-dependent distribution of vertex degree and number of vertices of given degree in the undirected web-graph process, a discrete random graph process introduced in [8]. For such processes we show that as $k \rightarrow \infty$, the expected proportion of vertices of degree $k$ has power law parameter $1+1/\eta$ where $\eta$ is the limiting ratio of the expected number of edge endpoints inserted by preferential attachment to the expected total degree. The proof for the undirected process generalizes naturally to give similar results for the directed hub-authority process, and an undirected hypergraph process.

Information

Type
Paper
Copyright
2006 Cambridge University Press