Граф-теория

Граф-теория (graph theory) — форма математического представления от­ношений между переменными, выраженная наглядно при помощи геомет­рических построений таким образом, что в результате отдельные перемен­ные начинают отображать некую систему (networks). Граф — это набор то­чек (узлы или вершины), а также паросочетания (двунаправленные связи) между ними (дуги или линии)⁴⁷.

В настоящее время теория графов стала очень популярной среди иссле­дователей, преподавателей и студентов. Оказывается, с ее помощью доволь­но просто решается широкий круг самых разнообразных математических задач. На языке графов условия задачи приобретают высокую наглядность, упрощается ее анализ. Сам процесс решения превращается чуть ли не в

⁴⁵ Mills C.W. The sociological imagination... P. 89.

⁴⁶ Ibid. P. 94.

⁴⁷ Oxford Dictionary of Sociology/ Marshall G. (ed.). Oxford, N.Y.: Oxford Univ. Press, 1998. P. 265.

увлекательное занятие и, в отличие от решений другими методами, не содер­жит утомительных вычислений. Таково несомненное преимущество графов, ведь изобилие математических выкладок вовсе не свидетельствует о содер­жательности теории. Теория графов притягательна как раз тем, что при всей своей наглядности и простоте помогает решать серьезные математические и прикладные проблемы⁴⁸.

Самое раннее упоминание о графах встречается в работе Л. Эйлера (1736). Дальнейшее ее развитие связано с решением важных практических задач. Изучая электрические цепи, Г. Кирхгоф (1847) разработал основные понятия и получил ряд теорем, касающихся деревьев в графах. Понятие «матрицы ин-циденций», введенное Кирхгофом для изучения электрических цепей, было привлечено А. Пуанкаре в топологию при создании его «analysis situs»; поня­тие «точки сочленения», с давних пор известное в социологии, впоследствии появилось в электронике. Окончательно как математическая дисциплина те­ория графов оформилась в 1936 г. после выхода монографии венгерского ма­тематика Д. Кенига («Теория конечных и бесконечных графов»). Он же и ввел в научный оборот термин «граф». Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых. Графы обыч­но изображаются в виде геометрических фигур, так что вершины графа изоб­ражаются точками, а ребра — линиями, соединяющими эти точки (рис. 38).

Особенно сильный импульс развитию теории графов дало развитие совре­менной вычислительной техники. Она активно применяется для решения разнообразных практических задач: транспорт, календарное планирование промышленного производства, сетевые методы планирования и управления, проблемы построения систем связи и исследования процессов передачи ин­формации, выбор оптимальных маршрутов и потоков в сетях, методы пост­роения электрических сетей, способы построения переключательных схем и многие другие. Сегодня считается, что теория графов — это раздел матема­тики, изучающий свойства различных геометрических схем (графов), обра­зованных множеством точек и соединяющих их линий. В последнее время теория графов стала простым, доступным и мощным средством решения воп­росов, относящихся к широкому кругу проблем. С помощью графов изобра­жаются схемы дорог, газопроводов, тепло- и электросети. Помогают графы в решении математических и экономических задач.

Рис. 38. Примеры графов

Коннов В.В., Клековкин Г.А., КонноваЛ.П. Геометрическая теория графов// http://alglib.dore.ru/ book/gegraph.html

Графы — это обобщение структуры деревьев. Формально граф — пара G = (V,E), где V — множество объектов произвольной природы, называемых вершинами, а Е — семейство пар е_:= (v_M, v_l2), v.. из V, называемых ребрами. Возможны случаи кратных ребер. Ребра — это соединения между узлами графа. Проще всего граф определить как модель, носителем которой явля­ется множество вершин, а отношение — бинарное отношение смежности вершин. Известны взвешенные и невзвешенные, ориентированные и неори­ентированные графы. Граф, в котором нет кратных ребер, можно задать при помощи весовой матрицы. Для каждой пары вершин в матрице указывается вес ребра, соединяющего вершины (если ребра нет, то полагаем соответству­ющий элемент матрицы равным бесконечности). Матрица может быть не­симметричной в случае ориентированного графа. В случае невзвешенного графа удобнее представлять его при помощи матрицы связности, элемент которой равен 1, если есть соответствующие ребро, и 0, если ребро отсутству­ет. Пример использования графа — задание условий в проблеме коммивоя­жера, здесь населенные пункты помешаются в вершины графа, а веса ребер определяют расстояние между соответствующими населенными пунктами⁴⁹.

