Рандомізації мережі

У попередній вправі ви могли помітити, що середня довжина шляху в мережі з фільму Forrest Gump була меншою, ніж середня довжина шляху у випадковій мережі. Якщо ви запускали код кілька разів, то бачили, що вона майже завжди нижча в мережі Forrest Gump, ніж у випадковій. Це свідчить про те, що мережа Forrest Gump є більш щільно взаємопов'язаною, ніж кожна з випадкових мереж, навіть попри те, що випадкові мережі мають однакову кількість вершин і приблизно однакову густину графа. Замість того щоб багаторазово перезапускати код, це можна формально перевірити, створивши 1000 випадкових графів із такою самою кількістю вершин і густиною, як у початковому графі Forrest Gump. Потім ви зможете підрахувати, скільки разів середня довжина шляху у випадкових графах менша, ніж у початковій мережі Forrest Gump. Це називають тестом рандомізації.

Граф g і його середня довжина шляху (яку ви обчислили в попередній вправі) g.apl уже є у вашому робочому середовищі.

Ця вправа є частиною курсу

Аналіз мереж у R

Переглянути курс

Інструкції до вправи

Згенеруйте 1000 випадкових графів на основі початкового графа g, виконавши код, що створює списковий об'єкт gl, і цикл for.
Обчисліть середню довжину шляху для 1000 випадкових графів за допомогою lapply(). Створіть вектор gl.apls із цих 1000 значень, виконавши код з unlist().
Побудуйте гістограму середніх довжин шляху для 1000 випадкових графів, викликавши hist() для вектора gl.apls. Додайте до графіка червону штрихову вертикальну лінію за допомогою abline() із перетином по осі x у значенні середньої довжини шляху початкового графа g.apl.
Обчисліть частку випадків, коли значення середньої довжини шляху випадкових графів gl.apls нижчі за значення початкового графа g.apl. По суті, це ймовірність отримати спостережувану середню довжину шляху випадково, з огляду на початкову густину та кількість вершин у початковому графі.

Інтерактивна практична вправа

Спробуйте виконати цю вправу, доповнивши цей зразок коду.

library(igraph)

# Generate 1000 random graphs
gl <- vector('list', 1000)
  
for(i in 1:1000){
  gl[[i]] <- erdos.renyi.game(n = gorder(g), p.or.m = gd, type = "gnp")
}

# Calculate average path length of 1000 random graphs
gl.apls <- unlist(lapply(gl, ___, directed = FALSE))

# Plot the distribution of average path lengths
___(gl.apls, xlim = range(c(1.5, 6)))
abline(v = ___, col = "red", lty = 3, lwd = 2)

# Calculate the proportion of graphs with an average path length lower than our observed
mean(___ < ___)

Редагувати та запускати код