понедельник, 7 декабря 2015 г.

Диффузия в сети: пример в R

В 2000-е гг. внимание исследователей в области сетей  было преимущественно приковано к их структуре и механизмам формирования. В это время появились работы Барабаши и Альберт, а также Ваттса и Строгатца, предлагающие модели эволюции сетей: модель предпочтительного соединения (preferential attachment model) и модель малого мира (small-world network), соответственно.
С появлением моделей роста и эволюции сетей, интерес исследователей переместился в область процессов, происходящих в самих сетях, например, на диффузию и перколяцию. Диффузией в сетях называют процесс, при котором какой-либо сигнал постепенно распространяется по всей сети.
Популярный пример диффузии в сети – это диффузия инноваций, при которой люди начинают пользоваться новыми устройствами или сервисами, которыми уже пользуются их друзья. Социальные сети называют важным механизмом распространения информациисоциальных инновацийзаболеваний и многого другого. Одним из важных факторов диффузии в социальных сетях является социальное влияние, о чем много написано в работах по динамике социальных сетей и поведения (например, здесь).


Распространение инноваций в социальной сети. Серые вершины – акторы, которые пока не используют новый продукт. Зеленые вершины – акторы, недавно начавшие его использование. Синие – акторы, давно использующие продукт. Источник.

В этом посте мы решили показать, как можно смоделировать распространение поведения в социальной сети в статистической среде R.
Моделируемая сеть выстроена по алгоритму предпочтительного присоединения, разработанного Альбертом-Ласло Барабаши и Рекой Альберт. Согласно этой модели, вершины, присоединяющиеся к социальной сети, с большей вероятностью будут создавать связи с популярными вершинами, у которых уже много контактов. Распространение моделируется по алгоритму SI (suspecious-infected), в соответствии с которым агенты сети могут либо быть носителями сигнала «Infected» (обладать информацией/быть зараженными болезнью), либо «Suspecious» (ожидают получения информации или заражения болезнью). Ниже представлен код в статистической среде R, моделирующий распространение сигнала по модели SI в сети предпочтительного присоединения. За основу кода взяты работы Ченга Ванга. infections_test
In [ ]:
# Нам потребуются пакеты igraph и animation
library(igraph)
library(animation)
In [ ]:
# Создадим случайную сеть
node_number <- 100
g <- barabasi.game(node_number)
plot(g)
In [ ]:
# Случайным образом заражаем некоторые вершины сети (обозначим их как diffusers)
seeds_num <- 1
set.seed(2014)
diffusers <- sample(V(g),seeds_num)
diffusers
infected <- list()
infected[[1]] <- diffusers
In [ ]:
# Задаем вероятность заражения
transmission_rate <- 0.4
coins <- c(1, 0) 
probabilities <- c(transmission_rate, 1-transmission_rate )        
toss <- function(freq) {
  tossing <- NULL
  for (i in 1:freq ) tossing[i] = sample(coins, 1, rep=TRUE, prob=probabilities)
  tossing <- sum(tossing)
  return (tossing)
}
In [ ]:
# Зараженные агенты передают болезнь своим соседям
update_diffusers <- function(diffusers){
  nearest_neighbors <- data.frame(table(unlist(neighborhood(g, 1, diffusers))));
  nearest_neighbors <- subset(nearest_neighbors, !(nearest_neighbors[,1]%in%diffusers))
  keep <- unlist(lapply(nearest_neighbors[,2], toss))
  new_infected <- as.numeric(as.character(nearest_neighbors[,1][keep >= 1]))
  class(new_infected) <- "igraph.vs"
  diffusers <- unique(c(diffusers, new_infected))
  return(diffusers)
}
In [ ]:
# Начинаем заражение!
total_time <- 1
while(length(infected[[total_time]]) < node_number){ 
  infected[[total_time+1]] <- sort(update_diffusers(infected[[total_time]]))
  cat(length(infected[[total_time+1]]), "-->")
  total_time <- total_time + 1}
In [ ]:
# Нарисуем, каким образом число зараженных вершин изменяется со временем
plot_time_series <- function(infected, m){
  num_cum <- unlist(lapply(1:m, 
                          function(x) length(infected[[x]]) ))
  p_cum <- num_cum/node_number
  p <- diff(c(0, p_cum))
  time <- 1:m
  plot(p_cum~time, type = "b", 
       ylab = "CDF", xlab = "Time",
       xlim = c(0,total_time), ylim =c(0,1))
}
plot_time_series(infected, length(infected))
In [ ]:
# А теперь посмотрим, каким образом заражение распространяется по социальной сети

saveGIF({
  ani.options(interval = 0.5, convert = shQuote("C:/DATA/convert.exe"))
m <- 1
  while(m <= length(infected)){
    V(g)$color = "white"
    V(g)$color[V(g)%in%infected[[m]]] = "red"
    plot(g, layout = layout.old)
    m = m + 1}
})



Процесс диффузии в сети. Красные вершины - зараженные агенты, белые - ожидающие заражения. Источник.
     
     В дальнейшем код может быть адаптирован для моделирования распространения по моделям SIS, SIR и SIRS в других социальных сетях, в частности, в сетях малого мира, случайной сети, а также эмпирически наблюдаемой. Например, используя SIRS на сети дружбы школьников можно попробовать предсказать процесс распространения гриппа или ОРВИ – заболеваний передающихся при контакте воздушно-капельным путем.

2 комментария:

  1. Супер!
    Маленькая деталь. Вы не задали "layout.old" в функции

    ОтветитьУдалить
  2. Спасибо!

    Можно задать любую раскладку графа. Например, layout.old = layout.fruchterman.reingold(g)

    ОтветитьУдалить