DocumentCode :
1481020
Title :
Distance-Dependent Kronecker Graphs for Modeling Social Networks
Author :
Bodine-Baron, Elizabeth ; Hassibi, Babak ; Wierman, Adam
Author_Institution :
Electr. Eng. Dept., California Inst. of Technol., Pasadena, CA, USA
Volume :
4
Issue :
4
fYear :
2010
Firstpage :
718
Lastpage :
731
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.
Keywords :
Internet; graph theory; greedy algorithms; matrix algebra; social networking (online); stochastic processes; Kronecker like operator; Poisson degree distribution; distance dependent kronecker graphs; greedy forwarding algorithm; hidden metric space; lattice based network model; social network modeling; Distributed algorithms; graph theory; networks; search methods; social factors;
fLanguage :
English
Journal_Title :
Selected Topics in Signal Processing, IEEE Journal of
Publisher :
ieee
ISSN :
1932-4553
Type :
jour
DOI :
10.1109/JSTSP.2010.2049412
Filename :
5456189
Link To Document :
بازگشت