Distance-Dependent Kronecker Graphs for Modeling Social Networks
Abstract
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
Name | Size | Download all |
---|---|---|
md5:ee8fdf5a4585cc1f2db6eb51a144056f
|
897.5 kB | Preview Download |
Additional details
- Eprint ID
- 20495
- Resolver ID
- CaltechAUTHORS:20101025-094230043
- Created
-
2010-11-30Created from EPrint's datestamp field
- Updated
-
2021-11-09Created from EPrint's last_modified field