Метод обобщенной центральности для анализа сетевого киберпространства

Горлушкина Наталия Николаевна кандидат технических наук Заведующая кафедрой интеллектуальных технологий в гуманитарной сфере, Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики (Университет ИТМО) 197101, Россия, г. Санкт-Петербург, ул. Кронверкский Пр., 49 Gorlushkina Natalia Nikolaevna PhD in Technical Science Head of the Department of Intellectual Technologies in the Humanities, St. Petersburg National Research University of Information Technologies, Mechanics and Optics 197101, Russia, g. Saint Petersburg, ul. Kronverkskii Pr., 49 nagor.spb@mail.ru Иванов Сергей Евгеньевич кандидат физико-математических наук доцент, кафедра интеллектуальных технологий в гуманитарной сфере, Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики 197101, Россия, г. Санкт-Петербург, Кронверкский проспект, 49 Ivanov Sergei Evgenievich PhD in Physics and Mathematics Associate Professor, Department of Intelligent Technologies in the Humanitarian Sphere, St. Petersburg National Research University of Information Technologies, Mechanics and Optics 197101, Russia, g. Saint Petersburg, ul. Kronverkskii Pr., 49 sivanov@mail.ifmo.ru Другие публикации этого автора

Иванова Любовь Николаевна аспирант, кафедра технологии приборостроения, Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики 197101, Россия, г. Санкт-Петербург, ул. Кронверкский Пр., 49 Ivanova Lubov Nikolaevna graduate student, Department of Theoretical and Applied Mechanics, St. Petersburg National Research University of Information Technologies, Mechanics and Optics 197101, Russia, Saint Petersburg, Kronverkskii pr., 49, aud. 203 ln2305@yandex.ru Другие публикации этого автора

• Введение

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

Анализ сетевого киберпространства на основе графовых моделей позволяет обнаруживать лидеров групп и сообществ, находить сплоченные группы, анализировать связи участников сети и процессы распространения информации и наглядно визуализировать результаты ^[3,4].

Графовую модель сетевого киберпространства можно представить в математической форме^[5-7]:

`G=(v,r),`

где v - множество вершин графа, r - множество ребер графа.

Участники сети являются вершинами графа, а ребра представляют связи между ними.

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

Рисунок 1. Графовая модель группы сетевого киберпространства

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

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

• Методы анализа центральностей

Рассмотрим методы анализа центральностей и применим их для анализа графовой модели, представленной на рисунке 1.

Центральность по степени (Degree Centrality) определяется как количество связей вершины и записывается математически в форме:

`Cd(v)=deg(v)`

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

Центральность по степени для вершин по порядку в графе на рисунке 1 равна:

Cd= {6, 6, 6, 5, 7, 5, 6, 5, 6, 6, 6, 6, 6, 6, 7, 8, 8, 5, 5, 5}.

Отсортированный по важности список участников сети имеет вид:

{17, 16, 15, 5, 14, 13, 12, 11, 10, 9, 7, 3, 2, 1, 20, 19, 18, 8, 6, 4}.

Наибольшую важность имеют два участника сети с номерами:{16, 17}.

На рисунке 2 представлена графовая модель для центральности по степени. Для каждого участника сети определена важность и графически представлена диаметром вершины.

Рисунок 2. Графовая модель для центральности по степени.

Центральность по близости (Closeness Centrality) определяет, как быстро распространяется информация от участника сети. Кратчайший путь по графу d определяет расстояние между двумя участниками сети (i,j). Она рассчитывается как величина обратная удаленности вершины:

`Cc(v)=(n-1)/(sum_(n=1) d_(ij))`

Центральность по близости для вершин по порядку в графе на рисунке 1 равна:

Cc= {0.513514, 0.542857, 0.59375, 0.527778, 0.59375, 0.527778, 0.527778, 0.558824, 0.558824, 0.513514, 0.558824, 0.59375, 0.542857, 0.575758, 0.59375, 0.612903, 0.59375, 0.5, 0.527778, 0.558824}.

Отсортированный по скорости распространения информации список участников сети имеет вид:{16, 17, 15, 12, 5, 3, 14, 20, 11, 9, 8, 13, 2, 19, 7, 6, 4, 10, 1, 18}.

Наибольшая скорость распространения информации от участника сети с номером: {16}.

Центральность по посредничеству (Betweenness Centrality) определяет важность участника сети при распространении информации. Она определяется как число кратчайших путей между всеми парами участников, которые проходят через рассматриваемого участника:

`Cb(v)=0.5 sum_(s!=i) sum_(t!=i) (G_(st)(v_i))/(G_s_t)`

где `G_(st)` - количество кратчайших путей из вершины `v_s` к вершине `v_t` ,

`G_(st)(v_i)` - количество кратчайших путей из вершины `v_s` к вершине `v_t`, проходящих через вершину `v_i `

Центральность по посредничеству для вершин по порядку в графе на рисунке 1 равна:

Cb= {6.6, 5.87897, 7.64484, 8.74643, 15.2667, 3.56349, 5.56349, 4.18016, 8.75913, 6.875, 8.15238, 10.2698, 5.68452, 6.35873, 9.60079, 15.1595, 10.8607, 3.02183, 5.92262, 4.89087}.

Отсортированный по важности участника сети при распространении информации список участников сети имеет вид:{5, 16, 17, 12, 15, 9, 4, 11, 3, 10, 1, 14, 19, 2, 13, 7, 20, 8, 6, 18}.

Наибольшая важность участника сети при распространении информации для участника с номером: {5}.

Центральность по радиальности (Radiality Centrality) определяется расстоянием до вершин и диаметром окрестности.

Центральность по радиальности для вершины i вычисляется через окрестность диаметра `g_i` для вершины i с помощью следующей формулы:

`Cr(v)=(sum_(j)(d-d_(ij)+1))/(d(n-1))`

где `d_(ij)` расстояние от вершины i до вершины j в окрестности `g_i` ,

d - диаметр окрестности `g_i`

Центральность по радиальности для вершин по порядку в графе на рисунке 1 равна:

Cr= {0.684211, 0.719298, 0.77193, 0.701754, 0.77193, 0.701754, 0.701754, 0.736842, 0.736842, 0.684211, 0.736842, 0.77193, 0.719298, 0.754386, 0.77193, 0.789474, 0.77193, 0.666667, 0.701754, 0.736842}.

Отсортированный по радиальности список участников сети имеет вид:

{16, 17, 15, 12, 5, 3, 14, 20, 11, 9, 8, 13, 2, 19, 7, 6, 4, 10, 1, 18}.

Наибольшая радиальность у участника с номером: {16}.

Центральность по эксцентричности (Eccentricity Centrality) определяется величиной, обратной максимальному расстоянию до вершины:

`Ce(v)=1/m_(i)`

где `m_i` - максимальное расстояние от вершины `v_i` ко всем другим связанным вершинам

Центральность по эксцентричности для вершин по порядку в графе на рисунке 1 равна:

Ce= {0.333333, 0.333333, 0.5, 0.333333, 0.333333, 0.333333, 0.333333, 0.333333, 0.333333, 0.333333, 0.333333, 0.333333, 0.333333, 0.333333, 0.333333, 0.333333, 0.5, 0.333333, 0.333333, 0.333333}.

Отсортированный по эксцентричности список участников сети имеет вид:

{17, 3, 20, 19, 18, 12, 16, 15, 14, 13, 11, 10, 9, 8, 7, 6, 5, 4, 2, 1}.

Наибольшая эксцентричность у участников сети с номерами: {3, 17}.

Центральность ссылочного ранжирования (PageRank Centrality) определяется путем подсчета важности ссылок на вершину:

`Cpr(v)=x_i=b sum_(j=1)^n a_(ij) (x_j)/(l_j)+(1-b)/n`

где `sum_(j=1)^n a_(ij)`- количество вершин, соединенных с вершиной j,

b- доля участия удаленных вершин.

Центральность ссылочного ранжирования для вершин по порядку в графе на рисунке 1 равна:

Cpr= {0.0505882, 0.0503478, 0.0496177, 0.0493386, 0.0512773, 0.049226, 0.0503508, 0.0488884, 0.0500094, 0.0501424, 0.0500401, 0.0499584, 0.0495168, 0.0497676, 0.0507312, 0.0517958, 0.0516391, 0.0488435, 0.049136, 0.048785}.

Отсортированный по центральности ссылочного ранжирования список участников сети имеет вид:{16, 17, 5, 15, 1, 7, 2, 10, 11, 9, 12, 14, 3, 13, 4, 6, 19, 8, 18, 20}.

Наибольшая центральность ссылочного ранжирования у участника с номером: {16}.

Центральность Каца (Katz Centrality) определяется количеством всех вершин, которые могут быть соединены:

`Ck(v)=x_i=b sum_(j=1)^n a_(ji)(x_j+1)`

где b - коэффициент затухания.

Центральность Каца для вершин по порядку в графе на рисунке 1 равна:

Ck= {2.43336, 2.46231, 2.6155, 2.21583, 2.70001, 2.24538, 2.45527, 2.33026, 2.55063, 2.51055, 2.53206, 2.56198, 2.67534, 2.62732, 2.87871, 3.08615, 3.11859, 2.38159, 2.29907, 2.3593}.

Отсортированный по центральности Каца список участников сети имеет вид:

{17, 16, 15, 5, 13, 14, 3, 12, 9, 11, 10, 2, 7, 1, 18, 20, 8, 19, 6, 4}.

Наибольшая центральность Каца у участника с номером: {17}.

Центральность по статусу (Status Centrality) определяется количеством соединенных вершин:

`Cs(v)=x_i=b sum_(j=1)^n a_(ij) (x_j+b)`

Центральность по статусу для вершин по порядку в графе на рисунке 1 равна:

