Большакова Е.И. и др. - Автоматическая обработка текстов на естественном языке и компьютерная лингвистика, страница 71

Связная 3-компонента – множество, состоящее из трех узлов, в которомкаждый узел достижим из другого узла, непосредственно или опосредованно. Такимобразом, в 3-компоненте центральный узел должен быть инцидентен двум другим.Множитель 3 введен из учета вариантов различных 3-компонент для каждого 3-цикла,этот множитель обеспечивает выполнение неравенства 0 ≤ C ≤ 1 . Тогда мы получаем:N∆ =N3 =∑aak >i > jij ik∑ (a ak >i > ja jk ;ij ik+ a ji a jk + aki akj ) ,где aij – элементы матрицы смежности A , соответствующей сети, сумма беретсяпо всем компонентам различных узлов i , j и k только один раз.Коэффициент кластерности может определяться как для каждого узла, так и длявсей сети.

Соответственно, уровень кластерности всей сети определяется какнормированная по количеству узлов сумма соответствующих коэффициентовотдельных узлов.Разница между двумя подходами к определению кластерности состоит в том, что,усреднив по вершинам, мы получаем во втором случае одинаковое влияние длякаждого треугольника в сети, а в первом случае учитывается равный взнос длякаждого узла.Это приводит к разным значениям коэффициента кластерности, потому что узлы сбольшими степенями с большей вероятностью входят в состав большего количестватреугольников, чем вершины с меньшими степенями.Рассмотренный ниже феномен «малых миров» непосредственно связан с уровнемкластерности сети.ПосредничествоЗначение узла для сети тем больше, чем в большем количестве путей онзадействован.

Поэтому, полагая, что обмен данными происходит по кратчайшимпутям между двумя вершинами, можно измерить количественно значение узла сточки зрения посредничества (betweenness), определяемого количеством кратчайшихпутей проходящих через узел. Эта характеристика отражает роль данного узла вустановлении связей в сети. Узлы с наибольшим посредничеством играют главнуюроль в установлении связей между другими узлами в сети. Посредничество bm узла mопределяется по формуле:bm = ∑i≠ jB ( i , m, j ),B (i, j )257где B ( i, j ) – общее количество кратчайших путей между узлами i и j , B ( i, m, j ) –количество кратчайших путей между узлами i и j , проходящих через узел m .Если учитывать, что кратчайшие пути могут быть неизвестны, и вместо этого длянавигации в сети используются поисковые алгоритмы, то посредничество(промежуточная центральность) узла может быть выражена вероятностью егонахождения поисковым алгоритмом.Уровень преобладания наибольшего посредника в этом случае определяется всоответствии с формулой:CPD =1∑ ( Bmax − Bi ),n −1 iгде Bmax – самое большое в сети значение уровня посредничества.Преобладание центрального узла будет равно 0 для клики и 1 для звезды, вкоторой центральный узел входит во все пути.Эластичность и уязвимость сетиПротивоположные свойства эластичности и уязвимости сетей относятся краспределению расстояний между узлами при изъятии отдельных узлов.Эластичность сети зависит от ее связности, т.е.

существовании путей между парамиузлов. Если узел будет изъят из сети, типичная длина этих путей увеличится. Еслиэтот процесс продолжать достаточно долго, сеть перестанет быть связной. Р. Альберт(Réka Albert) из университета штата Пенсильвания (США) при исследовании атак наинтернет-серверы изучала эффекты, возникающие при изъятии узла из сети,представляющей собой подмножество WWW из 326000 страниц [35].Среднее расстояние между двумя узлами, как функция от количества изъятыхузлов, почти не изменилось при случайном удалении узлов (высокая эластичность).Вместе с тем целенаправленное удаление узлов с наибольшим количеством связейприводит к разрушению сети.

Таким образом, Интернет является высоко эластичнойсетью по отношению к случайному отказу узла в сети, но высокочувствительной кнамеренной атаке на узлы с высокими степенями связей с другими узлами.Один из способов найти критичные компоненты сети – поиск самых уязвимыхузлов [36].

Если производительность сети связана с ее глобальной эффективностью,уязвимость узла может быть определена как спад производительности в случаеудаления узла и всех смежных емк ребер из сети:E − Ei,EVi =где E – глобальная эффективность исходной сети, а Ei – глобальная эффективностьпосле удаления узла i и всех смежных ему ребер.Упорядоченное распределение узлов относительно их уязвимостей связано соструктурой всей сети, таким образом, наиболее уязвимый узел занимает наивысшуюпозицию в сетевой иерархии. Мера уязвимости сети – максимальная уязвимостьсреди всех ее узлов:V = max Vi .iКоэффициент элитарностиВ наукометрии на протяжении длительного времени исследуются сетицитирований.