В социологической теории узлами являются отдельные индивиды, роли, организации, а в качестве связей между ними выступают социальные отно­шения — супружеские, дружеские, лидерские, властные и др. Граф называ­ется связным, если существует путь между любыми двумя его вершинами, и несвязным — в противном случае. Связи могут иметь определенное направ­ление (ориентированный граф) или не иметь такового (неориентированный граф). Если вы строите схему города, то стрелки расположатся вдоль ребер-улиц. Схема города предстанет в виде ориентированного графа. Ребро графа называется ориентированным, если одну из его вершин считать началом, а другую — концом этого ребра. Граф, у которого все ребра ориентированные, называется ориентированным графом. К примеру, ориентированные графы используют для наглядного представления процесса и результата спортив­ных соревнований.

На рис. 39 изображена (с помощью графа) схема игр между командами А, Б, В, Г, Д, Е. Но эта схема не дает информации о результатах игры. Обыч­но используют ориентацию ребра от выигравшей команды к проигравшей, т.е. если А выиграла у Д, то граф ориентируют от А к Д. На рис. 40 (с помо-

Рис. 39. Полный граф с пятью вершинами ⁴⁹ Быстрицкий В.Д. Структура данных // http://alglib.dore.nj/paper/struct.html

Рис. 40. Схема игр между командами А, Б. В, Г, Д £

щью ориентированного графа) показаны результаты игр между командами, изображенными с помощью графа на предыдущем рисунке. Если игра мо­жет быть сыграна вничью, то обычно ребро графа оставляют неориентиро­ванным (ребро BE) и такой граф называют смешанным⁵⁰.

Ориентированные графы в экономике активно используются в сетевом планировании, в математике — в теории игр, теории множеств, при реше­нии многих задач, в частности комбинаторных.

Связи между узлами могут указывать не только направление социальных отношений или социального взаимодействия (один индивид оказывает услугу другому, отдает приказ, делает пас мячом и т.д.), но и принимать конкрет­ную числовую величину (уровень измерения). Если вершинам и ребрам графа соответствуют числа, то такой граф называется взвешенным. Если в социо­логии в качестве чисел используются значения коэффициентов, например корреляции, то в естествознании вместо чисел могут использоваться заряд атома, валентность и т.д.

Любопытным примером использования граф-теории в исторической со­циологии может служить анализ отношений флорентийской элиты начала XV в. на примере семейства Медичи, проведенный Дж. Пэджеттом и К. Ан-селлом⁵¹. Известный клан покровителей искусства эпохи Возрождения, по­вязанный густой сетью брачных отношений (в современной социологии менеджмента этот феномен называется интерлокацией), на графе получил наибольшее количество путей. Плотность связей и характеристика ребер графа позволяла выявить причины, по которым представители этого семей­ства заняли доминирующее положение во Флоренции и контролировали важные сферы общественной жизни. В то же время анализ других перемен­ных (не брачного статуса, а богатства, древности рода и состояния, полити­ческого статуса, ближайшего окружения) свидетельствовал, что в этих сфе­рах между семейством Медичи и остальными олигархами, входящими в круг флорентийской элиты, существенных отличий не обнаружено.

-" Царство графов// 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.

Наряду с обычным бинарным графом (где связь либо существует, либо отсутствует) в социологии применяются также специальные их виды, напри­мер асимметричный (ориентированный, однонаправленный) граф для изоб­ражения спортивного соревнования, упорядоченный граф и сетевой граф (например, агрегированный сетевой граф подготовки производства на дей­ствующем предприятии), показывающий организационную структуру ком­пании, иерархическое дерево и классификационные системы. Кроме них, если верить авторитетному Оксфордскому словарю социологии⁵², использу­ются признаковый (signed) граф (+, —), применяемый в структурном балан­се, оценочный (real-valued)⁵³ граф для распределения заданий и постановки проблем, стохастический, или граф, указывающий степень вероятности су­ществования связи между объектами.

Граф-теория используется для выражения теорем (доказанных след­ствий) и алгоритмов (пошаговые процедуры), необходимых для получения точной информации, например о социальных характеристиках индивидов (популярность, сосредоточенность, незаконная любовная связь, статус кар­точного игрока), двух людей (наикратчайший путь между двумя точками), наконец малых групп и подгрупп (клики, триады). Сначала графы исполь­зовались в социометрии, позже — в сетевом анализе, наукометрии (иссле­дование социтирования), маркетинге (определение рыночных ниш и тру­довых вакансий).

