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

См. также: Модель конфигурации.

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

Фон

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

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

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

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

Использование

Есть несколько случаев, когда опубликованные исследования явно использовали рандомизацию с сохранением степени для анализа свойств сети. Деккер использовал перепрограммирование, чтобы более точно смоделировать наблюдаемые социальные сети, добавив вторичную переменную, $\pi$, что приводит к высокой степени предвзятости привязанности. Лю и др. дополнительно использовали рандомизацию с сохранением степени, чтобы утверждать, что контрольная центральность , метрика, которую они идентифицируют, мало меняется по сравнению с контрольной центральностью модели Эрдеша-Реньи, содержащей такое же количество $N$ узлы в своих симуляциях - Лю и др. также использовали модели рандомизации, сохраняющие степень, в последующей работе по изучению управляемости сети .

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

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

Пример

Далее следует небольшой пример, показывающий, как можно применить рандомизацию с сохранением степени к наблюдаемой сети, чтобы понять работу сети в отношении случайных изменений, сохраняя при этом аспект распределения степени в сети. У Ассоциации интернет-исследователей есть рассылка , которая составляет большинство тем дискуссий, касающихся их работы. На нем участники публикуют обновления о своих собственных исследованиях, предстоящих конференциях, приглашениях на подготовку докладов, а также вовлекают друг друга в предметные дискуссии в своей области. Эти электронные письма, в свою очередь, могут образовывать направленный временной сетевой граф, где узлы — это отдельные учетные записи электронной почты, принадлежащие Listserv, а края — это случаи, когда один адрес электронной почты отвечает на другой адрес электронной почты в Listserv.

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

В этой наблюдаемой сети свойства Listserv относительно легко вычислить - для сети из 3235 отдельных учетных записей электронной почты и 9824 обменов в общей сложности наблюдаемая взаимность сети составляет около 0,074, а [Средняя длина пути|среднее значение длина пути] составляет около 4,46. Могут ли эти ценности быть достигнуты просто за счет природы внутренней структуры сети?

Применение ${\frac {E}{2}}*ln(1/\epsilon )$ Как правило, этой сети потребуется около 67 861 отдельных перемонтажей ребер, чтобы построить, вероятно, достаточно случайный граф с сохранением степени. Если мы построим множество случайных графов, сохраняющих степень, на основе реального графа, мы сможем затем создать вероятностное пространство для таких характеристик, как взаимность и средняя длина пути, и оценить степень, в которой сеть могла бы выразить эти характеристики случайным образом. 534 сети были созданы с использованием рандомизации с сохранением степени. Поскольку и взаимность, и средняя длина пути на этом графике нормально распределены, а стандартное отклонение как для взаимности, так и для средней длины пути слишком узкое, чтобы включить наблюдаемый случай, мы можем обоснованно предположить, что эта сеть выражает характеристики, которые не являются случайным (и, таким образом, открытым для дальнейшей теории и моделирования).

Внешние ссылки

• Набор данных, например, предоставлен