Программа дисциплины Стохастическое Моделирование




Скачать 20.89 Kb.
НазваниеПрограмма дисциплины Стохастическое Моделирование
Дата03.02.2016
Размер20.89 Kb.
ТипПрограмма дисциплины
Министерство экономического развития и торговли
Российской Федерации


Государственный университет –

Высшая школа экономики




Факультет БИЗНЕС-ИНФОРМАТИКИ




Программа дисциплины


Стохастическое Моделирование


для направления 010500.68 – Прикладная математика и информатика подготовки магистра


Автор Жуков Л.Е. (Leonid.E.Zhukov@gmail.com)


Рекомендовано секцией УМС Одобрено на заседании
«Бизнес-информатика» кафедры анализа данных и

искусственного интеллекта

Председатель Зав. кафедрой

______________ Г.А.Лёвочкина _______________С.О. Кузнецов

«___» _________200_ г « » 2006 г.
Утверждено УС факультета

бизнес-информатики

Учёный секретарь

___________ А.И. Олейник

«___» ________200_ г.


Москва


Программа дисциплины Стохастическое Моделирование (Анализ комплексных сетей) для подготовки магистров по направлению 010500.68 (магистерская программа «математическое моделирование»)


I. Пояснительная записка

Автор программы: Л.Е. Жуков, Ph.D

Требования к студентам: Изучение курса "Стохастическое Моделирование" («Анализ комплексныx сетей») требует предварительных знаний по теории вероятности, линейной алгебре и теории алгоритмов (курс «Дискретная математика»).


Аннотация. Дисциплина “Стохастическое Моделирование” предназначена для подготовки магистров по направлению 010500.68 (магистерская программа «математическое моделирование»)


В последние годы ученые, занимающиеся исследованиями в самых разных областях науки, обнаружили, что во многих сетях - от интернета и энергетических линий, до экономических сетей и метаболической системы клетки - доминирует относительно небольшое число узлов (концентраторов), имеющих огромное количество связей. Таким структурам свойственна масштабная инвариантность и их поведение подчиняется определённым закономерностям: например, они необычайно стойки к случайным отказам, но чрезвычайно уязвимы для скоординированных атак. Понимание общих принципов построения и функционирования сети, независящих от способа реализации, поможет решить многие прикладные задачи. Изложение курса начинается с повторения основных понятий теории графов. Далее рассматриваются теоретические модели безмасштабных сетей и иx основные свойства: степенное распределению степеней узлов (power law), высокий коэффициент кластеризации (корреляция между соседями) и малое среднее расстоянию между узлами. Рассматривается три основных класса моделей: классические случайные графы (Erdos-Renyi), модели роста Barabasi-Albert и комбинированная модель Watts-Strogans. В последнее время социальные сети оказались в центре внимание пользователей интернета и представляют яркий пример безмасштабных сетей. В курсе изучаются их многочисленные структурные и групповые свойства с точки зрения математики, а также экономики и социологии. Интернет (WWW) на сегодня является самой большой масштабно-инвариантной сетью и следующая часть курса посвящена изучению его свойств и алгоритмам автоматического поиска и ранжирования веб сайтов. В последней части курса рассматриваются двудольные графы и их применение в e-commerce, рекомендационных системах, рекламных сетях и интернет аукционах.


Учебные задачи курса.

Данный курс знакомит студентов с новой и активно развивающейся областью – комплексными сетями и их применением в социологии, поисковых интернет системах, электронной коммерции. Студенты получат практические навыки анализа и обработки сетевых данных, программирования на Matlab а также использования средств визуализации информации.


II. Тематический план курса "Дискретные структуры"





Название темы

Всего часов по дисциплине

Аудиторные часы

Самостоятельная работа










Лекции

Сем. и практика занятия




1

Обзор курса, введение в комплексные системы



8

2

2

4

2

Основы теории графов и линейной алгебры.



8

2

2

4

3

Случайные графы и стохастические сети


10

2

2

6

4

Масштабно – инвариантные (scale-free) сети, феномен малого мира (small world)

10

2

2

6

5

Степенной закон распределения (power law), закон Zipf.

10

2

2

6

6

Анализ социальных сетей

20

4

4

12

7

Структура интернета и поисковые системы

20

4

4

12

8

Алгоритмы для электронной коммерции (e-commerce), сетевая реклама


20

4

4

12




Итого

106

22

22

62



