Preview

Труды Института системного программирования РАН

Расширенный поиск

Случайные графы, модели и генераторы безмасштабных графов

Аннотация

В статье рассматриваются различные модели случайных графов, описывающие реальные сети, возникающие в различных областях: биологии, компьтерных науках, инженерии, социологии. Особое внимание уделено моделям, описывающим социальные сети.

Об авторах

М. М. Берновски
ФизТех
Россия


Н. Н. Кузюрин
ИСП РАН
Россия


Список литературы

1. Mark Newman, Albert-László Barabási, Duncan J. Watts. The Structure and dynamics of networks. Princeton University Press, 2006.

2. P. Erdös and A. Rényi. On the evolution of random graphs // Publ. Math. Debrecen. 1959. V. 6. P. 290-297.

3. W. Aiello, F. Chung, L. Lu. A Random Graph Model for Massive Graphs. STOC'2000.

4. S. Janson, T. Łuczak, I. Norros, (2010), Large cliques in a power-law random graph, J. Appl. Probab. V. 47, N. 4 1124-1135.

5. L.-A. Barabási, R. Albert. Emergence of scaling in random networks. Science, 1999. V.286. P. 509-512

6. L.-A. Barabási, R. Albert, H. Jeong. Scale-free characteristics of random networks: the topology of the world-wide web. Physica, 2000. V. A281. P. 69-77.

7. L.-A. Barabási, R. Albert, H. Jeong. Diameter of the world-wide web. Nature, 1999. V. 401. P. 130-131.

8. R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, E. Upfal. Stochastic models for the web graph. Proc. 41st Symposium on Foundations of Computer Science. 2000.

9. B. Bollobás, O. Riordan. Mathematical results on scale-free random graphs. // Handbook of graphs and networks. Weinheim: Wiley-VCH, 2003. P. 1-34.

10. А.М. Райгородский. Модели случайных графов. МЦНМО, 2011.

11. P.G. Buckley, D. Osthus. Popularity based random graph models leading to scale-free degree sequence. Discrete Mathematics. Volume 282, Issues 1–3, 6 May 2004, Pages 53–68.

12. B. Bollobás, C. Borgs, T. Chayes, O.M. Riordan. Directed scale-free graphs. ProceedingSODA '03 Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms

13. Arthur R. Brady. A compact routing scheme for power-law networks using empirical discoveries in power-law graph topology. http://digg.cs.tufts.edu/readings/pdf/021.pdf

14. Deepayan Chakrabarti et al. R-MAT: A Recursive Model for Graph Mining. http://www.cs.cmu.edu/ christos/PUBLICATIONS/siam04.pdf

15. A. Medina et al. BRITE: Universal Topology Generation from a User’s Perspective. http://www.cs.bu.edu/brite/publications/usermanual.pdf

16. Joel C. Miller, Aric Hagberg. Efficient Generation of Networks with Given Expected Degrees. WAW, 2011.

17. Atif Nazir, Saqib Raza, Chen-Nee Chuah. Unveiling Facebook: a measurement study of social network based applications. IMC'08.

18. J. Leskovec, J. Kleinberg, and C. Faloutsos. Graph evolution: Densification and shrinking diameters. ACM Transact. on Knowledge Discovery from Data, 1(1), 2007.


Рецензия

Для цитирования:


Берновски М.М., Кузюрин Н.Н. Случайные графы, модели и генераторы безмасштабных графов. Труды Института системного программирования РАН. 2012;22.

For citation:


Bernovskiy M.M., Kuzyurin N.N. Random graphs, models and generators of scale-free graphs. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2012;22. (In Russ.)



Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)