Методика статического поиска скрытых групп в атрибутированных коммуникативных сетях

УДК 004.3

МЕТОДИКА СТАТИЧЕСКОГО ПОИСКА СКРЫТЫХ ГРУПП В АТРИБУТИРОВАННЫХ КОММУНИКАТИВНЫХ СЕТЯХ

© 2012 г. А.В. Пушенко, А.Г. Самойлов, РА. Хади

ФГНУ НИИ «Спецвузавтоматика», FGNU NII «Specvuzavtomatika»,

Ростов-на-Дону Rostov-on-Don

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

Ключевые слова: социальная сеть; многокомпонентность; скрытые группы; атрибутивность; неформальные лидеры.

In the present work the model of attributed communicative network is described (the mathematical representation of multicomponent social networks). For this model the decomposition process is determined, allowing to divide the network into components. The main objective of the work is a presentation of hidden group search algorithm, based on the idea of hierarchy in an organized group. This paper analyzes the metrics, allowing search of the informal leaders. Given the leaders hidden groups are then detected by clustering.

Keywords: social network; multicomponent; hidden groups; attributive; informal leaders.

Введение

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

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

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

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

Анализ существующих публикаций показывает, что для коммуникативных сетей существует два метода поиска скрытых групп: по динамической связности и статический [1 - 5], каждый из которых имеет свои достоинства, недостатки и использует различные трактовки понятия скрытой группы. Многие методы основываются на слишком простых и оттого слишком жестких критериях поиска скрытых групп, зачастую не отвечающих ограничениям реальных данных о коммуникативных сетях [1, 3] и не рассматривающих многокомпонентные сети. К недостаткам динамиче-

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

Атрибутированная коммуникативная сеть

Коммуникативная сеть в общем случае - это совокупность узлов и коммуникаций между ними.

Расширим модель коммуникативной сети до модели атрибутированной коммуникативной сети, добавив к описанию множества акторов и информационных потоков между ними наборы атрибутов для каждого узла сети. Атрибутом назовем объект, имеющий 2 свойства: признак и расшифровку признака. При этом получаем, что коммуникативная сеть является совокупностью нескольких коммуникативных сетей, каждая из которых имеет собственный признак - именно этот признак и является признаком атрибута.

Формально коммуникативная сеть с неориентированными связями, имеющими вес, и акторами, имеющими атрибуты, описывается следующим образом:

£ = (Р, А, В, D, w),

где Р = | рг|/ = 1, п| - множество акторов; А = |( pi, рк), (рк, pi) | 1 < i, к < п} - множество связей; ^ - функция силы связей, w : А 0, +с»); В = | Ь^]' = 1, к | -множество признаков;

i = 1, п, j = 1, к, I

dij - значение признака Ь^ для актора Рг I

Схема построения матрицы D рис. 1.

приведена на

D = <! d„

S=S1 uS2 =

сеть S =

S2 =(P2, A2,B2, D2, ^А2

) , И P = P U P2

А = Aj u A2,

Bi

B2/Bj

Pj

P2/PJ

Dj

матрица значений признаков.

Композицией коммуникативных сетей называют

В = В1 и В2, а матрица значений признаков D получается из D1 и D2 следующим образом:

1. В матрицу D1 добавляются строки, соответствующие акторам из Р2 \ Р1. При этом в новые строки вносится информация о значении признаков из В1 п В2для этих акторов из матрицы D2. Получаем матрицу D1'.

2. К полученной матрице D1' добавляем столбцы, соответствующие признакам из В2 \ В1. При этом в новые столбцы вносится информация о значении этих признаков для акторов из Р2 \ Р1 . Получаем матрицу D .

Рис. 1. Получение матрицы признаков при композиции сетей

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

Представление социальной сети в виде социоматрицы и графа

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

Для социальной сети £ = (Р, А), где Р = |рг |/' = 1, п| -

множество акторов, а А = | (Рг, рк )}с Р х Р - множество связей, социоматрицей будет матрица