Литература по курсу

  1. Albert-Laszlo Barabasi and Eric Bonabeau. Scale-Free Networks, 2003.

  2. L.A.N. Amarala and J.M. Ottino. Complex networks: Augmenting the framework for the study of complex systems, 2003.

  3. R. Albert and A.-L. Barabasi, Statistical mechanics of complex networks, Rev. Modern Phys., 74 (2002), pp. 47–97.

  4. M. E. J. Newman. The Structure and Function of Complex Networks, 2003

  5. S. N. Dorogovtsev and J. F. F. Mendes, Evolution of networks, Adv. in Phys., 51 (2002), pp. 1079–1187.

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

  7. D. J. Watts and S. H. Strogatz, Collective dynamics of “small-world” networks, Nature, 393 (1998), pp. 440–442.

  8. M. E. J. Newman, Models of the small world, J. Statist. Phys., 101 (2000), pp. 819–841.

  9. M. E. J. Newman, Power laws, Pareto distributions and Zipf's law, Contemporary Physics 46, pp 323-351 (2005).

  10. M.L. Goldstein, S.A. Morris, and G.G. Yena,Problems with fitting to the power-law distribution, Eur. Phys. J. B 41, pp 255–258 (2004).

  11. L.C. Freeman, Centrality in Social Networks Conceptual Clarification, Social Networks 1, pp 215-239 (1978/79)

  12. L. Page, S. Brin, R. Motwani, and T. Winograd, The Pagerank Citation Ranking: Bringing Order to the web, technical report, Stanford University, Stanford, CA, 1998

 

Books:


  1. Social Network Analysis: Methods and Applications. Stanley Wasserman, Katherine Faust. Cambridge University Press, 1995.

  2. Small Worlds: The Dynamics of Networks between Order and Randomness. Duncan J. Watts, Princeton University Press, 2003

  3. Mining the Web: Discovering Knowledge from Hypertext Data. Soumen Chakrabarti, Morgan Kaufmann, 2002)


Формы контроля и структура итоговой оценки.


Текущий контроль – домашнее задание.

Промежуточный контроль – зачет в конце первого модуля (120 мин);

Итоговый контроль – письменный экзамен (120 мин.)


Итоговая оценка складывается из следующих элементов:

  • домашнее задание - 10%;

  • письменный зачет – 25%

  • проект – 30%

  • письменный экзамен – 35%



Программа курса

Стохастическое Моделирование" («Анализ комплексныx сетей»)


Тема 1. Обзор курса, введение в комплексные системы

Комплексные сети, примеры безмасштабных (масштабно-инвариантных) сетей, интернет, социальные сети, технологические сети, экономические и бизнес сети, финансовые сети, надёжность и устойчивость сетей.


Основная литература


  1. Albert-Laszlo Barabasi and Eric Bonabeau. Scale-Free Networks, 2003.

  2. L.A.N. Amarala and J.M. Ottino. Complex networks: Augmenting the framework for the study of complex systems, 2003.



Дополнительная литература

  1. R. Albert and A.-L. Barabasi, Statistical mechanics of complex networks, Rev. Modern Phys., 74 (2002), pp. 47–97.

  2. M. E. J. Newman. The Structure and Function of Complex Networks, 2003

  3. S. N. Dorogovtsev and J. F. F. Mendes, Evolution of networks, Adv. in Phys., 51 (2002), pp. 1079–1187.


Тема 2. Основы теории графов и линейной алгебры


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


Основная литература


  1. А.А. Зыков, Основы теории графов, М., Наука, 1987.

  2. Ф. Харари, Теория графов, М., Мир, 1973.



Тема 3. Случайные графы

Модели Erdos-Renyi случайных графов, биномиальное распределение степеней, распределение Пуассона, фазовый переход, гигантская связная компонента, критические значения , средняя длина пути, коэффициент кластеризации.


Основная литература


  1. R. Albert and A.-L. Barabasi, Statistical mechanics of complex networks, Rev. Modern Phys., 74 (2002), pp. 47–97.

  2. M. E. J. Newman. The Structure and Function of Complex Networks, 2003

Дополнительная литература

  1. S. N. Dorogovtsev and J. F. F. Mendes, Evolution of networks, Adv. in Phys., 51 (2002), pp. 1079–1187.



Тема 4. Масштабно-инвариантные сети

