Доклад: Графовые модели в социальных сетях

Получив первоначальное представление об объекте исследований и приняв за основу методологию системного анализа – попробуем описать математически такой сложный социотехнический объект как социальная сеть.

Основные понятия и определения

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

Исторически первым понятие графа-сети как совокупности вершин и связей ввел в 1736 году Леонард Эйлер, который решил доказать, что прохожий не может обойти Кенигсберг (Калинград) используя лишь по одному разу каждый из семи городских мостов.

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

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

Рассматривается множество V, состоящее из соединенных некоторым образом точек. Множество V называют множество вершин и элементы v Í V — вершинами.

Граф G = G (V)
с множеством вершин есть некоторое семейство сочетаний или пар вида

E (a, b), a, b Í V,
указывающее, какие вершины считаются соединенными.

Полезным для дальнейшего рассмотрения является определение произведения 2 графов. Если даны 2 множества, V1иV2, то можно образовать множество всех пар

(v 1, v 2 ), v 1 Í V1, v 2 Í V 2
которое называется произведением и обозначается V 1 * V 2.
В этом случае каждая пара вершин (a, b) есть элемент произведения. Таким образом, можно сказать, что граф G с данными ребрами есть некоторое подмножество произведения V * V.

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

E = (a, b) = (b, a),
то говорят, что E есть неориентированное ребро; если же этот порядок существенен, то E называется ориентированным ребром. В последнем случае a называется также начальной вершиной, а b – конечной вершиной ребра.

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

Понятие графа можно расширить, если допустить, что пара вершин соединяется несколькими ребрами.

Связность и локальные степени. Число ребер, инцидентных одной вершине обозначают как

p (a) ,
и называют степенью графа.

Бинарное отношение. Бинарное отношение R определяется как соотношение

a R b,
которое выполняется для некоторых пар элементов заданного множества V. Бинарное отношение может быть представлено в виде графа с множеством вершин

G (R) = G(V)

Примером бинарных отношений в сфере социальных сетей являются отношения между подмножеством Агентов и Областями интересов.

Деревья. Связный неориентированный граф называется деревом, если он не имеет циклов.

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