Диссертация (1148128), страница 29
Текст из файла (страница 29)
№ 9. P. 1171—1176292Blau P. M. Inequality and heterogeneity: A primitive theory of social structure. New York: Free Press, 1977. Vol. 7.307 p.293Rytina S., Morgan D. L. The arithmetic of social relations: the interplay of category and network // American Journal ofSociology. 1982. P. 88—113132новые отношения. Время, которое может быть выделено для поддержанияконтактов, ограничено и будет снижаться по мере увеличения контактов одногоузла294, потому существует определенный предел для общественных отношений,после которого люди будут поддерживать свою сеть контактов, а инвестициивремени в новые не будут приносить столько же дивидендов. Более того,антрополог Р. Данбар предположил, что существует предел количества людей, скоторыми человек может поддерживать постоянные общественные отношения.Такой предел, названный числом Данбара, определяется в интервале от 100 до 230контактов (или 150)295.
Антропологи Р. Бернард и П. Киллворф оценивали среднеезначение на уровне 290, медиана была на уровне 231296,297.Такие ограничения должны накладывать и ограничения для плотностиграфа. Исследователи, проведя моделирование случайного выбора, пришли кзаключению, что максимальная плотность комплексных сетей не может бытьболее 0,5.Дж. Скоттпредлагаетсвойспособподсчетаплотностиграфа,чувствительного к его порядку:( × )⁄2 ,(37)=( − 1)⁄2где в числителе учитывается порядок графа и математическое ожиданиестепени узлов, а в знаменателе — максимально допустимое количество связей.Соответственно для ориентированного графа:=294 × ( − 1)(38)Mayhew B. H., Levinger R.
L. Size and the density of interaction in human aggregates // American Journal ofSociology. 1976. N 82. P. 86—110295Dunbar R. I. M. Neocortex size as a constraint on group size in primates // Journal of Human EVolution. 1992. Vol. 22.№. 6. P. 469—493296McCarty C. Killworth P. D., Bernard H. R., Johnsen E. C., Shelley G. A.
Comparing two methods for estimatingnetwork size // Human organization. 2001. Vol. 60. № 1. P. 28—39297Bernard H. R., Shelley G. A., Killworth P. How Much of a Network does the GSS and RSW Dredge Up? // SocialNetworks. 1987. Vol. 9. № 1. P. 49—61133Грановеттер пошел дальше и предложил метод нахождения оценкиплотности через выборочный контроль среднего объема (среднее количестволюдей, знакомых человеку) из больших групп населения298.В любом случае плотность как метрика является одной из основныхспособов оценки связанности участников сети.
Она надежно может бытьприменена как для эго-центричных, так и для социо-центричных сетей,ориентированных и неориентированных графов. Более того, существуетмножество теоретических наработок для применения плотности в компаративныхсетевыхисследованиях.Однаколучшим вариантом остаетсяразработкаситуационной плотности в сравнении идентичных сетей.Многие сети, представляющие интерес для науки — социальные,компьютерные сети, а также сети метаболизма — по своей природе разделяютсяна сообщества, или модули. Задача обнаружения и получения характеристикиэтой структуры сообществ является одним из нерешенных вопросов в изучениисетевыхструктур.Однимизвысокоэффективныхподходовявляетсямодулярность всех возможных разделений графа. Модулярность рассчитываетсякак разность между числом ребер внутри группы (кластера) и математическиможиданием этого числа при случайном перемещении этих ребер междувершинами299.
Модулярность принимает значения на интервале от –0,5 до 1(единица не входит), где значения ближе к единице показывают наиболееоптимальное разбиение графа. Сети с высокой модулярностью имеют плотныевнутренние связи в субграфе, но разряженные связи между субграфами. Большимнедостатком модулярности считают неспособность обнаруживать небольшиесубграфы или сообщества.Средний коэффициент кластеризации показывает, как связан граф —посредством транзитивных троек или клик, другими словами это — мера, всоответствии с которой узлы в графе имеют тенденцию группироваться вместе.Granovetter M. Network sampling: Some first steps // American Journal of Sociology.
1976. Vol. 81. № 6. P. 1287—1303299Newman M. E. J. Modularity and community structure in networks // Proceedings of the national academy of sciences,2006. Vol. 103. № 23. P. 8577—8582298134Транзитивность в теории графов определяется следующим образом.
Три узла А,Б, В являются транзитивными, если А связан с Б, Б связан с В, В связан с А. Это иесть клика. Степень транзитивности показывает количество транзитивных троек,разделенное на потенциальное их количество. Взвешенный коэффициенткластеризации (weighted clustering coefficient) отображает меру кластеризации сучетом интенсивности связи для взвешенных графов.Одной из особенностей сетевого анализа является применение алгоритмовкластеризации графов или нахождения сообществ для классификации узлов наосновании связей. Существует алгоритм кластеризации «глухой телефон»(Chinese Whispers Clustering Algorithm), названный в честь детской игры. Он былразработан в 2005 г. К.
Биманом и С. Тересинаки300. Алгоритм принадлежит кжестким методам разделения. Это означает, что во время запуска процесса одинузел может принадлежать только к одному кластеру. Алгоритм работаетследующим образом:1. Все узлы изначально принадлежат к разным кластерам, то есть n естьколичество узлов и кластеров.2. В случайном порядке узлы начинают «перекрашивать» соседние.
Узелприсоединяется к кластеру, с которым он имеет наибольшее количествосоединений.3. Предыдущий этап повторяется до тех пор, пока не закончится заданноеколичество итераций или пока алгоритм не сойдется.Алгоритмы кластеризации графов могут учитывать разные свойства«распространения связей» (affinity propagation). В статистике и в «добычеданных» или «интеллектуальном анализе данных» (data mining) «распространениесвязей» — это алгоритм кластеризации, построенный на распространениисообщения между узлами. В отличие от методов k-means и k-medoids, ему нетребуется заранее определять количество кластеров. В нашем исследовании мыиспользовали три разные настройки «распространения связей» в алгоритме300Biermann C. Chinese Whispers - an Efficient Graph Clustering Algorithm and its Applications to Natural LanguageProcessingProblems.2006.[Электронныйресурс].URL:http://wortschatz.unileipzig.de/~cbiemann/pub/2006/BiemannTextGraph06.pdf (дата обращения 26.12.2016)135«глухой телефон»: «Вершина» (Top), «Логарифм дистанции» (Log Distance) и«Дистанция» (Distance) для наилучшего понимания классификации узлов взависимости от пересчета влияния связей301.
Метод «Вершина» создает кластерына основе суммирования соседней сети расположения узлов. Метод «Дистанция»значительноотличаетсяотпредыдущего;значимостькаждогокластеразначительно увеличивается, что дает повышенную точность классификации иразбивку графа на большее количество субграфов. Уменьшается влияниеотдельных узлов, увеличивается влияние транзитивных соседей.
Логарифмдистанции делает тоже самое, лишь приводя все веса ребер в логарифмическуюшкалу, чтобы минимизировать влияние экстремальных значений отдельных хабовв графе.Такжечастоиспользуюталгоритмраспространенияметок(LabelPropagation Algotithm). Алгоритм разработан в 2007 г., его авторы — У.
Рагхаван,Р. Алберт, С. Кумара302. Основная идея алгоритма распространения меток состоитв следующем. Узел x имеет соседей x1, x2, каждый узел несет на себе меткупринадлежности к сообществу. Тогда x определяет свое сообщество на основаниитого, к какому сообществу максимальное количество его соседей принадлежит.Кластеризация (как в предыдущем алгоритме) начинается «снизу». Каждому узлуопределяется уникальная метка, а дальше метки начинают распространяться пографу. Клики и плотные скопления узлов быстро достигают единства в кластере, азатем они продолжают экспансию до тех пор, пока это возможно.301Cherven K. Mastering Gephi Network Visualization.
2015. 315 p.Raghavan U. N., Albert R., Kumara S. Near linear time algorithm to detect community structures in large-scalenetworks // Physical review E. 2007. Vol. 76. № 3. P. 036106302136§ 2.4 Компьютерные программыКомпьютеры играли ключевую роль в становлении сетевого анализа. Дляобработки данных, содержащих в себе отношения между узлами, необходимыбыли специальные процедуры, которые требовали разработки специальногопрограммного обеспечения. Самые первые из таких программ были относительнопростыми и решали конкретные задачи. В конце 1950-х годов Дж. Коулман иД. МакРей создали программу, которая обнаруживала кластеры тесно связанныхиндивидов в «датефрейме»303. Позже С.
Лейнхардт в 1971 г. написал программуSOCPAC I, которая находила различные виды пар и троек, которые можно былонайти в «датасете»304. В том же году Г. Хел и Х. Уайт представили BLOCKER,программу, решающую метрическую задачу нахождения лиц, занимающихцентральные позиции в сети305. В 1972 г. Р. Альба и М. Гутман вернулись к задачепоиска кластеров и написали программы SOCK и COMPLT, реализующие разныеалгоритмы для решения данной задачи306. Год спустя Р. Бернард и П. Килворфсоздали CATIJ, решающую задачу поиска кластеров307.
В 1975 г. Р. Бриджер,С. Бурман и Ф. Араби написали программу CONCOR, решающую задачу поискамассива лиц, занимающих аналогичные структурные позиции в сети308. Вследующем году Г. Хел и Х. Уайт представили новую версию BLOCKER. В томже году Рональд Барт представили STRUCTURE309. В 1975 г. В. Ричардспредставили NEGOPY, решающую задачу поиска кластеров310. В 1978 г.С. Сайдман и Б. Фостер написали SONET, содержащую в себе коллекцию303Coleman J.
S., MacRae D. Electronic processing of sociometric data for groups up to 1,000 in size // AmericanSociological Review. 1960. Vol. 25. № 5. P. 722—727304Holland P. W., Leinhardt S. A method for detecting structure in sociometric data // American Journal of Sociology.1970. P. 492—513305Heil G. H., White H. C. An algorithm for finding simultaneous homomorphic correspondences between graphs and theirimage graphs // Behavioral Science. 1976. Vol. 21. № 1.
P. 26—35306Alba R. D., Gutmann M. P. SOCK: A sociometric analysis system // ACM SIGSOC Bulletin. 1972. Vol. 3. № 3.P. 11—12307Killworth P., Bernard H. Catij: A new sociometric and its application to a prison living unit // Human Organization.1974. Vol. 33. № 4. P. 335—350308Breiger R. L., Boorman S. A., Arabie P. An algorithm for clustering relational data with applications to social networkanalysis and comparison with multidimensional scaling // Journal of mathematical psychology. 1975.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
