Generalizing Kronecker graphs in order to model searchable networks

Elizabeth Bodine-Baron, Babak Hassibi, Adam Wierman

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...

Figure