Модель графа с НППС

Случайные графы с НППС были впервые предложены В.Н. Задорожным в 2010 году в статье [2]. Данные графы генерируются на основе правила «предпочтительного связывания» (богатый становится богаче). Граф с НППС выращивается из графа-затравки итерационно, путём добавления вершин со случайным числом рёбер r, с заданной функцией предпочтения f ≥0, зависящей от степени связности k_i вершины. Вероятность присоединения свободным концом нового ребра к уже существующей вершине графа зависит от функции предпочтения и вычисляется по формуле (1):

, (1)

Эта модель обеспечивает абсолютно точное совпадение средней степени связности графа.

Модели графов с НППС в последнее время получили широкое развитие. В работе [3] были найдены эффективные способы генерации графа. В [2, 4] представлены такие способы калибровки графов, которые позволяют при заданном распределении вероятностей r, путём подбора функции предпочтения f (k) генерировать граф с требуемым распределением степени связности вершин.

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