Диссертация (1090614), страница 5
Текст из файла (страница 5)
1.20. В данном примереэлементы графа из пяти вершин и шести ребер представляются в видегоризонтальных и вертикальных отрезков.Рис. 1.20. Различные способы представления графа. а) вершины представлены ввиде точек, ребра – в виде прямых. б) вершины и ребра представлены в видесоответственно горизонтальных и вертикальных отрезков.Данной способ визуального представления графа был предложен в контекстезадачи разводки печатных плат [56].
Двусвязный неориентированный граф - этосвязный граф, не распадающийся на части при удалении любой вершины (и всехинцидентных ей рёбер). В работе [56] предложен линейный алгоритм построениятакого отображения для двусвязных планарных графов.37В [28] было доказано, что любой планарный граф может быть представлен втаком виде. И, в свою очередь, появился линейный алгоритм [60] построенияданного представления.1.2.2. Общее описание построения многополосного размещенияВ большинстве работ представление P (Определение 1.1) определяется втерминах видимости. Пусть задано множество горизонтальных отрезков,соответствующих вершинам графа.
Пара горизонтальных отрезков заданногомножества видна, если они могут быть соединены вертикальным отрезком так,чтобы он не пересекал остальные горизонтальные отрезки. Пара горизонтальныхотрезков заданного множества видна, если они могут быть соединенывертикальнойполосойненулевойширины,непересекающейдругихгоризонтальных отрезков.В [8] представление P (Определение 1.1) называется обзорным. Выделяютнесколькоосновныхтиповобзорныхпредставлений:слабоеобзорноепредставление, -обзорное представление и сильное обзорное представление.Слабое обзорное представление (w- обзорное представление) – такоепредставление вершин в виде непересекающихся горизонтальных отрезков и реберв виде вертикальных отрезков, при котором концы вертикального отрезка лежат насвязываемых горизонтальных отрезках, и этот вертикальный отрезок не пересекаетостальные горизонтальные отрезки.-обзорное представление – такое w-обзорное представление, при которомдва вершинных отрезка видны тогда и только тогда, когда соответствующие имвершины являются смежными.Сильное обзорное представление - такое w-обзорное представление, прикоторомдвавершинных отрезкавидны тогдаитолько тогда,когдасоответствующие им вершины являются смежными.Обзорное представление может быть использовано при размещении сетейвзаимосвязанных объектов с помеченными вершинами и ребрами.
Вершины сети38соответствуют исследуемым объектам, а ребра – связям между ними. Пометки навершинах и связях задают описания. Рассматривается задача отображенияподсетей на основе заданного множества объектов.Рассмотрим граф = (, ) без петель и с кратными ребрами, где –множество вершин, – множество ребер. Пометки на ребрах и вершинах заданыобъемлющими прямоугольниками. Наличие ориентации не имеет значения. Пустьзадано множество вершин 1 ⊆ .Тогда объектом визуализации будет служить граф ′ = ( ′ , ′ ) , где ′ ={ = (, ): ∈ 1 или ∈ 1 } , ′ = {: ∃ = (1, 2 ), ∈ ′ , = 1 или =2 }. Таким образом граф ′ содержит множество заданных вершин и связанных сними.
В работах [3, 11] предлагается использовать многополосное размещение, вкотором вершины из заданного множества представляются в виде горизонтальныхотрезков, пространство между которыми используется для размещения ребер и ихпометок (Рис. 1.21).Рис. 1.21. Фрагмент многополосного размещения: 1 , 2 – выделенныевершины, 1 , 2, 3, 4 – вторичные вершины.39Отрезки вершин выделенного множества размещаются друг под другом, чтов некоторых случаях может привести к трудночитаемым изображениям из-заналичия пересечения линий связей и выделенных объектов:• пересечение неизбежно появляется в случае наличия связи между заданнымивершинами, если они не являются соседними при размещении;• представление может стать трудночитаемым, когда вторичные объектысоединены с несколькими заданными вершинами, которые в размещении неявляются соседними.Для решения вышеперечисленных проблем предлагается использованиеслабого обзорного представления, что в случае с планарным графом будетгарантировать отсутствие пересечений между линиями связей и отрезками вершин.Врассмотренныхработахотсутствуютреализацияалгоритмовиформализованная процедура расположения вторичных объектов относительновыделенных вершин в контексте применения данного алгоритма к графамсоциальных сетей.1.3.Визуальный анализ структуры графа взаимодействующихобъектов на основе выделения «сообществ»1.3.1.Задача анализа графа на основе выделения «сообществ»Распознавание структуры, скрытой в реальных социальных сетях, являетсяключевой задачей, решение которой необходимо для понимания организациисложных сетей [1, 2, 15, 50].
Сложные системы обычно организуются в блоки,которые имеют определенные роли и функции. В представлении сети такие блокиявляются множеством вершин с высокой плотностью внутренних связей, в товремя как связи между блоками имеют сравнительно низкую плотность. Данныеблоки называются сообществами, или модулями, и встречаются в разнообразноммножестве структур взаимосвязанных объектов [20, 31, 58].40Правильноподобранноепредставлениепоможетвыявитьважнуюинформацию о сети, упростить восприятие и подчеркнуть скрытые структурныеособенности и особенности взаимосвязей объектов.
Возможны сети, разбитые насообщества с высокой плотностью связей внутри сообществ и низкой плотностьюсвязей между сообществами. Выделение сообществ является актуальной задачейтеории графов, которая формулируется как задача нахождения по заданномумультиграфу разбиения вершин на сообщества, при котором минимизируетсязаданная целевая функция. Под мультиграфом будет пониматься граф, у которогомежду парой вершин может быть более одной связи.На Рис. 1.22 приведен пример сети, разбитой на сообщества с высокойплотностью связей внутри сообществ и низкой плотностью связей междусообществами.Для использования алгоритмов выделения сообществ в задаче визуализацииграфа на плоскости требуется построение соответствующих геометрическихмоделей.Было разработано множество алгоритмов с использованием методов изразличных дисциплин, таких как физика, биология, информатика, прикладнаяматематика и социология [2, 31, 33].
Однако, не все алгоритмы надежны и могутбыть применены на практике.Рис. 1.22. Схема сети, разбитой на сообщества.41Граф взаимодействующих объектов - это модель социальной сети, анализструктурыкоторойявляетсяоднойизактуальныхзадачсовременныхинформационных технологий [1, 2, 15].Под социальной сетью [5] на качественном уровне понимается социальнаяструктура, состоящая из множества агентов (субъектов - индивидуальных иликоллективных, например индивидов, семей, групп, организаций) и определенногона нем множества отношений (совокупности связей между агентами, например,знакомства, дружбы, сотрудничества, коммуникации). Актуальность исследованиясоциальныхсетейобъясняетсятем,чтометодыизучениясоциальноговзаимодействия субъектов, основанные на использовании социальных сетей,базируются на понимании социальных феноменов главным образом через свойствавзаимосвязей между объектами сети.Активно разрабатываются различные методы анализа графов социальныхсетей [2, 15, 21, 22], которые позволяют выявлять структуры графа взаимодействиясубъектов, такие, например, как группы общения социальных сетей.
При этомвизуальные средства являются одним из методов анализа графа [75], в том числе ив совокупности с алгоритмами выявления сообществ [76], которые могутвыступать как дополнительные средства автоматического размещения привизуализации графов в прикладном программном обеспечении.Выделяют два типа графов социальных сетей. Обычно анализируют граф сисходно ненаправленными ребрами, описывающими постоянные связи объектовсоциальной сети, которого иногда называют «графом друзей».
Существует графконтактов объектов социальной сети, описывающий пересылку различного родаинформации между объектами. Этот, второй тип графа, содержит по своей природенаправленные ребра.Но для интересующего нас структурного анализа и выделения сообществвзаимодействия объектов сети граф второго типа можно рассматривать какненаправленный, заменив направленные ребра на ненаправленные, поскольку при42автоматическом размещении графа на плоскости построение соответствующейгеометрической модели учитывает только плотность связей между вершинами.Основной целью алгоритмов выделения сообществ в графах являетсяустановление внутренних свойств и взаимосвязей между вершинами, которыенедоступны посредством прямого анализа.Подробные обзоры по методам анализа социальных сетей, включая иструктурный анализ графов, содержатся в [1, 2, 5, 22].Следует отметить, что только в некоторых продуктах визуализации и анализаграфовприсутствуетодновременнаяподдержкавыделениясообществсвозможностью автоматического размещения на основе них [37, 49].Опишем типы алгоритмов, предложенных ранее для выделения сообществ.1.3.2.Алгоритмы, основанные на оценке характеристики «модулярность»Для оценки качества разбиения графа на сообщества в ряде работ [33, 50-54]было введено понятие «модулярность» (далее «модулярность Ньюмана-Гирвана»),которое должно, по мнению их авторов, описывать качество разбиения графа насообщества.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