Известно, что влиятельные исследователи определенных областей258формируют сообщества сетевого типа, выражающиеся, например, в публикациисовместных работ. Такая закономерность наблюдается также в других реальных сетяхи отражает такую тенденцию, как хорошая связность между узламиконцентраторами. Это явление, известное под названием элитарность (или феномен«клуба богатых» – rіch-club phenomenon), может быть охарактеризованокоэффициентом элитарности, введенным в работе [37].Анализ топологии веб, проведенный Ши Жоу (S.

Zhou) и Р. Дж. Мондрагоном(R.J. Mondragon) из Лондонского университета, показал, что узлы с большойстепенью исходящих гиперссылок имеют больше связей между собой, чем с узлами смалой степенью, тогда как последние имеют больше связей с узлами с большойстепенью, чем между собой. Исследование показало, что 27% всех соединений имеютместо между всего 5% наибольших узлов, 60% приходится на соединение других 95%узлов с 5% наибольших и только 13% – это соединение между узлами, которые невходят в лидирующие 5%.Элитарность степени k у сети G – это некое множество узлов со степенью,большей k , ℜ(k ) = {v ∈ N (G ) | kv > k } . Коэффициент элитарности степени k выражаетсяследующим образом:φ (k ) =1∑ aij ,| ℜ( k ) | (| ℜ( k ) | −1) i , j∈ℜ( k )где сумма соответствует удвоенному количеству ребер между вершинами в«элите».

Эта характеристика подобна коэффициенту кластерности, она определяетдолю связей, существующих между узлами со степенью превышающей k .Корреляция степеней связанных вершинЗначительное количество структурных и динамических свойств сети определяетсяс помощью оценки корреляции между степенями соседних узлов. Такая корреляцияможет быть выражена через совокупное распределение P(k , k ') , т.е.

как вероятностьтого, что произвольно выбранное ребро соединяет узел степени k с узлом степени k ' .Зависимость между степенями вершин можно выразить в терминах условнойвероятности того, что произвольно выбранный сосед вершины степени k имеетстепень k ' [38]:k P (k , k ').kP (k )При этом ∑ P(k ' | k ) = 1 . В случае неориентированных сетей P(k , k ') = P(k ', k ) иP(k ' | k ) =k'k ' P(k | k ') P(k ') = kP(k ' | k ) P(k ) .Если сеть ориентированная, то k – это степень предшествующего узла, k ' –степень последующего узла, значения k и k ' могут быть входными , выходными илиполными степенями. В общем случае P(k , k ') = P(k ', k ) .Значения P(k , k ') и P(k | k ') формально описывают корреляции степеней узлов,однако их сложно вычислять экспериментальным путем, что связано с размером сетии малой мощностью выборки узлов с высокими степенями.

Эту проблему можнорешить, вычислив среднюю степень ближайших соседей узлов с заданной степенью kпо формуле:S (k ) = ∑ k ' P(k ' | k ) .k'259Показатель корреляции степеней связности позволяет выделить отдельныеклассы сетей. Если корреляция отсутствует, то S (k ) не зависит от значений k ,S (k ) = k 2 / k . Если S (k ) возрастает при увеличении k , то узлы больших степенейтяготеют к соединениям с узлам больших степеней, и сеть относят к ассортативным(отсюда и феномен «клуба богатых»), тогда как если S (k ) – убывающая функция от k, то вершины больших степеней тяготеют к соединениям с вершинами малыхстепеней, и сеть называют дизассортативной [39].В работе [39] был подсчитан коэффициент корреляции Пирсона для некоторыхреальных и смоделированных сетей.

Было обнаружено, что, несмотря на отображениемоделями специфических особенностей структуры (степенное распределение степенисвязности узлов, свойство «малого мира»), большинство из них не воспроизводитассортативность реальной сети. Например, для модели построения сети со степеннымраспределением степеней связности узлов Барабаши-Альберта [40] значение r = 0 .Тем не менее, социальные сети склонны к ассортативности, а биологические итехнологические часто дизассортативны.Известно, что ассортативные сети менее уязвимы к равновероятным атакам, адизассортативные менее уязвимы к целенаправленным атакам на узлыконцентраторы. Также, например, синхронизация состояния компонент сетипроисходит быстрее в ассортативных сетях.