Понятие «малого мира”, модель Watts-Stroganz, решёточные графы, Moore граф, Caley деревья, безмасштабные сети, модели роста, модель предпочтительного присоединения Barabasi-Albert, непрерывное приближение, средняя длина пути, кластерный коэффициент


Основная литература

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

  2. D. J. Watts and S. H. Strogatz, Collective dynamics of “small-world” networks, Nature, 393 (1998), pp. 440–442.

  3. M. E. J. Newman, Models of the small world, J. Statist. Phys., 101 (2000), pp. 819–841.


Дополнительная литература

  1. R. Albert and A.-L. Barabasi, Statistical mechanics of complex networks, Rev. Modern Phys., 74 (2002), pp. 47–97.

  2. M. E. J. Newman. The Structure and Function of Complex Networks, 2003

  3. Small Worlds: The Dynamics of Networks between Order and Randomness. Duncan J. Watts, Princeton University Press, 2003


Тема 5. Степенной закон распределения (power law)

Генерирующие модели, математическое ожидание, средние влелечины, расходимость моментов, минимальные значения, нормировка, распределение Pareto, частоты слов, закон Zipf, зависимость ранг – частота, MLE наиболее вероянтая оченка параметров распределения из данных, функции рапспределения и плотности функций распределения


Основная литература


  1. M. E. J. Newman, Power laws, Pareto distributions and Zipf's law, Contemporary Physics 46, pp 323-351 (2005).

  2. M.L. Goldstein, S.A. Morris, and G.G. Yena,Problems with fitting to the power-law distribution, Eur. Phys. J. B 41, pp 255–258 (2004).


Дополнительная литература

  1. R. Albert and A.-L. Barabasi, Statistical mechanics of complex networks, Rev. Modern Phys., 74 (2002), pp. 47–97.

  2. M. E. J. Newman. The Structure and Function of Complex Networks, 2003


Тема 6. Анализ социальных сетей

Направленные и ненаправленные отношения, акторы, радиус и диаметер графа, центр графа, центральности узлов: степенная, промежуточная, центральность по близости, центральность графа (сети) по Фриману, престиж, ранг (статус) престиж, престиж по собственным векторам, стохастические матрицы


Основная литератрура


  1. L.C. Freeman, Centrality in Social Networks Conceptual Clarification, Social Networks 1, pp 215-239 (1978/79)


Дополнительная литература

  1. Social Network Analysis: Methods and Applications. Stanley Wasserman, Katherine Faust. Cambridge University Press, 1995.


Тема 7. Структура интернета и поисковые системы

WWW как граф, структура интернета, источники и стоки, случайные блуждания на графе, Марковские процессы, алгоритм PageRank, hubs и authorities. Архитектура поисковых систем.


Основная литературa


  1. Broder, R. Kumar et al, Graph structure in the the web. Proceedings of the 9th international World Wide Web conference on Computer networks, p 309-320, 2000

  2. L. Page, S. Brin, R. Motwani, and T. Winograd, The Pagerank Citation Ranking: Bringing Order to the web, technical report, Stanford University, Stanford, CA, 1998

  3. J. Kleinberg. Authoritative sources in a hyperlinked environment. Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998.


Дополнительная литература


  1. Mining the Web: Discovering Knowledge from Hypertext Data. Soumen Chakrabarti, Morgan Kaufmann, 2002)



Тема 8. Алгоритмы для электронной коммерции (e-commerce),


Основная литература

  1. Mining the Web: Discovering Knowledge from Hypertext Data. Soumen Chakrabarti, Morgan Kaufmann, 2002)


Дополнительная литература


  1. Websites: Amazon, Google Adwords, Yahoo Music, Yandex Direct



Тематика заданий по различным формам текущего контроля:


  1. Bводные понятие и примеры комплексных систем

  2. Понятие графов, классические алгоритмы на графах

  3. Распределение степеней узлов и фазовые переходы в моделях случайных графов

  4. Распределение степеней узлов, коэффициент кластеризации и средняя длина пути в моделях Watts-Strogans и Albert-Barabasi

  5. Свойства степенных распределений, особенности распределений Pаreto и Zipf

  6. Понятие центральности и престижа в социальных сетях

  7. Структура интернета, математические основы рангирующих алгоритмов

  8. Двудольнуе графы и их применение в е-commerce



Вопросы для оценки качества освоения дисциплины


Тема 1.

  1. Какие системы и сети называются комплексными (масштабно инвариантными)

  2. Привести примеры комплексных сетей



