Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published August 2010 | Published
Journal Article Open

Distance-Dependent Kronecker Graphs for Modeling Social Networks


This paper focuses on a generalization of stochastic Kronecker graphs, introducing a Kronecker-like operator and defining a family of generator matrices H dependent on distances between nodes in a specified graph embedding. We prove that any lattice-based network model with sufficiently small distance-dependent connection probability will have a Poisson degree distribution and provide a general framework to prove searchability for such a network. Using this framework, we focus on a specific example of an expanding hypercube and discuss the similarities and differences of such a model with recently proposed network models based on a hidden metric space. We also prove that a greedy forwarding algorithm can find very short paths of length O((log log n)^2) on the hypercube with n nodes, demonstrating that distance-dependent Kronecker graphs can generate searchable network models.

Additional Information

© 2010 IEEE. Manuscript received November 16, 2009; revised March 26, 2010; accepted April 09, 2010. Date of publication April 29, 2010; date of current version July 16, 2010. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Vikram Krishnamurthy.

Attached Files

Published - BodineBaron2010p11653Ieee_J-Stsp.pdf


Files (897.5 kB)
Name Size Download all
897.5 kB Preview Download

Additional details

August 22, 2023
August 22, 2023