Distance-Dependent Kronecker Graphs for Modeling Social Networks

摘要

This paper focuses on a generalization of stochasticudKronecker graphs, introducing a Kronecker-like operator anduddefining a family of generator matrices H dependent on distancesudbetween nodes in a specified graph embedding. We proveudthat any lattice-based network model with sufficiently smalluddistance-dependent connection probability will have a Poissonuddegree distribution and provide a general framework to proveudsearchability for such a network. Using this framework, we focusudon a specific example of an expanding hypercube and discussudthe similarities and differences of such a model with recentlyudproposed network models based on a hidden metric space. Weudalso prove that a greedy forwarding algorithm can find very shortudpaths of length O((log log n)^2) on the hypercube with n nodes,uddemonstrating that distance-dependent Kronecker graphs canudgenerate searchable network models.ud