Независимые множества в случайных графах пересечений: различия между версиями

Совокупность M иногда называется множеством меток, а ее элементы – метками. Обозначим за Ц для l 2 M множество вершин, выбравших метку l.

В силу зависимостей от ребер эта модель способна более точно (по сравнению с моделью случайных графов Бернулли <math>G_{n,p} \;</math>, предполагающей независимость от ребер) абстрагировать многие практические задачи. Кроме того, Филл, Шайнерманн и Сингер-Коэн в работе [ ] показали, что для некоторых диапазонов параметров n; m;p (m = na, a > 6) пространства <math>G_{n,m,p} \;</math> и <math>G_{n,p} \;</math> являются эквивалентными в том смысле, что суммарное вариационное расстояние между переменными случайного графа имеет предел, равный 0. Николетсис, Раптопулос и Спиракис [  ] предложили две новых модели, а именно модель случайных графов пересечений общего вида Gn m *,p = [p1; p2; pm] и модель регулярных случайных графов пересечений Gn^m^,X > 0, использующих различные способы случайного присвоения меток вершинам, но применяющих одно и то же правило вхождения ребер. Модель Gn m -i является обобщением равномерной модели, в котором каждая метка i 2 M выбирается независимо с вероятностью pi, тогда как в модели С "тд каждая вершина выбирает случайное подмножество M, содержащее в точности A меток.