IEEE Themes - Distance-Dependent Kronecker Graphs For Modeling Social Networks

Babak Hassibi from the California Insitute of Technology presents this generalization of stochastic Kronecker graphs, introducing a Kronecker-like operator and defining a family of generator matrices H dependent on distances between no design a specified graph embedding. The authors 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, the authors 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. The authors also prove that a greedy forwarding algorithm can find very short paths of length O.