Если мы сказали, что социальная сеть – это взаимодействующие агенты – то сразу напрашивается для ее описания – граф G (V, E), как совокупность узлов-вершин (агентов) и связей. Выделяют две трактовки социальной сети – как социальной структуры и как ее специфической Интернет-реализации.
Исторически первым понятие графа-сети как совокупности вершин и связей ввел в 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 – конечной вершиной ребра.
Понятие графа можно расширить, если допустить, что пара вершин соединяется несколькими ребрами.
Связность и локальные степени. Число ребер, инцидентных одной вершине обозначают как
p (a) ,
и называют степенью графа.
Бинарное отношение. Бинарное отношение R определяется как соотношение a R b, которое выполняется для некоторых пар элементов заданного множества V. Бинарное отношение может быть представлено в виде графа с множеством вершин
G (R) = G(V)
Примером бинарных отношений в сфере социальных сетей являются отношения между подмножеством Агентов и Областями интересов.
Деревья. Связный неориентированный граф называется деревом, если он не имеет циклов.
Лес – определяют как граф без циклов, связные компоненты которого являются деревьями.