Cs= {0.00115635, 0.00117923, 0.00134261, 0.000973547, 0.00137066, 0.00100449, 0.00116814, 0.00109779, 0.00127676, 0.00123734, 0.0012597, 0.00129302, 0.00141872, 0.00136883, 0.00157949, 0.00174226, 0.00177754, 0.0011647, 0.00107481, 0.0011313}.

Отсортированный по центральности статуса список участников сети имеет вид:

{17, 16, 15, 13, 5, 14, 3, 12, 9, 11, 10, 2, 7, 18, 1, 20, 8, 19, 6, 4}.

Наибольшая центральность статуса у участника с номером: {17}.

Центральность по собственному вектору (Eigenvector Centrality) определяется как сумма центральностей соседних вершин, поделенных на константу:

`Cev(v)=x_i=1/l sum_(j) x_j=1/l sum_(j=1)^n a_(ij) x_j`

где `a_(ij)` - элемент матрицы смежности для вершин графа равен 1, если вершины i и j соединены и равен 0 если не соединены.

l-наибольшее собственное значение,

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

Центральность по собственному вектору для вершин по порядку в графе на рисунке 1 равна:

Cev= {0.0433355, 0.0437758, 0.0528677, 0.0353534, 0.0507128, 0.0368908, 0.0426414, 0.042369, 0.0494251, 0.047534, 0.0487807, 0.0508136, 0.0583498, 0.055747, 0.0642794, 0.0702966, 0.0722693, 0.0475646, 0.0423869, 0.0446066}.

Отсортированный по центральности собственного вектора список участников сети имеет вид:

{17, 16, 15, 13, 14, 3, 12, 5, 9, 11, 18, 10, 20, 2, 1, 7, 19, 8, 6, 4}.

Наибольшая центральность по собственному вектору у участника с номером: {17}.

• Метод обобщенной центральности

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

Представлена новая математическая модель обобщенной центральности в виде:

`Cq(v_i)=(sum_(s!=i) sum_(t!=i) (G_(st) (v_i))/G_(st))/(6 max sum_(v_s) sum_(v_t) (G_(st (v_i))/G_(st)))+ (deg(v_i) sum_j d_(ij)+(n-1)max(deg(v_j)) )/(3 sum_j d_(ij) max(deg(v_j))) `

где

`d_(ij)` - кратчайший путь по графу между вершиной i и вершиной j,

`G_(st)` - количество кратчайших путей из вершины `v_s` к вершине `v_t` ,

`G_(st) (v_i)` - количество кратчайших путей из вершины `v_s` к вершине `v_t` , проходящих через вершину `v_i`

Обобщенная центральность для вершин по порядку в графе на рисунке 1 равна:

Cq= {0.673384, 0.6736, 0.739835, 0.68634, 0.947917, 0.573176, 0.658511, 0.603525, 0.745169, 0.679388, 0.731921, 0.797149, 0.669354, 0.701968, 0.824208, 0.997661, 0.893383, 0.546242, 0.624685, 0.619043}.

Отсортированный список участников сети имеет вид:

{16, 5, 17, 15, 12, 9, 3, 11, 14, 4, 10, 2, 1, 13, 7, 19, 20, 8, 6, 18}.

Наибольшие обобщенную центральность имеют участники сети с номерами:{16, 5, 17}.

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

Рисунок 3. Графовая модель для обобщенной центральности

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

Cq= {16, 5, 17, 15, 12, 9, 3, 11, 14, 4, 10, 2, 1, 13, 7, 19, 20, 8, 6, 18}

Cd= {17, 16, 15, 5, 14, 13, 12, 11, 10, 9, 7, 3, 2, 1, 20, 19, 18, 8, 6, 4}

Cc= {16, 17, 15, 12, 5, 3, 14, 20, 11, 9, 8, 13, 2, 19, 7, 6, 4, 10, 1, 18}

Cb= {5, 16, 17, 12, 15, 9, 4, 11, 3, 10, 1, 14, 19, 2, 13, 7, 20, 8, 6, 18}

Cr= {16, 17, 15, 12, 5, 3, 14, 20, 11, 9, 8, 13, 2, 19, 7, 6, 4, 10, 1, 18}

Ce= {17, 3, 20, 19, 18, 12, 16, 15, 14, 13, 11, 10, 9, 8, 7, 6, 5, 4, 2, 1}

Cpr= {16, 17, 5, 15, 1, 7, 2, 10, 11, 9, 12, 14, 3, 13, 4, 6, 19, 8, 18, 20}

Ck= {17, 16, 15, 5, 13, 14, 3, 12, 9, 11, 10, 2, 7, 1, 18, 20, 8, 19, 6, 4}

Cs= {17, 16, 15, 13, 5, 14, 3, 12, 9, 11, 10, 2, 7, 18, 1, 20, 8, 19, 6, 4}

Cev= {17, 16, 15, 13, 14, 3, 12, 5, 9, 11, 18, 10, 20, 2, 1, 7, 19, 8, 6, 4}

Результаты показывают, что первые три лидера сети с номерами {16, 5, 17}, определенные по обобщённой центральности являются также лидерами по всем остальным центральностям.

Заключение

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

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