Stochastic Kronecker Graphs
A random graph model based on Kronecker products of probability matrices has been recently proposed as a generative model for large-scale real-world networks such as the web. This model simultaneously captures several well-known properties of real-world n
- PDF / 405,585 Bytes
- 8 Pages / 430 x 660 pts Page_size
- 6 Downloads / 222 Views
Abstract. A random graph model based on Kronecker products of probability matrices has been recently proposed as a generative model for large-scale real-world networks such as the web. This model simultaneously captures several well-known properties of real-world networks; in particular, it gives rise to a heavy-tailed degree distribution, has a low diameter, and obeys the densification power law. Most properties of Kronecker products of graphs (such as connectivity and diameter) are only rigorously analyzed in the deterministic case. In this paper, we study the basic properties of stochastic Kronecker products based on an initiator matrix of size two (which is the case that is shown to provide the best fit to many real-world networks). We will show a phase transition for the emergence of the giant component and another phase transition for connectivity, and prove that such graphs have constant diameters beyond the connectivity threshold, but are not searchable using a decentralized algorithm.
1
Introduction
A generative model based on Kronecker matrix multiplication was recently proposed by Leskovec et al. [10] as a model that captures many properties of realworld networks. In particular, they observe that this model exhibits a heavytailed degree distribution, and has an average degree that grows as a power law with the size of the graph, leading to a diameter that stays bounded by a constant (the so-called densification power law [12]). Furthermore, Leskovec and Faloutsos [11] fit the stochastic model to some real world graphs, such as Internet Autonomous Systems graph and Epinion trust graphs, and find that Kronecker graphs with appropriate 2×2 initiator matrices mimic very well many properties of the target graphs. Most properties of the Kronecker model (such as connectivity and diameter) are only rigorously analyzed in the deterministic case (i.e., when the initiator matrix is a binary matrix, generating a single graph, as opposed to a distribution over graphs), and empirically shown in the general stochastic case [10]. In this paper we analyze some basic graph properties of stochastic Kronecker graphs with an initiator matrix of size 2. This is the case that is shown by Leskovec
Work performed in part while visiting Yahoo! Research.
A. Bonato and F.R.K. Chung (Eds.): WAW 2007, LNCS 4863, pp. 179–186, 2007. c Springer-Verlag Berlin Heidelberg 2007
180
M. Mahdian and Y. Xu
and Faloutsos [11] to provide the best fit to many real-world networks. We give necessary and sufficient conditions for Kronecker graphs to be connected or to have giant components of size Θ(n) with high probability1 . Our analysis of the connectivity of Kronecker graphs is based on a general lemma (Theorem 1) that might be of independent interest. We prove that under the parameters that the graph is connected with high probability, it also has a constant diameter with high probability. This unusual property is consistent with the observation of Leskovec et al. [12] that in many real-world graphs the effective diameters do not increase, o
Data Loading...
