кузьминов. институты, сети
.pdfГлава 3. Сети в институциональном анализе
Цикл
вграфе
Циклом называется путь, начальная и конечная вершины которого совпадают. На рис. 3.6а ребра (/,, /3, /4) образуют цикл.
М а р ш р у т , путь и дистанция между
вершинами графа
Маршрутом между вершинами п. и я в графе называется последовательность ребер, ведущая от некоторой начальной вершины п. к конечной вершине п.. Путем называется маршрут, не содержащий циклов. Дистанцией между двумя ребрами называется кратчайший путь между ними.
Граф G называется связным, если для любых двух его вершин существует путь, их соединяющий. В противном случае граф G называется несвязным. На рис. 3.8 представлен несвязный граф.
Рис. 3.8
Несвязный
граф
142
3.1. Инструментарий теории сетей
Любой несвязный граф является совокупностью таких связных графов, которые обладают следующим свойством: никакая вершина одного из них не связана путем ни с какой вершиной другого. Каждый из этих графов называется компонентой графа G. В данном примере граф состоит из двух связных компонентов.
М о с т
Ребро а называется мостом графа G, если граф, получившийся из G после удаления ребра а (такой граф обозначается G\ а), содержит больше компонент, чем граф G.
Ребро а графа G является мостом тогда и только тогда, когда а не принадлежит ни одному циклу.
Плотность
графа
ПЛОТНОСТЬ графа характеризуется коэффициентом плотности А — отношением числа ребер (L) в анализируемом графе к числу ребер в полном графе с тем же числом вершин (g):
L |
2L |
g ( g - i ) |
s U - i ) ' |
Коэффициент плотности варьируется в промежутке от 0 до 1, 0 < А < 1. Единичная плотность соответствует полному графу, нулевая — графу, в котором все вершины изолированные. Используя формулу для средней степени вершин, получаем
А = — .
. £ - 1
Подграфом графа G называется граф, вершины которого являются подмножеством вершин графа G и ребра которого, образуя подмножество ребер в G, соединяют эти вершины в графе G.
Отметим, что можно оценивать плотность и отдельных подграфов, входящих в граф. Коэффициент плотности подграфа (subgraph), будет равен
А = |
2 £ - |
|
|
8, {ss -1) |
* |
где Ls — общее число ребер подграфа; gs — общее число вершин подграфа.
деревья
Частным случаем графов являются деревья. Они характеризуются тем, что содержат минимальное число ребер, необходимое для связности.
143
Глава 3. Сети в институциональном анализе
При этом
• любое ребро дерева представляет собой мост;
существует только один путь между любыми двумя вершинами.
С помощью деревьев можно представить теоретико-игровые взаимодействия в расширенном виде — в виде так называемого дерева игры (рис. 3.9). Вершинами дерева являются точки, где игроки принимают решения. Инцидентные этим вершинам ребра — возможные действия, которые доступны игроку в данный момент игры.
Рис. 3.9
Дерево
Ориентированные
графы:' основные понятия
Если рассматривается множество упорядоченных пар 1к = (я., я.) и з множества точек N= {и,, ..., «], и на каждом ребре из множества Z— {/,,..., /.} задается направление, то граф Gd = (N, Z) называется ориентированным (рис. 3.10а и 3.1 Ob). Если же на каждом ребре из множестваZ= {/,,..., /.} направление не задается, то граф G = (N, Z) называется неориентированным графом, или просто графом3.
3 В соответствии с определением, данным выше.
144
3.1. Инструментарий теории сетей
Рис. 3.10
Примеры
ориентированного
графа
а) Граф с семью вершинами |
Ь) Граф с шестью вершинами |
Степени вершины ориентированного графа
В ориентированном графе для каждой вершины различаются входящие и исходящие ребра. Поэтому для характеристики отношений, связанных с конкретной вершиной, используют два показателя:
•степень захода djn, которая равна числу ребер, входящих в вершину; и
•степень исхода dmt, которая равна числу ребер, исходящих из вершины. Данные определения позволяют ввести два показателя средней степени вершин
1 ' л м
dout, =
и их вариации
—\2
Апоскольку общее число входящих ребер равно общему числу исходящих, то
-, L
145
Глава 3. Сети в институциональном анализе
Плотность ориентированного графа
ПЛОТНОСТЬ ориентированного графа характеризуется коэффициентом плотности А:
Д=
Матричное
представление
графов
Матрицы — альтернативная форма представления и суммирования информации о социальных сетях. Такой способ в ряде случаев удобнее, чем графический.
Рассмотрим квадратную матрицу ^размерности пхп, где п ~ количество акторов в группе. Зададим элементы этой матрицы следующим образом:
х..= 1, если между акторами / и / существует связь,
х.= 0, если между акторами / и j связь отсутствует.
Данная матрица содержит в себе полную информацию о связях акторов в группе. Так, матрица, описывающая граф на рис. 3.10Ь, имеет вид
/ |
«1 |
п2 |
«3 |
«4 |
«5 |
«6 |
|
||||||
и, |
0 |
1 |
0 |
0 |
1 |
0 |
п2 |
0 |
0 |
1 |
0 |
0 |
1 |
Х = п3 |
0 |
0 |
0 |
0 |
0 |
0 |
п4 |
0 |
0 |
0 |
0 |
1 |
0 |
П5 |
0 |
0 |
0 |
0 |
0 |
1 |
|
0 |
1 |
0 |
0 |
0 |
0 , |
Заметим, что для ненаправленного графа матрица симметрична.
С помощью матричного представления графов можно, пользуясь простейшими операциями матричной алгебры, определять важные свойства этих графов. Обратимся к примеру.
На рис. 3.11 даны графическое и матричное описание сети отношений влияния между десятью акторами, образующими группу. Определить, на скольких членов группы тот или иной актор оказывает непосредственное влияние, достаточно просто. Но как определить, на скольких членов группы он влияет косвенно? Скажем, актор 1 не оказывает прямого влияния на актора 9, однако делает это косвенно через актора 5. А вот актор 6 не оказывает на актора 9 никакого влияния — ни прямого, ни косвенного.
146
3.1. Инструментарий теории сетей
Рис. 3.11
Отношения
влияния
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
0 |
|
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
0 |
|
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
0 |
|
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
1 |
1 |
1 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
1 |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
|
1 |
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|
0 |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|
1 |
|
0 |
На самом деле, элемент (/,/) матрицы X = Хх Хх ...х X |
описывает количество марш- |
|
' |
М |
' |
рутов4 длины М от актора i к актору j. В частности, для данного примера количество связей длины 2 и 3 от актора к актору описывается следующими матрицами, которые наглядно показывают, что, скажем, между акторами 7 и 8 существует две связи длины 2 и семь связей длины 3:
0 |
0 |
0 |
|
0 |
0 |
0 |
1 |
1 |
1 |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
3 |
3 |
3 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|
1 |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
3 |
3 |
3 |
0 |
0 |
0 |
|
0 |
0 |
0 |
1 |
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
3 |
3 |
3 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|
1 |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
3 |
3 |
3 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
3 |
|
3 |
3 |
|
0 |
0 |
0 |
0 |
0 |
0 |
9 |
9 |
9 |
9 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
2 |
|
2 |
2 |
|
0 |
0 |
0 |
0 |
0 |
0 |
6 |
7 |
7 |
7 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
3 |
|
2 |
2 |
|
0 |
0 |
0 |
0 |
0 |
0 |
7 |
6 |
7 |
7 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
2 |
|
3 |
2 |
|
0 |
0 |
0 |
0 |
0 |
0 |
7 |
7 |
6 |
7 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
2 |
|
2 |
3 |
|
0 |
0 |
0 |
0 |
0 |
0 |
7 |
7 |
7 |
6 |
С помощью такой методики может оцениваться количество возможных маршрутов распространения информации, каналов поиска товара и его продвижения на рынок, средств контроля за экономическими агентами в иерархии и пр.
4 Этот факт доказывается во многих учебниках по теории графов (см., например: Харари Ф. Теория графов. М.: УРСС, 2003). Одним из первых он был отмечен Фестингером, а также Люком и Перри (Festinger L. The Analysis of Sociograms Using Matrix Algebra// Human Relations. 1949. Vol. 2. P. 153—158; Luce R.D., Perry A.D. A Method of Matrix Analysis of Group Structure // Phychometrika. 1949. Vol. 14. P. 95—116).
147
3.2
Применение
инструментария теирии графив к социальным сетям
В этом разделе описывается, как понятия теории графов могут использоваться при анализе социальных сетей. Особое внимание уделено показателям центральности и престижа, которые характеризуют активность экономического агента, включенного в сетевые отношения.
Почему экономисты говорят не только об экономических, но и о социальных сетях? Дело в том, что на эффективность и структуру экономических отношений оказывают влияние как экономические связи (товарные сделки, отношения взаимной помощи, отношения обмена информацией, отношения рационирования), так и связи неэкономические по своей природе (любовь, отношения родства, отношения старых сослуживцев или соучеников, принадлежность к одной нации, к одной церкви, языковая общность, наличие дипломатических отношений).
Социальные сети, в том числе сложившиеся помимо экономических причин, часто формируют готовые каналы экономического взаимодействия агентов: между ними постепенно возникает доверие, а следовательно, сложившиеся пары или сети агентов обладают преимуществом на фоне остальных (рис. 3.12).
Проиллюстрируем введенные выше понятия теории графов на социальных сетях. Для этого вернемся прежде всего к самому понятию социальной сети.
Социальная сеть. Социальная сеть представляет собой группу g из акторов, которые связаны друг с другом социальными отношениями. Обозначим множество акторов как N = {л,, ..., я }, а множество социальных отношений как Z ={/,,..., / }.
Граф. С помощью графа описывается множество акторов и связей между ними. Например, граф, изображенный на рис. 3.6b, может представлять собой и множество из четырех человек, часть которых знакома друг с другом (вершины обозначают людей, а ребра — наличие знакомства); и множество из четырех фирм, часть которых установила друг с другом производственные отношения (вершины обозначают фирмы, а ребра — наличие производственных отношений).
Ребра отражают связи между акторами. Эти связи могут быть как формальными, так и неформальными, как реальными, так и потенциальными.
148
3.2. Применение инструментария теории графов к социальным сетям
Рис. 3.12 |
- |
•••:•:.:<-. |
• |
Каналы
экономического
взаимодействия
агентов
наибольшая |
(доступная |
|
Л вероятность |
||
история |
||
выполнения |
||
сделок) |
||
обязательств |
||
|
^ - - |
л У ч ш е е |
(доступная |
|
история |
|
|
Hi качество |
сделок) |
Г |
|
|
i |
лучшая |
(текущее |
J |
||
! |
цена |
предложение) |
Ориентированный граф. Ориентированный граф, изображенный на рис. 3.10а, показывает отношения знакомства футбольных болельщиков, живущих в разных городах, со своим кумиром: они его знают, а он их — нет, между собой болельщики тоже не знакомы. С помощью ориентированного графа можно описывать отношения между акторами, когда важно направление связей между ними (материальные, информационные и иные потоки). -
Степень вершины. Степень вершины является значимой характеристикой социальных связей актора, который соответствует этой вершине. Чем меньше степень вершины, тем меньше связей у актора с группой, описываемой данным графом. Вершина степени 0 называется изолированной (у соответствующего этой вершине актора нет отношений ни с одним из членов группы).
Полный граф. Полный граф описывает, например, потенциальные торговые связи на идеальном рынке, где все могут торговать со всеми, а искажение информации, благодаря прямым информационным связям между всеми участниками, сведено к минимуму. Взаимодействие участников торгов на электронной бирже описывается практически полным графом.
Путь и дистанция. Если ребра графа описывают информационные связи, то пути — это каналы, по которым в графе движется информация. Заметим: чем длиннее дистанция между акторами, тем сильнее искажения информации и тем выше затраты по ее передаче. В частности, чем длиннее дистанция, тем сложнее осуществлять мониторинг деятельности экономических агентов (возникает своего рода «испорченный телефон»), —
Связность графа. Граф, которым описываются отношения «жить по соседству» в группе студентов (рис. 3.8), включает в себя в качестве вершин всех членов группы, однако не все эти студенты живут рядом друг с другом. Граф не является связным и содержит две компоненты.
Связные компоненты описывают сферы влияния акторов. Так, если граф несвязный, то в нем существуют акторы, между которыми нет пути.
149
Глава 3. Сети в институциональном анализе
Мост. Мостами служат купцы, торговцы, посредники, дипломаты. При этом актор, занимающий в структуре сети позицию моста, является важным, «центральным» участником сети (рис. 3.13).
Рис. 3.13
Мост
Плотность графа. Плотность графа отражает активность связей, долю реализованных взаимодействий в той или иной группе. , -
Деревья. Деревом описываются иерархические отношения в группе. Подобные отношения, например, свойственны организации, в которой каждый ее член подчиняется ровно одному начальнику и сам является непосредственным начальником конкретной группы исполнителей. Поскольку каждая связь в дереве является мостом, все они очень важны, и эффективность каждой принципиальным образом влияет на эффективность организации в целом. Действительно, если начальник не контролирует кого-то из своих непосредственных подчиненных, то тем самым он не контролирует и нижестоящие звенья, связь с которыми осуществляется исключительно через этого подчиненного.
О структурных
илокальных
свойствах
сетей
Как при анализе социальных взаимодействий распознать наиболее важных акторов, и если под «важными» понимать таких участников сети, которые активно включены в отношения с
150
3.2. Применение инструментария теории графов к социальным сетям
другими, то что брать в качестве критерия активности? На данный вопрос исследователи отвечают по-разному. Согласно одному из подходов, к важным относятся те акторы, которые включены во многие связи. На этом принципе основано понятие центральности актора. Здесь важен сам факт участия актора в связях, а не его роль — донора или реципиента — в них5. Согласно другому подходу, важными являются не все связи, а только те, в которых актор является реципиентом. На этом принципе основано понятие престижа {статуса). Действительно, престиж актора растет по мере того, как он становится объектом связей (а не по мере того, как растет количество инициируемых им связей).
Размещение производства и структура дорог в СССР
Еще в 1930-х гг. известный советский математик и экономист Л.В. Канторович, ставший впоследствии лауреатом Нобелевской премии, разработал основы теории оптимального размещения производства (в числе перспективных направлений ее применения была и прокладка дорог). Однако то, что реализовалось в действительности, далеко не всегда отвечало теории.
Почему Томский нефтехимический комбинат построен вдали не только от источников сырья, но и от транспортной артерии? Да просто местный начальник хотел, чтобы производство располагалось на подведомственной ему территории, а эффективность производства его не интересовала.
А сложившаяся у нас сеть автомобильных дорог? В каждой области она имеет лучевую структуру: из областного центра дороги ведут в районные центры, а из них — в мелкие деревни и населенные пункты. Добраться из населенного пункта одной области в населенный пункт другой, минуя центр, практически невозможно, даже если между этими пунктами каких-нибудь 10 км. Иногда дорога все-таки доходит до края области, но разворачивается и идет обратно. Почему сеть устроена столь неэффективно? Да просто потому, что для чиновников важнее не дорога в соседнюю область, а дорога в районный центр, в Москву, к начальству. Циркуляция администраторов, а не грузов — вот чем они руководствовались, принимая решения о прокладке дорог. И это происходило в СССР даже несмотря на жесткий партийный контроль.
Если вас удивляет структура сети, ищите факторы, которые могли ее обусловить.
Прежде чем перейти к последовательному обсуждению центральности и престижа для неориентированных и ориентированных графов, скажем несколько слов об оценке центральности. В отличие от престижа, ее можно анализировать применительно и к направленным, и к ненаправленным связям. Разные способы оценки порождают целое семейство показателей центральности актора. Произвольный показатель из этого семейства обозначим как СА(п.) и определим СА(п) как максимальное значение показателя центральности по всем акторам графа, вычисленное по данной методике:
Тогда показатель центральности графа, согласно Фриману6, будет равен
5 Данный подход предложен и развит в работах: Bavelas A. A Mathematical Model for Group Structure // Human Organizations. 1948. Vol. 7. P. 16—30; Bavelas A. Communication Patterns in Task-Oriented Groups // Journal of the Acoustical Society of America. 1950. Vol. 22. P. 271—282.
6 Freeman L.C. A Set of Measured of Centrality Based on Betweens // Sociometry. 1977. Vol. 40. P. 35—41.
151