Авт. обработка текстов на естественном языке и комп. лингвистика. Большакова (2014) (1185448), страница 69
Текст из файла (страница 69)
В настоящее времянаряду с традиционным теориями графов, систем и сетей масоового обслуживанияактивно развивается теория сложных сетей (от англ. – Complex Networks), в рамкахкоторой предлагаются подходы к решению вычислительно сложных задач,характерных для современных сетей.§ 3.1.Основы концепции сложных сетейОсновной причиной актуальности теории сложных сетей являются результатысовременных работ по описанию реальных компьютерных, биологических исоциальных сетей. Такие сети имеют характеристики, не свойственные сетям сравновероятной связностью узлов, а строятся на основе связных структур, степенныхраспределений и узлов-концентраторов.Представляющие интерес сети чаще всего разрежены – присутствует лишь малаячасть возможных ребер, соединяющих отдельные узлы. Поэтому сегодня особуюактуальность приобретают методы работы с разреженными матрицами.Действительно, практически все современные сети можно считать сложными.
Так,например, известная задача синтеза топологии сети допускает комбинаторныйподход, опирающийся на представление сети в виде конечного графа без петель икратных ребер, вершины которого соответствуют узлам сети, а ребра – линиям связи.Вместе с тем, использование методов перечисления графов для решения задачитопологической оптимизации считается неперспективнымм, так как необходимоиссследовать огромное количество возможных вариантов соединения узлов линиямисвязи. Например, в сети из 10 узлов существует 245 вариантов размещения линийсвязи (для 10 узлов теоретически возможно C102 =10 ⋅ 9= 45 линий соединений.
Каждая2из этих возможных линий связи может реально существовать – состояние «1», или несуществовать – состояние «0», то есть всего возможностей 245 ).Для меншего количества узлов (например, n = 3 ) линии связи, могут быть3⋅2реально посчитаны ( 2 2 = 8 ) вариантами (рис. 6.12).Рис. Часть VI.12. Варианты размещения линий связи при n = 3252Сложные сети обычно рассматриваются в абстрактном пространстве, в которомрасположение вершин не имеет значения. Для некоторых реальных типов сетей такоерассмотрение оправдано.Однако, существует множество систем, в которых расположение компонентвесьма важно, поскольку влияет на эволюцию сети.
Такие сети называютсягеографическими или пространственными. В географических сетях существованиепрямого соединения между вершинами может зависеть от многих ограничений, такихкак расстояние между ними, географический рельеф, территориальные ограничения ит.д. Модели, предназначаемые для представления таких сетей, должны учитывать этиограничения.§ 3.2.Параметры сложных сетейТеория сложных сетей как область дискретной математики изучаетхарактеристики сетей, учитывая не только их топологию, но и статистическиефеномены, распределение весов отдельных узлов и ребер, эффекты протекания,просачивания, проводимости в таких сетях тока, жидкости, информации и т.д.Оказалось, что свойства многих реальных сетей существенно отличаются от свойствклассических случайных графов.
Изучения таких параметров сложных сетей, каккластерность, посредничество или уязвимость напрямую относятся к теорииживучести, так как именно от этих свойств зависит способность сетей сохранять своюработоспособность при деструктивном воздействии на их отдельные узлы или ребра(связи).Несмотря на то, что в рассмотрение теории сложных сетей попадают различныесети – электрические, транспортные, информационные, наибольший вклад в развитиеэтой теории внесли исследования социальных сетей. Термин «социальная сеть»обозначает сосредоточение социальных объектов, которые можно рассматривать каксеть (или граф), узлы которой – объекты, а связи – социальные отношения.
Этоттермин был введен в 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 связны, если существует маршрут между ними.Отношение связности транзитивно, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
