Материал: bikkulov_as_chugunov_av_setevoi_podkhod_v_sotsialnoi_informa

−формальные отношения (власть и влияние);

−биологические отношения (родство, происхождение). Типы связей, отношений в свою очередь могут быть

−направленными (когда мы отмечаем направление связи между акторами);

−ненаправленными (когда важно зафиксировать только наличие связи между акторами);

−маркированными (означенными) (когда мы фиксируем положительные, отрицательные и нейтральные выборы);

−оценочными (когда мы измеряем интенсивность связи между акторами через частоту контактов, денежный торговый оборот между странами и др.).

Всоциометрических исследованиях, при построении социограмм (в том числе социограмм социальных сетей) используется понятийнокатегориальный аппарат, способы визуализации и математический аппарат теории графов. Основные положения теории графов изложены в следующем параграфе.

1.3.Теория графов

Для того чтобы свободно пользоваться сетевым подходом и понимать его терминологию, необходимо рассмотреть основы теории графов, на которой во многом базируется сетевая теория с математической точки зрения.

Начало теории графов относится к 1736 г., когда Леонард Эйлер решил задачу «О кенигсбергских мостах» (доказав принципиальную невозможность ее решения при классических условиях) и определил критерий существования в графе специального маршрута (т.н. «эйлерова цикла»), который проходит по всем ребрам графа, проходя по каждому ребру лишь единожды. Во времена Л. Эйлера в Кенигсберге (после 1945 г.

— г. Калининград) через р. Преголя были семь мостов между речными берегами и двумя крупными островами в русле. Задача о мостах звучала так: можно ли проложить такой маршрут прогулки, чтобы он проходил по каждому мосту один раз (при этом маршрут может начинаться и заканчиваться в разных точках)? Л. Эйлер изобразил два берега реки и острова точками, а мосты, соединяющие их, — линиями. Считается, что так получился первый граф, который получил название графа

кенигсбергских мостов.

Однако этот результат более ста лет оставался практически единственным результатом теории графов. В середине XIX в. инженер-

электрик Г. Кирхгоф разработал теорию графов для исследования электрических цепей, а математик А.Кэли использовал эту теорию для описания строения углеводородов. Таким образом, появившись при решении головоломок и занимательных игр (задачи о шахматном коне, о ферзях, "кругосветное путешествие", задачи о свадьбах и гаремах и т.п.), теория графов стала доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем.

В настоящее время теория графов используется для решения широкого круга вопросов — любую сеть вне зависимости от природы соотношений между объектами можно представлять в виде графа.

Основные понятия

Графом называется совокупность множества вершин (обозначаются обычно точками или окружностями) и множества связей (линий) соединяющих некоторые пары вершин.

Графом G = (X, A) называется совокупность двух множеств: множества вершин X и множества A неупорядоченных или упорядоченных пар элементов множества X — т.е. множества линий, связей, соединяющих некоторые пары вершин.

Неупорядоченная связь пары вершин (обозначаемая на графе простой линией) называется ребром, а упорядоченная (обозначаемая на графе стрелкой из одной вершины в другую) — дугой. Вершины, ребра и дуги графа называются его элементами.

Граф обычно обозначается символом G, вершины — X, а ребра — A. Таким образом стандартное обозначение графа — это G = (X, A).

Имеются разные типы графов. В зависимости от наличия (отсутствия)

элементов, графы бывают конечными, пустыми и нулевыми.

Конечным граф называется в том случае, если число его вершин конечно и не равно нулю.

Пустой граф — это граф, не содержащий ни вершин, ни ребер, т. е. X = и A = . Пустой граф обозначается G .

Нуль-граф — это граф, в котором нет ребер (A = ). Такой граф состоит только из изолированных вершин и обозначается G0.

Графы также могут быть ориентированными, неориентированными и смешанными.

Ориентированным (орграфом) G называется граф, у которого множество ребер (А) состоит только из дуг. Дуга обозначается линией со стрелкой.

Неориентированным (неографом) G называется граф, у которого множество связей А содержит только ребра, т.е. отсутствуют дуги.

