Library
|
Your profile |
Cybernetics and programming
Reference:
Gorlushkina N.N., Ivanov S.E., Ivanova L.N.
The generalized centrality method for analyzing network cyberspace
// Cybernetics and programming.
2019. № 2.
P. 55-64.
DOI: 10.25136/2644-5522.2019.2.23117 URL: https://en.nbpublish.com/library_read_article.php?id=23117
The generalized centrality method for analyzing network cyberspace
DOI: 10.25136/2644-5522.2019.2.23117Received: 25-05-2017Published: 27-05-2019Abstract: 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}, определенные по обобщённой центральности являются также лидерами по всем остальным центральностям.
Заключение
Анализ сетевого киберпространства на основе графовых моделей позволяет обнаруживать лидеров групп и сообществ, находить сплоченные группы и наглядно визуализировать результаты. Основными методам теории графов применяемых для сетей являются методы анализа центральностей для определения относительного веса или важности вершин графа. В киберпространстве социальных сетей используются методы анализа центральностей: по степени, по близости, по посредничеству, по радиальности, по эксцентричности, по статусу, Каца, собственного вектора, ссылочного ранжирования. Недостаток этих методов в том, что они основываются только на одном или нескольких свойствах участника сети. В работе на основе методов анализа центральностей предложен новый обобщенный метод центральностей, учитывающий такие свойства участника как популярность участника, важность и скорость распространения информации в сети. Приведена математическая модель метода обобщенной центральности. Выполнено сравнение результатов представленного метода с методами анализа центральностей. В качестве наглядного примера проанализирована группа сетевого киберпространства, состоящая из двадцати участников, представленная графовой моделью. Сравнительный анализ показал точность метода обобщенной центральности при учете сразу ряда факторов и свойств участника сети. References
1. Davern M. Social Networks and Economic Sociology: A Proposed Research Agenda for a More Complete Social Science // American Journal of Economics & Sociology. 1997. Vol. 56. Is. 3. p. 287–302.
2. Charu C. Aggarwal. Social Network Data Analytics. 2011. 520 p. 3. Fortunato S. Community Detection in Graphs // Phys. Rep. 2010. Vol.486. No. 3–5. p. 75–174. 4. Wasserman S., Faust K. Social Network Analysis: Methods And Applications. N. Y.: Cambridge University Press, 1994. 825 p. 5. Jensen D., Neville J. Data Mining in Social Networks // Proceedings of the National Academy of Sciences Symposium on Dynamic Social Network Analysis. 2002. p. 289–302. 6. Bonchi F., Castillo C., Gionis A., Jaimes A. Social Network Analysis and Mining for Business Applications // ACM TIST. 2011. Vol. 2 (3). p. 22–58. 7. Leskovec J., Backstrom L., Kumar R., Tomkins A. Microscopic Evolution of Social Networks // Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. N. Y., 2008. p. 462–470. 8. Inokuchi A., Washio T. A Fast Method to Mine Frequent Subsequences from Graph Sequence Data // Proceedings of the IEEE International Conference on Data Mining. 2008. p. 303–312. 9. Tantipathananandh C., Berger-Wolf T., Kempe D. A Framework for Community Identification in Dynamic Social Networks // Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. N. Y.: ACM Press, 2007. p. 717–726. 10. Ferlez J., Faloutsos C., Leskovec J., Mladenic D., Grobelnik M. Monitoring Network Evolution Using MDL // Proceedings of the International Conference on Data Engineering. 2008. p. 1328–1330. 11. Liu Z., Yu J., Ke Y., Lin X., Chen L. Spotting Significant Changing Subgraphs in Evolving Graphs // Proceedings of the 8th International Conference on Data Mining. 2008. p. 917–922. 12. Borgwardt K. M., Kriegel H.-P., Wackersreuther P. Pattern Mining in Frequent Dynamic Subgraphs // Proceedings of the IEEE International Conference on Data Mining. 2006. p. 818–822. |