Р=( ) _ =11 (Р', Рк)е А;

{г'к),,к=1,п, Г'к | 0, (рг, рк) г А.

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

w(Рг, Рк X (Рг, Рк ) 6 А; о, (Рг, Рк) г А.

В данной статье используются социоматрицы Р и атрибутированной неориентированной

коммуникативной сети £ = (Р, А, В, D) с функцией

силы связей w : А ^ (0, +с»), Р = | Рг | г = 1, п |,

А = | (Рг, Рк),(Рк, Рг )}с Р х Р . Социоматрица Р применяется для поиска центральности по степени по формуле Бонацича, а задание - для поиска кластеров с помощью алгоритма /£2_модификация.

Представление социальной сети с использованием графов [7] является интуитивно понятным, оно удобно для определения центральностей в социальной сети и применения методов поиска подгрупп, а также для визуализации сетей. Изображение графа, представляющего социальную сеть, называют социо-граммой.

Rw =

k=1,n , Г'к

0

Пусть коммуникативная сеть задается как £ = (Р, А), где Р = | р= 1, п | - множество акторов, а А = { (, рк)} с Р х Р - множество связей,

отношение на множестве Р .

Построим задание атрибутированной коммуникативной сети £ = (Р, А, В, D) с функцией силы связей

w : А ^ (0, +с»). Пусть граф G = (V, Е) имеет множество вершин V = | vi | i = 1, п} и пусть функция Ф: Р ^ V отображает множество акторов на V по следующему закону: V/' = 1,п : ф(pi) = vi. Тогда (vi, vk) е Е » (pi, рк) е А , и отображение ф сохраняет отношения. Функция силы связей w переходит в весовую функцию f: Е 0, , т. е. f ^ ,vk) = w(pi,рк).

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

Представление коммуникативной сети с помощью графа использовано для подсчета центральности по посредничеству по формуле Фримана с помощью алгоритма Брандса.

Декомпозиция атрибутированной сети, заданной социоматрицей

Пусть дана атрибутированная социальная сеть £ = (Р, А, В, D), заданная социоматрицей R , множеством признаков В = { Ь1, Ь2,..., Ьк} и матрицей

D = ( dij) ___Произведем декомпозицию соци-

V > п=1,п,]=1,к

альной сети £, выделив из нее подсеть, состоящую из всех акторов сети £, имеющих ненулевое значение признака Ь], и связей между ними. По определению

должна быть получена атрибутированная социальная сеть £1 =(Р1, А1, В, D1), такая что Р1 с Р , А1 с А ,

Л = 1, |Р1|: d1,y. * 0 и Л/'(рг е Р \ Р1): dij = 0.

Множество акторов Р1 выделяется по признаку: dij * 0 ^ р1 е Р1. Множество связей А1 - с помощью полученного ранее множества акторов Р1 по признаку: ((рг, рк) е А) & ((рг е Р ) || (рк е Р)) ^ (рг, рк) е А) . Таким образом, если социальная сеть задана социо-матрицей R или Rw, то при декомпозиции социомат-

рица подсети £1 = (Р1, А1, В, D1) состоит из элементов,

расположенных на пересечении строк и столбцов, соответствующих акторам Р1 (рис. 2).

R =

f]k

'kk

R={ Pi, Pj, Pk}

J

r II r 4 rik

r j rj rjk

rki rkj rkk

^ R1 =

рI, Р], рк}

Рис. 2. Социоматрица подсети

При этом номера строк и столбцов в исходной социоматрице и в результирующей будут соответствовать разным акторам. Таким образом, при реализации декомпозиции необходимо помимо социоматриц хранить и множества акторов.

Поиск неформальных лидеров

Теория социолога Карен Стивенсон гласит, что в любом обществе всегда существует неформальная сетевая структура, в которой люди связаны определенными ролями, а в каждой организации могут существовать три типа неформальных лидеров: связные (перевалочные базы), брокеры (вратари) и пограничники (измерители пульса) [8].

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

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

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

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

r

r

r

r

r

r

r

ное положение в структуре сети, а личный авторитет и влияние. Оставим для рассмотрения только лидеров первого и второго типов.

Центральность по степени

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

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

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

п

ХСР (Рк) = £ Ср (pi )гкг , где Р - матрица смежности

г=1

для неориентированной сети, X - константа, необходимая для наличия ненулевого решения уравнения. Приходим к матричному уравнению ХСР = РСР , где

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

СР,а, р (Рк ) = Е(а + РСР,а,р (Рг ))Гкг ,

г=1

в матричной форме: СР а р -рРСР а р = аР1, где 1 -это вектор, состоящий из единиц. Следовательно,

Сй,а,р=а(I -ßR)-1 R1.

Центральность по посредничеству

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

Кратчайшим путем в коммуникативной сети £ будем называть кратчайший путь в невзвешенном графе, матрицей инцидентности которого является Р - этот граф повторяет граф сети £ с точностью до весов дуг. Для определения центральности по посредничеству актора Рк используется формула

n-1 n