Граф, в котором присутствуют и ребра (линии), и дуги (стрелки), называется смешанным.

Втеории графов используется понятия инцидентности и смежности, которое описывает специфику связей вершин и дуг.

Втом случае, если xn, xk — концевые вершины дуги ai, то обозначается, что вершины xn и xk инцидентны дуге ai или дуга ai инцидентна вершинам xn и xk.

Вершины xn, xk графа G = (X, A) называются смежными, если они инцидентны одному ребру.

Два ребра называются смежными, если они имеют общую вершину, т.е. инцидентны одной вершине.

Дуга, у которой начальная и конечная вершины совпадают, называется петлей. Например, в частом примере (при построении сетей научного цитирования ученых) могут быть петли, когда ученый цитирует собственные предыдущие работы.

Одинаковые пары в множестве А называются кратными (или параллельными) ребрами, т.е. кратные ребра связывают одну и ту же пару вершин. Такое может быть, например, если мы на одном графе социограммы отношений в группе отмечаем и позитивное отношение, и негативное. Тогда, имея неориентированный граф (т.е. если не обозначается направление негатива-позитива), то в случае, когда из двух человек один вполне позитивно настроен по отношению ко второму, а второй первого воспринимает негативно, то у нас будут два параллельных ребра — и позитивное, и негативное. Это будет значить, что в отношениях между этими двумя людьми не все в порядке.

Граф G = (X, A), у которого существует хотя бы одна пара вершин, соединяемых кратными (параллельными) m ребрами, называется

мультиграфом, а максимальное m — мультичислом графа G. Так, в

приведенном выше примере с неоднозначным отношением двух людей в группе, эта неоднозначность делает граф отношений в группе мультиграфом с мультичислом 2 (у нас есть два параллельных ребра между этими людьми).

Локальной степенью вершины i неографа [обозначается d(xi)]

называется число, равное количеству ребер, инцидентных данной вершине (иначе говоря, локальная степень вершины неориентированного графа — это количество связей-линий этой вершины с другими).

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

Вершина графа называется висячей, если ее степень равна единице (т.е., например, при построении сетей дружбы в группе висячая вершина будет соответствовать человеку, с которым дружит только один человек из рассматриваемой группы).

Вершина графа называется изолированной, если ее степень равна нулю. В примере отношений в группе изолированная вершина соответствует аутсайдерам группы — формально они входят в группу, но с ними никто не дружит, и они сами тоже ни с кем не дружат.

Для ориентированного графа (орграфа) вводятся понятия полустепени исхода и полустепени захода.

Полустепенью исхода вершины xi — d0(xi) называется количество дуг (стрелок), исходящих из этой вершины.

Полустепенью захода вершины xi — dt(xi) называется количество дуг (стрелок), входящих в эту вершину.

Для того, чтобы определить граф, его нужно задать. Существует несколько способов задания графов:

−геометрический способ − диаграмма (в социометрии при отображении отношений между людьми и группами, это называется социограмма); в этом случае вершины графа изображаются точками или кружками, а связи между ними — линиями или стрелками;

−теоретико-множественное представление графов (граф описывается перечислением математических множеств вершин и дуг);

−задание графов соответствием (в этом случае описание графов состоит в задании множества вершин X и некоего соответствия, которое показывает, как между собой связаны вершины);

−матричное представление графов (граф может быть задан с помощью матриц или списков смежности, матриц инциденций и списка концов ребер).

Матрица смежности — это квадратная матрица А=||aij|| размерностью n×n, где n — число вершин графа, которая однозначно определяет отношение между вершинами графа.

Приведем некоторые примеры матриц и графов (примеры взяты из учебного пособия Л. И. Федосеевой «Дискретная математика»7). Ориентированный граф, например, может быть задан такой матрицей смежности:

Рис. 1. Матрица смежности ориентированного графа

По матрице смежности можно найти характеристики вершин. Так, сумма элементов i-й строки матрицы дает полустепень исхода вершины xi, а сумма элементов i-го столбца дает полустепень захода вершины xi. Например, полустепень исхода и полустепень захода вершины x1 в приведенном примере равны:

