Программные продукты и системы

Многие распределенные системы, в частности сети сотовой связи, компьютерные сети и Интернет, обладают развитой топологией и имеют в своей основе сложные социальные процессы. По мнению создателя технологии World Wide Web Тима Бернерса Ли, следующим этапом в развитии Всемирной паутины станет «Гигантский глобальный граф» [1]. Такой граф, в отличие от сети, связывающей компьютеры, и Всемирной паутины, связывающей документы, свяжет между собой людей и, благодаря семантическим технологиям, предоставит им сервисы более высокого класса.

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

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

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

Граф нечеткой социальной сети

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

На нечеткие социальные сети естественным образом распространяются понятия четких социальных сетей и предложенные ранее меры центральности, положения и принадлежности к подгруппам: центральность на основе степени; центральность по близости; центральность по посредничеству; центральность на основе собственных векторов; степень; плотность; обхват; диаметр; радиус; средняя длина пути; средняя длина цикла; коэффициент кластеризации [5].

Метрики социальной сети

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

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

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

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

.

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

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

Центральность по близости. Показатель центральности по близости характеризует центральность вершины на основе расстояния от центрального актора до других вершин графа.

Центральность актора определяется как величина, обратная сумме длин кратчайших путей от данного актора к остальным акторам:

,

где N – число вершин в графе.

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

Чем меньше число вершин, достижимых из вершины актора, тем ниже показатель центральности. Значение показателя уменьшается с увеличением расстояния между центральным актором и другими акторами.

Заметим, что показатель центральности по близости можно рассчитать только для связного графа. Неопределенность показателя для изолированных вершин, расстояние до которых бесконечно, является главным недостатком центральности по близости.

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

, где gjk– число кратчайших путей от j до k; gjk(ni) – число кратчайших путей от j до k, проходящих через ni.

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

Средняя длина пути рассчитывается как среднее арифметическое расстояний между центральной вершиной и остальными вершинами в графе:

.

Средняя длина цикла рассчитывается как среднее арифметическое длин всех циклов в графе. При этом целесообразно рассматривать только циклы длиной ³ 3.

Коэффициент кластеризации измеряет плотность подграфа, состоящего из вершин, находящихся на расстоянии единицы от центрального актора. Другими словами, это мера вероятности того, что «если А знает B, а B знает C, то A знает C» для фиксированной вершины B. Это эквивалентно процентному отношению замкнутых треугольников в окрестности центрального актора. Для вершин в полном подграфе (клике) коэффициент кластеризации будет равен 1. Для вершины в центре звезды коэффициент кластеризации примет нулевое значение.

Для вычислений будем использовать формулу плотности графа: , где N и E – число вершин и ребер в подграфе соответственно.

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

Плотность графа – отношение числа существующих ребер к возможным ребрам в графе.

Плотность для неориентированного графа вычисляется по формуле: .

Расчет для ориентированного графа производится по формуле: .

Заметим, что в мультиграфах плотность может принимать значение больше единицы.

Обхват графа – это длина кратчайшего цикла (³3) в графе.

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

.

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

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

Список литературы

1. Глобальный граф. // Поиск. - № 49(967). -2007.

2. Wasserman S., and Faust K. Social Network Analysis: Methods and Applications. – Cambridge University Press,1994.

3. Nair P.S. and Sarasamma S.T. Data Mining Through Fuzzy Social Network Analysis // North American Fuzzy Information Processing Society, 2007.

4. Берштейн Л.С., Боженюк А.В. Нечеткие графы и гиперграфы. – М.: Научный мир, 2005.

5. Holder L.B. and Cook D.J. Mining Graph Data. – Wiley, 2007.