Графы сегодня используются в анализе социальных сетей (social, network, analysis). Это направление активно развивается прежде всего в зарубежной со­циологии, которая традиционно на порядок выше российской в области мате­матического оснащения. Здесь накоплен богатый математический аппарат, позволяющий строить весьма сложные модели социальных взаимодействий. Сеть социальных взаимодействий состоит из совокупности социальных акто­ров и набора связей между ними. В качестве социальных акторов могут высту­пать индивиды, социальные группы, организации, города, страны. Под связя­ми понимаются не только коммуникационные взаимодействия между актора­ми, но и связи по обмену различными ресурсами и деятельностью, включая конфликтные отношения. Сформировавшаяся сеть взаимодействий может быть проанализирована с помощью различных стратегий, в том числе методами тео­рии графов, теории информации, математической статистики⁵⁴. Анализ соци­альных сетей используется для исследования и моделирования информацион­ных потоков в сетях, прогнозирования путей развития социальных ситуаций, объяснения специфики исполнения социальных ролей (в том числе и в тендер­ных исследованиях), анализа процессов социального обмена, изучения струк­туры социальных организаций и взаимодействий между ними, решения задач социометрии, экономической социологии, социологии массовых коммуника­ций и Интернета, истории, политики и международных отношений.

Графовые модели социальных сетей используются для моделирования экономических и коммуникационных связей индивидов, анализа процессов

⁵² Oxford Dictionary of Sociology / Marshall G. (ed.). Oxford, N.Y.: Oxford Univ. Press, 1998. P. 265.

⁵³ К сожалению, в русской литературе до настоящего времени отсутствует единая терминология потеории графов, поэтому при переводе с английского языка для обозначения одного и того же типаграфов используются зачастую разные термины.

⁵⁴ См.: ЧураковА.Н. Анализ социальных сетей//Социологические исследования. 2001. № 1.С. 109—121.

распространения информации, нахождения различных неформальных объ­единений и связанных подгрупп, на которые можно разбить общую сеть со­циальных взаимодействий. Например, В. Баскенс разработал теоретическую модель отношений, основанных на доверии между продавцами и покупате­лями на рынке информационных продуктов, учитывающую эффекты управ­ления и обучения. В данной модели различаются два типа взаимодействий: 1) повторяющееся взаимодействие между теми же акторами и 2) обществен­ные сети, которые действуют как информационные каналы и связи между продавцом и покупателем, дающие информацию об отношениях продавца с другими покупателями. Эмпирическая проверка созданной графовой моде­ли проводилась с помощью опроса продавцов и покупателей на рынке ин­формационных продуктов⁵⁵.

Пример граф-теории № 1. Примером высокоформализованной теории в социологии, использующей методологию построения графов, может быть теория статусных характеристик/ожиданий (Expectation States Theory — EST). В 1966 г. сформировалась исходная версия теории (Бергер, Коген, Зелдитч), в 1974 г. она была расширена Бергером и Физеком, а в 1977 г. — Бергером, Физеком, Норманом и Зелдитчем. Наконец, в 1983 г. Бергер, Физек, Нор­ман и Вагнер придали теории окончательный вид⁵⁶.

Первоначальная версия касалась двух агентов, обладающих по одной ста­тусной характеристике и взаимодействующих в ходе решения одной задачи. Во второй версии этой теории два агента обладали любым числом статусных характеристик, которые делились на два типа — диффузные и специфичес­кие. Третья версия включала кроме неограниченного числа статусных харак­теристик неограниченное количество агентов взаимодействия. В четвертом варианте теории статусные характеристики дополнены переменными вознаг­раждения.

Каждая версия строится при помощи формально-логического и матема­тического аппарата с соблюдением всех методологических требований, предъявляемых к научным теориям. Используются граф-теории — разновид­ности формального исчисления. Основное уравнение: P(S) = m + q(C — С).

Рассмотрим некоторые положения третьей версии. В ней даны следую­щие определения исходных понятий.

Статусная характеристика — характеристика агента, обладающего двумя или большим количеством состояний, которые различно оцениваются в тер­минах репутации (почестей), уважения или притягательности. Таковыми являются пол (мужской и женский), уровень исполнения заданий (квалифи­кация).

Экспектация — утвердившееся мнение о том, как индивид, обладающий данной характеристикой, будет вести себя или что-то исполнять.

Теорема утверждает функциональную связь между двумя переменными и более.

Теорема 1. Чем больше возрастает уместность между двумя состояния­ми — усилением и дифференциацией — и результатом решения задачи, тем выше степень дифференциации статусных характеристик.

³³ ЧураковА.Н. Анализ социальных сетей//Социологические исследования. 2001. № I.C. 109—121.

³⁶ См.: 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.

Доказательство. Авторов интересуют ситуации, описанные в следующей формуле:

