Лекция Марка Ньюмана (SFI) – Зарождающаяся наука о сетях


Автор:

Picture 2Как и обещал, выкладываю конспект лекций института Santa Fe. Начнем с Марка Ньюмана и его лекции о зарождающейся науке о сетях.

Примеры сетей. Сначала Марк привел ряд примеров сетей:

  • Технологических – сеть компьютеров, связанных в Интернет; маршрутная сеть полетов авиакомпаний США; электросеть;

Picture 4Picture 5Picture 6

  • Информационных – сеть Web страниц; сеть цитирования научных статей о теории графов и сеть судебных дел (кейсов). Не забыл Марк объяснить и суть алгоритма Page Rank от Google.

Picture 7Picture 8

  • Биологических – экосеть (пищевая цепочка), метаболическая и протеиновые сети.

Picture 10Picture 11Picture 12

  • Социальных – сеть друзей в школе, сеть френдов в социальной сети Friendster, сеть распространения туберкулеза, сеть персонажей в романе (кстати, я до сих пор не оставляю идеи построить сеть персонажей “Войны и мир” – никто не хочет присоединиться?).

Picture 13Picture 14Picture 15

Феномен малых миров. Рассказав о социальных сетях, г-н Ньюман поведал об эксперименте Милграма, в ходе которого к 100 жителям штата Небраска обратились с просьбой передать письмо через сеть своих знакомых  одному жителю Бостона. Из 100 писем дошло около 20 и выяснилось, что в среднем для того, чтобы письмо попало из Небраски в Бостон, нужно 6 промежуточных узлов. Отсюда и появился термин “6 степеней отчуждения”, о котором поставлена даже пьеса и фильм.

Также Марк рассказал об игре “6 степеней Кэвина Бэйкона” и о некоторых вариациях на эту тему: 6 степеней Моники Левински, например :-)

Распространение вируса. В заключение своей лекции Ньюман объяснил как исследование сетей помогает вскрыть динамику распространения вирусов: от компьютерных до человеческих. Порадовало видео, демонстрирующее как за 24 часа распространялся вирус Code Red, наделавший немало шуму в 2003 году. Далее Марк выделил 2 характеристики сети: коэффициент кластеризации и степень  связности (degree).

  • Коэффициент кластеризации – степень, определяющая насколько узлы стремятся к кластеризации. Например, в сети друзей это вероятность того, что 2 моих друга являются друзьями между собой. То есть это некоторая оценка фрагментированности сети. При высокой кластеризации можно ожидать, что вирус будет распространяться лишь в определенной подгруппе (кластере). При низкой кластеризации высока вероятность быстрого распространения вируса по всей сети.
  • Степень связности определяется по среднему количеству связей у каждого узла сети. Причем Ньюман пояснил, что нужно считать не среднее количество связей, а его квадрат. Почему? Представим, что есть узел у которого 100 связей. Это означает 2 вещи: 1) если такой узел будет заражен, то он заразит еще 100 узлов; 2) у такого узла в 100 раз выше вероятность заражения другими узлами, нежели у узлов, у которых всего одна связь. Поэтому при оценке связности необходимо считать среднее по квадратам количества связей (в данном случае 100 * 100 = 10000).

Ну и в заключение Марк объяснил, что структура сети определяет динамику распространения эпидемии. Например, ниже представлена сеть распространения вируса SARS в Сингапуре и мы видим, что существует небольшое количество hub-ов (узлов с большим количеством связей).

Picture 21

Динамика показателя “количество зараженных ” может принять вид кнута: количество зараженных стремительно возрастает, потом может практически свестись к нулю, но за счет всего одной связи с другим таким hub-ом эпидемия может вновь разгореться, причем с еще большей силой.

Вкратце это все, о чем говорил Ньюман. Спасибо за внимание и следите за своей сетью! :)


6 отзывов

  • By Арсений Арутнев, October 28, 2009 @ 10:10 am

    Байрам, мне понравилась идея с сетью персонажей в Войне и Мире. А в связи с чем она у тебя появилась? И будет ли это полезным занятием?

    Ответить

  • By Bayram Annakov, October 28, 2009 @ 11:22 am

    Арсений, эта идея у меня возникла, когда я читал “Войну и Мир”: в какой-то момент поймал себя на мысли, что запутался во всех именах и связях людей между собой (кто кому тетя и внучатый племянник). Но дополнительно, построив такую сеть, мы сможем привлечь внимание других к идее сетевого анализа.

    Ответить

  • By ARS_VENTURA, October 28, 2009 @ 3:46 pm

    Я думаю можно попробовать. во-первых, хочется повнимательнее перечитать сие великое произведение, во-вторых, познакомиться с методами описания сети. А вот еще вопрос: можно ли потом будет проанализировать эту сеть?

    Ответить

  • By Bayram Annakov, October 28, 2009 @ 5:17 pm

    Можно будет, но надо понять для чего?

    Ответить

  • By Ирина, August 2, 2010 @ 4:59 pm

    Уважаемый Bayram Annakov!
    Подскажите, пожалуйста, где еще можно найти лекции или статьи на русском языке Марка Ньюмана?

    Ответить

    Bayram Annakov Ответ:

    Ирина, к сожалению, с Ньюманом помочь не могу – а зачем вам? Есть другие авторы, пишущие на тему сетевого анализа и распространения эпидемий

    Ответить

Ссылки на эту статью

Оставить отзыв

WordPress Themes