Freeman [1] предложил три различных интуитивных понятий центральности, а именно: степени, близость, промежуточная центральность, которые в основном используются для определения ключевых игроков в социальной сети. Bonacich [2] [3] предложил собственный вектор центральности для нахождения относительного значения узла, который используется для определения влияния узла на соседние узлы. Everett и др. [4] в своей работе, расширили меры центральности такие как: степень, близость и промежуточность с целью применения их к группам и классам, а также физическим лицам. UCINET - инструмент для анализа социальных сетей был выпущен Everett и др. [5] с большинством количеством необходимых метрик SNA для анализа данных.

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

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

Рисунок 2.1 - пример сети

2. Метрики соседства (Neighborhood metrics)

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

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

2.1 Степень (Degree)

Степень [6] узла показывает сколько соседей имеет данный узел.

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

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

Вычислим степень каждого узла для сети на рисунке 2.1. Результаты показаны в таблице 2.1.

Таблица 2.1 - общие, законные и мошеннические степени.

Из таблицы видно, что узел A имеет самую высокую степень в сети. Причем узел А имеет связи с 5 законными узлами и 1 мошенническим. Это мошеннические и легитимные (законные) степени.

2.2 Треугольники (Triangles)

Треугольником [6] в сети является подграф, состоящий из трех узлов, которые связаны друг с другом. Данный метод показывает влиятельный эффект тесно связанных групп узлов. Узлы, которые входят в состав группы (треугольника), зависят от убеждений, интересов, мнений, и так далее из этой группы.

2.3 Плотность (Density)

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

Она вычисляется по формуле.

Где M и N число ребер и узлов в сети соответственно.

Вычислим плотность каждого узла для сети на рисунке 2.1, результат показан в таблице 2.2.

Таблица 2.2 - плотность каждого узла в сети

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

2.4 Реляционный классификатор (Relational Neighbor Classifier)

Relational Neighbor Classifier [6] использует предположение, в котором говорится, что узлы имеют склонность принадлежать к одному и тому же классу. Если два узла связаны, они как правило, демонстрируют аналогичное поведение. Апостериорная вероятность класса для узла N, который принадлежит к классу С вычисляется следующим образом:

Где ? ? представляет собой окрестность узла n, w (n, ) - вес связи между n и и Z представляет собой коэффициент нормализации, чтобы убедиться, что все вероятности в сумме дают единицу.

Рассмотрим пример сети, изображенный на рисунке 2.2, где F и NF представляют собой мошеннические и не мошеннические узлы соответственно.

Рисунок 2.2 - схема сети

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

Поскольку обе вероятности необходимо подводить к 1, Z равна 5, так что вероятности становятся:

Таким образом, центральный узел является мошенническим с вероятностью 2/5 = 0,4 или 40%, и законным с вероятностью 3/5 = 0,6 или 60%.

Определим Relational Neighbor Classifier для графа на рисунке 2.1.

Результаты приведены в таблице 2.3.

Таблица 2.3 - демонстрация Relational Neighbor

Высокое значение Relational Neighbor Classifier указывает на высокую вероятность того, что узел является мошенническим.

2.5 Вероятностный реляционный классификатор (Probabilistic Relational Neighbor Classifier)

Вероятностный реляционный классификатор [6] является простым расширением реляционного классификатора, где апостериорная вероятность класса для N-ого узла, который принадлежит классу C рассчитывается следующим образом:

Обратите внимание, что суммирование выполняется по всей окрестности узлов. Вероятности Р может быть результатом локальной модели, или предварительно нанесенной сетевой модели. Рассмотрим схему на рис 2.3.

Рисунок 2.3 - схема сети

Расчеты принимают следующий вид:

Так как обе вероятности необходимо подводить к 1, Z равна 5, так что вероятности становятся:

Таким образом, центральный узел является мошенническим с вероятностью 0,45 или 45%, и законным с вероятностью 0,55 или 55%.

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

3. Метрики центральности (Centrality metrics)

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

3.1 Степень центральности (Degree Centrality)

Степень центральности [1] определяется как число прямых связей или соединений с узлом. Узел с более высоким значением степени центральности часто рассматривается как центр и активный субъект в сети. В террористических и преступных сетях, указывает на то, что узел является «властным»; это такой тип человека или сайта, который может быстро распространить информацию среди других людей. Не обязательно, что узел с самой высокой степенью центральности является лидером в сети. Вообще социальная сеть G представляется в виде матрицы смежности А.