где ситуация характеризуется как С, = С_п= С *. Когда п уменьшается, диф­фузный эффект от С, увеличивается. Доказательство строится как уравне­ние с операторами и формально-логическими процедурами.

К теореме 2 приведен граф связей для двух переменных:

А. Совместимая статусная ситуация

Р — высококвалифицированный работник, О — малоквалифицированная работница. Пол и профессиональный разряд определяют способность выполнять задание. Совместимые статусные характеристики порождают максимальный уровень несправедливости между Р«0.

Б. Несовместимая статусная ситуация

Р — малоквалифицированный работник, О — высококвалифицированная работница. Пол и профессиональный разряд определяют способность выполнить задание. Совместимые статусные характеристики порождают минимальный уровень несправедливости между Р и О.

Обозначения: D,(±) — уровень квалификации (высокий +, низкий —), D,(+) — статусные характеристики пола (мужчина, женщина), С*(±) —уро­вень выполнения задания (высокий +, низкий —), Т(±) — состояние результа­та задания (пунктирная линия не несет никакой содержательной нагрузки, она приведена для ясности, т.е. означает, что D₂(+) и D₂(—) находятся в одной ситуации).

Из теоремы 2 следует, что если мужчина и женщина трудятся рядом, то наименьшая справедливость будет достигнута в том случае, когда женщина работает лучше мужчины при условии равенства зарплаты. Существующий в обществе стереотип предполагает, что мужчины трудятся больше женщин и должны получать больше, но если они получают одинаковую зарплату, то меньше трудиться должен мужчина. То же происходит, когда наряду с зар­платой мы учитываем квалификацию. Большинство людей привыкли счи­тать, что зарплата мужчины должна быть выше, чем зарплата женщины, и если разряд первого агента ниже разряда второго, то ситуация превращается в справедливую. Возникает статусная совместимость. Статусная несовмес­тимость возникает в тех случаях, когда характеристики, присущие одному агенту, вдруг начинают принадлежать другому. Теорема 3 гласит: чем боль­ше несовместимость статусных характеристик, тем меньше степень их диф­ференциации⁵⁷.

Несмотря на то что теория статусных характеристик поражает формаль­но-логической строгостью и, по видимости, соответствует идеалам научно­го метода, она вызвала серьезную критику, суть которой сводилась к следу­ющему⁵⁸. Если данная теория является аксиоматической, то она должна со­ответствовать следующим требованиям: 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.

1) граф-теория должна иметь метрику; 2) набор теоретических функций дол­жен определяться и переводиться в граф-теоретическую метрику. Новая метрика должна записываться на языке теории вероятностей, но этого у ав­торов нет. Для этого надо переопределить термины и отношения, вместо ненаправленных графов ввести направленные⁵⁹.

Если в социологии и проводится формализация, то она касается измери­тельных процедур и шкал, но почти не достигает теоретического уровня и не ведет к созданию аксиоматических теорий. Социология только тогда станет теоретической наукой, когда она будет содержать математические аксиомати­зированные теории, открывающие социологические законы. Это не значит, что в социологии должны быть аксиомы. Разработанная и полностью акси­оматическая теория в науке — исключительный случай даже в развитых дис­циплинах. Главное не в том, чтобы аксиоматизировать социологические те­ории постфактум, а в том, чтобы делать это заранее, в самой программе⁶⁰.

Пример граф-теории № 2. Представитель одной из самых сильных науч­ных школ в советской социологии труда И.М. Попова в середине 1970-х гг. провела серьезное эмпирическое исследование в области трудовых отноше­ний и мотивации труда⁶¹. Стимулирование труда выступало у нее как сред­ство управления, а управление трактовалось как условие совершенствования стимулирования и развития мотивации труда.

Стимулирование — это не единственный способ управления. Наряду с ним существует еще один — ценностно-нормативный способ, действующий по­средством прямого воздействия наличность. При этом И.М. Попова исхо­дила из того, что человек усваивает некие идеалы как социально значимые побуждения к действию. Они становятся ценностями, а ценности — это важ­ный психологический компонент. Усвоенные культурные нормы превраща­ются в мотивы поведения. Стало быть, они, т.е. нормы, перейдя из внешне­го плана во внутренний, превращаются из стимулов в мотивы. Однако при этом нормы не перестают существовать как объективные, существующие в обществе и независимые от воли и сознания людей регуляторы поведения, а потому они не перестают быть стимулами. Стимул является хотя и внешним, но личностно-значимым фактором, который неразрывно связан с внутрен­ним побуждением. Такому определению вполне отвечают социальные нор­мы. В них воплощено единство внутреннего и внешнего.

