Variations on the preferential attachment graph

The aim of this thesis is to study some variations of the preferential attachment graph, a dynamically evolving random graph. In every time step a new vertex with m edges incident to it are added to the graph. The m neighbors of this new vertex are chosen among the old vertices by preferential attachment, i.e. with probability proportional to their degree. The Preferential Attachment Graph is used to model large complex networks describing a wide range of systems in nature and society. Examples of such networks appear in communications, biology, social sciences and economics.; In Chapter 1 we study a dynamically evolving random graph which adds vertices and edges using preferential attachment and deletes vertices and edges randomly. At time t, with probability alpha 1 > 0 we add a new vertex ut and m random edges incident with ut. The neighbors of ut are chosen among all the existing vertices with probability proportional to their degree. With probability alpha - alpha1 ≥ 0 we add m random edges to existing vertices where the endpoints are chosen with probability proportional to degree.; In Chapter 2 we study a dynamically evolving random graph that adds vertices and edges using preferential attachment and is "attacked by an adversary". At time t, we add a new vertex ut and m random edges incident to ut. The neighbors of ut are chosen with probability proportional to degree. After adding the edges, the adversary is allowed to delete vertices. The only constraint on the adversarial deletions is that the total number of vertices deleted by time n must be no larger than deltan, where delta is a constant.; In Chapter 3 we study a random graph Gn that combines certain aspects of geometric random graphs and preferential attachment graphs. The vertices of Gn are n sequentially generated points x1,x 2,...,xn chosen uniformly at random from the unit sphere in R3. After generating xt, we randomly connect it to m points from those points in x1,x 2,...,xt-1 which are within distance r.; In Chapter 4, we study a model where the presence of highly popular search engines like Google substantially mediate the act of hyperlink creation by limiting the author's attention to a small set of "celebrity" URLs. Page authors (who are also Web surfers) frequently (with probability p) locate pages using a search engine. Then they link to popular pages among those they visit. (Abstract shortened by UMI.)...