Стохастическое Mоделирование: Aнализ Социальных и Экономических Сетей.

Осень 2009

Тематический План Курса

  1. Обзор курса, введение, примеры комплексных сетей
  2. Анализ сетей: метрики и структурные свойства
  3. Анализ сетей: статистические свойства и законы распределения
  4. Формирование сетей : случайные сети
  5. Формирование сетей: модели роста
  6. Формирование сетей: модели малого мира
  7. Формирование сетей : стратегические модели
  8. Процессы в сетях: диффузия, распространение убеждений и координационные игры
  9. Процессы в сетях: пороговые модели поведения и информационные каскады
  10. Приложения: социометрия, экономические и торговые сети, социальные сети

Модуль 1

Лекции

  1. Комплексные сети [01.09.2009]
    Введение в теорию комплексных систем, основы теории графов и линейной алгебры. Основные понятия в теории сетей
  2. Степенные законы распределения [16.09.2009]
    Степенное распределение. Масштабно-инвариантные сети (scale-free networks). Распределение Парето. закон Ципфа, нормализация, моменты, граф ранк-частота
  3. Случайные графы [23.09.2009]
    Модель Erdos-Renyi. Пуассоновские случайные сети. Функция распределния степеней. Фазовые переходы, возникновение связанной компоненты
  4. Динамические модели роста сетей [30.09.2009]
    Модель Barabasi-Albert. Предпочтительное присоединение. Временная зависимость. Распределение степеней узлов
  5. Модели "малого мира" [07.10.2009]
    Модель Watts-Strogats. Однопараметрическая модель. Коэффициент кластеризации. Средняя длина пути
  6. Метрики для анализа сетей [14.10.2009]
    Структурные метрики и коэффициенты. понятия центральности и престижа
  7. Зачет [21.10.2009]

Домашние задания

  1. [16.09.2009] Пострoить распределение степеней узлов в графе web graph. Показать, что это распределение носит степенной характер. Вычислить показатель степени используая метод максимального правдоподобия.
  2. [23.09.2009]. a) Написать программу для генерации случайных графов в модели Erdos-Renyi. Визуализировать графы для различных фазовых состояний (с гигантской связанной компонентой и без нее). Для визуализации использовать пакет GraphVis . Для работы с ним необходимо установить программу graphviz.exe и установить и поместить в Matlab path пакет graphvis2mat. Вызов функции производится командой draw_dot(A), где А матрица смежности графа
    b) Показать что в пределе больших n и фиксированного среднего биномиальное распределение превращается в Пуассоновксое.
  3. [30.09.2009] Найти скорость роста степени узлов от времени и функцию распределения степеней узлов в модели роста B-A при равновероятном присоединении.
  4. [07.10.2009] a) Вычислить диаметр Cayley Tree (Moore Graph) с N узлами.
    b) Показать что коэффициент кластеризации для регулярного графа из модели W-S равен C = 3(k-2)/4(k-1), где k- степень узлов в графе.
  5. [14.10.2009] Вычислить вектор престижа для узлов произвольного неориентированного графа

Модуль 2

Лекции

  1. Стратегические модели формирования сетей [28.10.2009]
    Symmetric connection model. Понятия "network efficency" и "pairwise stability"
  2. Диффузия в сетях [11.11.2009]
    Diffusion of Innovations. Networked Coordination Game.Cascading Behavior in Networks,
  3. Социальное влияние [18.11.2009]
    Social Influence. DeGroot model. Reaching consensus
  4. Информационнные каскады [25.11.2009]
    Information cascades,fads, fashion, custom, following the crowd
  5. Презентации проектов [02.12.2009]
    Панкратьева, Зильмухамедов
  6. Презентации проектов [09.12.2009]
    Шкляева, Смирнова
  7. Презентации проектов [16.12.2009]
    Кононыхин, Шевченко, Ревенко,Чичикина,Ильина,
  8. Зачет [23.12.2009]

Домашние задания

  1. [28.10.2009] Исследовать социальные сети выбранной компании и для каждой сети предоставить краткий отчет содержащий следующую информацию: число узлов и ребер графа, плотность графа; распределения (гистограммы), а также min, max, ave, std значения для кластерного коэффициента, степенной центральности (degree centrality), betweenness centrality, closeness centrality и престижа (prestige) где возможно. Найти и указать узлы имеющие минимальные и максимальные значения метрик. Для визуализации сетей удобно использовать программу yEd, простой конвертер разряженной Matlab матрицы для записи в .TGF формат для работы с yEd здесь. Для вычисление кратчайших путей на графе, а также некоторых метрик можно использовать MatlabBGL.

    Данные по социальным сетям в организациях: компания 1, компания 2, компания 3, компания 4 (all updated!)

Курсовые проекты

Темы:
  1. [Шкляева] Чиленное моделирование структуры случайных сетей (Poisson random graphs ), сравнение с данными.
  2. [Панкратьева] Численное моделирование структуры динамически растущих сетей в модели preferential attachment (Barabasi-Albert) сетей, сравнение с данными.
  3. [Cмирнова] Численное моделирование структуры сетей в модели малого мира(Watts-Strogatz), сравнение с данными.
  4. [Ильина] Численное моделирование структуры сетей в стратегических моделях (Jackson-Wolynksi), сравнение с данными.
  5. [Шевченко] Численное моделирование структуры сетей в других моделях, например evolutionary model, (статья), сравнение с данными.
  6. Численный расчет эффективности и стабильности модельных и практических сетей.
  7. [Зильмухамедов] Численный расчет процессов диффузии в модельных и практических сетях.
  8. [Ревенко] Численный расчет социального влияния в модельных и практических сетях.
  9. [Чичикина] Нахождение сообществ (групп) в сетях, выделение их структуры, (статья)
  10. Разработка новых моделей структуры, роста и развития социальной сети.
Расписание презентации курсовых проектов:

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

Вводные статьи Обзоры Научные статьи