Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 4863))
Included in the following conference series:
2140Accesses
Abstract
The web graph may be considered as embedded in a topic space, with a metric that expresses the extent to which web pages are related to each other. Using this assumption, we present a new model for the web and other complex networks, based on a spatial embedding of the nodes, called theSpatial Preferred Attachment (SPA) model. In the SPA model, nodes have influence regions of varying size, and new nodes may only link to a node if they fall within its influence region. We prove that our model gives a power law in-degree distribution, with exponent in [2, ∞ ) depending on the parameters, and with concentration for a wide range of in-degree values. We also show that the model allows for edges that span a large distance in the underlying space, modelling a feature often observed in real-world complex networks.
The authors gratefully acknowledge support from NSERC and MITACS grants.
This is a preview of subscription content,log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bonato, A.: A survey of web graph models. Proceedings of Combinatorial and Algorithm Aspects of Networking (2004)
Chung, F.R.K., Lu, L.: Complex Graphs and Networks. American Mathematical Society, Providence (2006)
Cooper, C.: The age specific degree distribution of web-graphs. Combinatorics Probability and Computing 15, 637–661 (2006)
Flaxman, A., Frieze, A.M., Vera, J.: A geometric preferential attachment model of networks. Internet Mathematics 3, 187–205 (2006)
Flaxman, A., Frieze, A.M., Vera, J.: A geometric preferential attachment model of networks II (preprint)
Janson, S., Łuczak, T., Ruciński, A.: Random Graphs. Wiley, New York (2000)
Menczer, F.: Lexical and semantic clustering by Web links. JASIST 55(14), 1261–1269 (2004)
Penrose, M.: Random Geometric Graphs. Oxford University Press, Oxford (2003)
Pittel, B., Spencer, J., Wormald, N.: Sudden emergence of a giantk-core in a random graph. Journal of Combinatorial Theory, Series B 67, 111–151 (1996)
Wormald, N.: The differential equation method for random graph processes and greedy algorithms. In: Karoński, M., Prömel, H.J. (eds.) Lectures on Approximation and Randomized Algorithms, PWN, Warsaw, pp. 73–155 (1999)
Author information
Authors and Affiliations
University of British Columbia, Vancouver, Canada
W. Aiello
Wilfrid Laurier University, Waterloo, Canada
A. Bonato
King’s College, London, UK
C. Cooper
Dalhousie University, Halifax, Canada
J. Janssen & P. Prałat
- W. Aiello
You can also search for this author inPubMed Google Scholar
- A. Bonato
You can also search for this author inPubMed Google Scholar
- C. Cooper
You can also search for this author inPubMed Google Scholar
- J. Janssen
You can also search for this author inPubMed Google Scholar
- P. Prałat
You can also search for this author inPubMed Google Scholar
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Aiello, W., Bonato, A., Cooper, C., Janssen, J., Prałat, P. (2007). A Spatial Web Graph Model with Local Influence Regions. In: Bonato, A., Chung, F.R.K. (eds) Algorithms and Models for the Web-Graph. WAW 2007. Lecture Notes in Computer Science, vol 4863. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77004-6_8
Download citation
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-540-77003-9
Online ISBN:978-3-540-77004-6
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative