Рандомизация с сохранением степени

Рандомизация с сохранением степени - это метод, используемый в науке о сетях, целью которого является оценка того, могут ли вариации, наблюдаемые в данном графе, быть просто артефактом присущих графу структурных свойств, а не свойств, уникальных для узлов в наблюдаемой сети.

В каталоге еще в 1996 г. ^[1] простейшая реализация рандомизации с сохранением степени основана на алгоритме Монте-Карло , который случайным образом перестраивает или «перемонтирует» сеть таким образом, что при достаточном количестве переустановок распределение степени сети идентично начальное распределение степени сети, хотя топологическая структура сети стала полностью отличной от исходной сети.

Рандомизация с сохранением степени, хотя и имеет множество различных форм, обычно принимает форму относительно простого подхода: для любой сети, состоящей из узлов с ребрами, выберите два узла, связанных диадически. Для каждой из этих диадических пар поменяйте местами ребра так, чтобы новые диадические пары не совпадали. После достаточного количества этих несоответствий сеть все больше теряет свою первоначальную наблюдаемую топографию.${\ Displaystyle Н}$${\ Displaystyle Е}$

Как это обычно бывает с алгоритмами, основанными на цепях Маркова , количество итераций или отдельных переподключений, которые должны произойти на данном графе, чтобы граф был достаточно случайным и отличался от исходного графа, неизвестно, хотя Эспиноза ^[2] утверждает, что безопасный минимальный порог равен , где «не менее 100» (Эспиноза). Другие внесли свой вклад в решение этой проблемы, в том числе один автор, который утверждает, что безопасный минимум вместо этого может быть не менее , где эпсилон находится в диапазоне между и , хотя в конечном итоге правильное число в настоящее время неизвестно. ^{[3] [4]}${\ Displaystyle Q * E}$${\ Displaystyle Q}$${\ displaystyle {\ frac {E} {2}} * ln (1 / \ эпсилон)}$${\ Displaystyle 10 ^ {- 6}}$${\ Displaystyle 10 ^ {- 7}}$

Есть несколько случаев, когда опубликованные исследования явно использовали рандомизацию с сохранением степени для анализа свойств сети. Деккер ^[5] использовал перепрограммирование, чтобы более точно смоделировать наблюдаемые социальные сети, добавив вторичную переменную , которая вводит предвзятость высокой степени привязанности. Лю и др. ^[6] дополнительно использовали рандомизацию с сохранением степени, чтобы утверждать, что определяемая ими метрика Control Centrality мало меняется по сравнению с Control Centrality модели Эрдёша-Реньи, содержащей такое же количество узлов в их симуляциях — Liu et al. также использовали модели рандомизации с сохранением степени в последующей работе по изучению${\ Displaystyle \ пи}$${\ Displaystyle Н}$сетевая управляемость . ^[7]

Кроме того, была проделана некоторая работа по изучению того, как рандомизация с сохранением степени может использоваться для решения вопросов анонимности в сетевых исследованиях данных, что, как было показано, вызывает беспокойство в анализе социальных сетей , как в случае исследования Льюиса. и другие. ^{[8] [9]} В конечном итоге работа, проведенная Ин и Ву, начиная с фундамента рандомизации с сохранением степени, а затем передавая несколько модификаций, продемонстрировала умеренные успехи в защите анонимности без ущерба для целостности базовой полезности наблюдаемой сети. ^[10]

Демонстрация одной итерации алгоритма рандомизации с сохранением степени.

Результаты испытаний рандомизации с сохранением степени.