Тема 2.

  1. Дать определение расстояние между узлами на графе

  2. B чем отличие между понятиеми связанные и сильно связанные компоненты?

  3. Дать определение собственными значениями и собственными векторами матрицы



Тема 3.

Для графов изображенных на рисунке, определить:





  1. Какой из приведённых графов был наиболее вероятно сгенерирован используя Erdos-Renyi модель G(n,p) с N=5 и p=0.3 . Почему?

  2. Чему равна средняя ожидаемая степень узла при данных параметрах модели?

  3. Какой из графов (если есть такие) не мог быть сгенерирован этой моделью?



Темa 4

  1. Вычислить диаметр, среднюю длину пути и коэффициент кластеризации для Moore graph (Caley tree)

  2. Вычислить рапсределение степеней узлов в модели Barabasi-Albert при условии равновероятностного присоединения, P(k) = 1/(m_0 + T)



Тема 5.

  1. В чем заключается распределение (закон) Zipf? Как оно связано со степенным распределением (power law)?

  2. Что такое rank-frequency plot ( ранг – частота) ?

  3. Привести пример распределения Zipf



Тема 6.

Для данной сети найти:



  1. Радиус и диаметр

  2. Центр графа и переферийные узлы

  3. Узлы с наибольшей и наименьшей степенной центральностью.

  4. Узлы с наибольшей и наименьшей betweenness центральностью.

  5. Кластерные коэффициенты узлов 1,4,7,9,11

  6. Среднюю величину степенной центральности графа и коеффициент степенной центральности графа по Фриману



Темы 7-8.


  1. Для данного графа написать матрицу смежности. Какое будет конечное (стационарное) распределение собственного вектора eigenvector престижа в этой сети ?






b) Для данного графа написать матрицу смежности и вычислить стационарное распределиени собственного вектора (eigenvector) престижа и соответствующее собственное значение (eigenvalue)






  1. Изменим направление одного из ребер в сети (b) на противоположенное. Как измениться рапсределиние престижа? Возможен ли его прямой расчет как в предыдущем случае? Если нет, предложите какой-либо способ для “исправления” ситуации.



Автор программы: _____________________________/ Л.Е. Жуков/

Похожие:

Программа дисциплины Стохастическое Моделирование iconПрограмма дисциплины Стохастическое моделирование  для направления 657100«Прикладная математика»
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки по...
Программа дисциплины Стохастическое Моделирование iconРабочая программа учебной дисциплины ен. Р. 02 Математическое моделирование процессов транспортирования нефти и газа для специальности 130501 Проектирование, сооружение и эксплуатация газонефтепроводов и газонефтехранилищ
Рабочая программа составлена на основании программы дисциплины «Математическое моделирование процессов трубопроводного транспорта...
Программа дисциплины Стохастическое Моделирование iconПрограмма дисциплины Информационное моделирование (на английском языке) для направления 080700. 68 «Бизнес-информатика»
Моделирование бизнес-процессов. Управление бизнес-процессами (bpm). Интегрированное проектирование информационных систем
Программа дисциплины Стохастическое Моделирование iconРабочая программа дисциплины ен. Р. 06 Моделирование систем

Программа дисциплины Стохастическое Моделирование iconРабочая программа дисциплины б в. 9 Исследование и моделирование систем управления

Программа дисциплины Стохастическое Моделирование iconУчебно-методический комплекс учебной дисциплины «численные методы и математическое моделирование»
В современной физике исключительно важную роль играет математическое моделирование явлений природы. Основным аппаратом при этом является...
Программа дисциплины Стохастическое Моделирование iconПрограмма наименование дисциплины: Мультисервисные сети связи
Магистерская специализация «Математическое моделирование оптических наноструктур»
Программа дисциплины Стохастическое Моделирование iconРабочая программа дисциплины «Математическое моделирование в машиностроении»
Профиль подготовки: 150700. 62 Технологии, оборудование и автоматизация машиностроительных производств
Программа дисциплины Стохастическое Моделирование iconРабочая программа учебной дисциплины «математичское моделирование. Часть ii»
«Системный анализ организационно-управленческой деятельности в больших системах»
Программа дисциплины Стохастическое Моделирование iconРабочая программа учебной дисциплины дс. Р “случайные процессы и имитационное моделирование”
Государственное образовательное учреждение «Кемеровский государственный университет»
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib2.znate.ru 2012
обратиться к администрации
Библиотека
Главная страница