Граф-теория (graph theory) — форма математического представления отношений между переменными, выраженная наглядно при помощи геометрических построений таким образом, что в результате отдельные переменные начинают отображать некую систему (networks). Граф — это набор точек (узлы или вершины), а также паросочетания (двунаправленные связи) между ними (дуги или линии)47. В настоящее время теория графов стала очень популярной среди исследователей, преподавателей и студентов. Оказывается, с ее помощью довольно просто решается широкий круг самых разнообразных математических задач. На языке графов условия задачи приобретают высокую наглядность, упрощается ее анализ. Сам процесс решения превращается чуть ли не в 45 Mills C.W. The sociological imagination... P. 89. 46 Ibid. P. 94. 47 Oxford Dictionary of Sociology/ Marshall G. (ed.). Oxford, N.Y.: Oxford Univ. Press, 1998. P. 265. 546 увлекательное занятие и, в отличие от решений другими методами, не содержит утомительных вычислений. Таково несомненное преимущество графов, ведь изобилие математических выкладок вовсе не свидетельствует о содержательности теории. Теория графов притягательна как раз тем, что при всей своей наглядности и простоте помогает решать серьезные математические и прикладные проблемы48. Самое раннее упоминание о графах встречается в работе Л. Эйлера (1736). Дальнейшее ее развитие связано с решением важных практических задач. Изучая электрические цепи, Г. Кирхгоф (1847) разработал основные понятия и получил ряд теорем, касающихся деревьев в графах. Понятие «матрицы ин-циденций», введенное Кирхгофом для изучения электрических цепей, было привлечено А. Пуанкаре в топологию при создании его «analysis situs»; понятие «точки сочленения», с давних пор известное в социологии, впоследствии появилось в электронике. Окончательно как математическая дисциплина теория графов оформилась в 1936 г. после выхода монографии венгерского математика Д. Кенига («Теория конечных и бесконечных графов»). Он же и ввел в научный оборот термин «граф». Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых. Графы обычно изображаются в виде геометрических фигур, так что вершины графа изображаются точками, а ребра — линиями, соединяющими эти точки (рис. 38). Особенно сильный импульс развитию теории графов дало развитие современной вычислительной техники. Она активно применяется для решения разнообразных практических задач: транспорт, календарное планирование промышленного производства, сетевые методы планирования и управления, проблемы построения систем связи и исследования процессов передачи информации, выбор оптимальных маршрутов и потоков в сетях, методы построения электрических сетей, способы построения переключательных схем и многие другие. Сегодня считается, что теория графов — это раздел математики, изучающий свойства различных геометрических схем (графов), образованных множеством точек и соединяющих их линий. В последнее время теория графов стала простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем. С помощью графов изображаются схемы дорог, газопроводов, тепло- и электросети. Помогают графы в решении математических и экономических задач.
Рис. 38. Примеры графов Коннов В.В., Клековкин Г.А., КонноваЛ.П. Геометрическая теория графов//http://alglib.dore.ru/ book/gegraph.html 547 Графы — это обобщение структуры деревьев. Формально граф — пара G = (V,E), где V — множество объектов произвольной природы, называемых вершинами, а Е — семейство пар е:= (vM, vl2), v.. из V, называемых ребрами. Возможны случаи кратных ребер. Ребра — это соединения между узлами графа. Проще всего граф определить как модель, носителем которой является множество вершин, а отношение — бинарное отношение смежности вершин. Известны взвешенные и невзвешенные, ориентированные и неориентированные графы. Граф, в котором нет кратных ребер, можно задать при помощи весовой матрицы. Для каждой пары вершин в матрице указывается вес ребра, соединяющего вершины (если ребра нет, то полагаем соответствующий элемент матрицы равным бесконечности). Матрица может быть несимметричной в случае ориентированного графа. В случае невзвешенного графа удобнее представлять его при помощи матрицы связности, элемент которой равен 1, если есть соответствующие ребро, и 0, если ребро отсутствует. Пример использования графа — задание условий в проблеме коммивояжера, здесь населенные пункты помешаются в вершины графа, а веса ребер определяют расстояние между соответствующими населенными пунктами49. В социологической теории узлами являются отдельные индивиды, роли, организации, а в качестве связей между ними выступают социальные отношения — супружеские, дружеские, лидерские, властные и др. Граф называется связным, если существует путь между любыми двумя его вершинами, и несвязным — в противном случае. Связи могут иметь определенное направление (ориентированный граф) или не иметь такового (неориентированный граф). Если вы строите схему города, то стрелки расположатся вдоль ребер-улиц. Схема города предстанет в виде ориентированного графа. Ребро графа называется ориентированным, если одну из его вершин считать началом, а другую — концом этого ребра. Граф, у которого все ребра ориентированные, называется ориентированным графом. К примеру, ориентированные графы используют для наглядного представления процесса и результата спортивных соревнований. На рис. 39 изображена (с помощью графа) схема игр между командами А, Б, В, Г, Д, Е. Но эта схема не дает информации о результатах игры. Обычно используют ориентацию ребра от выигравшей команды к проигравшей, т.е. если А выиграла у Д, то граф ориентируют от А к Д. На рис. 40 (с помо-
Рис. 39. Полный граф с пятью вершинами 49 Быстрицкий В.Д. Структура данных // http://alglib.dore.nj/paper/struct.html 548
Рис. 40. Схема игр между командами А, Б. В, Г, Д £ щью ориентированного графа) показаны результаты игр между командами, изображенными с помощью графа на предыдущем рисунке. Если игра может быть сыграна вничью, то обычно ребро графа оставляют неориентированным (ребро BE) и такой граф называют смешанным50. Ориентированные графы в экономике активно используются в сетевом планировании, в математике — в теории игр, теории множеств, при решении многих задач, в частности комбинаторных. Связи между узлами могут указывать не только направление социальных отношений или социального взаимодействия (один индивид оказывает услугу другому, отдает приказ, делает пас мячом и т.д.), но и принимать конкретную числовую величину (уровень измерения). Если вершинам и ребрам графа соответствуют числа, то такой граф называется взвешенным. Если в социологии в качестве чисел используются значения коэффициентов, например корреляции, то в естествознании вместо чисел могут использоваться заряд атома, валентность и т.д. Любопытным примером использования граф-теории в исторической социологии может служить анализ отношений флорентийской элиты начала XV в. на примере семейства Медичи, проведенный Дж. Пэджеттом и К. Ан-селлом51. Известный клан покровителей искусства эпохи Возрождения, повязанный густой сетью брачных отношений (в современной социологии менеджмента этот феномен называется интерлокацией), на графе получил наибольшее количество путей. Плотность связей и характеристика ребер графа позволяла выявить причины, по которым представители этого семейства заняли доминирующее положение во Флоренции и контролировали важные сферы общественной жизни. В то же время анализ других переменных (не брачного статуса, а богатства, древности рода и состояния, политического статуса, ближайшего окружения) свидетельствовал, что в этих сферах между семейством Медичи и остальными олигархами, входящими в круг флорентийской элиты, существенных отличий не обнаружено. -" Царство графов// http://school-sector.relarn.ru/dckt/projects/ctrana/graf/gr7.htm " Padgett J.F., Ansell С.К. Robust action and the rise of the Medici, 1400-1434 // American Journal of Sociology. 1993. Vol. 98. P. 1259-1319. 549 Наряду с обычным бинарным графом (где связь либо существует, либо отсутствует) в социологии применяются также специальные их виды, например асимметричный (ориентированный, однонаправленный) граф для изображения спортивного соревнования, упорядоченный граф и сетевой граф (например, агрегированный сетевой граф подготовки производства на действующем предприятии), показывающий организационную структуру компании, иерархическое дерево и классификационные системы. Кроме них, если верить авторитетному Оксфордскому словарю социологии52, используются признаковый (signed) граф (+, —), применяемый в структурном балансе, оценочный (real-valued)53 граф для распределения заданий и постановки проблем, стохастический, или граф, указывающий степень вероятности существования связи между объектами. Граф-теория используется для выражения теорем (доказанных следствий) и алгоритмов (пошаговые процедуры), необходимых для получения точной информации, например о социальных характеристиках индивидов (популярность, сосредоточенность, незаконная любовная связь, статус карточного игрока), двух людей (наикратчайший путь между двумя точками), наконец малых групп и подгрупп (клики, триады). Сначала графы использовались в социометрии, позже — в сетевом анализе, наукометрии (исследование социтирования), маркетинге (определение рыночных ниш и трудовых вакансий). Графы сегодня используются в анализе социальных сетей (social, network, analysis). Это направление активно развивается прежде всего в зарубежной социологии, которая традиционно на порядок выше российской в области математического оснащения. Здесь накоплен богатый математический аппарат, позволяющий строить весьма сложные модели социальных взаимодействий. Сеть социальных взаимодействий состоит из совокупности социальных акторов и набора связей между ними. В качестве социальных акторов могут выступать индивиды, социальные группы, организации, города, страны. Под связями понимаются не только коммуникационные взаимодействия между акторами, но и связи по обмену различными ресурсами и деятельностью, включая конфликтные отношения. Сформировавшаяся сеть взаимодействий может быть проанализирована с помощью различных стратегий, в том числе методами теории графов, теории информации, математической статистики54. Анализ социальных сетей используется для исследования и моделирования информационных потоков в сетях, прогнозирования путей развития социальных ситуаций, объяснения специфики исполнения социальных ролей (в том числе и в тендерных исследованиях), анализа процессов социального обмена, изучения структуры социальных организаций и взаимодействий между ними, решения задач социометрии, экономической социологии, социологии массовых коммуникаций и Интернета, истории, политики и международных отношений. Графовые модели социальных сетей используются для моделирования экономических и коммуникационных связей индивидов, анализа процессов 52 Oxford Dictionary of Sociology / Marshall G. (ed.). Oxford, N.Y.: Oxford Univ. Press, 1998. P. 265. 53 К сожалению, в русской литературе до настоящего времени отсутствует единая терминология потеории графов, поэтому при переводе с английского языка для обозначения одного и того же типаграфов используются зачастую разные термины. 54 См.: ЧураковА.Н. Анализ социальных сетей//Социологические исследования. 2001. № 1.С. 109—121. 550 распространения информации, нахождения различных неформальных объединений и связанных подгрупп, на которые можно разбить общую сеть социальных взаимодействий. Например, В. Баскенс разработал теоретическую модель отношений, основанных на доверии между продавцами и покупателями на рынке информационных продуктов, учитывающую эффекты управления и обучения. В данной модели различаются два типа взаимодействий: 1) повторяющееся взаимодействие между теми же акторами и 2) общественные сети, которые действуют как информационные каналы и связи между продавцом и покупателем, дающие информацию об отношениях продавца с другими покупателями. Эмпирическая проверка созданной графовой модели проводилась с помощью опроса продавцов и покупателей на рынке информационных продуктов55. Пример граф-теории № 1. Примером высокоформализованной теории в социологии, использующей методологию построения графов, может быть теория статусных характеристик/ожиданий (Expectation States Theory — EST). В 1966 г. сформировалась исходная версия теории (Бергер, Коген, Зелдитч), в 1974 г. она была расширена Бергером и Физеком, а в 1977 г. — Бергером, Физеком, Норманом и Зелдитчем. Наконец, в 1983 г. Бергер, Физек, Норман и Вагнер придали теории окончательный вид56. Первоначальная версия касалась двух агентов, обладающих по одной статусной характеристике и взаимодействующих в ходе решения одной задачи. Во второй версии этой теории два агента обладали любым числом статусных характеристик, которые делились на два типа — диффузные и специфические. Третья версия включала кроме неограниченного числа статусных характеристик неограниченное количество агентов взаимодействия. В четвертом варианте теории статусные характеристики дополнены переменными вознаграждения. Каждая версия строится при помощи формально-логического и математического аппарата с соблюдением всех методологических требований, предъявляемых к научным теориям. Используются граф-теории — разновидности формального исчисления. Основное уравнение: P(S) = m + q(C — С ). Рассмотрим некоторые положения третьей версии. В ней даны следующие определения исходных понятий. Статусная характеристика — характеристика агента, обладающего двумя или большим количеством состояний, которые различно оцениваются в терминах репутации (почестей), уважения или притягательности. Таковыми являются пол (мужской и женский), уровень исполнения заданий (квалификация). Экспектация — утвердившееся мнение о том, как индивид, обладающий данной характеристикой, будет вести себя или что-то исполнять. Теорема утверждает функциональную связь между двумя переменными и более. Теорема 1. Чем больше возрастает уместность между двумя состояниями — усилением и дифференциацией — и результатом решения задачи, тем выше степень дифференциации статусных характеристик. 33 ЧураковА.Н. Анализ социальных сетей//Социологические исследования. 2001. № I.C. 109—121. 36 См.: Wagner D.G., Berger J. Do Sociological Theories Grow? // American Journal of Sociology. 1985. Vol. 90. № 4. P. 697—728; Humphreys P., Berger J. Theoretical Consequences of the Status Characteristics Formulation // American Journal of Sociology. 1981. Vol. 86. № 5. P. 953-983. 551 Доказательство. Авторов интересуют ситуации, описанные в следующей формуле:
где ситуация характеризуется как С, = Сп= С *. Когда п уменьшается, диффузный эффект от С, увеличивается. Доказательство строится как уравнение с операторами и формально-логическими процедурами. К теореме 2 приведен граф связей для двух переменных: А. Совместимая статусная ситуация
Р — высококвалифицированный работник, О — малоквалифицированная работница. Пол и профессиональный разряд определяют способность выполнять задание. Совместимые статусные характеристики порождают максимальный уровень несправедливости между Р«0. Б. Несовместимая статусная ситуация
552 Р — малоквалифицированный работник, О — высококвалифицированная работница. Пол и профессиональный разряд определяют способность выполнить задание. Совместимые статусные характеристики порождают минимальный уровень несправедливости между Р и О. Обозначения: D,(±) — уровень квалификации (высокий +, низкий —), D,(+) — статусные характеристики пола (мужчина, женщина), С*(±) —уровень выполнения задания (высокий +, низкий —), Т(±) — состояние результата задания (пунктирная линия не несет никакой содержательной нагрузки, она приведена для ясности, т.е. означает, что D2(+) и D2(—) находятся в одной ситуации). Из теоремы 2 следует, что если мужчина и женщина трудятся рядом, то наименьшая справедливость будет достигнута в том случае, когда женщина работает лучше мужчины при условии равенства зарплаты. Существующий в обществе стереотип предполагает, что мужчины трудятся больше женщин и должны получать больше, но если они получают одинаковую зарплату, то меньше трудиться должен мужчина. То же происходит, когда наряду с зарплатой мы учитываем квалификацию. Большинство людей привыкли считать, что зарплата мужчины должна быть выше, чем зарплата женщины, и если разряд первого агента ниже разряда второго, то ситуация превращается в справедливую. Возникает статусная совместимость. Статусная несовместимость возникает в тех случаях, когда характеристики, присущие одному агенту, вдруг начинают принадлежать другому. Теорема 3 гласит: чем больше несовместимость статусных характеристик, тем меньше степень их дифференциации57. Несмотря на то что теория статусных характеристик поражает формально-логической строгостью и, по видимости, соответствует идеалам научного метода, она вызвала серьезную критику, суть которой сводилась к следующему58. Если данная теория является аксиоматической, то она должна соответствовать следующим требованиям: 1) модель должна выводиться из теории; 2) модель должна генерировать неизвестные значения терминов в левой части уравнения, если значения в правой известны. Иными словами, теоретические предсказания должны генерироваться средствами математики. Но так ли это? Данная модель не фальсифицируема, так как теория не может быть проверена с ее помощью, т.е. модель не выводится из теории. Линейная модель Бергера, Физека и Нормана не имеет теоретического использования. Она определена лишь на области экспериментальных, а не теоретических данных. Она способна лишь post hoc описывать эмпирические данные. Формулировка 1977 г. только распространяет теорию на более широкий класс явлений, но не добавляет новых теоретических идей. По существу, она даже не требовала граф-теории, которая здесь использована. Авторы считают, что такой способ формализации не дает преимуществ науке с точки зрения кумулятивного прироста знаний. Для этого модель должна отвечать двум условиям: Описание теории статусных характеристик дается по источнику: Humphreys P., BergerJ. Theoretical Consequences of the Status Characteristics Formulation //American Journal of Sociology. 1981. Vol. 86. № 5. P. 953-983. vs См.: Theoretical Methods in Sociology / Ed. by L. Freese. Pittsburg: Univ. of Pittsburg Press, 1980. P. 338-361. 553 1) граф-теория должна иметь метрику; 2) набор теоретических функций должен определяться и переводиться в граф-теоретическую метрику. Новая метрика должна записываться на языке теории вероятностей, но этого у авторов нет. Для этого надо переопределить термины и отношения, вместо ненаправленных графов ввести направленные59. Если в социологии и проводится формализация, то она касается измерительных процедур и шкал, но почти не достигает теоретического уровня и не ведет к созданию аксиоматических теорий. Социология только тогда станет теоретической наукой, когда она будет содержать математические аксиоматизированные теории, открывающие социологические законы. Это не значит, что в социологии должны быть аксиомы. Разработанная и полностью аксиоматическая теория в науке — исключительный случай даже в развитых дисциплинах. Главное не в том, чтобы аксиоматизировать социологические теории постфактум, а в том, чтобы делать это заранее, в самой программе60.
Ви переглядаєте статтю (реферат): «ГРАФ-ТЕОРИЯ» з дисципліни «Фундаментальна соціологія»
