Диссертация (1148128), страница 28
Текст из файла (страница 28)
Другими словами, значимостьузла определяется тем, насколько значимы его соседи. Довольно часто приводятGoogle RankPage как пример использования центральности по престижу.281Stephenson K. A., Zelen M. Rethinking centrality: Methods and examples // Social Networks. 1989. Vol. N 11. P. 1—37Dangalchev Ch., Residual Closeness in Networks, Phisica A 365, 556. 2006. [Электронный ресурс]. URL: https://svn.labri.fr/repos/visu/survey_metrics/biblio/closeness/dangalchev_2006.pdf (дата доступа: 26.12.2016)282124Для нахождения центральности по престижу используется матрицасмежности. отображает оценку i-ого узла.
, — матрица смежности графа,где , = 1 если -тый узел смежен с j-тым узлом, в противном случае , = 0.Кроме того, матрица смежности , может отображать интенсивность связи, а нетолькоеёфакт.Дляi-огоузлацентральностьпопрестижупрямопропорциональна сумме всех оценок узлов, с которыми он связан. Другимисловами: =11∑ = ∑ , ,∈()(25)=1где () множество узлов соседей, а константа. Также данная формула можетбыть записана в виде:=1 ⇔ = (26)Существуют различные варианты конструирования собственных значенийвектора исходя из его связей. Однако по теореме Перрона-Фробениуса есть однотребование — все записи собственного вектора были положительные283.В нашем примере (см.
Рисунок 9) максимальным престижем обладает узелA — 1, но и остальные не меньше C — 0,8, E — 0,77, M — 0,76, F — 0,76.Newman M. E. J. The mathematics of networks [Электронныйpersonal.umich.edu/~mejn/papers/palgrave.pdf 1 (дата обращения 26.12.2016)283ресурс].URL:http://www-125Рисунок 9 – Цвет и размер узлов обозначает центральность по престижу.Для комплексных сетей характерно, чтобы узлы, имеющие связь междусобой, имели также связь с другими узлами сети.
Для описания транзитивнойсвязи между тремя узлами, образующую клику, был предложен коэффициенткластеризации: =2, ( − 1)(27)126где – число связей между соседями узла i.Так как узел имеет степень ( − 1)⁄2 максимум число связей.Суммируя вышеперечисленное, мы утверждаем, что метрики центральностиузла, то между его соседями может бытьне во всех случаях показывают одинаковый результат. Например, сводныйрезультат показан в Приложении Г. Это связано с тем, что метрики центральностиимеют своё значение, применять их необходимо к специальным задачамисследованиям,еслиисследовательдлясвоихнужднеразрабатываетспециальную метрику центральности.Кроме метрических характеристик узлов и ребер графа, которые принятоназывать локальными, существуют еще метрики, позволяющие судить в целом осети.Одной из основных принято считать среднюю степень узла или валентность(average degree).
Мы её понимаем как 〈〉 и она высчитывается следующимобразом:12〈〉 = ∑ =(28)=1Для ориентированного графа:11〈 〉 = ∑ = 〈 〉 = ∑ ==1(29)=1Распределение степеней узлов (degree distribution) является важнойхарактеристикой сложной сети и дает представление о характере связей внутрисети (см. Рисунок 10). Оно дает вероятность, что случайно выбранный узел в сетиимеет степень k: =,(30)127где есть числи узлов с степенью k. Так как распределение степеней узлов естьвероятность, то она должна быть нормализована:∞∑ = 1(31)=1Кроме того, средняя степень узлов может быть посчитана следующим способом:∞〈〉 = ∑ (32)=0Распределение степеней узлов занимает центральное место в сетевом анализе взадачах по нахождению безразмерных сетей.Распределение степенейузлов0,700,600,500,400,300,200,100,00012345Рисунок 10 – Распределение степеней узлов.Расстояние является весьма важной характеристикой сети, которая говорито дистанции между узлами в графе, например, сколько контактов необходимобудет предпринять для взаимодействия с каждый узлом или за сколько шаговинформация дойдет до получателей.
Следует понимать под расстояниемколичество переходов между узлами. В графе расстояние между двумя узламипонимают как (, ), и оно показывает кратчайший путь между узлами i и j.128Например, в графе на Рисунке 11 d(A,E)=2 (A – B\D, B\D – E), а d(A,B)=1.Диаметр графа — это максимально пройденное расстояние без циклов междуузлами графа. Обозначается диаметр d. Зависимости диаметра графа d отколичества узлов в графе нет, зависит диаметр графа d от топологии, на чтовлияют ребра графа и образованные ими меры центральности узлов и величиныкластеризации. В нашем примере диаметр равен 2, так как существуют именнотакиемаксимальнопройденныерасстояния.Еслидиаметрпоказываетмаксимальное расстояние между узлами, то кратчайшее, исходя из названия, —самое короткое. Количество кратчайших путей в графе раскрывает, как связаныузлы в графе.Рисунок 11 – Расстояние на графе.
Цвет обозначает путь от узла A к узлу E.Существует еще один показатель расстояния – средняя длина пути. Этоусредненное расстояние между всеми парами узлов сети:=1( − 1)∑,(33),≠0,;≠Например, именно данный показатель учитывался в исследовании Нэнси Ликак среднее количество контактов, необходимых для поиска подпольного врача.129В графе существует метрика, которая показывает, как велико количестворебер — плотность.
Она описывает общий уровень связанности междуучастниками сети. Она принимает значение от 0 до 1 и есть количество ребер,поделенное на количество максимально возможных ребер. Граф с максимальновозможным количеством ребер называется полным: =( − 1),2(34)где n – количество вершин или узлов в графе. В полном графе все участникисети связаны со всеми максимально возможными способами. Матрица смежноститакого полного графа должна быть заполнена единицами, кроме главнойдиагонали матрицы смежности, которая по такой логике должна содержатьзначения петлей.Плотность зависит от двух параметров сетевой структуры: «включенности»графа и суммы степеней узлов284.
Включенность отображает количество узлов,включенных в граф любыми ребрами. Включенность есть совокупностьсвязанных в компонент узлов без узлов изолятов. Самый лучший способвысчитать включенность — это представить количество связанных компонент,деленное на общее количество узлов. Так, например, граф с 20 узлами и пятьюизолятами будет иметь включенность 0,75. Изоляты не вносят никакого вклада вплотность графа. Следовательно, чем больше включенность, тем плотнее граф.Связанные узлы будут отличаться друг от друга по своей степени узла иликоличеством связей: одни будут иметь минимальное расстояние к остальнымузлам, другие будут иметь одну или несколько связей. Высокая степень узлаповышает плотность графа.Таким образом, плотность можно выразить как количество ребер графа,деленое на максимально допустимое количество ребер графа такого порядка:=284,( − 1)/2Scott J.
Social network analysis. Sage, 2012. P. 70(35)130где – количество ребер графа, а ( − 1)/2 – максимум ребер в порядкеграфа .В ориентированных графах матрица смежности не обладает симметриейотносительного главной диагонали, поэтому подсчет плотности по этой формулене представляется верным. Для ориентированного графа справедлива следующаяформула:=( − 1)(36)Барнс предложил два подхода к изучению сетей в сетевом анализе285. Водномподходе,которыйстоитназватьэго-центричным,исследовательзаинтересован найти центрального агента, вокруг которого выстроена сеть (см.Рисунок 12). В таком подходе плотность будет считаться на основании всехсвязей в сети.
В другом подходе, который следует назвать социо-центричным,исследователь заинтересован в связях внутри сети без связей ключевого агента.Плотность социо-центричного подхода не учитывает связи центрального агента,нивелируя его медиативные контакты. = 0,8 = 0,4Рисунок 12 – Плотность в левом графе графе – 0,8. Плотность в правом графе – 0.4.285Barnes J. Social Networks // Module in Anthropology.
1974. N 26. P. 1—29131Как мы можем заметить по рисунку, социо-центричный подход фиксируетвнимание на связи членов сети без фокального узла. Сравнение графов из двухподходов может дать исчерпывающее представление о структуре сети вокругфокального агента, а также оценить его вклад в плотность сети отношений.Одна из фундаментальных проблем подсчета плотности в графе связана сподсчетом плотности в графах с большим количеством узлов. Следствиемявляется то, что плотность в графах разного порядка не идентична, а потомувозникают проблемы со сравнением этого показателя в разных графах286,287,288.Плотность измеряется от размерности графа (суммы всех ребер), при это онаникак не учитывает порядок графа. В изучении комплексных сетей возникаеттрудность в том, что максимальное возможное количество связей будетзначительно ниже теоретически возможного максимума.
Кроме того, для членовсети может быть верхний предел числа отношений, которые они могутподдерживать или в которые вступали. Например, в моделях секс-сетей, которыестроят для моделирования распространения болезней, передающихся половымпутем289,290,291, явно существует предел половых сношений, который далек оттеоретического максимума ребер графа. Такое ограничение числа ребер дляодного узла приводит к тому, что плотность графов высокого порядка всегдабудет иметь низкую плотность, чем плотность графов меньшего порядка292,293.Более того, Б. Мэйхью и Р. Левингер утверждают, что существуют ограниченияпо времени: людям необходимо время для поддержания контактов и инвестиций в286Friedkin N. E. The development of structure in random networks: an analysis of the effects of increasing networkdensity on five measures of structure // Social Networks.
1981. Vol. 3. № 1. P. 41—52287Niemeijer R. Some applications of the notion of density to network analysis // Boissevain y Mitchell, editores. 1973.Vol. 21. №. 6. P. 45—64288Snijders T. A. B. The degree variance: an index of graph heterogeneity // Social networks. 1981. Vol. 3. № 3. P. 163—174289De P., Singh A. E., Wong T., Yacoub W., Jolly A. M. Sexual network analysis of a gonorrhoea outbreak // Sexuallytransmitted infections. 2004.
Vol. 80. № 4. P. 280—285290Potterat J. J., Muth S. Q., Rothenberg R. B., Zimmerman-Rogers H., Green D. L., Taylor J. E., White H. A. Sexualnetwork structure as an indicator of epidemic phase // Sexually transmitted infections. 2002. Vol. 78. № suppl 1. P. i152—i158291Schneider J. A., Saluja G. S., Oruganti G., Dass S., Tolentino J., Laumann E. O., Pitrak D. HIV infection dynamics inrural Andhra Pradesh south India: a sexual-network analysis exploratory study // AIDS care. 2007. Vol. 19.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