На этих предпосылках строилась общетеоретическая часть программы исследования, из которой вполне логично следовал частнотеоретический раздел, выполненный на очень высоком научном уровне.

Автор сравнивала три группы факторов: а) диапазон реальных возможно­стей (условия труда и жизни); б) субъективные характеристики (вербально выраженные ориентации, мотивацию, оценки и информированность); в) фактическое поведение в труде. В основе частнотеоретической модели ле­жала матрица корреляций, заключающая в себе данные о взаимосвязи исход­ных признаков. Она строилась на основе коэффициента Чупрова. В качестве исходных признаков были выделены квалификация (1), стаж на заводе (2),

⁵⁴ Theoretical Methods in Sociology / Ed. by L. Freese. Pittsburg: Univ. of Pittsburg Press, 1980. P. 338-347.

⁶⁰ Ibid. P. 361.

⁶¹ Попова И.М. Стимулирование трудовой деятельности как способ управления. Киев: Наукова дум­ка, 1976.

стаж по специальности (3), образование (4), возраст (5), величина заработ­ной платы (6). Фактическое поведение в трудовой деятельности описывалось с помощью следующих характеристик: выполнение норм выработки (7), дисциплинированность (8), качество работы (9), участие в рационализации и изобретательстве (10). Группа признаков, характеризующая субъективное отношение к труду, включала как интегральную удовлетворенность работой на предприятии (11) и специальностью, так и удовлетворенность различны­ми элементами производственной (рабочей) ситуации: организацией труда (13), содержанием труда (14), заработной платой (15), отношением с адми­нистрацией (16), степенью физической нагрузки (12). В процессе анализа выделялись два, три и четыре фактора (группа признаков)⁶².

Анализ показал, что субъективные характеристики группируются ком­пактно (относительно замкнуто), что может свидетельствовать о некоторой самостоятельности сферы сознания по отношению к фактическому поведе­нию людей в производстве, а также по отношению к их профессиональным и демографическим признакам. Следует сказать, что ключевая посылка тео­ретического анализа — рассогласование сознания, вербального поведения и реальных действий. Она была основательно проработана с помощью теоре­тических моделей, в частности граф-теории, а затем проверена на широком эмпирическом материале.

В исследовании обнаружилась интересная особенность: связь между про­фессиональными и демографическими признаками, с одной стороны, и фак­тическим поведением работника — с другой, оказалась очень сильной, а связь между субъективным отношением к труду и поведением оказалась очень слабой (рис. 41).

Рис. 41:

F1 — социально-демографические характеристики; F2 — фактическое поведение в сфере труда; F3 — удовлетворенность работой и специальностью; F4 — оценка элементов рабочей ситуации

^<)2 Попова И.М. Указ. соч. С. 95.

Частнотеоретический уровень, выраженный в том числе графами, полно­стью показал свою плодотворность. Именно благодаря этому были соверше­ны многие научные открытия, которые не потеряли своего значения и по сей день. Объясняется это максимально плотной увязкой каждого теоретическо­го положения с эмпирическими данными. Можно даже сказать так: ни одно теоретическое положение не вводится до тех пор, пока оно не подтверждено практикой. В роли эмпирической базы в хорошей частносоциологической теории выступали не просто процентовка или одномерные распределения, а матрицы корреляций, коэффициенты разной степени сложности, графичес­кие схемы. То, что нельзя вывести на этот уровень, неявно считалось «мета­физикой». (Но так, к сожалению, было только на частнотеоретическом уров­не. На общетеоретическом уровне советские социологи вытворяли такие чу­деса, от которых и сегодня голова идет кругом, придумывали фразы, весь ужас которых они, возможно, и сами до конца не понимали.)

Среди удачных теоретических находок И.М. Поповой следует признать то, как умело она использовала в своих частнотеоретических построениях понятие «социальная норма зарплаты». «Социальная норма зарплаты трак­туется как такой ее уровень, который работники определенной группы счи­тают для себя нормальным, достижимым. Соответственно те, кто имеет зар­плату ниже нормы, будут недовольны ею (заплатой), так как не использова­ли всех возможностей для увеличения своего дохода»⁶³. Речь идет о неформальных нормах, т.е. представлении работников о том, что является социально справедливой (как у всех или не хуже, чем у всех) зарплатой. В качестве эмпирически проверяемых признаков вновь введенного понятия выбирались оценки зарплаты и доступности предприятия, а также оценки определенного образовательного уровня. Оценка зарплаты в том числе рас­крывалась через удовлетворенность ею работника.

^н Попова И.М. Указ. соч. С. 98.

Дата добавления: 2015-06-04