A Geometric Preferential Attachment Model of Networks

@incollection{citeulike:1323082, abstract = {We study a random graph G n that combines certain aspects of geometric random graphs and preferential attachment graphs. The vertices of G n are n sequentially generated points x 1, x 2,..., x n chosen uniformly at random from the unit sphere in . After generating x t , we randomly connect it to m points from those points in x 1, x 2,..., x t –1 which are within distance r. Neighbours are chosen with probability proportional to their current degree. We show that if m is sufficiently large and if r ≥ log n / n 1/2– β for some constant then whp at time n the number of vertices of degree k  follows a power law with exponent 3. Unlike the preferential attachment graph, this geometric preferential attachment graph has small separators, similar to experimental observations of [7]. We further show that if m ≥ K log n, K sufficiently large, then G n is connected and has diameter O ( m/ r) whp .}, author = {Flaxman, Abraham D. and Frieze, Alan M. and Vera, Juan}, citeulike-article-id = {1323082}, journal = {Algorithms and Models for the Web-Graph}, keywords = {attachment, diameter, geometric, law, power, preferential}, pages = {44--55}, posted-at = {2007-05-23 23:53:04}, priority = {0}, title = {A Geometric Preferential Attachment Model of Networks}, url = {http://www.springerlink.com/content/302vc9p3ad0mqgpg }, year = {2004} }

TY - CHAP ID - citeulike:1323082 L3 - citeulike-article-id:1323082 N2 - We study a random graph G n that combines certain aspects of geometric random graphs and preferential attachment graphs. The vertices of G n are n sequentially generated points x 1, x 2,..., x n chosen uniformly at random from the unit sphere in . After generating x t , we randomly connect it to m points from those points in x 1, x 2,..., x t –1 which are within distance r. Neighbours are chosen with probability proportional to their current degree. We show that if m is sufficiently large and if r ≥ log n / n 1/2– β for some constant then whp at time n the number of vertices of degree k  follows a power law with exponent 3. Unlike the preferential attachment graph, this geometric preferential attachment graph has small separators, similar to experimental observations of [7]. We further show that if m ≥ K log n, K sufficiently large, then G n is connected and has diameter O ( m/ r) whp . JF - Algorithms and Models for the Web-Graph EP - 55 TI - A Geometric Preferential Attachment Model of Networks SP - 44 KW - attachment KW - diameter KW - geometric KW - law KW - power KW - preferential AU - Flaxman, Abraham AU - Frieze, Alan AU - Vera, Juan PY - 2004/// UR - http://www.springerlink.com/content/302vc9p3ad0mqgpg ER -