A Caltech Library Service

Distance-Dependent Kronecker Graphs for Modeling Social Networks

Bodine-Baron, Elizabeth and Hassibi, Babak and Wierman, Adam (2010) Distance-Dependent Kronecker Graphs for Modeling Social Networks. IEEE Journal of Selected Topics in Signal Processing, 4 (4). pp. 718-731. ISSN 1932-4553.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription DOIArticle
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.
Subject Keywords:Distributed algorithms; graph theory; networks; search methods; social factors
Issue or Number:4
Record Number:CaltechAUTHORS:20101025-094230043
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:20495
Deposited By: Tony Diaz
Deposited On:30 Nov 2010 22:44
Last Modified:29 Jul 2020 22:40

Repository Staff Only: item control page