Directed Scale-Free Graphs

Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) |

We introduce a model for directed scale-free graphs that grow with preferential attachment depending in a natural way on the in- and out-degrees. We show that the resulting in- and out-degree distributions are power laws with diff erent exponents, reproducing observed properties of the worldwide web. We also derive exponents for the distribution of in- (out-) degrees among vertices with fi xed out- (in-) degree. We conclude by suggesting a corresponding model with hidden variables.