Степень центральности i-ого узла в сети может быть определена как

Где ( , ) это элемент в матрице смежности А в [i,j] положении. N - общее количество узлов в сети. (N-1) является коэффициентом нормализации.

3.2 Геодезический путь (Geodesic Path)

Геодезический путь или кратчайший путь определяет минимальное расстояние между двумя узлами в сети. Ключевой вопрос в мошенничестве: на какое расстояние удалены мошеннические узлы в сети от целевого узла? Если мошеннический узел находится в близком соседстве, мошенничество может оказать влияние на этот узел.

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

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

Таблица 2.4 - демонстрация геодезических путей

3.3 Близость (Closeness centrality)

Центральность по близости [1] выражает, насколько близко узел расположен к остальным узлам сети. Центральность по близости (Closeness centrality) является показателем того, насколько быстро распространяется информация в сети от одного узла к другим, то есть насколько близок рассматриваемый узел ко всем остальным узлам сети.

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

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

Близость по центральности i-ого узла в сети может быть определена следующим образом

Где ( ) расстояние или длина пути между двумя узлами I и J.

Определим близость для каждого узла для сети на рисунке 2.1. Результаты показаны в таблице 2.5.

Таблица 2.5 - значения близости для каждого узла

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

3.4 Промежуточность (Betweenness Centrality)

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

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

Промежуточность узла в сети может быть определена следующим образом:

Где это общие кратчайшие пути между двумя узлами j и k, и ( ) это общие кратчайшие пути между j и k, которые проходят через i узел. Для нормализации значений используются коэффициенты (N-1) (N-2).

Определим промежуточность каждого узла для сети на рисунке 2.1. Результаты расчетов приведены в таблице 2.6.

Таблица 2.6 - значения близости для каждого узла

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

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

Рисунок 2.4 - Иллюстрация промежуточности между сообществами узлов

3.5 Теоретический центр графа (Graph theoretic center)

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

4. Алгоритмы коллективного вывода (Collective Inference algorithms). Групповые показатели центральности

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

Они имеют три характеристики:

• Связанные экземпляры (Related instances): экземпляры, которые должны быть (например, веб-страницы, сообщения электронной почты) явно или неявно связаны между собой.

• Классификатор (Classifier): для классификации экземпляра (например, веб-страницы), базовый классификатор использует нереляционные функции (например, слова в странице) и реляционные функции (например, наиболее распространенные метки класса среди других страниц, связанных с текущей). Классификаторы, которые были использованы для этой цели:

сети Байеса, сети Маркова и логистическая регрессия.

• Коллективный вывод (Collective inference): алгоритм коллективного вывода используется для обновления меток класса (или условных вероятностей), которые затем используются для пересчета реляционных значений-признаков.

4.1 Алгоритм PageRank

социальный сеть анализ мошенничество

Алгоритм PageRank [10] разработан Пейджем и Брином в 1999 году и лежит в основе известного алгоритма поисковой системы Google для ранжирования веб-страниц. Это поисковый алгоритм ранжирования с использованием гиперссылок в Интернете. Зависит от числа внешних ссылок на данную страницу и от их веса.

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

PageRank узла в сети может быть определена следующим образом:

Где - узлы, подключенные к узлу и ( ) является общими ссылками, исходящие к узлу b. () это PageRank от узла b.

Для сети на рисунке 2.1 попробуем применить алгоритм PageRank. Результат работы алгоритма показан в таблице 2.7.

Таблица 2.7 - демонстрация работы PageRank

PageRank для оценки примера на рисунке 2.1 вычисляется, не выделяя мошеннические метки (PageRank ) и с акцентом на мошенничество ( PageRank ). Самый высокий рейтинг присваивается узлу А при применении PageRank , поскольку узел А имеет самую высокую степень в сети. И далее, при применении PageRank узлы с наивысшим рейтингом - это узлы D, F, E. Это не удивительно, так как эти узлы изначально были определены как мошеннические. Обратите внимание на то, что законный узел G имеет более высокий рейтинг, чем мошеннический узел I. Узел G получает высокий рейтинг мошенничества, что указывает на то, что этот узел зависит от влияния мошеннических узлов в его окрестности.

4.2 Выборки Гиббса (Gibbs sampling)

Выборки Гиббса [6] представляют собой процедуру коллективного вывода, которая использует локальный классификатор для определения апостериорной вероятности класса для инициализации меток узлов в сети.

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

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

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

5. Методы сбора данных