This thesis presents space-efficient algorithms to sample from random web graphs
generated by two important stochastic graph models based on concept of copying:
the linear copy model and the hostgraph model. The goal is to avoid constructing
the entire random graph, and instead use an amount of space nearer to the desired
(smaller) sample size. The efficiency of our algorithms is achieved by refraining from
making unnecessary random decisions when constructing the sample. The construc-
tion of a sample subgraph from a random graph with n nodes and k outgoing links
on each node based on the linear copying model uses an expected O(klnn) words for
each node in the sample subgraph. The construction of a sample subgraph from a
random graph with n nodes based on the hostgraph model uses, for any small sample
size, an expected n+o(n) words.
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/1327 |
| Date | 08 January 2009 |
| Creators | Zhuang, Yan |
| Contributors | King, Valerie |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Rights | Available to the World Wide Web |
Page generated in 0.0023 seconds