Диссертация (1148128), страница 27
Текст из файла (страница 27)
В сетевых исследованиях центральность применяется дляопределения влиятельных лиц в организациях, выявления ключевых узловинфраструктуры,используемыхпространственнойразметкидорог(spaceилизданийвтеориираспространителейsyntax),языкаболезней,информации и другого. Многие идеи и термины в рамках центральности какметодапришлиизобщественныхнаукиотражаютсоциологическоепроисхождение274. Примеры подобных терминов — сплоченность, солидарность,членство275.
Влиятельные или важные акторы понимаются по-разному, поэтомуразличные меры отражают различные аспекты центральности. Мы рассмотримосновные метрики центральности: степень узла или валентность (degree) и еёвариации для взвешенного графа — взвешенная степень узла (weighted degree),для ориентированного графа — входящая (in-degree) и исходящая (out-degree)степеньузла;промежуточнаяцентральностьилицентральностьпопосредничеству (betweenness centrality); центральность по близости (closenesscentrality); центральность по престижу (eigenvector centrality).
Многие термины неимеют устоявшихся русскоязычных эквивалентов.Самой простой мерой центральности является степень узла, мы будемиспользовать такую запись: . Она показывает количество инцидентных узлуребер, другими словами — количество, связей, которые имеет узел. Существуетопределенная зависимость между размером графа E и степенью:1 = ∑ 2(14)=1274Newman M. E.
J. Networks. An Introduction. Oxford University Press, 2010. 168 p.Hansen D. L., Shneiderman B., Smith M. A. Analyzing social media networks with NodeXL: Insights from a ConnectedWorld. Morgan Kaufmann, 2010. P. 3275116Половина суммы всех связей между узлами составляет совокупность реберграфа. К примеру, связь между узлом 2 и узлом 5 мы считаем дважды: сперва,суммируя все связи узла 2, а затем все связи узла 5.Зачастую степень узла понимают как атрибут узла, показывающийустойчивость системы или показывающий риск заражения (в исследованияхраспространения болезней). Для графа = (, ) с n вершин степень узла ()для узла определяется как: () =,−1(15)где – степень узла.Если граф ориентированный, то степень узла означает две отдельные мерыцентральности — входящую и исходящую.
Входящая степень есть сумма всехребер, в которых данный узел выступает в роли цели. () =−1(16)где – входящая степень узла.Исходящая степень есть сумма всех ребер, в которых данный узелвыступает в роли источника. () =−1(17)где – исходящая степень узла.Взвешенная степень узла во взвешенных графах суммирует все связи узла,но также оперирует к атрибуту веса, или интенсивности, и умножает его на связь.Для графа ≔ (, ) со взвешенными ребрами { ∶ ∈ } взвешенная степеньузла () для узла определяется как: () = ∑{ ∶ ∈ }(18)117Подсчет степени узла для всех узлов V в графе займет Θ( 2 ) времени вплотной матрице смежности, в разряженной матрице смежности для ребер E этозаймет Θ() времени.Более того, степень узла можно всегда получить из значений элементов вматрицы смежности.
Для ненаправленных графов: = ∑ = ∑ =1Длянаправленныхграфов(19)=1входящаяиисходящаястепеньузлапредставляют соответственно сумму по строками и столбцам:= ∑ ;=1= ∑ (20)=1Следует отметить, что данная мера центральности прекрасно демонстрируетколичественные характеристики сети, её топологию, ранжирует узлы и кластерыпо степени интенсивности, а также предопределяет возможность узнать центр ипериферию графа по узлам и кластерам.В нашем примере на рисунке 6 можно заметить, что наибольшая степеньузла у узла A – 11 и узла E – 11.
Они имеют максимальное количество связей сдругими узлами. Чуть менее центральными являются узлы F (9 связей), C (8связей), M (7 связей). Степень узла дает представление о структуре сети, однакоданная мера центральности имеет и недостатки. Она указывает, насколькоколичественно централен узел, но не раскрывает, как именно узел расположен всети.Воплощая в себе идеи брокериджа (брокеража; brokerage) и маклерствапромежуточная центральность указывает на характер сети, где именно узлывыполняют сетевую роль мостов или посредников, не отвечая на вопрос118«насколько?», а показывая «как» центральны различные узлы.
Положение узла наключевых связях было описано в 1977 г. Л. Фриманом в статье «A Set of Measuresof Centrality Based on Betweenness»276.Рисунок 6 – Цвет и размер узлов обозначает средняя степень узла.Промежуточная центральность — это мера центральности узлов в графе(существует также промежуточная центральность ребер (edge betweenness)), черезкоторые проходят кратчайшие пути из любого узла в любой другой при их276Freeman L.C.
A set of measures of centrality based on betweenness // Sociometry. 1977. Vol. 40. P. 35—41119чередовании.Вотличиеотпростогоподсчетаинцидентныхсвязей,промежуточная центральность определяется для каждого узла как количествократчайших путей, проходящих через данный узел из всех узлов ко всем другимузлам, что имеет место в расчете диаметра графа.Для графа ≔ (, ) с узлами промежуточная центральность () для узла считается следующим образом:1. Для каждой пары узлов (, ∈ ) высчитываются все кратчайшиерасстояния между ними.2. Для каждой пары узлов (, ∈ ) определяется количество кратчайшихпутей, проходящих через заданный узел. В нашем случае это узел ∈ .3. Суммируем частоту на всех парах узлов (, ∈ ).Или проще: () =∑≠≠∈ (),(21)где количество кратчайших путей из узла в узел , а () —количество кратчайших путей из узла в узел , проходящих через узел .
Этавеличина может быть нормализована делением на количество пар узлов невключая узел — ( − 1)( − 2) для ориентированных графов и ( − 1)( − 2)/2 для ненаправленных графов. Например, в неориентированном графе, имеющемформу звезды, центральный узел содержит все возможные кратчайшиерасстояния и его промежуточная центральность вычисляется как: ( − 1)( − 2)/2 (1 – единицу, если значение нормализовано), а лучики, через которые непроходит ни один кратчайший путь имеют промежуточную центральность 0 —ноль.Применив на примере данную метрику центральности, мы можем показатьдругие результаты (см. Рисунок 7). Роль сетевого моста здесь выполняет узел E –70,5. Меньшую промежуточную центральность имеет узел A – 64,8. Далее за нимследуют F – 56,5, C – 50,9, M – 29,8.120В топологии и смежных областях в математике, близость есть основноепонятие измерения пространства.
Мы можем сказать, что два множестванаходятся близко друг к другу, если они расположены в произвольном порядке поотношению друг к другу. Данное понятие можно определить естественно вметрическом пространстве, где единица дистанции между элементами впространстве определена или задана, но она может быть обобщена в топологиипространств, где мы не имеем ни одного предположения как измерить расстояние.Рисунок 7 –.Цвет и размер узлов обозначает промежуточная центральность.121В теории графов для связанных графов существует естественный показательрасстояния между всеми парами узлов, определяемый по длине их кратчайшихпутей.Удаленностьопределяетсякаксуммаребер.Другимисловами,центральность по близости показывает, насколько данный узел располагается всети близко или далеко по отношению к каждому другому узлу.
Узлы, имеющиемножественные связи с другими узлами, имеют тенденцию находиться накратчайших путях в графе и имеют высокую центральность по близости. Всетевой теории близость является сложной метрикой центральности. Оноопределяется как среднее кратчайших путей между узлом и всех других узлов,которые можно достичь из него:∑∈\ (, ),−1(22)где ≥ 2 есть размер сети связанных компонент , достигаемых из узла .Близости можно приписать величину того как далеко может распространитьсяинформация из узла 277.
Некоторые исследователи определяют близость каквеличину обратную расстоянию, но понимаемую так же как атрибут передачиинформации (на этот раз оценивая скорость вместо временного интервала)278.Центральность по близости () для узла обратно пропорциональна суммекратчайших путей к другим узлам : () =1∑∈\ (, )(23)Таким образом, чем более централен узел, тем меньше его общеерасстояние до других узлов.
А. Бавелас в статье «Communication patterns in taskoriented groups»279 определял центральность по близости как величину обратнуюотдаленности. Очень важно понимать, что чем больше приближена к единицеNewman M. E. J. The mathematics of networks [Электронный ресурс]. URL: http:// wwwpersonal.umich.edu/~mejn/papers/palgrave.pdf (дата обращения 26.12.2016)278Sabidussi, G.
The centrality index of a graph, 1966. Psychometrika 31. P. 581—603279Bavelas A. Communication Patterns in Task-Oriented Groups // Acoustical Society of America Journal. 1950. Vol. 22.P. 725—730277122данная метрика, тем лучше, так как единица — это кратчайшее расстояние вграфе.В нашем примере (см. Рисунок 8) самыми центральными являются узлы:A – 1,68, M – 1,8, F – 1,8, E – 1,84 и C – 1,84. Так, они тяготеют к роли хабов.Можно представить разные методы и алгоритмы для измерения близости.Центральность случайного хождения (random walk centrality) Ноха и Ригера естьмера скорости, с которой случайно шагают сообщения к узлу отовсюду в графе.Такой вид случайного хождения для центральности по близости280.Рисунок 8 – Цвет и размер узлов обозначает центральность по близости.Noh J. D., Rieger H. Random walks on complex networks // Physical review letters.
2004. Vol. 92. №. 11. P. 1187011— 118701-4280123Другаяметрикацентральностипоблизости—информационнаяцентральность (information centrality) Стефенсона и Зелена. По сути даннаяметрика измеряет гармоническое среднее длины путей, оканчивающихся в узле .Данная центральность меньше, если узел имеет много кратчайших путей,соединяющих его с другими узлами281.С целью изучить живучесть или уязвимость сети Дангалчев модифицировализмерение близости для применения её в разорванных графах282: () = ∑ 2−(,)(24)∈\Подсчетметрикцентральностипоблизостиипромежуточнойцентральности для всех узлов в графе требует подсчет всех кратчайших путеймежду всеми узлами в графе.
Это занимает Θ( 3 ) времени с алгоритмом ФлойдаВаршалла (Floyd-Warshall algorithm), разработанным не только для нахождениякратчайших путей, но и подсчета всех кратчайших путей между двумя узлами.Для разряженных графов больше подходит алгоритм Джонсона (Johnson’salgorithm), занимающий ( 2 log + ) времени. Для невзвешенных графов,используя алгоритм Брандеса (Brandes algorithm), подсчет промежуточнойцентральности занимает () времени.Центральность узла зависит еще и от того, с кем именно он имеетсоединения. Центральность по престижу или центральность собственного вектораприсваивает относительные оценки всем узлам в сети на основе той концепции,что связи с более центральными узлами вносят больший вклад в центральностьданного узла, чем связи его с менее центральными.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
