Directed scale-free graphs

ABSTRACT

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 different exponents, reproducing observed properties of the worldwide web. We also derive exponents for the distribution of in- (out-) degrees among vertices with fixed out- (in-) degree. We conclude by suggesting a corresponding model with hidden variables.

REFERENCES

• 1: W. Aiello, F. Chung and L. Lu, A random graph model for power law graphs, Experiment. Math., 10 (2001), pp. 53--66.
• 2: R. Albert and A. L. Barabási, Statistical mechanics of complex networks, arXiv:cond-mat/0106096 (2001)
• 3: R. Albert, H. Jeong and A. L. Barabási, Diameter of the world-wide web, Nature, 401 (1999), pp. 130--131.
• 4: K. Azuma, Weighted sums of certain dependent variables, Tôhoku Math. J., 3 (1967), pp. 357--367.
• 5: A.-L. Barabási and R. Albert, Emergence of scaling in random networks, Science, 286 (1999), pp. 509--512.
• 6: A.-L. Barabási, R. Albert and H. Jeong, Mean-field theory for scale-free random networks, Physica A, 272 (1999), pp. 173--187.
• 7: A.-L. Barabási, R. Albert and H. Jeong, Scale-free characteristics of random networks: the topology of the world-wide web, Physica A, 281 (2000), pp. 69--77.
• 8: G. Bianconi and A.-L. Barabási, Competition and multiscaling in evolving networks, cond-mat/0011029.
• 9: B. Bollobás, Random Graphs, Second Edition, Cambridge studies in advanced mathematics, vol. 73, Cambridge University Press, Cambridge, 2001, xvi+498pp.
• 10: B. Bollobás, Martingales, isoperimetric inequalities and random graphs, in Combinatorics (Eger, 1987), pp. 113--139, Colloq. Math. Soc. János Bolyai, 52, North-Holland, Amsterdam 1988.
• 11: B. Bollobás and O. M. Riordan, The diameter of a scale-free random graph, to appear in Combinatorica.
• 12: Béla Bollobás , Oliver Riordan , Joel Spencer , Gábor Tusnády, The degree sequence of a scale-free random graph process, Random Structures & Algorithms, v.18 n.3, p.279-290, May 2001 [doi>10.1002/rsa.1009]
• 13: Andrei Broder , Ravi Kumar , Farzin Maghoul , Prabhakar Raghavan , Sridhar Rajagopalan , Raymie Stata , Andrew Tomkins , Janet Wiener, Graph structure in the Web, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.309-320, June 2000, Amsterdam, The Netherlands
• 14: C. Cooper and A. Frieze, A general model of web graphs, preprint.
• 15: S. N. Dorogovtsev and J. F. F. Mendes, Evolution of random networks, preprint.
• 16: P. Erdös and A. Rényi, On random graphs. I, Publ. Math. Debrecen, 6 (1959), pp. 290--297.
• 17: P. Erdös and A. Rényi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl., 5 (1960), pp. 17--61.
• 18: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, ACM SIGCOMM Computer Communication Review, v.29 n.4, p.251-262, Oct. 1999
• 19: E. N. Gilbert, Random graphs, Ann. Math. Statist., 30 (1959), pp. 1141--1144.
• 20: W. Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc., 58 (1963), pp. 13--30.
• 21: H. Jeong, B. Tombor, R. Albert, Z. N. Oltvai and A.- L. Barabási, The large-scale organization of metabolic networks, Nature, 407 (2000), pp. 651--654.
• 22: J. Kleinberg, R. Kumar, P. Raghavan, S. Rajagopalan and A. Tomkins, The web as a graph: measurements, models, and methods, COCOON 1999.
• 23: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Extracting Large-Scale Knowledge Bases from the Web, Proceedings of the 25th International Conference on Very Large Data Bases, p.639-650, September 07-10, 1999
• 24: R. Kumar , P. Raghavan , S. Rajagopalan , D. Sivakumar , A. Tomkins , E. Upfal, Stochastic models for the Web graph, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.57, November 12-14, 2000
• 25: M. E. J. Newman, The structure of scientific collaboration networks, Proc. Natl. Acad. Sci USA, 98 (2001), pp. 404--409.
• 26: M. E. J. Newman, S. H. Strogatz and D. J. Watts, Random graphs with arbitrary degree distributions and their applications, Phys. Rev. E, 64 (2001), 026118.
• 27: D. Osthus and G. Buckley, Popularity based random graph models leading to a scale-free degree distribution, preprint.
• 28: D. J. Watts and S. H. Strogatz, Collective dynamics of 'small-world' networks, Nature, 393 (1998), pp. 440--442.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.m Miscellaneous

General Terms:
Algorithms, Theory