d0 (x1) = 2, dt (x1 ) = 3.

Неориентированный граф может, например, быть задан такой матрицей смежности:

Рис. 2. Матрица смежности неориентированного графа

Для неориентированного графа матрица А является симметричной относительно главной диагонали, а для ориентированного — нет.

По матрице смежности неографа можно найти характеристики вершин. Так, сумма элементов i-й строки (или i-го столбца) матрицы дает степень i-й вершины неографа. Например, степень вершины x3 неографа G3 равна:

d(x3) = 3.

В случае графа с кратными ребрами в соответствующей клетке матрицы смежности А указывается кратность соответствующего ребра или его вес.

7 Федосеева Л.И. Дискретная математика: курс лекций. Пенза: 2012. С. 80—87.

Рис. 3. Матрица смежности неориентированного графа (граф с кратными ребрами)

Матрица инциденций представляет собой прямоугольную матрицу В=||bij|| размером n×m, где n — количество вершин графа, а m — количество дуг графа.

Для ориентированного графа каждый элемент матрицы инцидентности определяется следующим образом:

bij = 1, если xi является начальной вершиной дуги aj; bij = -1, если xi является конечной вершиной дуги aj;

bij = 0, если xi не является концевой вершиной дуги aj или если aj является петлей. В некоторых случаях, чтобы отличать петли, они обозначаются любым другим числом (обычно берут 2).

Поскольку каждая дуга инцидентна двум различным вершинам, за исключением того случая, когда дуга образует петлю, то каждый столбец либо содержит один элемент, равный 1 и один — равный -1, либо все элементы равны 0. В случае петли стоит либо ноль, либо, например, 2.

Рис. 4. Матрица инцидентности графа

Для неорграфа строки матрицы инцидентности будут соответствовать вершинам графа, а столбцы — его рёбрам. Элементы матрицы инцидентности В=||bij|| определяются следующим образом:

bij = 1, если xi инцидентна ребру aj, bij = 0, в противном случае.

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

Рис. 5. Список концов ребер для орграфа

По списку концов ребер можно построить соответствующую таблицу инцидентности. Каждый столбец этого списка соответствует столбцу матрицы с тем же номером. Аналогично можно выполнить обратную процедуру.

Виды графов и подграфов

Полным графом Gn (n N) называется граф с n вершинами без петель, кратных и противоположных дуг (ориентация безразлична), у которого каждая вершина соединена со всеми остальными. Частным видом полного графа также является граф, состоящий из одной вершины.

Симметрическим графом G называется граф, если для любой его дуги (xi, xk) существует противоположно ориентированная дуга (xk, xi), т.е. все его ориентированные связи взаимны, двусторонни.

Полным симметрическим графом G, называется граф, в котором каждая вершина (xi) соединена со всеми остальными двунаправленными дугами.

Антисимметрическим графом G называется граф, если ни у одной дуги (xi, xk) не существует противоположно ориентированной дуги (xk, xi), т.е. все его ориентированные связи однонаправлены. В антисимметрическом графе нет петель.

Полным антисимметрическим графом (турниром) G называется граф, в котором каждая вершина (xi) соединена со всеми остальными однонаправленными дугами. Второе название этого графа происходит от того, что результаты соревнований, построенных по турнирному принципу, где каждый играет с каждым и ничья не предусмотрена, можно представить именно в виде такого графа.

Изоморфные графы. В ряде случаев один и тот же граф геометрически можно изобразить различными способами. Такие графы называются изоморфными (рис. 6).

16

Рис. 6. Изоморфные графы

Геометрической (планарной) реализацией называется геометрический граф, изоморфный заданному.

Иногда не так легко понять, одинаковы ли графы, изображенные разными чертежами. На практике предварительно определяют некоторые параметры обоих графов. Такими параметрами могут быть число вершин, число ребер, число компонент связности и др. Даже если все параметры у графов совпали, это не гарантирует, что графы изоморфны. Так, на рис. 7 приведены два графа, у которых все параметры (количество вершин и дуг) совпадают, и тем не менее они различны.

