The Kronecker theory of power law graphs
January 1, 2012
Book Chapter
Author:
Published in:
Graph Algorithms in the Language of Linear Algebra, pp. 205-220.
R&D Area:
R&D Group:
Summary
An analytical theory of power law graphs is presented based on the Kronecker graph generation technique. Explicit, stochastic, and instance Kronecker graphs are used to highlight different properties. The analysis uses Kronecker exponentials of complete bipartite graphs to formulate the substructure of such graphs. The Kronecker theory allows various high-level quantities (e.g., degree distribution, betweenness centrality, diameter, eigenvalues, and iso-parametric ratio) to be computed directly from the model parameters.