Geometric graph properties of the spatial preferred attachment model

被引:17
作者
Janssen, Jeannette [1 ]
Pralat, Pawel [2 ]
Wilson, Rory [1 ]
机构
[1] Dalhousie Univ, Dept Math & Stat, Halifax, NS B3H 4R2, Canada
[2] Ryerson Univ, Dept Math, Toronto, ON M5B 2K3, Canada
基金
加拿大自然科学与工程研究理事会;
关键词
Node similarity; Co-citation; Bibliographic coupling; Link analysis; Complex networks; Spatial graph model; SPA model; COCITATION; WORLD;
D O I
10.1016/j.aam.2012.09.001
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
The spatial preferred attachment (SPA) model is a model for networked information spaces such as domains of the World Wide Web, citation graphs, and on-line social networks. It uses a metric space to model the hidden attributes of the vertices. Thus, vertices are elements of a metric space, and link formation depends on the metric distance between vertices. We show, through theoretical analysis and simulation, that for graphs formed according to the SPA model it is possible to infer the metric distance between vertices from the link structure of the graph. Precisely, the estimate is based on the number of common neighbours of a pair of vertices, a measure known as co-citation. To be able to calculate this estimate, we derive a precise relation between the number of common neighbours and metric distance. We also analyse the distribution of edge lengths, where the length of an edge is the metric distance between its end points. We show that this distribution has three different regimes, and that the tail of this distribution follows a power law. (c) 2012 Elsevier Inc. All rights reserved.
引用
收藏
页码:243 / 267
页数:25
相关论文
共 23 条
[1]   A Spatial Web Graph Model with Local Influence Regions [J].
Aiello, W. ;
Bonato, A. ;
Cooper, C. ;
Janssen, J. ;
Pralat, P. .
INTERNET MATHEMATICS, 2008, 5 (1-2) :175-196
[2]   Emergence of scaling in random networks [J].
Barabási, AL ;
Albert, R .
SCIENCE, 1999, 286 (5439) :509-512
[3]   THE COMBINED USE OF BIBLIOGRAPHIC COUPLING AND COCITATION FOR DOCUMENT-RETRIEVAL [J].
BICHTELER, J ;
EATON, EA .
JOURNAL OF THE AMERICAN SOCIETY FOR INFORMATION SCIENCE, 1980, 31 (04) :278-282
[4]   Geometric Protean Graphs [J].
Bonato, Anthony ;
Janssen, Jeannette ;
Pralat, Pawe L. .
INTERNET MATHEMATICS, 2012, 8 (1-2) :2-28
[5]  
Bonato A, 2010, LECT NOTES COMPUT SC, V6516, P110, DOI 10.1007/978-3-642-18009-5_11
[6]   The Structure of Geographical Threshold Graphs [J].
Bradonjic, Milan ;
Hagberg, Aric ;
Percus, Allon G. .
INTERNET MATHEMATICS, 2008, 5 (1-2) :113-139
[7]  
Cooper Colin, 2012, Algorithms and Models for the Web Graph. Proceedings 9th International Workshop, WAW 2012, P29, DOI 10.1007/978-3-642-30541-2_3
[8]   Finding related pages in the World Wide Web [J].
Dean, J ;
Henzinger, MR .
COMPUTER NETWORKS, 1999, 31 (11-16) :1467-1479
[9]   Preferential attachment in growing spatial networks [J].
Ferretti, Luca ;
Cortelezzi, Michele .
PHYSICAL REVIEW E, 2011, 84 (01)
[10]   A Geometric Preferential Attachment Model of Networks [J].
Flaxman, Abraham D. ;
Frieze, Alan M. ;
Vera, Juan .
INTERNET MATHEMATICS, 2006, 3 (02) :187-205