Московский Технический Университет Связи и Информатики

МОСКОВСКИЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
СВЯЗИ И ИНФОРМАТИКИ



Версия для слабовидящихВерсия для слабовидящих


К списку новостей

Семинар

  

Президиум Российской Академии Наук,

Департамент транспорта и связи города Москвы,
Математический институт им. В.А.Стеклова РАН (МИРАН),

Институт математического моделирования РАН (ИММ РАН)
 Московский автомобильно-дорожный институт (МАДИ(ГТУ)),

Московский технический университет связи и информатики (МТУСИ)


Информационное сообщение ежемесячного семинара
«Научно - практические задачи развития

автомобильно-дорожного комплекса в России»

Уважаемый участник семинара!

Пятое  заседание семинара 2009-2010 гг

состоится 25 февраля  2010 г.   в  15:00 по адресу: 

Московский Технический Университет Связи и Информатики (МТУСИ),

ул. Народного ополчения , 32.  Проезд : м. Октябрьское поле,

тролл. 59,61,19 до ост.”Институт связи” . Регистрация  в 14:30  в ауд.  309, просим при себе иметь паспорт.

Основной доклад

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

Райгородский Андрей Михайлович, д.ф.-м.н.

-        МГУ им. М.В. Ломоносова,   механико-математический факультет, доцент кафедры математической статистики и случайных процессов;

-        МФТИ,   факультет инноваций и высоких технологий, профессор кафедры «Анализ данных»;

-        Яндекс,   руководитель группы «Лаборатория комбинаторных и вероятностных методов»

Руководитель семинара - Козлов В.В.,

Вице-президент РАН, академик РАН

Заместители:

Аджемов А.С., д.т.н., ректор МТУСИ 

Бугаев А.С., академик РАН, ИРЭ РАН

Приходько В.М., чл.-корр. РАН, ректор МАДИ(ГТУ)

Четверушкин Б.Н., чл.-корр. РАН,  директор  ИПМ РАН

Оргбюро

Буслаев А.П., д.ф.-м.н.,  МАДИ (ГТУ),

Ведешин Л.А., к.т.н., пом. вице-президента РАН

Гасников А.В., к.ф.м.н., МФТИ

Яшина М.В.,  д.т.н., МТУСИ

Тел. для справок: (499)155-04-36,  факс (499)-1927274,  email: apal2006@yandex.ru

Семинар «Научно - практические задачи развития  автомобильно-дорожного комплекса в России», четверг,  25.02.2010,  МТУСИ, 15:00

А.М. Райгородский. Модели случайных веб-графов и их приложения к задачам анализа данных в интернете и других сложных сетях

К концу 90х годов ХХ века интернет уже представлял собой весьма сложную и динамически развивающуюся сеть. Это с неизбежностью привело к появлению многочисленных статистических исследований «веба». Здесь особое внимание уделялось вебу как графу, вершины которого (в зависимости от контекста) суть сайты или страницы, а ребра – ссылки между ними. Среди наиболее значимых статистик веба, которые были изучены в первую очередь, следует выделить диаметр веб-графа и последовательность степеней его вершин. Довольно быстро стало понятно, что во многом интернет устроен так же, как и многие другие сложные (социальные, биологические, транспортные) сети. Однако имеются и существенные отличия. В результате возникла интересная с теоретической точки зрения и важная для практических приложений задача моделирования веба. За последние 10 лет был придуман ряд нетривиальных моделей, которые в той или иной степени адекватно описывают процесс роста интернета.

В нашем докладе мы расскажем прежде всего об истории проблематики, приведем различные эвристики и опишем наиболее важные и жизнеспособные модели веб-графов, среди которых модели предпочтительного присоединения Барабаши – Альберт, Боллобаша – Риордана и др. Далее, мы поговорим о приложениях этих моделей к анализу данных в интернете. В частности, речь пойдет об отыскании «неестественных» подструктур в веб-графах и о задачах ранжирования в поиске.

ЛИТЕРАТУРА:

1.        B. Bollobas, Random Graphs, Cambridge Univ. Press, Second Edition, 2001.

2.        L.-A. Barabasi, R. Albert, Emergence of scaling in random networks, Science, 286 (1999), 509 - 512.

3.        L.-A. Barabasi, R. Albert, H. Jeong, Scale-free characteristics of random networks: the topology of the world-wide web, Physica, A281 (2000), 69 - 77.

4.        R. Albert, H. Jeong, L.-A. Barabasi, Diameter of the world-wide web, Nature, 401 (1999), 130 - 131.

5.        A. Broder et al., Graph structure in the Web, Computer Networks, 33 (2000), 309 - 320.

6.        J.M. Kleinberg et al., The Web as a graph: measurements, models, and methods, Computing and Combinatorics, 5th Annual International Conference, COCOON '99, Tokyo, Japan, July 26-28, 1999, Proceedings,Lecture Notes in Computer Science 1627 (1999), Springer.

7.        J. Leskovec, J. Kleinberg, Ch. Faloutsos, Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations, Proc. of KDD'05, August 21-24, 2005, Chicago, Illinois, USA.

8.        R. Kumar et al., Stochastic models for the web graph, 41st Annual Symposium on Foundations of Computer Science, 2000.

9.        B. Bollobas, O. Riordan, J. Spencer, G. Tusnady, The degree sequence of a scale-free random graph process, Random Structures Algorithms, 18 (2001), N3, 279 - 290.

10.     B. Bollobas, Ch. Borgs, J. Chayes, O. Riordan, Directed scale-free graphs, Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, MD, 2003), 132 - 139, ACM, New York, 2003.

11.     B. Bollobas, O. Riordan, Mathematical results on scale-free random graphs, Handbook of graphs and networks, 1 - 34, Wiley-VCH, Weinheim, 2003.

12.     B. Bollobas, O. Riordan, The diameter of a scale-free random graph, Combinatorica, 24 (2004), N1, 5 - 34.

13.   N. Berger, B. Bollobas, Ch. Borgs, J. Chayes, O. Riordan, Degree distribution of the FKP network model, Theoret. Comput. Sci., 379 (2007), N3, 3 06 - 316.


 

Московский Технический Университет Связи и Информатики