Графовые модели в социальных сетях
Получив первоначальное представление об объекте исследований и приняв за основу методологию системного анализа – попробуем описать математически такой сложный социотехнический объект как социальная сеть.
Основные понятия и определения
Если мы сказали, что социальная сеть – это взаимодействующие агенты – то сразу напрашивается для ее описания – граф, как совокупность узлов и связей.
Исторически первым понятие графа-сети как совокупности вершин и связей ввел в 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)
Примером бинарных отношений в сфере социальных сетей являются отношения между подмножеством Агентов и Областями интересов.
Деревья. Связный неориентированный граф называется деревом, если он не имеет циклов.
Лес – определяют как граф без циклов, связные компоненты которого являются деревьями.
Маршруты, цепи и простые цепи.
Маршрутом в графе G называют такую конечную или бесконечную последовательность ребер., что каждые 2 соседних ребра имеют общую конечную точку. Циклический маршрут называют циклом.
Социальная сеть как мультиграф
Виртуальная социальная сеть, в которой взаимодействуют агенты, характеризуемые набором сведений об образовании, работе, интересах, электронных друзей, (называемых обычно профилем), а также активностей в обсуждаемых темах, записями в блогах и прочих характеристик, формально может быть описана мультиграфом.
Топологические характеристики сетей
Для анализа достигнутых характеристик связности сетевого как классического так и виртуального проекта применимы топологические показатели из теории графов, рассмотренные в [Давыденко].
Кластеризация. Присутствие связей между вершинами А и В, и между В и С приводит к связи между А и С. Или иначе. Если В имеет двух соседей по сети А и С, то они связаны друг с другом на основании их общей связи с В. В топологических терминах: существует высокая плотность треугольников АВС (в сети) и кластеризация может быть определена количественно, измерением этой плотности:
С ( I ) = 3 * (число треугольников на графе) / число связных троек вершин)
Альтернативное определение индекса кластеризации:
Сi = (число треугольников, соединенных с вершиной i) / (число троек, центрированных на i)
Индекс кластеризации в среднем по сети:
n
Cср = (1\n) ∑ Ci
i =1
Распределение степени. Степень вершины в сети – это число ребер соединенных с заданной вершиной. Определим pk как часть вершин в сети, которые имеют степень k. В случайном большом графе каждое ребро присутствует или отсутствует с разной степенью вероятности и распределения степени – биномиальное или пуассоновское. Далекие от распределения Пуассона распределения степени вершин в большинстве сетей искажены со скосом вправо – распределения имеют длинную хвостовую часть.
Данные о степени представляются формированием кумулятивной функции распределения:
Pk = ∑ pk
Эластичность сети. Степень эластичности сетей относится к распределению степени при удалении вершин. Большинство сетей основано на их связности, то есть существования путей между парами вершин. Если вершина удалена из сети, типичная длина этих путей увеличивается, и в конечном счете пары вершин станут разъединенными. Имеется ряд способов удаления вершин и различные сети показывают вариацию степени эластичности к этим способам. Можно случайно удалять вершину из сети или иметь цепь удаления определенного класса вершин (например, с самыми высокими степенями, так называемых NetWokers).
Исследование атак на Интернет-серверы с 326 тысячами страниц производилось Р.Альбертом {__}. Среднее расстояние вершина-вершина, как функция числа удаленных вершин, почти не изменялась при случайном удалении вершин (высокая эластичность). Целенаправленное удаление вершин с наиболее высокими степенями приводило к разрушению сети. Таким образом, было показано, что Интернет является высоко эластичной сетью по отношению случайного отказа вершин сети, но высокочувствителен к преднамеренной атаке на вершины с наиболее высокими степенями.
Приведенный пример из топологии классических вычислительных сетей относится и к социальным сетям.
Коэффициент корреляции. Вершина с высокой степенью корреляции имеет тенденцию быть соединенной (в среднем) с вершинами с низкой степенью, и наоборот. Для количественной оценки этого эффекта необходимо измерить коэффициент корреляции степеней смежных вершин в сети.
Структура сообщества. Разделяется группами вершин, имеющих высокую плотность ребер между ними с более низкой плотностью ребер между группами. Метод извлечения структуры сети – кластерный анализ. Метод, в котором приписывается сила связи парам вершин в сети, представляющих интерес. Каждой из 0,5 n (n-1) возможных пар сети из N вершин назначена такая «сила» (причем не только соединенных ребрами). Затем, начиная с вершины без ребер между любыми из них, прибавляются ребра в порядке уменьшения силы связи. Когда все ребра добавлены, все вершины соединены с другими – получается требуемая кластеризация. Приемлемые методы назначения силы связи включают взвешенные меры расстояния вершина-вершина, размеры максимального потока и взвешенных путевых индексов между вершинами.
Структура сообществ социальных сетей – важное свойство, на которое не всегда обращают внимание.
Электронные друзья - Облака - Активности
Социальная сеть, так же как и другие общественные, социальные, природные и галактические образования – явно неоднородна. Говорят, что большая часть массы вселенной сосредоточена в галактиках, звездных группировках и самих звездах. Также можно трактовать как проявление принципа или правила Парето – 80/20.
Аналогичную ситуация складывается и в социальных сетях. Для того, чтобы иметь возможность упорядочить и саму сеть и принципы и правила работы и общения в сетевой социальной системе, кроме профиля, заполняемого добровольно участником сети, постепенно каждый активный участник формирует свой круг электронных друзей, причастность к группам интересов и пр.
Электронные друзья и облака интересов
Электронные друзья с позиций теории графов – это дерево выделенных взаимодействующим в сети Актором из общего круга участников сети многоуровневых иерархических отношений. Как правило, определяют 3 круга друзей – 1 круг, 2 круг и 3 круг.
Круги могут отличаться правами доступа к личной информации, записям, публикуемым новостям и блогам, возможностями комментирования записей в блоги и сообщества, созданные инициатором – корнем дерева.
Причем – данные отношения демократичны и взаимны.
Традиционно, друзья из 1 круга обладают телефонной информацией и почтовыми адресами «электронного друга», имеют возможность комментировать записи, писать на стене и пр. детали и тонкости, облегчающие сетевое взаимодействие равноправных сторон.
|
|
|
|
|
С  ам
|
|
|
|
|
1 Круг
|
|
|
|
|
|
|
|
|
|
|
|
А 
|
|
|
В
|
|
С 
|
|
|
|
|
|
|
|
|
|
|
|
|
2 Круг
|
АА
|
АА
|
АА
|
|
В  В
|
В В
|
|
СС
|
СС
|
|
|
|
|
|
|
|
|
|
|
3 Круг
|
|
|
|
ВВВ
|
ВВВ
|
ВВВ
|
|
|
|
Рис. ___ Круги электронных друзей
|
Круги электронных друзей могут использоваться для рассылки извещений о новостях, изменениях, записях в блогах.
Следует заметить, что число E-друзей растет очень быстро. Для примера, в бытность лучших времен Моего Круга у Автора было порядка 60 электронных друзей в 1 Круге, и более 10 тысяч – в 3-ем.
Облака интересов – это установление бинарных отношений между Множеством Акторов и Множестом Интересов, обсуждаемых и циркулирующих в сети.
Причем интересы, такие как например Психология, Политика, Социология, Наука, Спорт, Книги – на главной странице сетевого ресурса показываются более крупным шрифтом, что получило наименование в данной среде – «облака».
|
Множество Акторов
|
|
Множество Интересов
|
|
|
|
|
Соответствие
|
|
|
|
|
|
|
|
|
|
|
ПОЛИТИКА
|
|
|
|
A 1
|
|
|
|
|
|
|
A 2
|
A 3
|
A 4
|
A 5
|
|
|
|
|
|
|
A
|
A
|
A
|
A
|
A
|
|
СОЦИОЛОГИЯ
|
|
|
|
A
|
A
|
A
|
A
|
A
|
|
|
|
|
|
|
|
…
|
|
|
|
|
ФИЛОСОФИЯ
|
|
|
A n
|
|
|
|
СПОРТ
|
|
|
|
|
|
|
|
|
|
|
|
КНИГИ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис. 2__. Множество Акторов и «облака» интересов
|
В терминах и на языке теории графов – данное соответствие – бинарное отношение.
Активности и рейтинги
Активности – это текущий индикатор происходящих в Сети событий и обсуждаемых тем.
Как правило, любая активность имеет свойство выгорать или «затухать».
Указание активности является очень полезным с точки зрения возможности выбора темы и вместе с рейтингом является основой механизма формирования групп в сети.
Метаязык описания социальной сети
Изложенный выше классический подход теории графов и множеств может послужить основой создания формального языка описания социальной сети, который становится особенно актуальным при постановке перед социальной сетью задач политической и структурной модернизации.
Классический язык программирования включает описание переменных и их типов, синтаксис и семантику языка.
Язык программирования может быть встроен в систему управления компьютером и его доступом в мировую сеть. Причем в связи с наблюдаемыми тенденциями молодых- ретивых (Google) интегрировать функции доступа в Сеть в программные оболочки – задача создания метаязыка приобретает глобальное значение.
В данной, безусловно пионерской работе, предпринимается попытка системного описания социально-сетевых ресурсов и метаязыка управления социальной сетью, который может представлять интерес для разработчиков программных систем и пакетов.
|