cb (Pk) = E E by (PkЬ где b„ (Pk) =

i=1 j=i+1

, и ст„ -

это количество кратчайших путей, связывающих Рг и

Рj, а у (Рк) - число геодезических линий между Рг и

Р, которым принадлежит Рк . Значение СВ

зависит от размера сети, в которой оно вычисляется. Фриман [10] доказал, что максимальное значение,

которое может принимать CB (pk), равно

n2 - 3n + 2

Таким образом, после нормирования центральность по посредничеству вычисляется по формуле

C B(Pk) =

n-1 n

2 E E bj

i=1 j=i+1

n2 - 3n + 2

Параметр а влияет только на длину вектора

СР а р, и его нужно выбирать таким образом, чтобы

п 2

Е СР а р (Рг) = п . Параметр р нужно выбирать по

г=1

значению таким, чтобы (1 -|р|) 1 было приблизительным значением радиуса действия метрики, т. е. предполагаемого количества уровней соседей, влияющих на центральность актора. Если р = 0, то рассматриваются только прямые связи акторов, соседи первого уровня. Для поиска центральностей по степени положим р = +1, тогда (1 -|р|) 1 = 2 , т. е. будет рассматриваться два уровня, соседних с актором [9].

Поиск кратчайших путей

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

Рг и р^ , а также количество путей аг]- (Рк), проходящих через заданную вершину Рк .

Для решения задачи поиска кратчайших путей в графе применяются различные алгоритмы: алгоритм Дейкстры, Флойда - Уоршелла, Беллмана - Форда, Джонсона. Самыми эффективными считаются алгоритмы Дейкстры (сложность составляет 0(п2 + т) при п - количестве вершин графа, т - количестве ребер) и Флойда - Уоршелла (сложность - 0(п3)), однако они определяют каждый по одному кратчайшему пути между каждой парой вершин графа, что не

ст

соответствует поставленной задаче поиска всех кратчайших путей между всеми парами вершин.

Эффективные алгоритмы подсчета центральности по посредничеству предложены Брандсом в работе [11].

Путем из вершины 5 в вершину t называют чередующуюся последовательность ребер и вершин 5,(5,v1),v1,...,vn,t),t, начинающуюся с 5 и закачивающуюся в t, и обозначаются как (5, Г) -путь. Алгоритм Брандса основывается на определении парных зависимостей:

Vs, v е V: 5

w:

dist (s,w)=dist (s,v)+1