Рис. 7. Неизоморфные графы

Геометрический граф называют правильно реализованным (правильным графом), если его дуги не пересекаются (кроме как в вершинах графа) при изображении на плоскости.

Рассмотрим графы G1 и G2, изображенные на рис. 8. Граф G1 не является правильно реализованным, граф G2 — правильный. Так как графы G1 и G2 изоморфны, то G2 — правильная реализация G1.

Рис. 8. Изоморфные графы (G2 — правильная реализация)

Плоским или планарным называется граф, если существует его правильная планарная реализация (без пересечения на плоскости ребер и дуг).

17

Взвешенным называется граф, если его элементам приписаны количественные характеристики. В простейшем случае ребру может быть приписан вес в виде длины ребра, а вершине — в виде степени ее значимости.

Деревом называется конечный, связный граф, не имеющий циклов. При этом количество ребер в дереве всегда меньше количества вершин на единицу, т.е. если дерево состоит из шести вершин (рис. 9,а), то нетрудно посчитать, что количество ребер в таком графе будет пять.

Рис. 9. Графы типа «дерево»:

а - неориентированное дерево; б - ориентированное дерево; в - лес из трех деревьев

Лесом называется несвязный граф без циклов. Связные компоненты леса являются деревьями (рис. 9,в).

Регулярным графом (или графом, регулярным степени r) называется граф, у которого все вершины имеют одну и ту же степень.

Связность графов

Важной задачей, для чего и применяется представление связей в виде графов, является установление связей между различными элементами графов.

Маршрутом (путем), соединяющим вершины xi и xk, является последовательность ребер (дуг) от вершины xi до xk, в которой конец одного ребра (дуги) является началом другого. При этом вершина xi считается начальной, a xk — конечной вершиной маршрута (пути).

Замкнутый маршрут — это такой маршрут (путь), когда его начальная вершина совпадает с конечной, т.е. в этом случае образуется цикл.

Цепью называют незамкнутый маршрут (путь), в котором все ребра (дуги) попарно различны (не повторяются). При этом любые две различные вершины дерева можно соединить единственной (и притом простой) цепью.

Путь называют минимальным (максимальным), если его длина является минимальной (максимальной)8.

Две вершины неографа считаются связанными, если существует маршрут, соединяющий эти вершины.

Связный неограф — это граф, в котором между любыми двумя вершинами существует маршрут, соединяющий эти вершины.

Если неограф не связный, то множество его вершин можно разделить на непересекающиеся подмножества, каждое из которых содержит все связанные между собой вершины, и вместе с инцидентными им ребрами образует связный подграф.

Орграф называется сильносвязным или сильным, если любые две его вершины достижимы друг для друга, т.е. для любых его двух вершин xi и xj найдется путь из xi в xk, и путь из xk в xi.

Орграф называется односторонне-связным или односторонним, если для любых его двух вершин (xi и xk) найдется путь либо из xi в xk, либо из xk в xi, или оба пути существуют одновременно (но оба пути существуют при этом не для всех вершин).

Орграф называется слабо связным или слабым, если для любых двух различных вершин графа существует, по крайней мере, один неориентированный маршрут (т.е. мы при поиске маршрута пренебрегаем направлением дуг в графе).

Орграф называется несвязным, если хотя бы для одной пары вершин орграфа не существует неориентированного маршрута, соединяющего эти вершины.

При исследования социальных сетей и сетевых сообществ используется понятие плотность сети.

Плотность сети — это отношение числа имеющихся в графе связей к максимально возможному. Плотность сети представлена числовыми значениями от 0 до 1, где значение «1» соответствует ситуации, когда каждый из членов сообщества связан со всеми другими членами сообщества (полный граф), а ноль, когда совокупность состоит из одиночек, не связанных между собой. В социометрической матрице аналогом данного показателя является «сплоченность».

По признаку связности можно классифицировать и подграфы.

8 Градосельская Г.В. Сетевые измерения в социологии: учебное пособие. М.:

Новый учебник, 2004. С. 204—206.