CaltechAUTHORS
  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. http://resolver.caltech.edu/CaltechAUTHORS:20101025-094230043

[img]
Preview
PDF - Published Version
See Usage Policy.

876Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20101025-094230043

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.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/JSTSP.2010.2049412 DOIUNSPECIFIED
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5456189PublisherUNSPECIFIED
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
Record Number:CaltechAUTHORS:20101025-094230043
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20101025-094230043
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:20495
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:30 Nov 2010 22:44
Last Modified:26 Dec 2012 12:33

Repository Staff Only: item control page