Analytic theory of power law graphs
March 12, 2008
Abstract
Author:
Published in:
SIAM Conference on Parallel Processing for Scientific Computing
R&D Area:
R&D Group:
Summary
An analytical theory of power law graphs is presented basedon the Kronecker graph generation technique. The analysisuses Kronecker exponentials of complete bipartite graphsto formulate the sub-structure of such graphs. This allows various high level quantities (e.g. degree distribution,betweenness centrality, diameter, eigenvalues, and isoparametric ratio) to be computed directly from the model pa-rameters. The implications of this work on “clustering”and “dendragram” heuristics are also discussed.