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

Этоттермин был введен в 1954 году социологом из «Манчестерской школы» Дж. Барнсом(J. Barnes) в работе «Классы и сборы в норвежском островном приходе». Во второйполовине XX столетия понятие «социальная сеть» стало популярным у западныхисследователей, при этом в качестве узлов социальных сетей стали рассматривать нетолькопредставителей социума, но и другие объекты, которым присущиисоциальные связи. В теории социальных сетей получило развитие такое направление,как анализ социальных сетей (Socіal Network Analysіs, SNA). Сегодня термин«социальная сеть» обозначает понятие, оказавшееся шире своего социальногоаспекта, оно включает, например, многие информационные сети, в том числе и вебпространство или социальные интернет-сети.В рамках теории сложных сетей рассматривают не только статистические, нодинамические сети, для понимания структуры которых необходимо учитыватьпринципы их эволюции.В теории сложных сетей выделяют три основных направления: исследованиестатистических свойств, которые характеризуют поведение сетей; создание моделисетей; предсказание поведения сетей при изменении структурных свойств.

Вприкладных исследованиях обычно применяют такие типичные для сетевого анализахарактеристики, как размер сети, сетевая плотность, степень центральности и т.п.253О «структуре сообщества» в сложной сети можно говорить тогда, когдасуществует фрагмент сети – группа узлов, которые имеют высокую плотность ребермежду собой, при том, что плотность ребер между отдельными фрагментами –низкая. Традиционный метод для выявления структуры сообществ – кластерныйанализ. Существуют десятки приемлемых для этого методов, которые базируются наразных мерах расстояний между узлами, взвешенных путевых индексах междуузлами и т.п. В частности, для больших социальных сетей наличие структурысообществ оказалось неотъемлемым свойством.К потере живучести информационной системы может привести разрыв связеймежду ее компонентами, например, при устранении из информационногопространства наиболее весомых компонент, то есть таких, которые имеют, допустим,наибольший коэффициент посредничества (betweenness).

Этот коэффициент дляконкретного узла сети определяется как сумма по всем парам узлов сети соотношенийколичества кратчайших путей между ними, проходящими через заданный узел, кобщему количеству кратчайших путей между ними.При анализе сложных сетей как и в теории графов исследуются параметрыотдельных узлов; параметры сети в целом; сетевые подструктуры.Параметры узлов сетиДля отдельных узлов выделяют следующие параметры:- входная степень связности узла – количество ребер графа, которые входят вузел;- выходная степень связности узла – количество ребер графа, которые выходятиз узла;- расстояние от данного узла до каждого из других;- среднее расстояние от данного узла до других;- эксцентричность (eccentrіcіty) – наибольшее из геодезических расстояний(минимальных расстояние между узлами) от данного узла к другим;- посредничество (betwetnness), показывающее, сколько кратчайших путейпроходит через данный узел;- центральность – общее количество связей данного узла по отношению кдругим;- уязвимость, рассматриваемая как уровень спада производительности сети вслучае удаления вершины и всех смежных ей ребер.Степень связности ki узла i – это количество ребер, соединенных с этойвершиной.Соответственно, средняя степень всей сети рассчитывается как среднее всех kiдля всех узлов сети.Как отмечено выше, в случае ориентированных сетей имеется две разновидностистепеней связности узла: выходная, соответствующая количеству исходящих изданного узла ребер, и входная, равная количеству заходящих в данный узел ребер.Общие параметры сетиДля расчета индексов сети в целом используют такие параметры, как: числоузлов, число ребер, геодезическое расстояние между узлами, среднее расстояние отодного узла к другим, плотность – отношение количества ребер в сети к возможномумаксимальному количеству ребер при данном количестве узлов, количествосимметричных, транзитивных и циклических триад, диаметр сети – наибольшее254геодезическое расстояние в сети, уязвимость, рассчитываемая как максимальнаяуязвимость всех вершин сети, ассортативность как мера корреляции между степенямиузлов и т.д.Существует несколько актуальных задач исследования сложных сетей с точкизрения живучести, среди которых можно выделить следующие основные:- определение фрагментов сети (клик, кластеров), в которых узлы связаны междусобой сильнее, чем с членами других подобных фрагментов;- выделение фрагментов сети (компонент связности), которые связаны внутри ине связаны между собой;- нахождение перемычек, т.е.

узлов, при изъятии которых сеть распадается нанесвязанные части.Распределение степеней связности узловВажной характеристикой сети является функция распределения степеней узловP(k ) , которая определяется как вероятность того, что узел i имеет степень ki = k Тоесть распределение степеней P(k ) отражает долю вершин со степенью k .Для ориентированных сетей существует распределение выходящей полустепениoutP (k out ) , и полустепени входной Pin (k in ) , а также распределение общей степениP io (k in , k out ) .

Последнее задает вероятность нахождения узла с входной полустепеньюk in и выходной полустепенью k out .весьма разноеСети, характеризующиеся разными P(k ) , демонстрируютповедение. P(k ) в некоторых случаях может быть распределениями Пуассона (P (k ) = e − m m k / k ! , где m – математическое ожидание), экспоненциальным ( P (k ) = e − k / m )или степенным ( P(k ) ~ 1/ k γ , k ≠ 0, γ > 0 ).Важной особенностью многих реальных сетей является распределение степенейузлов P(k ) по степенному закону.Сети со степенным распределением степеней связности узлов называютсябезмасштабными (scale-free).

Именно безмасштабныераспределения частонаблюдаются вреально существующих сложных сетях. При степенномраспределении возможно существование узлов с очень высокой степенью, чтопрактически не наблюдается в сетях с пуассоновым распределением.Путь между узламиЕсли два узла i и j можно соединить с помощью последовательности из mребер, то такую последовательность называют маршрутом (walk) между узлами i иj , а m называю длиной маршрута.Говорят, что узлы i и j связны, если существует маршрут между ними.Отношение связности транзитивно, т.е.

если узел 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-цикл определяется при этом как множество трех узлов с ребрами между каждойпарой узлов.