Моделирование социальной сети случайным графом с заданными параметрами
Для имитационного моделирования процессов в социальных сетях необходима модель самой сети.
Эта модель должна иметь те же статистические характеристики, что и сама сеть.
Модель сети представляет собой граф, вершинами которого являются абоненты сети, а ребрами –связи между ними.
Граф компактно представляется в двух видах.
Список ребер хранит все пары вершин (п,т), связанных ребрами.
Список смежности содержит для каждой вершины перечень связанных с ней вершин(соседей), нулевым элементом перечня обычно является число соседей(степень данной вершины).
Требуется разработать алгоритм построения связного графа со случайно установленными связями, распределение степеней вершин которого соответствует заданному распределению (рk), то есть алгоритм составления списка смежности и списка ребер графа.
Указание.
Задается число вершин графа N(не менее 1000 для статистической значимости).
Для каждой i-вершины в соответствии с распределением (рk)генерируется ее степень ki, которая записывается в отдельный массив.
Затем для каждой вершины генерируются случайные числа из диапазона от i+1 до N, являющиеся номерами претендентов в соседние вершины.
Если для очередной вершины с генерированным номером j степень (0-элемент j-строки списка смежности) меньше заданного значения kj, то 0-элемент увеличивается на единицу, соответствующие номера вершин вносятся в список смежности (вершине i–номер j, и наоборот), добавляется запись (i,j)в список ребер.
Если очередной претендент заполнен, то номер пропускается. Процедура генерирования для каждой вершины повторяется, пока не будет достигнута ее степень ki, либо пока не останется ни одной незаполненной вершины.
Для оптимизации процедуры целесообразно номера незаполненных вершин записать в отдельный список, исключая из него номера по мере заполнения степени вершин, и генерировать новые номера только из этого списка.
Тогда условием останова будет исчерпание списка незаполненных вершин.
Поскольку останов может произойти до достижения последней вершины, то необходимо проверить полученное распределение степеней (0-элементы списка смежности) по критерию хи-квадрат на соответствие заданному распределению.
Если соответствие не подтверждается, то генерирование графа производится заново.
После генерирования графа необходимо проверить его связность.
Если граф несвязный, то полученный результат отбрасывается, и граф генерируется заново.