Зависимость разведзащищённости от степени неоднородности сетей

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

Множество графических степенных последовательностей Пi вместе с соответствующими характеристиками приведены в таблице2.

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

i=1 i=16

i=7 i=8

Рис.9. Графы последовательностей 1,7,8 и 16

Рис.10. Графики зависимости вероятности распознавания от времени и от дисперсии степени вершин

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

Однако, с уменьшением степени неоднородности графа возрастает число автоморфизмов графа, т.е. число изоморфизмов графа на себя.

Теоретически число вариантов построения графа определяется числом групп с одинаковыми степенями вершин и числом таких вершин, входящих в группу:

, , 1≤ L ≤ n

где N- число вариантов построения графа;

n- число вершин графа;

L- число групп вершин с одинаковыми степенями;

k_i- число вершин в группе.

При L=N, т.е. когда количество различимых групп равно количеству различимых вершин, (все вершины имеют разные степени) существует всего один вариант построения графа. При L=1, N=n!.

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

Максимальное число вариантов получается когда d_i=6. Покажем пример подсчета числа вариантов для последовательности с наибольшим числом вариантов.

v_i1 2 3 4 5 6 7 8 9 10 11 12

d_i 6 6 6 6 6 6 6 6 6 6 6 6 П₁₆

Первую вершину можно выбрать 12 способами, далее нужно выбрать 6 вершин из оставшихся 11. Это можно сделать , таким образом первый шаг можно выполнить 12.462=5444 способами.

Второй шаг:

v_i8 9 10 11 12 2 3 4 5 6 7 1

d_i 6 6 6 6 6 5 5 5 5 5 5 0

Первую вершину можно выбрать 5 способами, порядок следующих 4^х, имеющих степень 6 не играет роли. 6, 7-ю вершину со степенью 5 можно выбрать одним из способов, таким образом второй шаг можно сделать 15х5 =75 способами.

Третий шаг:

v_i9 10 11 12 4 5 6 7 2 3 1 8

d_i 5 5 5 5 5 5 5 5 4 4 0 0

Первую вершину можно выбрать 8-ю способами, вторую группу вершин (5) можно выбрать способом, таким образом третий шаг можно выполнить 8х21=168 способами.

Четвертый шаг:

v_i6 7 10 11 12 4 5 2 3 1 8 9

d_i 5 5 4 4 4 4 4 4 4 0 0 0

Первую вершину можно выбрать 2-мя способами, вторую группу вершин (со степенью d_i =4) можно выбрать способами, таким образом четвертый шаг можно выполнить 2х35=70 способами.

Пятый шаг:

v_i7 5 2 3 10 11 12 4 1 8 9 6

d_i 4 4 4 4 3 3 3 3 0 0 0 0

Первую вершину можно выбрать 4-мя способами, вторую группу вершин (со степенью d_i =3) можно выбрать 4 способами, таким образом четвертый шаг можно выполнить 4х4=16 способами.

Шестой шаг:

v_i5 2 3 11 12 4 10 1 8 9 6 7

d_i 3 3 3 3 3 3 0 0 0 0 0 0

Первую вершину можно выбрать 6-ю способами, вторую группу вершин (со степенью d_i =3) можно выбрать способами, таким образом шестой шаг можно выполнить 6х10=60 способами.

Седьмой шаг:

v_i12 4 10 2 3 11 1 8 9 6 7 5

d_i 3 3 2 2 2 2 0 0 0 0 0 0

Первую вершину можно выбрать 2-мя способами, вторую группу вершин (со степенью d_i =2) можно выбрать способами, таким образом седьмой шаг можно выполнить 6х2=12 способами.

Восьмой шаг:

v_i4 3 11 10 2 1 8 9 6 7 5 12

d_i 2 2 2 1 1 0 0 0 0 0 0 0

Первую вершину можно выбрать 3-мя способами, восьмой шаг может быть выполнен 3 способами.

Девятый шаг:

v_i3 11 10 2 1 8 9 6 7 5 12 4

d_i 1 1 1 1 0 0 0 0 0 0 0 0

Первую вершину можно выбрать 4-мя способами, девятый шаг также может быть выполнен 4-мя способами.

Десятый шаг:

v_i10 2 3 4 5 6 7 1 8 9 11 12

d_i 1 1 0 0 0 0 0 0 0 0 0 0

Десятый шаг –соединение 10 и 2 вершины, можно выполнить 2-мя способами, однако, поскольку графы не ориентированы, то порядок соединения не играет роли, поэтому число вариантов 10-го шага –1.

Общее число вариантов равно сумме вариантов на каждом шаге, таким образом для последовательности П₁₆ существует 5953 изоморфных графа.

Число вариантов для других последовательностей показано в таблице 1.

Изоморфность графов проверялось по ходу их построения.

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

Вероятность распознавания конкретной структуры Р_кс по полученной вероятности распознавания типовой структуры Р_тс, можно получить из следующего соотношения:

Р_ТС=1-(1-Р_КС)^N, откуда , или , или . Графки для пересчета Р_ТС в Р_КС в зависимости от числа вариантов показаны на рис.11.

Рис. 11. Графики нахождения вероятности распознавания конкретной структуры

При N=1, соответственно lgN=0, Р_ТС = Р_КС. для того, чтобы получить значение Р_КС , необходимо иметь с графика рис.3 значение Р_ТС, определить из таблицы №1 значение N и по этим двум параметрам с графики рис.4 снять значение Р_КС.