dc.contributor.author | Wang, Changping. | en_US |
dc.date.accessioned | 2014-10-21T12:36:44Z | |
dc.date.available | 2006 | |
dc.date.issued | 2006 | en_US |
dc.identifier.other | AAINR19597 | en_US |
dc.identifier.uri | http://hdl.handle.net/10222/54835 | |
dc.description | We propose new evolutionary stochastic models for the Web graph and other massive networks, where edges are deleted over time and an edge is chosen to be deleted with probability inversely proportional to the in-degree of the destination. The expected degree distributions of graphs generated by our models follow a power law. A rigorous proof of power law degree distributions is given. Depending on the parameters, the exponent of the power law can be any number in (2, infinity). | en_US |
dc.description | We study the partial duplication model and investigate its degree sequence. We propose a new copying model with edge-deletion and show that the expected degree distribution exhibits a power law. | en_US |
dc.description | We consider the game of Cops and Robber on a certain family of graphs C (n) (cycles with handles), on the graphs generated by the copying models, and on the random graph G (n, p). For any natural number n, we bound the cop number of C (n). We also prove that, with probability 1 as n approaches infinity, the cop number of G (n, p) is concentrated around logs n, where s = 11-p . | en_US |
dc.description | We introduce two new countable infinite graphs RnH and R(n). Such graphs are inspired by recent research on the Web graph and the infinite random graph. The graph R(n) can arise naturally from an infinite random process. We prove that R(n) is the unique infinite graph satisfying certain properties. We also prove that the induced subgraphs of R(n) coincide with the new graph class of countable n-ordered graphs, which generalize partial n-trees. We study some properties of RnH such as clique number, chromatic number and the conditions for the existence of homomorphisms. | en_US |
dc.description | Thesis (Ph.D.)--Dalhousie University (Canada), 2006. | en_US |
dc.language | eng | en_US |
dc.publisher | Dalhousie University | en_US |
dc.publisher | | en_US |
dc.subject | Mathematics. | en_US |
dc.title | Stochastic models for self-organizing networks and infinite graphs. | en_US |
dc.type | text | en_US |
dc.contributor.degree | Ph.D. | en_US |