Теория безмасштабных сетей (scale-free networks) бурно развивалась последние 9 лет, после основополагающей публикации Барабаши [1]. Безмасштабные сети - это случайные графы, где распределение связей узлов - степенное и основные свойства сети не зависят от размера сети. Было показано, что социальные, коммуникационные сети, документы WWW, биологические и другие системы хорошо моделируются безмасштабными графами. В последнее время теория получила более глубокую формальную базу [2,3,4], а также появились интересные работы с практическим применением теории как в области компьютерных наук [5], так и в социологии [6,7,8] и экономике [9]. Одновременно появляются или становятся доступными данные, которые можно анализировать в контексте этой теории: данные он-лайновых социальных сетей, корпоративные базы (контакты, структуры сделок, электронная почта). При этом, устоявшиеся промышленные технологии управления данными плохо подходят для задач анализа сетей.

В докладе рассматривается теория безмаштабных сетей и основные результаты этой теории:

• степенное распределение связей
• механизмы образования безмасштабных графов
• само-похожесть безмасштабных графов
• малый диаметр безмасштабных графов
• устойчивость к случайным разрушениям и неустойчивость к целенаправленным разрушениям.

Далее рассматриваются интересные приложения теории:

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

В завершение рассматриваются проблемы, встающие перед современными системами управления данными при анализе безмасштабных сетей и мотивируется создание специализированных систем решения этих проблем.

Слайды к докладу в формате PDF: velikhov.pdf

Литература:

1. Barabasi, Albert-Laszlo and Reka, Albert. "Emergence of scaling in random networks". Science, 286:509-512, October 15, 1999.
2. Dorogovtsev, S.N. and Mendes, J.F.F. and Samukhin, A.N., "Structure of Growing Networks: Exact Solution of the Barabasi-Albert's Model", Phys. Rev. Lett. 85, 4633 (2000).
3. Reuven Cohen, Shlomo Havlin, "Scale-Free Networks are Ultrasmall" Phys. Rev. Lett. 90, 058701 (2003).
4. Li, L., Alderson, D., Tanaka, R., Doyle, J.C., Willinger, W., Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications (Extended Version). Internet Mathematics, 2005.
5. Haijun Zhou and Reinhard Lipowsky, "Dynamic pattern evolution on scale-free networks", Proccedings National Academy of Sciences U S A. 2005 July 19.
6. Zoltan Dezso? and Albert-Laszlo Barabasi, "Halting viruses in scale-free networks", Physical Review 2002, May 21.
7. Ormerod, Paul. "Hayek, 'The Intellectuals And Socialism', аnd Weighted Scale-Free Networks", Economic Affairs 26 (1), 41–47 (2006).
8. Z. Toroczkai and K.E. Bassler "Network Dynamics: Jamming is Limited in Scale-free Systems", Nature 428, 716 (2004).
9. Benczur, A. A., Csalogany, K., Sarlos, T. and Uher, M. Spamrank - fully automatic link spam detection. In First International Workshop on Adversarial Information Retrieval on the Web, 2005.
10. L. Adamic, R. Lukose, B. Huberman, A. Puniyani "Search in Power Law Networks", Phys. Rev. E, 64 46135 (2001).
11. M. Newman, "Fast algorithm for detecting community structure in networks.", Phys. Rev. 18 Jun 2004.
12. G. Jeh, J. Widom, "SimRank: A Measure of Structural-Context Similarity", ACM SIGKDD 2002.
13. Liben-Nowell, D., Kleinberg, J. "The Link Prediction Problem for Social Networks", CIKM 2003.