Статья 'Метод обобщенной центральности для анализа сетевого киберпространства' - журнал 'Кибернетика и программирование' - NotaBene.ru
по
Меню журнала
> Архив номеров > Рубрики > О журнале > Авторы > О журнале > Требования к статьям > Редакция и редакционный совет > Порядок рецензирования статей > Политика издания > Ретракция статей > Этические принципы > Политика открытого доступа > Оплата за публикации в открытом доступе > Online First Pre-Publication > Политика авторских прав и лицензий > Политика цифрового хранения публикации > Политика идентификации статей > Политика проверки на плагиат
Журналы индексируются
Реквизиты журнала

ГЛАВНАЯ > Вернуться к содержанию
Кибернетика и программирование
Правильная ссылка на статью:

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

Горлушкина Наталия Николаевна

кандидат технических наук

Заведующая кафедрой интеллектуальных технологий в гуманитарной сфере, Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики (Университет ИТМО)

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
Другие публикации этого автора
 

 

DOI:

10.25136/2644-5522.2019.2.23117

Дата направления статьи в редакцию:

25-05-2017


Дата публикации:

27-05-2019


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


Ключевые слова:

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

Abstract: The subject of the research is the methods of network cyberspace analysis based on graph models. The analysis allows to find leaders of groups and communities, to find cohesive groups and visualize the results. The main methods of the graph theory used for cyberspace social networks are the methods of analyzing the centrality to determine the relative weight or importance of the vertices of the graph. There are known methods for analyzing centralities: by degree, by proximity, by mediation, by radiality, by eccentricity, by status, eigenvector, referential ranking. The disadvantage of these methods is that they are based only on one or several properties of the network participant. Based on the centrality analysis methods, a new generalized centrality method is proposed, taking into account such participant properties as the participant's popularity, the importance and speed of information dissemination in the cyberspace network. A mathematical model of a new method of generalized centrality has been developed. Comparison of the results of the presented method with the methods of the analysis of centralities is performed. As a visual example, a subgroup of cyberspace consisting of twenty participants, represented by a graph model, is analyzed. Comparative analysis showed the accuracy of the method of generalized centrality, taking into account at once a number of factors and properties of the network participant.


Keywords:

network cyberspace, community analysis methods, centrality method, graph model, social networks, definition of group leaders, weights of vertices, degree centrality, closeness centrality, betweenness centrality

  • Введение

Киберпространство является важной областью социальной активности людей, что связано с оборотом информации в компьютерных сетях: социальных сетях, региональных, ведомственных, корпоративных. Киберпространство объединяет граждан многих стран и культур, которые собирают и используют разнообразную информацию. Одной из наиболее важных проблем социальных сетей является определение лидеров групп и сообществ, нахождение сплоченных групп в киберпространстве [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}, определенные по обобщённой центральности являются также лидерами по всем остальным центральностям.

Заключение

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

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

Библиография
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
References
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.

Результаты процедуры рецензирования статьи

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

Рецензия на статью «Метод обобщенной центральности для анализа сетевого киберпространства»
Предметом данного исследования являются исследование сетевого киберпространства на основе графовых моделей.
Методология исследования Автором была предложена концепция анализа центральностей для определения относительного веса вершин графа, интерпретируемого как показатель лидерства в группе или сообществе задействованного киберпространства. На основе методов анализа центральностей предложен новый обобщенный метод централь-ностей, учитывающий такие свойства участника как популярность участника, важность и скорость распространения информации в сетевом киберпространстве.
Актуальность темы связано с тем, что киберпространство является важной областью социальной активности людей, что связано с оборотом информации в компьютерных сетях: социальных сетях, региональных, ведомственных, корпоративных. Киберпространство объединяет граждан многих стран и культур, которые собирают и используют разнообразную информацию. Одной из наиболее важных проблем социальных сетей является определение лидеров групп и сообществ, нахождение сплоченных групп в киберпространстве. Анализ сетевого киберпространства на основе графовых моделей позволяет обнаруживать лидеров групп и сообществ, находить сплоченные группы, анализировать связи участников сети и процессы распространения информации и наглядно визуализировать результаты
Научная новизна. Недостатком известных методов анализа центральностей является то, что они основываются только на одном или нескольких свойствах участника сети. Автором предложен новый обобщенный метод центральностей, учитывающий такие свойства участника как популярность участника, важность и скорость распространения информации в сетевом киберпространстве. Так же разработана математическая модель нового метода обобщенной центральности. Выполнено сравнение результатов представ-ленного метода с существующими методами. В качестве наглядного примера проанализирована подгруппа киберпространства, состоящая из двадцати участников. Сравнительный анализ, проведенный автором показал точность метода обобщенной центральности при учете сразу ряда факторов и свойств участника сети.

Стиль, структура, содержание статьи соответствует требованиям ведущих научных изданий.
Библиография представлена 12 современными источниками.
Выводы: Анализ сетевого киберпространства на основе графовых моделей позволяет обнаруживать лидеров групп и сообществ, находить сплоченные группы и наглядно визуализировать результаты. На основе методов анализа центральностей предложенный авто-ром новый обобщенный метод учитывает такие свойства как популярность участника, важность и скорость распространения информации в сети. Работа может быть интересна специалистам .связанным с сетевыми технологиями.


Ссылка на эту статью

Просто выделите и скопируйте ссылку на эту статью в буфер обмена. Вы можете также попробовать найти похожие статьи


Другие сайты издательства:
Официальный сайт издательства NotaBene / Aurora Group s.r.o.