где ст(5, t) - число кратчайших (5, ^ -путей, ст(5,11V) -число кратчайших (5, ^ -путей, в которые входит вершина V, отличная от 5 и /, показатель централь-

ст

ности по посредничеству равен СВ (V) = £ —т—\

5,vеV 5, t)

и при этом определено, что 0 = 0. Для вычисления СВ (V) = £ 8 (51V) необходимо повторять вычисление

5еV

8(51V) для всех 5 е V . Обоснование алгоритма Брандса находится в [11]. Для невзвешенных графов его сложность равна 0(п • т). Для получения в результате С 'В (рк) необходимо разделить полученный результат на 2 и нормировать, как показано в формуле (1).

Неформальные лидеры в атрибутированной сети

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

которых искать связный, и подсети с |В| = 2, в которых искать брокеров.

Формальное описание поиска связных:

£____£ц,£12,...,£1 р, при этом £и =(Р,А,Вь,

D1i , W I A1i ) И \B 1i| = 1

тогда множество акторов-

Подсети для поиска брокеров получаем с помощью попарного объединения сетей SXi, которые имеют непустые пересечения: Br = у Brij-, а

i, j=\Tp, Pli nPi j

Brij - это множество акторов-брокеров в композиции сетей Svi и Svj.

Определение кластеров

Следующим после выявления множества Sv u Br неформальных лидеров шагом является определение соответствующих им скрытых групп. Признаком, который позволяет определить их, является то, что помимо наличия в подгруппе иерархии, коммуникации в ней должны быть более плотными, чем между членами группы и акторами, лежащими вне группы. Среди имеющихся методов поиска сплоченных групп наиболее подходящим для коммуникативных сетей, связи в которых имеют вес, является поиск по метрикам сплоченности групп (алгоритмы «IS» (Iterative Scan), «IS2» (Iterative Scan2) [3]). В результате применения этих алгоритмов к каждому актору сети получают набор пересекающихся сплоченных групп. Для того чтобы определить сплоченные группы, содержащие акторов из Sv u Br, необходимо либо найти все сплоченные группы и выбрать из них только необходимые, либо применить модифицированный алгоритм «¿^модификация» [12], который по данной вершине seed, графу G и метрике сплоченности W(C) получает сплоченную группу, содержащую вершину seed.

Разработка автоматизированной системы поиска скрытых групп

Программа, реализующая полученный метод, представляет собой библиотеку функций. Для разработки библиотеки использован язык программирования C++, стандартная библиотека шаблонов STL, для построения изображений - библиотека Graphviz. На рис. 3 приведен пример результата работы программы: произведен поиск скрытой группы в социальной сети, состоящей из 6 акторов, были найдены 2 неформальных лидера и скрытая группа и 4 акторов.

связных Sv = у Svi , где Svi - это множество связ-

i=1, p

ных в сети SH .

Рис. 3. Результат работы системы, где 2 и 4 - акторы из скрытой группы, 1 и 3 - неформальные лидеры, 21 и 12 - обычные акторы

Выводы

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

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

Вторым критерием является сплоченность скрытых групп. Для поиска сплоченных групп, содержащих неформальных лидеров, был использован алгоритм IS2 и 15"2_модификация. Этот метод позволил производить поиск пересекающихся сплоченных групп, имеющих внутреннюю иерархию.

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

Литература

1. Discovering hidden groups in communication networks / J. Baumes [et al.]. 2nd NSF/NIJ Symposium on Intelligence and Security Informatics (ISI 2004), Tucson, AZ, June 11 - 12, 2004.

2. On Hidden Groups in Communication Networks / J. Baumes [et al.] // Technical Report 05-15, Rensselaer Polytechnic Institute, 2005.

3. Finding Communities by Clustering a Graph into Overlapping Subgraphs / J. Baumes [et al.] // International Conference on Applied Computing (IADIS 2005), Algarve, Portugal, Feb. 22 - 25, 2005.

4. Efficient Identification of Overlapping Communities / J. Baumes [et al.] // IEEE Symposium on Intelligence and Security Informatics (ISI 2005), Atlanta, GA, May 19 - 20, 2005.

5. Locating Hidden Groups in Communication Networks Using Hidden Markov Models / M. Magdon-Ismail [et al.] // Intelligence and Security Informatics: First NSF/NIJ Symposium, ISI 2003, Tucson, AZ, USA, June 2 - 3, 2003. Proceedings.

6. Пушенко А.В, Аграновский А.В. Динамический поиск скрытых групп в социальных сетях // Х междун. науч.-практ. конф. «Информационная безопасность-2008» / ТРТУ. Таганрог, 2008. C. 234 - 236.

7. Knoke D., Kuklinski J.H. Network analysis // SAGE. 1996. P. 96.

8. Stephenson K. The quantum theory of trust: Power, Networks and the Secret Life of Organisations. FT Prentice Hall. 2006. P. 256.

9. Bonacich P. Power and centrality: a family of measures // The American journal of sociology. 1987. № 5. P. 1170 - 1182.

10. Freeman L. A set of measures of centrality based on be-tweeness // Sociometry. 1977. № 40. P. 35 - 41.

11. Brandes U. A faster algorithm for betweenness centrality // The journal of mathematical sociology. 2001. № 25. P. 163 -177.

12 Пушенко А.В., Хади Р.А. Модель межпользовательского взаимодействия в компьютерных сетях для идентификации скрытых групп // Материалы VII Междунар. науч.-практ. конф. «Моделирование. Теория, методы и средства» (Ч. 3). Новочеркасск, 2007. C. 76 - 78.

Поступила в редакцию 1 июля 2011 г.

Пушенко Анна Виталиевна - аспирант, Южный Федеральный Университет, младший научный сотрудник ФГНУ НИИ Спецвузавтоматика. Тел. (863)201-28-17. E-mail: pushenkoanna@gmail.com

Самойлов Андрей Геннадьевич - научный сотрудник ФГНУ НИИ Спецвузавтоматика. Тел. (863) 201-28-17. E-mail: andrew.samoilov@gmail.com

Хади Роман Ахмедович - канд. техн. наук, доцент, директор ФГНУ НИИ Спецвузавтоматика. Тел. (863) 20128-17. E-mail: nosecureinfo@gmail.com

Pushenko Anna Vitalievna - post-graduate student, Southern Federal University, junior research scientist in FGNU NII Specvuzavtomatika. Ph. (863)201-28-17. E-mail: pushenkoanna@gmail.com

Samoylov Andrey Gennadyevich - research scientist of FGNU NII Specvuzavtomatika. Ph. (863) 201-28-17. E-mail: andrew. samoilov@gmail.com

Khady Roman Ahmedovich - Candidate of Technical Sciences, associate professor, director of FGNU NII Specvuzavtomatika. Ph. (863) 201-28-17. E-mail: nosecureinfo@gmail.com