Generalizing Kronecker graphs in order to model searchable networks
Lists
Only you see this
Abstract
This paper describes an extension to stochastic Kronecker graphs that provides the special structure required for searchability, by defining a ¿distance¿-dependent Kronecker operator. We show how this extension of Kronecker graphs can generate several existing social network models, such as the Watts-Strogatz small-world model and Kleinberg's lattice-based model. We focus on a specific example of an expanding hypercube, reminiscent of recently proposed social network models based on a hidden hyperbolic metric space, and prove that a greedy forwarding algorithm can find very short paths of length O((log log n)2) for graphs with n nodes.
BibTeX
@inproceedings{bodinebaron2009generalizing,
author = {Elizabeth Bodine-Baron and Babak Hassibi and Adam Wierman},
title = {{Generalizing Kronecker graphs in order to model searchable networks}},
booktitle = {Allerton},
year = {2009},
doi = {10.1109/allerton.2009.5394816},
}Loading related content...