Авт. обработка текстов на естественном языке и комп. лингвистика. Большакова (2014) (1185448), страница 70
Текст из файла (страница 70)
если узел i связн с узлом j , а j связн с k , тоi связн с k . При этом маршрут, у которого начало, и конец находятся в одном и томже узле, причем все остальные вершины используются ровно один раз, называетсяциклом.Расстояние между узлами определяется как длина маршрута от одного узла додругого. Естественно, узлы могут быть соединены прямо или опосредованно. Путеммежду узлами dij назовем кратчайшее расстояние между ними. Для всей сети можноввести понятие среднего пути, как среднее по всем парам узлов кратчайшегорасстояния между ними:255l=2∑ dij ,n(n + 1) i≥ jгде n – количество узлов, dij – кратчайшее расстояние между узлами i и j .Венгерскими математиками П.
Эрдешем (P. Erdős) и А. Реньи (A. Rényі) былопоказано, что среднее расстояние между двумя вершинами в случайном графе растеткак логарифм от числа вершин [32, 33].На практике живучесть сети связи определяют как вероятность наличия путимежду любой парой узлов.Некоторые сети могут оказаться несвязными, т.е.
в них найдутся узлы, расстояниемежду которыми является бесконечным. Соответственно, средний путь можетоказаться также равным бесконечности. Для учета таких случаев вводится понятиеглобальной эффективности сети как среднего инверсного пути между узлами,рассчитываемое по формуле:E=11,∑n(n − 1) i ≠ j d ijгде сумма учитывает все пары узлов. Эта характеристика отражает эффективностьсети при пересылке информации между узлами (предполагается, что эффективность впересылке информации между двумя узлами i и j обратно пропорциональнарасстоянию между ними).Обратная величина глобальной эффективности – среднее гармоническоегеодезических расстояний:h=1.EТак как данная формула снимает проблему расхождения при определениисреднего пути, то эта характеристика лучше подходит для графов с несколькимикомпонентами связности.Эффективное расстояние между двумя узлами в общем случае больше, чемкратчайшее расстояние.Сети также характеризуются таким параметром как диаметр или максимальный подлине путь, то есть равный максимальному значению из всех dij .Коэффициент кластерностиД.
Уаттс (D. Watts) и С. Строгатц (S. Strogatz) в 1998 году определили такойпараметр сетей, как коэффициент кластерности [34], который соответствует уровнюсвязности узлов в сети. Этот коэффициент характеризует тенденцию к образованиюгрупп взаимосвязанных узлов, так называемых клик (clіque). Кроме того, дляконкретного узла коэффициент кластеризации показывает, сколько ближайшихсоседей данного узла являются также ближайшими соседями друг для друга.Коэффициент кластерности для отдельного узла сети определяется следующимобразом.
Пусть из узла выходит k ребер, которые соединяют его с k другимиузлами, ближайшими соседями. Если предположить, что все ближайшие соседисоединены непосредственно друг с другом, то количество ребер между нимисоставляло бы1k ( k − 1) .2То есть это число, которое соответствует максимальновозможному количеству ребер, которыми могли бы соединяться ближайшие соседивыбранного узла. Отношение реального количества ребер, которые соединяют256ближайших соседей данного узла к максимально возможному (такому, при которомвсе ближайшие соседи данного узла были бы соединены непосредственно друг сдругом) называется коэффициентом кластерности узла i – C (i ) .
Естественно, этавеличина не превышает единицы.Существует еще один способ вычисления коэффициента кластерности(транзитивности), базирующийся на такой формуле:3N ∆,N3где N ∆ – количество 3-циклов в сети, а N 3 – количество связных 3-компонент.C=3-цикл определяется при этом как множество трех узлов с ребрами между каждойпарой узлов. Связная 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 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
