Методы лапласовской теории орграфов в структурном анализе систем

Чеботарев, Павел Юрьевич

Системный анализ, управление и обработка информации (по отраслям)

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

доктора физико-математических наук: Чеботарев, Павел Юрьевич
город: Москва
год: 2008
специальность ВАК РФ: 05.13.01

Диссертация по информатике, вычислительной технике и управлению на тему «Методы лапласовской теории орграфов в структурном анализе систем»

Автореферат диссертации по теме "Методы лапласовской теории орграфов в структурном анализе систем"

УЧРЕЖДЕНИЕ РОССИЙСКОЙ АКАДЕМИИ НАУК ИНСТИТУТ ПРОБЛЕМ УПРАВЛЕНИЯ им. В.А.ТРАПЕЗНИКОВА РАН

УДК 519 177 519 173 519 816 На правах рукописи

Чеботарев Павел Юрьевич

МЕТОДЫ ЛАПЛАСОВСКОЙ ТЕОРИИ ОРГРАФОВ В СТРУКТУРНОМ АНАЛИЗЕ СИСТЕМ

Специальность 05 13 01 — Системный анализ, управление и обработка информации (в отраслях информатики, вычислительной техники и автоматизации)

□03440147

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математичес

Москва - 2008

003446147

Работа выполнена в Учреждении Российской академии наук Институте проблем управления им В.А. Трапезникова РАН

Официальные оппоненты:

доктор физико-математических наук профессор В В. Дикусар

доктор физико-математических наук Г.А Кошевой

доктор технических наук профессор В.В. Подиновский

Ведущая организация — Московский государственный университет им.М В.Ломоносова.

Защита состоится _ 2008 г. в_ч. на заседании Диссертационного Совета Д 002.226.02 Института проблем управления им. В.А. Трапезникова РАН по адресу 117997, Москва, ул. Профсоюзная, 65.

С диссертацией можно ознакомиться в библиотеке Института проблем управления им. В.А. Трапезникова РАН.

Автореферат разослан_2008 г

Ученый секретарь Диссертационного Совета кандидат технических наук

В.Н. Лебедев

Общая характеристика работы

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

Два основных направления в этой теории связаны с исследованием матрицы смежности графа и его лапласовской1 матрицы, по существу, отличающейся от матрицы смежности своей главной диагональю Первое направление наиболее полезно при анализе маршрутно-циклической структуры графов, второе — при анализе их древесной (лесной) структуры Первое направление развилось раньше, но к 90-м годам XX века все больше исследователей стало заниматься лапласовской алгебраической теорией графов, уже в 60—70-е гг существенные продвижения в ней были получены работавшим тогда в Институте проблем управления А К Кельмансом

К настоящему времени лапласовская теория неориентированных графов довольно хорошо разработана Еще в 90-е годы вышли обзоры

'Своим названием она обязана процессу дискретизации оператора Лапласа, приводящему к матрицам такого рода

Р Мерриса с соавторами и Б Мохара, а также монография Ф Р К Чанг, в которых были систематизированы более ранние результаты и представлены оригинальные результаты авторов этих работ

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

1 Децентрализованное управление многоагентными системами Линейный оператор согласования характеристик2, входящий в большинство дифференциальных и дискретных моделей распределенного управления, представляется лапласовской матрицей, соответствующей орграфу коммуникаций между агентами При этом свойства траекторий (сходимость, устойчивость и др ) полностью или частично определяются спектром и собственными подпространствами этой лапласовской матрицы

2 Химическая информатика Задачи идентификации сложных органических молекул и поиска связей между их структурными инвариантами и физико-химическими свойствами веществ требуют анализа графов, представляющих молекулы, методами теории матриц Лапласовские матрицы используются в этой области уже более четверти века

3 Кластер-анализ Один из подходов к кластеризации на графах связан с нахождением спектров и собственных подпространств их лапла-совских матриц

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

2Этот оператор часто называют оператором достижения консенсуса

пути характеризуют пропускной способностью по отношению к информации и управляющим воздействиям, критичностью разрыва по отношению к связности сети, сеть в целом оценивают степью связности, сплоченности, однородности, взаимности связей и т д Потребность в "оцифровке" возникает и при анализе/синтезе транспортных, компьютерных, организационных, семантических и других сетей, а также баз данных Другой класс задач, требующий специальной оцифровки вершин графов, — агрегирование экспертных оценок, оценка силы участников турнира, если турнир -некруговой или данные неполные, или план парных сравнений не сбалансирован Далее, следует упомянуть популярную в последнее время задачу ранжирования интернет-страниц, найденных поисковой машиной по пользовательскому запросу (PageRank problem) ранжирование производится с использованием орграфа ссылок страниц друг на друга Наконец, задачи такого типа нужно решать при разработке алгоритмов работы распределенных компьютерных рекомендательных систем, где каждый пользователь, указав свои музыкальные, литературные, кинематографические и т п предпочтения, получает рекомендации — что еще послушать (почитать, посмотреть), сформированные на основе предпочтений пользователей, имеющих близкие вкусы

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

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

Лапласовские матрицы ориентированных графов и соотношения их свойств и свойств орграфов изучены пока недостаточно, работ по этой про-

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

Цель диссертации — частично восполнить этот пробел Приложения, которым в работе уделяется наибольшее внимание, — построение структурных индексов графов и сетей, алгебраические методы агрегирования предпочтений и управление многоагентными системами

Цель работы: разработать основы лапласовской теории ориентированных графов и ее применений Достижение поставленной цели требует решения следующих основных задач

• Исследование лапласовских спектров орграфов,

• Разработка методов классификации остовных3 лесов (ор)графов,

• Разработка методов анализа (ор)графов с помощью классификации остовных лесов и с использованием матриц лесов,

• Установление соотношений между матрицами лесов с одной стороны и лапласовской матрицей, ее собственным проектором, матрицами, обобщенно обратными к ней, и другими матрицами орграфа — с другой,

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

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

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

1 Получена матричная теорема о лесах, обобщающая классическую матричную теорему о деревьях На ее основе построено новое семейство

3 Остовнъш называют подграф, множество вершин которого совпадает с множеством вершин графа, лес — граф без циклов

структурных индексов графов Введен класс лесных метрик графа и изучены его свойства, установлены связи между лесными метриками и резисторной метрикой графа

2 Получены выражения для собственного проектора, компонент и псевдообратной по Дразину произвольной вырожденной матрицы через аннулирующий многочлен для любой степени матрицы, большей или равной ее индексу

3 Изучена лесная структура графов и орграфов и алгебраические свойства матриц, представляющих остовные леса Доказано, что матрица максимальных входящих лесов орграфа является собственным проектором его лапласовской матрицы Следствие этого факта — матричная теорема о деревьях для цепей Маркова Матрицы лесов проинтерпретированы в терминах вероятностей многошаговых переходов цепей Маркова Получены явные выражения и топологические интерпретации для псевдообратных по Дразину и Муру-Пенроузу лапласовских матриц графов и орграфов

4 Локализована область спектров лапласовских матриц орграфов Полученные результаты анализа лапласовских спектров орграфов применены к исследованию моделей согласования характеристик в децентрализованном управлении многоагентными системами

5 Аксиоматически построен и исследован новый метод агрегирования неполных предпочтений — обобщенный метод суммы очков, оценки которого выражаются с помощью матричной теоремы о лесах Наиболее известные алгебраические методы агрегирования предпочтений проверены на выполнение аксиомы самосогласованной монотонности

6 Разработан нормативный подход к анализу мер близости вершин графов и орграфов Введено понятие функций ^-близости и установлена их двойственность метрикам

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

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

целевых функций" (Хаген, 1995 г), Российско-испанском семинаре по групповому выбору (Барселона, 1995 г), Международном семинаре по агрегированию информации и решений (Вашингтон, 1996 г), 3 Международном симпозиуме Общества социального выбора и благосостояния (Маастрихт, 1996 г), Международной научно-практической конференции "Управление большими системами" (Москва, 1997 г), 7 Конференции Международного общества по линейной алгебре (Мэдисон, 1998 г), 1 Международной конференции по проблемам управления (Москва, 1999 г), 20 Международной конференции по социальным сетям (Ванкувер, 2000 г), 5 Международном симпозиуме Общества социального выбора и благосостояния (Аликанте, 2000 г), Международной конференции по анализу порядковых и символьных данных (Брюссель, 2000 г), 7 Конференции Международной федерации обществ классификации (Намюр, 2000 г), 4 Международной конференции "Эконометрические модели принятия решений конструирование и применение целевых функций" (Хаген, 2000 г), 2 Международной конференции "Логика, теория игр и социальный выбор" (Санкт-Петербург, 2001 г), Международной конференции по линейной алгебре (Хайфа, 2001 г), 2 Европейском семинаре по алгебраической теории графов (Эдинбург, 2001 г), Международной конференции "Теория полезности и ее применения" (Триест, 2002 г), Международной конференции по матричному анализу и его применениям (Форт Лодердейл, 2003 г), 13 Конференции Международного общества по линейной алгебре (Амстердам, 2006 г), Международной конференции обществ GAMM и SIAM по прикладной линейной алгебре (Дюссельдорф, 2006 г)

Публикации. Материал диссертации опубликован в 77 работах, среди которых 22 - статьи в ведущих рецензируемых журналах (список ВАК России) [1-4,17,18,22,28-33,37,43,44,46,47,50,52,57,59], 21 - статьи в других изданиях [5-10,12,14-16,20,34,38,41,45,51,53-56,58] и 34 - тезисы докладов (объемом не более 3 страниц), в том числе [11,13,19,21,2327,35,36,39,40,42,48,49] 18 работ опубликовано по смежной теме — кооперативному принятию решений, из них 4 — в журналах из списка ВАК РФ Объем и структура работы. Диссертация состоит из введения,

десяти глав, заключения и списка литературы, число наименований в котором — 403 Основное содержание работы изложено на 279 страницах

Содержание диссертации

Во введении обосновывается актуальность темы диссертации, определяется цель исследования, приводится краткое содержание работы, перечисляются основные результаты

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

В терминологии теории графов мы следуем в основном Ф Харари Пусть С - взвешенный мультиграф с множеством вершин = {1, ,п} и мультимножеством4 ребер £'(С), Г — взвешенный мультиорграф5 с множеством вершин У(Г) = {1, , п} и мультимножеством дуг Е(Т), п> 1 Ребро — неупорядоченная пара вершин, дуга — упорядоченная пара вершин

Через > 0 обозначим вес р-го ребра (дуги) из г в ] £ ~ (г1}) — матрица суммарных весов ребер (дуг) для пар вершин

где пч — число ребер (дуг), соединяющих г с у еч — 0 тогда и только тогда, когда из г нет ребер (дуг) в ] Произведение весов всех ребер (дуг) подграфа Я мультиграфа С (мультиорграфа Г) называем весом Н и обозначаем е(Н) Вес подграфа, не имеющего ребер (дуг), принимается равным 1 Для непустого множества 0 подграфов его вес есть

4В мультимножестве допускается кратное вхождение элементов 5В работе всюду рассматриваются взвешенные мультиграфы и мультиорграфы, прилагательное "взвешенный" и префикс мульти- будем иногда опускать

£(а) = ]Г£(я)

Нед

Вес пустого множества равен нулю

Определение. Лапласовская матрица взвешенного мультиорграфа Г — это (п х п)-матрица Ь = ДГ) = (£г]) с элементами

Матрица Кирхгофа взвешенного мультиорграфа Г — это (п х гг)-матрица

Отличие определений лапласовской матрицы и матрицы Кирхгофа

— порядок индексов в выражениях недиагональных элементов Лапласовской матрицей представляется линейный оператор согласования характеристик (оператор достижения консенсуса), входящий в большинство дифференциальных и дискретных моделей децентрализованного управления мно-гоагентными системами Это приложение лапласовской теории орграфов рассмотрено в главе 5 диссертации

Лес - граф без циклов Дерево - связный лес Корневой лес — лес с одной отмеченной вершиной (корнем) в каждом дереве Корневое дерево

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

Ь = £(Г) = [£,3) с элементами

Через ^""(Г) = и = р^* обозначаем множество всех

остовных исходящих лесов мультиорграфа Г и множество всех остовных исходящих лесов Г с к дугами и Т1*^1 — множество всех остовных

исходящих лесов, где у принадлежит дереву, исходящему из г, и множество таких же остовных исходящих лесов с к дугами Соответствующие обозначения для входящих лесов , и Г^'3 Аналогичные обозначения для неориентированных графов !Р, Тк, Т""3 и Т^ Рассмотрим матрицы

IV = Щв) = 1 + ¿(С?), Ш = И^Г) = 1 + 1(Г), Ш = ]¥{Г) = 1 + ЦГ),

где I - единичная матрица Пусть <3 = (д ) = <3 = (<?ц) = И/"-1 (если эти матрицы существуют)

Теорема 1.4 (матричная теорема о лесах)6

1 Для любого взвешенного мулътпиграфа существует матрица (5, и дг] =

г(ЯЧ/£(Я = 5(Я)/£(Я, г,3 = 1, ,п

2 Для любого взвешенного мультиорграфа существуют матрицы <3, <2, « % = % = г,3 = 1, ,п

В главе 1 приведены два доказательства этой теоремы и указаны ее взаимосвязи с другими результатами алгебраической теории графов Существенная часть результатов диссертации связана с этой теоремой

Во второй главе диссертации приведен ряд результатов по теории матриц Первоначально они были получены при исследовании собственного проектора лапласовской матрицы орграфа, используемого в задачах управления многоагентными системами и других приложениях Далее эти результаты были сформулированы и доказаны в общем виде А именно, получены выражения для собственного проектора (главного идемпотента) произвольной вырожденной матрицы А, ее компонент, минимального мно-вНумерация теорем, формул, рисунков — как в диссертационной работе

гочлена и псевдообратной по Дразпну А° через любой ненулевой аннулирующий многочлен для А™, где и тс! А

Пусть А € Спх" — квадратная матрица Через %{А) и ]\[{А) обозначаем образ и ядро А соответственно Индексом А, тс1 А, называют наименьшее к е 1Ки{0}, при котором гапк(Л,с+1) = тапк(Ак) Пусть шс1А = и Собственным проектором (главным идемпотентом) матрицы А, соответствующим собственному значению 0, или, для краткости, собственным проектором А называют такой проектор (т е идемпотентную матрицу) Z, что 71(2) = М(А") и = К{А") Собственный проектор единствен, т к проектор определяется своим образом и ядром

Теорема 2 1. Пусть тс1 А = V, и £ ВЧ и {0}, и > и Тогда для любого многочлена <^(А) = Аг(А9 + рхХ4'1 + + рч) (рч ф 0), аннулирующего для Аи, матрица

г = /г(Аи),

где /г(Л) — А9 -Ь^А9-1 + + р9), — собственный проектор для А

Пусть Лг, , А3 — различные собственные значения А Через Уи обозначим индекс собственного значения \к (к = 1, , а), т е размер наибольшей жордановой клетки А, соответствующей А^, равный степени множителя (А — А^) в минимальном многочлене А Собственным проектором А, соответствующим А к, называют собственный проектор матрицы А — А ¡¡I Найдя Аь , А„, можно использовать теорему 2 1 для нахождения соответствующих им собственных проекторов, что, в свою очередь, позволяет строить функции от матрицы Для любой функции / С —» (С, имеющей в точках А^ (к — 1, , з) конечные производные f<J>>(Xk) порядков 3 = 0, , у к, по определению,

где /(°)(Ак) = /(Ак), а матрицы 2к3 — так называемые компоненты А Компонента гкй есть собственный проектор А, соответствующий А к, а остальные компоненты находятся последовательным домножением на А — А

и числовые коэффициенты

гк^(зГ\А-хк1угк0 (2 16)

Все компоненты линейно независимы, поэтому среди них нет нулевых При этом для всех к = 1, (А — \к1)"к = 0 Таким образом, после нахождения компоненты Дщ с помощью теоремы 2 1 остальные компоненты вычисляются по формуле (2 16), процедура заканчивается, когда получен 0 Найденное число компонент равно ик

Теперь знание и ик позволяет построить минимальный многочлен для А ■¡/'(А) = — Итак, начав с нахождения собственных

значений А и аннулирующих многочленов для {А — Л^/)", и > 1пс1(А — Лк1), к = 1, ,5, далее находим собственные проекторы, соответствующие всем собственным значениям, а также компоненты А, индексы собственных значений и минимальный многочлен для А

Следующее выражение для собственного проектора матрицы А и ее компонент полезно в случае, когда известны не коэффициенты аннулирующих многочленов, а все различные собственные значения А

Теорема 2.2. Пусть А 6 СГ1ХП имеет индекс V и собственный проектор 2", пусть Ах, , А, — все ее различные собственные значения, и\, — их индексы, а целые числа и,щ, ,и3 таковы, что и > и и щ ^ I/, (г — 1, , в) Тогда

П (Аи - А,"/)"'

2 = -гтг-, (2 17)

(п (-агоУ

V 1 м /

\ Л.^О

2к] = *к-^-ЬГЧА-Х^у, (2 18)

где к = 1, , в, ] = 0, , ик - 1

Теорема 2 2 обобщает известную формулу, верную для недефектных матриц Результаты главы 2 применяются в главе 3, где, в частности, изучаются собственные проекторы матриц Кирхгофа и Лапласа

В третьей главе подробно исследованы свойства максимальных исходящих лесов взвешенного орграфа и соответствующей им матрицы Доказано, что матрица максимальных входящих лесов является собственным проектором лапласовской матрицы орграфа Рассмотрены цепи Маркова, связанные со взвешенным орграфом, и показано, что прямым следствием полученных в работе утверждений является известная матричная теорема о деревьях для цепей Маркова (в англоязычной литературе — Markov chain tree theorem) Эти результаты составляют основу анализа моделей согласования характеристик в управлении многоагентными системами (гл. 5) Обсуждается применение матриц максимальных лесов в задаче выявления структуры орграфа Другие их применения — в задачах агрегирования предпочтений и измерения близости вершин взвешенного орграфа — изложены в главах 6 и 9 Ниже приводятся основные результаты главы 3 и необходимые определения

Остовный исходящий лес F мультиорграфа Г максимален, если в Г нет остовных исходящих лесов с числом дуг, большим, чем в F Каждый максимальный исходящий лес содержит минимально возможное число исходящих деревьев, это число назовем размерностью мультиорграфа по исходящим лесам и обозначим v Число дуг в любом таком лесе равно п — v Число входящих деревьев в любом максимальном входящем лесе

— размерность мультиорграфа по входящим лесам, обозначаемая v' Для мультиорграфа на п вершинах v,v' € {1, , n}

Рассмотрим матрицы Qk ~ (<?£,) с элементами g* = к =

О, ,п — v В частности, элемент матрицы Q„-v есть вес множества всех максимальных исходящих лесов Г, в которых вершина г принадлежит дереву, исходящему из j Матрицу Qn~v назовем матрицей максимальных исходящих лесов Г Нормированной матрицей максимальных исходящих лесов назовем матрицу J = (Jy) = Qn-v/<rn-v, где cr„_„ =

Непустое подмножество вершин К С V(T) мультиорграфа Г — недоминируемый узел7 в Г, если все вершины, принадлежащие К, взаимно

7Недоминируемые узлы называют также базовыми бикомпонентами (бикомггонента

— компонента сильной, т е двусторонней связности)

достижимы и недостижимы из других вершин Г Пусть К = У Ки где

«=1

А'ъ , Кч — все недоминируемые узлы Г, а К* — множество всех вершин, достижимых из Кг и недостижимых из других недоминируемых узлов Через Г к обозначим сужение Г на К и через Г-к — подграф с множеством вершин У(Г) и множеством дуг £,(Г)\£,(Г/<) Зафиксировав К, через Т обозначим множество всех остовных исходящих деревьев мультиорграфа IV, а через V — множество всех максимальных исходящих лесов мультиорграфа Г_к Через Тк (к 6 К) обозначим подмножество Т, состоящее из деревьев, исходящих из к, а через -рК'~*1 £ 1/(Г)) — множество всех максимальных исходящих лесов в Т~к, где г достижима из некоторой вершины, принадлежащей К Через 3 3 обозначаем _?-й столбец 3

Теорема 3.2'. Пусть К — недоминируемый узел мультиорграфа Г Выполняются следующие утверждения

_ _ п _

1 3 — строчно-стохастическая Зг] ^ 0, «Лк = 1, г, ^ = 1, ,п

2 Зчф 0 (з е К иг достижима из ] в Г)

3 Пусть з & К Для любого г е К(Г) 31} = е(Т}) £(-рК'~*г)/<гп-и Если при этом г £ К+, то 31} = З3] — £(Т3)1е(Т)

4 = 1

^к

5 Если л, л € К, то 3 ь = (е{Т]*) I е{Тп)) 3 п

Теорема 3.3. Для любого мультиорграфа Г и всех г,] £ {1, , п} имеет место следующее

1 3ц ^ 3

2 Если Зп > 3}1, тог 6 К и ] $ где К^ Э г, и, следовательно, Г не содержит путей из ] в г

3 Если Зп > Зп > 0, то з ф К, и значит, ] не является корнем ни в одном максимальном исходящем лесе Г

4 Если Зг}

> О, то Зи = 3

— — 2 — Теорема 3.4. Матрица 3 идемпотентна 3=3

Теорема 3.5. 13= 31 = О

Теорема 3.6. J = limг_оо(/ + r L)_1

Теорема 3.7. Для любого мулътиорграфа

1 Матрицеi8 L + J* невырождена,

2 rank L = n — v, rank J — v,

3 JV(L) - u ЩЬ) = Af(J),

4 7l(L)nft(J) = {0},

5 mdL = 1,

6 J — собственный проектор матрицы L

Определение 3 2. Будем говорить, что стационарная цепь Маркова с множеством состояний {1, , п} и переходной матрицей Р связана с ор-

Определение 3.3. Предельная матрица средних вероятностей цепи Маркова с переходной матрицей Р — это матрица9

Из п 6 теоремы 3 7 выводится следующая теорема, впервые полученная А Вентцелем и М Фрейдлиным и позже неоднократно переоткрывавшаяся

Теорема 3 8 (матричная теорема о деревьях для цепей Маркова) Для любой цепи Маркова, связанной с мультиорграфом Г, предельная матрица средних вероятностей Р°° равна 1(Г)

Матрицей достижимостей орграфа Г называют матрицу (гу), каждый элемент г, которой равен 1, если Г содержит путь из г в и 0 в противном случае

Использование матриц лесов для выявления структуры орграфа основано на использовании теорем 3 2' и 3 3 и следующего предложения

вЧерез У обозначена матрица, эрмитово сопряженная (в данном случае — транспонированная) к 1

9Данный предел, в отличие от Ьт^с Рк, всегда существует

графом Г, если существует а ф 0, такое что Р = I — a L(Г)

(3 12)

Предложение 3.16. Матрица достижимостей орграфа может быть получена из матрицы (?т(т), где 0(т) = (/ + тЬ)-1, при любом т > О заменой всех ее непулевых элементов на 1 Поскольку результат не зависит от весов дуг, все они могут быть выбраны равными 1

Отметим, что нахождение матрицы 1 позволяет сразу определить недоминируемые узлы мультиорграфа и вершины, достижимые из каждого узла, что важно для приложений Методы вычисления ,/ приведены в главах 2, 3 и 4 диссертации

В четвертой главе изучается множество всех остовных исходящих лесов орграфа и связанные с ним матрицы Показано, что нормированная матрица исходящих лесов орграфа 0(т) = (I + тЬ)~1 является матрицей переходных вероятностей в геометрической модели наблюдения за цепью Маркова Получены выражения псевдообратной матрицы Ь+ и групповой обратной матрицы Ь* для матрицы Кирхгофа Ь через матрицу максимальных исходящих лесов орграфа Матрицы исходящих лесов с заданным числом дуг и нормированные матрицы исходящих лесов представлены многочленами от матрицы Кирхгофа, с помощью этого представления дано новое доказательство матричной теоремы о лесах и некоторых других результатов алгебраической теории орграфов Для матрицы Кирхгофа указан аннулирующий многочлен, степень которого определяется размерностью орграфа по исходящим лесам Области приложения этих результатов управление многоагентными системами, агрегирование предпочтений, анализ структуры графов и сетей и построение их алгебраических индексов

Пусть цепь Маркова связана с орграфом в смысле определения 3 1, и а - параметр связи Рассмотрим следующую модель, приводящую к геометрическому распределению моментов наблюдения Геометрическая модель выбора момента наблюдения. Проводятся испытания Бернулли с вероятностью успеха д (0 < д < 1) в моменты времени ¿ = 0,1,2, Момент первого успеха становится моментом наблюдения

Рассмотрим переходы цепи Маркова за случайное число шагов от начального состояния, в котором цепь находится в момент £ = 0, к состоя-

нию в момент наблюдения, подчиняющийся геометрической модели с параметром д Пусть Р(а, <7) = (ру(а,д)) — матрица безусловных вероятностей переходов данной цепи за указанное число шагов

Теорема 4.1. Для любых взвешенного орграфа, параметра т > 0 и связанной с орграфом цепи Маркова имеет место

${т) = Р(а,Я), где Я = {т/а + 1)~1

Существенным результатом главы 4 является рекуррентная процедура вычисления матриц исходящих лесов фь , £)п-у, где б^ = (<?*), 4% — — , п, а также весов — множеств лесов

Начав с матрицы С)й = I, остальные матрицы <3ь включая <5= можно последовательно найти с помощью следующей теоремы

Теорема 4.2. Для любого взвешенного орграфа

<2к+1 = - (Га.+1 = к = 0, , п - и

к + 1

Эта теорема позволяет также проинтерпретировать матрицы, вычисляемые при получении характеристического многочлена матрицы Кирхгофа с помощью алгоритма Леверье— Фадцеева

Далее, установлено, что матрицы (¿к исходящих лесов с к дугами выражаются очень простыми многочленами от матрицы Кирхгофа

Теорема 4.3. Для любого взвешенного орграфа и любого к = 0, , п — V

»=0

С помощью теоремы 4 3 нормированная матрица исходящих лесов <5 = (/ + ¿) также представляется в виде многочлена от Ь

Теорема 4.4. Для любого взвешенного орграфа

г—О

где вк = о3 — вес множества исходящих лесов в Г с числом дуг, не превосходящим к, а = = ак

Изучены свойства нормированных матриц Jk = aklQk исходящих лесов с к дугами (к = 0, ,п — v), J = J„_v В частности,

Предложение 4 5. Матрицы Jk — строчно-стохастические

Получены выражения групповой обратной L* и обобщенно обратной по Муру-Пенроузу L+ для матрицы Кирхгофа

Теорема 4.7. При любом а ф О

L* = {L +а J)'1 -а'1 J, причем L*L = LL* — I — J

Предложение 4.6. l* = lim t[q{t) — J^ Предложение 4.7 L* = (Jn~v~1 (Jn_„_! - J)

Gn—V

Пусть Z = L + J* Доказано, что эта матрица невырождена

Теорема 4.8. L+ = L'iZZ')'1 = L*(J*J +LL*)'1

Как установлено в главе 2, для нахождения собственного проектора вырожденной матрицы А, ее компонент, функций от нее, псевдообратных и др полезно знать аннулирующий многочлен для Аи при и > md А Согласно теореме 3 7 md L = 1 По теореме Кэли-Гамильтона аннулирующим является характеристический многочлен Следующее предложение указывает аннулирующий многочлен более низкой степени

Предложение 4.9. Многочлен р(А) = сгп_„_, (—А)1 является ан-

нулирующим для L

В главе изучены также некоторые свойства линейных операторов, определяемых матрицами L, J и J*

Зная свойства матриц Кирхгофа, легко установить свойства лапла-совских матриц Для этого достаточно обратить все дуги орграфа (с сохранением их весов) Тогда лапласовская матрица исходного орграфа равна

матрице Кирхгофа получившегося, исходящие леса получившегося орграфа однозначно и с сохранением весов соответствуют входящим лесам исходного Таким образом, "графовые" свойства лапласовской матрицы получаются из свойств матрицы Кирхгофа заменой исходящих лесов на входящие и инверсией индексов — точно так, как в матричной теореме о лесах (теорема 1 4) В следующих главах чаще встречаются лапласовские матрицы, т к в формулировках их свойств порядок индексов оказывается более естественным

В пятой главе изучается спектр лапласовских матриц орграфов и соотношение спектров лапласовских и стохастических матриц Показано, что нормированные лапласовские матрицы Ь являются полусходящимися Установлено, что кратность собственного значения 0 матрицы Ь равна размерности по входящим лесам соответствующего орграфа, а кратность собственного значения 1 на единицу меньше размерности по входящим лесам дополнительного орграфа Доказано, что спектры матриц Ь принадлежат пересечению двух кругов с центрами в точках 1 /п и 1 - 1/п и радиусом 1 — 1/п Кроме того, область, их содержащая, входит в пересечение двух определенных в данной главе угловых областей с вершинами 0 и 1 и полосы |1т(л)| ^ (в пределе — полоса |1т(.г)| < Построен многоугольник, все точки которого являются собственными значениями нормированных лапласовских матриц порядка п и сформулирована гипотеза, что этот многоугольник совпадает с областью собственных значений указанных матриц Эти результаты необходимы для анализа моделей управления мно-гоагентными системами и уже нашли применение в этой области

Действительную квадратную матрицу порядка п называем нормированной (стандартизованной) лапласовской матрицей, если (1) ее строчные суммы равны 0, (2) ее недиагональные элементы неположительны и не превосходят 1/п по модулю Использование такой нормировки облегчает сравнение результатов, касающихся локализации спектров лапласовских матриц, при разных п Нормированные лапласовские матрицы обозначаем Ь

Если рассматривается класс Оь взвешенных орграфов с весами дуг,

не превосходящими Ь > 0, и Ь(Г) — лапласовская матрица взвешенного орграфа Г на п вершинах, то нормированная лапласовская матрица, связанная с Г, определяется в классе Оь как ¿(Г) = (пЬ)~1£(Г)

Пусть 7 £ И"*" — матрица10 со всеми элементами 1 /п, К = I — .] К 6 Ипх" — нормированная лапласовская матрица полного орграфа с весами всех дуг Ь в классе орграфов Оь Определим матрицы

Р = I + ■/, (5 9)

Ьс = К-I (5 10)

Тогда Р — стохастическая матрица, Ьс - нормированная лапласовская матрица дополнительного взвешенного орграфа Гс, в котором (Ь — ег1)

- вес дуги (г,^), ] ф г, где е1} — вес той же дуги в Г Если ец = Ь, то в Гс нет дуги (г,з) и наоборот если в Г нет дуги (г,]), то вес дуги (г,з) в Гс равен Ъ В силу (5 9), (5 10) и определения К

Р = 1-1с (5 11)

Следующие результаты касаются соотношения спектров ¿, Р и Ьс

Теорема 5.3. Пусть Ь — нормированная лапласовская матрица, Р и Ьс определяются (5 9) и (5 10) Тогда для А {0,1} следующие утверждения эквивалентны11

(а) А 6 эр ¿, (б) А е эр Р, (в) 1 - А 6 эр Ье, причем эти собственные значения имеют одну и ту же геометрическую кратность Кроме того, и — собственный вектор Ь, соответствующий собственному значению А ^ {0,1}, тогда и только тогда, когда вектор12

у (5 12)

— собственный вектор Р, соответствующий А, а также собственный вектор Ьс, соответствующий 1 — А

шНе путагь с матрицей 7, изучавшейся в главе 3

"ар Л — спектр матрицы А

"Вместо ~А иногда пишем где А - матрица, а ф 0 - комплексное число

Теорема 5.4. Пусть /¿(А), /р(А) и fic(X) — характеристические многочлены L, Р и Lc соответственно Тогда для всех А ^ {0,1}

ÎP{ А) = ^Д(А), (5 14)

/£с(А) = (-1Г114дЛ(1-Л) (5 15)

Теорема 5 5 Для любой нормированной лапласовской матрицы L и матрицы Р, определяемой (5 9), L и Р — полусходящиеся

Теорема 5 6. Пусть d и dc — размерности по входящим лесам орграфа, соответствующего L, и дополнительного орграфа Тогда13

1)m£(0) = d, т£(1) = 4-1,

2) тР{0) = d - 1, mP(l) = dc,

3)m£c(l) = d-l, mLc(0) = dc,

и эти собственные значения — полупростыеи,

4) Если15 v G VL{0) и Kv ф- 0, то Kv € V>(0) = Vic{\), если х G Vp(l) = VjJO) «fo^O, mo Ka; G VL(l)

Теорема 5.7. 1 Все собственные значения нормированных лапласовских матриц порядка п принадлежат

• пересечению двух замкнутых кругов с центрами в точках 1/п и 1 — 1 /пи радиусом 1 — 1/п,

• меньшей замкнутой угловой области, ограниченной лучами, исходящими из точки 1 и проходящими через точки е~2т!п и е2™/п,

• меньшей замкнутой угловой области, ограниченной лучами, исходящими из точки 0 и проходящими через точки и

2 Для мнимых частей А) собственных значений А нормированных лапласовских матриц имеет место |Э(А)| ^ ^ctg^

13тд(А) - алгебраическая кратность А е sp.A

14Т е с совпадающими алгебраической и геометрической кратностями

15Уд(А) — собственное подпространство А, соответствующее А

Замечание 5.2. Используя теорему Дмитриева и Дынкина (1946) о спектрах стохастических матриц, можно показать, что spL содержит собственное значение с аргументом \ — \ тогда и только тогда, когда Г — гамиль-тонов цикл на п вершинах При этом собственное значение А с таким аргументом единственно и |А| $ | sin Э(А) < ^ sm Данному собственному значению соответствует собственный вектор, компоненты которого — вершины правильного n-угольника на комплексной плоскости Аналогично sp L содержит собственное значение, принадлежащее отрезку [1, е2?], тогда и только тогда, когда Гс — гамильтонов циклом на п вершинах Такое собственное значение Л' также единственно и З(А') $ ~ sin ~

Рис 5 2 Область, согласно теореме 5 7 содержащая спектр нормированной лапласов-ской матрицы порядка п (заштрихована), здесь п~7

Теорема 5 7 и замечание 5 2 иллюстрируются рисунком 5 2 Пусть £„ — класс нормированных лапласовских матриц порядка п Изучим вопрос о локализации спектров матриц Ь € Сп Положим

Ак(п) = ^ (к - е~2т/п - -в"2*"/»), к = 1, ,п- 1 (5 22) Это выражение приводится к виду

sin ^

Afc(n) = n"1 I fc - -j-f - e-(l+1)"/n , к = 1, , n - 1 (5 23)

\ sm ñ /

Обозначим через 5(71) выпуклый многоугольник с вершинами

А0(п) = 0, Ai(n), , An_2(n), A„_i(n) = 1, Ä„_2(n), ,Äi(rc) (5 24)

Теорема 5 8. Каждая точка многоугольника S(n) — собственное значение некоторой матрицы L Е Сп

Пусть h(n) = sup{íí(A) А — собственное значение L 6 £„} В силу теоремы 5 7 для всех п = 2,3, /i(n) é

Теорема 5.9. Если п нечетно, то

= (5 26)

кроме того, h(n) = Q(A(n_i)/2(n)), где \n-i)ß{n) определено (5 22) Следствие 5.2 из теоремы 5 7 lim h(n) = \)-к

п—>оо

Следующее предположение пока не доказано

Предположение 5.1. Вне многоугольника S(n), вершины которого задаются формулой (5 24), не существует собственных значений нормированных лапласовских матриц порядка п

Теорема 5.10 Граница многоугольника S(n) с вершинами (5 24) при п —> оо сходится к овалу, образуемому участками двух циклоид с параметрическими уравнениями z(t) = х(т) + гу(т) и z(t) = х(т) — гу(т), где т € [0,2тг],

i(T) = (2ir)~1(T-smr), (5 27)

у(т) = (2тг)-1(1 -cos г) (5 28)

3(а)

1 Я(Л)

Рис 5 3 Многоугольник лапласовских собственных значений при п = 4ип = 5и предельная кривая, задаваемая теоремой 5 10

На рис 5 3 показаны многоугольники 5(п) при п — 4 и п = 5, а также предельная кривая, уравнение которой определяется теоремой 5 10

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

Вазовая дифференциальная модель распределенного согласования характеристик агентов имеет вид

где п - число агентов, — характеристика г-го агента в момент £, ач(1) ^ 0 — вес, с которым г-й агент учитывает расхождение в значении характеристики с >ым агентом В качестве характеристик могут рассматриваться положение в пространстве (если агентам необходимо сблизиться), скорость (если они участвуют в совместном движении), моменты ожидаемого прибытия в пункты назначения (если эти моменты необходимо синхронизировать) и т д Данную модель называют также моделью достижения консенсуса

Обычно при децентрализованном управлении необходимо решать бо-

,71.

(5 29)

лее сложные задачи, чем простое согласование характеристик Так, если рассматривается управление комплексом движущихся объектов, то типичная задача — движение по заданной траектории с сохранением геометрической формы комплекса объектов и стабильной ориентации по отношению к курсу движения Если необходимо произвести резкий маневр, то при маневре геометрическая форма может быть изменена, но после его окончания она должна быть восстановлена Изменение и последующее восстановление формы характерны также для ситуаций, когда комплекс движущихся объектов сталкивается с опасностью или встречает препятствие Во всех этих случаях согласование характеристик агентов — далеко не единственный, но обязательно присутствующий элемент стратегии управления Этот элемент — ключевой в том смысле, что именно от него обычно зависят показатели устойчивости системы, ее управляемости и т д Поэтому анализ моделей согласования, таких, как модель (5 29), в том или ином виде производится и при исследовании более сложных процессов управления Именно моделям согласования в главе 5 уделяется наибольшее внимание

Модели (5 29) ставят в соответствие взвешенный ориентированный граф коммуникаций агентов Г(<), и в матричной форме она приобретает вид

1(4) =-¿(4) ®(«), (5 30)

где х(4) = (21(4), , хп(^)г, Ь{Ь) - матрица Кирхгофа орграфа коммуникаций Г(£) Тем самым, свойства траекторий модели (5 29) определяются спектральными свойствами лапласовских матриц / матриц Кирхгофа, изученными в данной главе и главе 3 Поэтому некоторые из этих свойств, впервые опубликованные нами в 2000 г, позже неоднократно переоткрывались в работах по децентрализованному управлению

Дискретизацией модели (5 29) получают итерационную модель распределенного согласования характеристик

х1(к+1)~Хг(к)-Е'^2а1]{к)(хг{к)-х](к)), г = 1, ,п, (5 31)

3=1

где к — дискретное время, е > 0 — шаг разностной схемы В матричной форме модель (5 31) имеет вид

х(к + 1) = Рех(к), (5 32)

где Ре ~ I — еЬ — строчно-стохастическая (при достаточно малом е) матрица, изучавшаяся в главах 3—5 диссертации Свойства модели (5 32) определяются спектральными свойствами матрицы Ре Они могут быть исследованы с помощью собственного проектора матрицы I — РЕ, совпадающего с собственным проектором Ь и с нормированной матрицей остовных исходящих лесов 7 орграфа коммуникаций Г(£), изученной в диссертации Модели (5 29), (5 31) являются базовыми, при анализе более сложных моделей децентрализованного управления, предполагающем исследование сходимости, устойчивости, управляемости, скорости сходимости и т д , также применимы (и уже применялись) результаты по локализации спектров ла-пласовских матриц, полученные в главах 3—5

В шестой главе подход, связанный с построением структурных индексов графов, используется для анализа, в духе теории группового выбора, "чувствительных" алгебраических методов агрегирования предпочтений Введена аксиома, "самосогласованной монотонности" (ССМ) и установлено, что ряд известных алгебраических методов оценивания относится к классу процедур, комбинирующих победы и поражения и, согласно доказанной в главе 6 теореме, нарушают ССМ Получено достаточное условие самосогласованной монотонности и указаны процедуры, ему удовлетворяющие

Рассматриваются данные о предпочтениях в форме массива А — (А^, , Апарных сравнений объектов, где А^ = (о^)пхп Элемент арл есть результат сравнения объектов % и ], произведенного р-ым индивидуумом а^ = 1 интерпретируется как чистый выигрыш, ар1к = 0 — как чистый проигрыш, и допускаются промежуточные градации, например, арк = 0,5 (ничья, равноценность) Такой массив, вообще говоря, неполный (не все аргк определены) называем профилем индивидуальных предпочтений Оценивающая процедура — функция 5 из множества рассматриваемых профилей в Л", где значение в = (з^ , яп)Т функции 5 есть вектор-столбец оценок объектов Оценивающие процедуры, рассматриваемые в главе 6, нейтральны (любая переиндексация объектов сохраняет их оценки) и анонимны (лю-

бая переиндексация участников сохраняет оценки объектов) Под агрегированием предпочтений понимаем сопоставление объектам оценок 51, , чем больше оценка, тем интенсивнее коллективное предпочтение

Самосогласованная монотонность (ССМ). Процедура оценивания 5 самосогласованно монотонна, если для любого множества объектов ¿Г, любого профиля А и любых объектов € ¿Г она удовлетворяет следующему условию

Пусть и{ ~ {а%к | к, р) и 113 = (а'( | - мультимножества результатов сравнений объектов г и ] соответственно Предположим, что II, может быть разбито на II/ и а £/, может быть разбито на и* и и'1 таким образом, что

(Л) Если аргк € и', то а?гк - 1, если а'}1 е и*, то а®, = О,

(В) существует взаимно-однозначное соответствие п из и*1 на и'!, такое что п{а%к) = ачз1 влечет а%к > ая}1 и Эк > я;

Тогда 5, г*

Кроме того, если [// непусто, или [/' непусто, или хотя бы одно неравенство в (В) хотя бы в одном случае — строгое, то зг >

Рисунок 6 2 иллюстрирует соотношение объектов г и ], удовлетворяющих посылке самосогласованной монотонности

Рис 6 2 Фрагмент массива предпочтений, включающий результаты г и J

Будем говорить, что процедура оценивания 5 основана на индивидуальных оценках, если существуют функции / и <5, такие что для всех про-

филей А — > соответствующие им векторы оценок в предста-

вимы в виде в = ¿(э^1', где — вектор оценок, зависящий лишь

от матрицы сравнений участника р = /(А^), р = 1, , т

Предложение 6.1. Существуют оценивающие процедуры, основанные на индивидуальных оценках, которые удовлетворяют ССМ на полных предпочтениях, но никакая процедура этого типа не удовлетворяет ССМ на неполных предпочтениях

Далее рассматриваются процедуры, в которых итоговая оценка, вообще говоря, не может быть построена по совокупности оценок, определяемых предпочтениями отдельно взятых участников Такие процедуры называем совокупными Многие известные процедуры этого типа сводятся к манипуляциям с матрицей А = (аг]) суммарных результатов сравнений на

парах объектов /

О, если а?г] не определено ни при одном р € {1, , т}, в противном случае

. р

Далее в главе 6 изучается ряд таких процедур, в частности, — процедуры Уэя—Кендалла, Хассе, Рамануяхариулу, Каца—Томпсона—Тейлора, Дэниэлса—Ушакова—Годдарда—Левченкова Попутно рассматриваются алгебраические индексы графов, связанные с этими процедурами

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

1 А

ш, = — г = 1, ,П, (6 19)

где с~ = г = 1. > п

В наших обозначениях эта процедура сводится к нахождению неотрицательных и не полностью нулевых решений системы уравнений

Гги = 0, (6 21)

где Ь — матрица Кирхгофа (определение см на с И) мультиорграфа Г результатов парных сравнений, или, эквивалентно,

= ^(-t^Wj, г = 1, ,тг (6 22)

зфг

Очки имеют интересные и разнообразные интерпретации

Интерпретации очков в процедуре направленных деревьев.

(1) Очки тг пропорциональны суммарным весам деревьев, исходящих из соответствующих вершин в Г (Берман, 1980),

(2) Очки wt пропорциональны, стационарным вероятностям "выигрывающей марковской цепи" (Ушаков, 1971 и др),

(3) w есть вектор "честных ставок в модели Муна и Палмена (1970)

Далее в главе 6 рекурсивно вводится понятие индекса побед-праже-ний - пары векторов [w,l) = ((y;i, ,и„)т, (l\, ,ln)r), в которой первый вектор в определенном смысле агрегирует "победы" объектов в сравнениях, а второй — "поражения" Из-за ограниченности объема реферата соответствующую серию определений опускаем Затем вводится определение 6 4, устанавливается, что рассмотренные выше процедуры ему соответствуют и доказывается основной результат (теорема 6 1)

Определение 6.4 Оценивающая процедура S есть процедура, комбинирующая победы и поражения, если для любого профиля .4 существует индекс побед—поражений (w, Z) и функция h, т^кие что

st = h(w„k), г = 1, ,п

Теорема 6 1. Любая оценивающая процедура, комбинирующая победы и поражения и имеющая область определения, выючающую все неразлооюи-мые профили предпочтений, нарушает уановие С СМ

Далее рассмотрена процедура наименьших квадратов, также нарушающая ССМ, и получено достаточное условия выполнения ССМ

Теорема 6 2. Пусть для процедуры оценивания S существует функция f(s, V), где s Е 1R, V — конечное мультимнооюеетво пар действительных чисел, со следующими свойствами

(A) Для любого профиля А пусть V, = ((а^, в^) | ],р), г = 1, ,п Тогда /(в„К)= 0, г = 1, ,п

(B) Функция /(з, V) строго возрастает по каждому элементу каждой пары из V и строго убывает по э

если (1, вк) 6 V,, то /(в„ в*)) < /(зг, V,), если (О, вк) € Ц, то /(ви О, в*)) > /(з,, V,) Тогда £ удовлетворяет самосогласованной монотонности

В Таблице 6 1 указаны четыре известные процедуры, удовлетворяющие достаточному условию теоремы 6 2, а значит, и ССМ

Процедура Обл опред * /()в теореме 6 2

Цермело (1928), Брэдли и Терри (1952) ГО

Дэниэлс (1969), Гиновкер (1981) ГО £ (ач|* -

Коуден (1975) ГО П Е ач -з]

п £(а,;в, +а,,(1 - а,)) 3 = 1

Обобщ процедура суммы очков |18,47] и - - - 3,Р

* ГО означает неразложимые профили предпочтений, I) — все профили

Таблица 6 1 Некоторые процедуры, удовлетворяющие ССМ

Одна из них — предложенная автором обобщенная процедура суммы очков, которой посвящена глава 7 Глава 6 завершается формулировками аксиом независимость от макровершины и сохранение баланса при разбиении, которые могут быть использованы в дальнейшем при аксиоматическом синтезе процедур агрегирования предпочтений

В седьмой главе аксиоматически построен и изучен метод агрегирования неполных предпочтений, названный обобщенным методом суммы, очков Он связан с использованием матрицы остовных корневых лесов графа сравнений В случае линейных и слабых порядков "на входе" он совпадает с методами Борда и Коупленда соответственно, а в случае турниров

— с методом суммы очков При несбалансированных данных он сводится к решению системы линейных уравнений Установлено, что оценки метода совпадают с гребневыми оценками параметров модели парных сравнений Шеффе

Рассмотрим множество объектов X — {-Хь , Хп} и массив V, = , представляющий результаты парных сравнений эле-

ментов X по предпочтению, где Тб1^ (р = 1, , та) — матрица парных сравнений порядка п, в которой г^ и при г ф ] выражают результат сравнения объектов Хг и Х3 в р-й серии экспериментов Элементы грп не соответствуют сравнениям, и их значения определяются некоторым техническим соглашением Матрицы вообще говоря, заполнены частично если X, и Х3 не сравнивались в р-ой серии экспериментов, то г^ и не определены Если матрица полностью определена, называем ее полной Массив И полон, если полны все матрицы Гб2\ , Гбт> Числа п и т — параметры И

Каждому объекту Хг сопоставляется "сумма очков" в 71

г=1> >п' (71)

где обозначает суммирование по тем ] и р, для которых г^ определено в И, если все г^ не определены, то в, не определено Метод суммы очков упорядочивает объекты по убыванию величин я, В случае неколичественных парных сравнений элементы Я1'^ могут быть определены так Гу = 1, если в р-ой серии экспериментов Хг превосходит Х3, г^ = —1, если X] превосходит Хг и г^ = О, если Хг и Х7 равноценны или г = ]

Рассмотрим множество всех действительных кососимметрических матриц, вообще говоря, неполных, с нулевой главной диагональю, т е неполных матриц, таких что (а) если г^ определено, то = —г^ и (Ь) грп = 0,1,3 = 1, ,п, р= 1, ,т

Рассмотрим следующее обобщение сумм очков (7 1)

1 = >п> (74)

0.р)1»

где

/£ = /(:с„х„т*) (7 5)

— "вклад" в оценку xt объекта Х1 от сравнения его с ЛГ^ в р-ой серии экспериментов Функцию / R3 Б, называем функцией платежа Для конкретной функции / соотношения (7 4) при условии (7 5) образуют систему п уравнений с п неизвестными х\, ,хп

я, = f{x„xrr?j), « = 1, .п (76)

(j.P)I>

Наложим на функцию платежа два ограничения

Условие согласованности. Для любого полного массива TZ вектор сумм очков (7 1) — допустимый (хотя, возможно, не единственный допустимый•) вектор оценок

Условие ставки Если определено, то = —

Используя кососимметричность, запишем условие ставки в виде

V (я, г/, г) е И3 Дх, у, г) = -/(у, г, -г) (7 9)

Характеризация всех функций, удовлетворяющих условиям согласованности и ставки, дана в [47] Однако "почти все" эти функции всюду разрывны Добавим следующее естественное требование к функции платежа

Условие непрерывности в одной точке. Функция f непрерывна хотя бы в одной точке (х, у, г) 6 1R3

Главный результат главы 7 — следующая теорема

Теорема 7.1 Функция f(x,y,r) при данных п > 3 и т £ IN удовлетворяет условиям ставки, согласованности и непрерывности в одной точке тогда и только тогда, когда при некотором е € 1R

V (х, у, г) е Н3 f{x,y,r) = г + е (у-х + тпг) (7 10)

Слабое условие неубывания. При некоторых х, у\, уч > у\ и г имеет место /(х, уг, г) > f(x, ух, г)

Это естественное условие, добавление которого влечет е > 0 Теперь функции (7 10) можно подставить в систему уравнений (7 6)

хг = Щ + е С1; - + г = 1, , га (7 12)

При любом выбранном е ^ 0 оценки хг, , хп, удовлетворяющие (7 12), будем называть обобщенными суммами очков

Предложение 7.1 Система уравнений (7 12) эквивалентна системе

I, = в, + е' °{х1-х}), г = 1, ,п, (7 13) Ь,р) 1«

где сумма с "©" берется по таким ] и р, что г" не определено в и

е' = е/(1 + етп) (7 14)

Из (7 14) и неотрицательности е следует 0 ^ е' < 1/(тп) В матричной форме вектор решений (7 12) представим в виде

х = (/ + + етгф,

где Ь — лапласовская матрица неориентированного графа количеств сравнений Поэтому (I + еЬ)~1 = (¿(е) — матрица взвешенных остовных корневых лесов данного графа, и каждая обобщенная сумма очков есть линейная комбинация сумм очков с коэффициентами, равными суммарным весам лесов, "соединяющих" соответствующие пары вершин

Далее в главе 7 изучены свойства обобщенных сумм очков доказаны свойства существование и единственность, центрированность, совпадение с суммами очков при полноте массива, совпадение с суммой очков при локальной полноте массива, нулевая презумпция, аддитивность при одинаковом заполнении, транспонируемость, независимость от сравнений внутри макровершины, независимость несвязанных частей, доминирование, монотонность, ограниченность, динамическая монотонность (два последних — для парных сравнений с ограниченными результатами)

Рассмотрены также вероятностные модели парных сравнений, для которых обобщенные суммы очков являются оптимальными (в определенном смысле) оценками параметров Речь идет о гребневых оценках для модели Шеффе Е(г^) = ßt — где Д — неизвестный параметр, характеризующий г-ый объект, и о наилучших линейных предикторах для байесовского варианта модели Шеффе

Для случая парных сравнений с ограниченным результатом введены понятия корректности выбора параметров е и е1. Установлено, что эти понятия корректности эквивалентны и равносильны выполнению неравенств О « е < (т(п - 2))-1 и 0 $ еЧ (2т(п - I))"1

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

В заключение главы 7 предложены методы выбора параметра модели г и рассмотрены примеры

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

пьютерные сети, химическая информатика, наукометрия, семантические и социальные сети) также обсуждаются в данной главе Предложено неравенство треугольника для функций близости — аналог неравенства треугольника для метрик Введено понятие функций Е-близости, установлено, что в определенном смысле они двойственны метрикам

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

Подробнее остановимся на результатах о функциях сигма-близости

Определение 8.2. Пусть А — непустое конечное множество, Е — действительное число Функцию а А2 —* II назовем Е-близостью на А, если для любых х,у,г е А выполняются

1) условие нормировки Х^геЛ = Т,,

2) неравенство треугольника для близостей а(х, у) + а(х, г) — а(у, г) $ а(х, х), причем если г = у и х ф у, то неравенство строгое

Предложение 8 1. Пусть а есть И-близостъ на А Тогда Ух, у 6 А о(х,у) = а(у,х) (симметричность), если х фу, то о(х,х) > о(х, у) ("эгоцентризм")

Исследуем соотношение между Е-близостями и метриками Пусть <1 — метрика на А и |А| = п Введем обозначения

(8 12)

в, «ел

Предложение 8.2. Для любой метрики в, на А функция

(8 13)

(8 14)

является Е-близостью на А

Предложение 8.3. Для любой Т,-близости а на А функция

d(x, у) = 0,5(а(х, х) + о(у, у)) - а{х, у) (8 16)

является метрикой па А

Отображения, задаваемые (8 14) и (8 16) обозначим ip(d) и ф(а) Теорема 8.6. (риф задают взаимно-однозначные соответствия множеств метрик на А и 0,-близостей на А, ф = <р~1

Обобщим эти результаты на случай бесконечных множеств Пусть А — непустое множество, Ai и — множества всех функций А —> И и Л2 —► R соответственно

Определение 8 3. Вещественный функционал ц, заданный на множестве Вх Ç Ai, назовем линейным усредняющим функционалом, если fi и В1 обладают следующими свойствами

1) Вх — линейное пространство над R, содержащее все константы,

2) ц — линейный функционал, константам сопоставляющий их значения,

3) если /, g S Вх и Vx € А /(х) ^ д(х), то /и(/) > ц(д) (монотонность)

Пусть /i — линейный усредняющий функционал на Вх Пусть / £ А2, и при любом х0 6 А /(х0, у) принадлежит Вг как функция у Через f(x, ) = fiy(f(x, у)) обозначим функцию от х, каждому х ставящую в соответствие результат применения ft к f(x, у) как к функции у

Определение 8.4. В2 Ç А2 назовем семейством двухместных усредняемых функций, если В2 — линейное пространство над И, содержащее все константы и все элементы В1 как функции каждого из аргументов, постоянные по второму аргументу, и для любой функции / £ В2

1)VxGA gx(y) 6 Вь где gx(y) = f(x, у),

2) f{x, •) е В1 и д(х) € Bv где д{х) = f{x,x)

Пусть для А заданы Въ ¡л и В2, определенные выше, m 6 R

Определение 8.5. Функцию а £ В2 назовем £т-близ остью на А, если для любых х, у, z £ А выполняются

1) условие нормировки а(х, ) = т,

2) неравенство треугольника для близостей а(х, у) + а(х, z) — а(у, z) ^ а(х, х), причем если z = у п х ф у, то неравенство строгое

Тогда, как показано в диссертации, выполняются прямые аналоги предложений 8 1-8 3 и теоремы 8 6 Пример использования этих результатов - следствие 8 1

Следствие 8.1. Для любых множества А, метрики d S В2 и х G А d(x, ) > d( , )/2

Пример И-близости — относительная достижимость по лесам

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

Относительная достижимость по лесам — это мера близости вершин графа, задаваемая матрицей Q = (I + где L — лапласовская матрица графа В случае орграфов рассматриваются две меры близости, задаваемые матрицами Q — (I + L)~l (достижимость по входящим лесам) и Q = (I+L)~l (достижимость по исходящим лесам), где L — лапласовская матрица, L — матрица Кирхгофа В главе 9 рассматриваются свойства и применения этих показателей и связанных с ним структурных индексов При этом используются те же характеристические условия, что и в главе 8, и ряд специфических условий (в частности, стохастичность и независимость от макровершины) Доказана

Теорема 9 2 (об одношаговом изменении относительной достижимости по лесам) Пусть в мультиграфе G вес некоторого ребра epkt увеличился на Aekt > 0 или к G добавлено новое ребро между k ut с весом Askt > О Пусть G' — полученный мультиграф и W = W(G'), Q' = Q(G') Тогда

1) = ЛД, где АQ = Q'-Q, к = (<1Ы+ 1/&еыГ\ с1ы = дкк +да -2Чы, К = (ГУ)пхп - матрица с элементами гг] =

2) все строки и все столбцы матрицы Д<3 пропорциональны,

3) если > то > О тогда и только тогда, когда > д]к, и Д^у < О тогда и только тогда, когда ц]к >

4) знаки всех приращений не зависят от модуля ДеИ > О, а модули ненулевых Адг] строго возрастают по

5) VI,з € У(С) Мг) = -¿а +<*„ +1/Деы)-1 и ^ < ^

Аналог этой теоремы доказан и для орграфов Получено разложение относительной достижимости по лесам по маршрутам со стоками

В силу матричной теоремы о лесах матрица относительной достижимости по лесам представима в виде С} — ^((¿о + <31+ + Фп-и), где О к - матрица лесов с к ребрами (дугами), V — размерность графа по лесам Наряду с матрицей в главе 9 изучены меры близости, определяемые матрицами (Цп-ь-г и £?п-г) — Для графов и орграфов Рассмотрены также параметрические меры близости, определяемые матрицами <2(т) = (/ + тL)~1 (г — параметр)

Для неориентированных графов псевдообратная (по Муру-Пенро-узу) матрица Ь+ = (<?*) проинтерпретирована в графовых терминах

Теорема 9 7 (графовая интерпретация матрицы, псевдообратной к Ь)

где К — множество вершин компоненты графа (7, содержащей г

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

при з е К,

(9 18)

п—у)

иначе.

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

Рассмотрим следующий однопараметрический класс показателей взвешенной достижимости по лесам при выбранном а > 0 матрица <2(а) = (<7у) сравнительной близости вершин задается формулой

<Э(а) = (/ + аЬ)'1 (10 1)

Матрицы (¿(а) — дважды стохастические и симметричные Параметр а определяет пропорцию учета длинных и коротких связей вершин Нами введены следующие метрики

Определение 10.1. При выбранном параметре а > 0 величину

= + «..7 = 1. (Ю4)

назовем лесным расстоянием между вершинами г и ], а величину

= а(<£+ <£-<£-<£)= 2а = ,п (105)

назовем приведенным лесным расстоянием между вершинами г и ]

Зафиксировав а, будем использовать обозначения ¿г; и рг] В силу предложения 8 3 с?ц и действительно, являются расстояниями Из двойной стохастичности <2(а) следует (1г] 1, ру < 2а (г, J = 1, ,гг), причем равенство достигается только когда г и ] — две изолированные вершины

Р Меррис (1997) дал иную оценку для с1г] <1%} ^ (1 4- аа(С?))-1, где а(б) — введенная М Фидлером алгебраическая связность графа — второе

минимальное собственное значение Ь Заметим, что (1 +аа(С))-1 — второе максимальное собственное значение <3(а)

В силу теоремы 9 2, если суммарный вес ребер С? с концами к и Ь получил приращение Аеы > 0, то при отсутствии других изменений в С?

^^ ЙГ <106>

Для мультиграфа С, отличающегося лишь ребром от через Аек1 — £ обозначаем приращение веса ребра (к, £), переводящее С? в С, все обозначения со штрихами относятся к С, без штрихов — к С

Лемма 10.1. Пусть взвешенный мулътиграф С отличается от С лишь ребром (М) Тогда (р'ы)~1 - = Аеы

Так, при добавлении ребра (М) к невзвешенному графу 1/р'ы = 1/ры 4-1

Определение 10 3. Пусть г, ] € У(С) и г ф ] Совокупным весом связей между г и у в б назовем величину в1} = (ру)-1 — (2а)-1

В силу леммы 10 1 = вк1 при добавлении дуги (Л;, ¿) с весом е Следующее утверждение проясняет смысл совокупного веса связей

Теорема 10.1. Пусть гф ], ех} — суммарный вес ребер (г,]) в й

1) в — + е г(9е — совокупный вес связей между г и ] в графе, получающемся из С удалением всех ребер (г,о),

2) ^ ? ¿у .

3) вч = ег] тогда и только тогда, когда г и у не связаны ребрами ни с какими другими вершинами — лишь, возможно, друг с другом

Отсюда

¿ц<(1 + 2аеу)-\ (10 14)

<((2а)-1 + ^Г\ М = ,п (10 15)

Условия равенства здесь те же, что теореме 10 1 В диссертации получены соотношения, связывающие лесные расстояния для пары графов, отличающихся одним ребром

Фрагментацией графа, отделяющей ] от г называем остовный корневой лес, в котором г — корень дерева, и ] не принадлежит этому дереву Рассмотрена модель случайного выбора леса в графе и доказана

Теорема 10 2 Лесное расстояние (1г] равно вероятности выбора фрагментации, разделяющей г и ], в модели случайного выбора леса

Изучены асимптотические свойства лесной метрики графа, а именно, найдены пределы д™ = кт^^ и р^ = Ьт^оо Кроме того, получены соотношения между лесной метрикой и резисторной метрикой графа введено понятие »-расширения графа и показано, что, с одной стороны, рг]{Са) = где р1} — резисторная метрика, Са — а-расширение <3, а

с другой стороны р^ = рх]

В заключении диссертации подведены итоги проведенных исследований и кратко изложены основные выводы

Основные результаты диссертационной работы

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

Основные научные результаты, полученные в диссертационной работе, состоят в следующем

1 Получена матричная теорема о лесах

2 Разработан подход к нахождению собственного проектора и компонент квадратной матрицы А с помощью произвольного ненулевого аннулирующего многочлена для Аи, где и > шсЗ А

3 Изучены структура и свойства множеств остовных корневых лесов графов и орграфов и связанных с ними матриц Установлено, что матрица максимальных входящих лесов орграфа является собственным проектором лапласовской матрицы Из последнего факта выведена матричная теорема о деревьях для цепей Маркова Эти результаты составляют основу анализа моделей распределенного согласования характеристик в многоагентных системах

4 Впервые исследованы свойства лапласовского спектра орграфов Потребность в таком исследовании неоднократно высказывалась специалистами по децентрализованному управлению в связи с анализом моделей функционирования многоагентных систем

5 Введена аксиома самосогласованной монотонности для процедур агрегирования предпочтений Ряд известных алгебраических методов агрегирования предпочтений и их классов протестирован на выполнение этой аксиомы Классы методов при этом определялись в терминах свойств индуцируемых ими алгебраических индексов на орграфах предпочтений

6 Аксиоматически построен и исследован новый метод агрегирования неполных предпочтений — обобщенный метод суммы очков, обобщающий процедуры Борда, Коупленда и турнирную процедуру агрегирования Показано, что метод эквивалентен нахождению гребневых оценок параметров статистической модели парных сравнений Шеффе и что назначаемые методом итоговые баллы можно трактовать как прогнозные значения сумм очков после пополнения массива предпочтений

7 Предложена система нормативных требований к показателям близости вершин графов Изучены свойства ряда известных показателей близости Область применения этих результатов — построение алгебраических индексов графов и анализ сетей различной природы

8 Аксиоматически введен класс функций Е-близости Доказана теорема о двойственности понятий Е-близость и расстояние Область приложения этих результатов — анализ данных

9 На основе матричной теоремы о лесах введен новый показатель близости вершин графов — относительная достижимость по лесам Изучены его свойства и на его основе построено семейство структурных индексов графов Область применения — анализ социальных, семантических и других сетей

10 Введен класс лесных метрик графов Исследованы свойства этих метрик, дана вероятностная интерпретация лесного расстояния, установлены соотношения между лесными метриками и резисторной метрикой графа Области применения — анализ сетей, химическая информатика

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

Публикации по теме работы

1 А гаев Р П, Чеботарев П Ю Матрица максимальных исходящих лесов орграфа и ее применения // Автоматика и Телемеханика — 2000 — № 9 — С 15-43

2 Агаев Р Я, Чеботарев П Ю Остовные леса орграфа и их применение II Автоматика и Телемеханика — 2001 — № 3 — С 108-133

3 Агаев Р П, Чеботарев П Ю О нахождении собственного проектора и компонент матрицы с помощью аннулирующего многочлена II Автоматика и Телемеханика — 2002 - № 10 - С 3-12

4 Агаев Р П, Чеботарев П Ю Лапласовские спектры орграфов и их приложения И Автоматика и Телемеханика — 2005 — № 5 — С 47-62

5 Пригарина Т А , Чеботарев П Ю Методы экспертных оценок на примере определения предпочтительности объектов Препринт — Москва ЦЭМИ АН СССР, 1989

6 Пригарина Т А , Чеботарев П Ю Методы экспертных оценок и определение предпочтительности объектов // Экспертные оценки в социологических исследованиях Гл VIII / Под ред В И Паниотто - Киев Наукова думка, 1990 - С 190-225

7 Пригарина Т А , Чеботарев П Ю , Шмерлинг Д С Анализ нечисловой информации // Математические методы в социально-экономических исследованиях /Под ред С М Ермакова, В Б Меласа — СПб Петрополис, 1996 - С 123-138

8 Пригарина Т А , Чеботарев П Ю , Шмерлинг Д С Парные сравнения объектов (аналитический обзор) // Научно-техническая информация Серия 2 Информационные процессы и системы — 1996 — № 2 — С 20-25, 32

9 Чеботарев П Ю Аксиоматическое задание одного метода оценивания объектов по результатам экспертного опроса //Труды науч - техн конф молодых ученых и спец Моек ин-га нефти и газа - 1987 - С 27-32 - Деп в ВИНИТИ 24 07 87, № 5369-В87

10 Чеботарев П Ю Байесовское оценивание качества объектов по результатам парных сравнений // Материалы X конф Молодых ученых Ун-та дружбы народов -42 — 1987 - С 35-38 - Деп в ВИНИТИ 29 12 87, № 9152-В87

11 Чеботарев П Ю Обобщение метода строчных сумм для неполных парных сравнений IIIII Всес школа-семинар "Программно-алгоритмическое обеспечение прикладного многомерного статистического анализа" Тезисы докладов - Ч 2 — М ЦЭМИ,

1987 - С 249-250

12 Чеботарев П Ю Два метода упорядочения объектов по произвольному множеству парных сравнений - 1988 - Деп в ВИНИТИ 22 07 88, № 5879-В88

13 Чеботарев П Ю Использование метода обобщенных строчных сумм для обработки числовых экспертных оценок с пропусками // Научно-практическая школа-семинар "Программное обеспечение ЭВМ индустриальная технология, интеллектуализация разработки и применения" Тезисы докладов — Т 2 — Ростов-на-Дону ВНИИПС,

1988 - С 153-155

14 Чеботарев П Ю Неполные парные сравнения и метод строчных сумм — 1988 — Деп в ВИНИТИ 26 02 88 , № 1576-В88

15 Чеботарев П Ю Агрегирование неполных предпочтений // III Всесоюзная конференция "Методы социологических исследований" — Т 5 — Москва ИС АН СССР,

1989 - С 59-62

16 Чеботарев П Ю Метод оценивания объектов по неполному набору парных сравнений И Комплексный подход к анализу данных в социологии — Москва ИС АН СССР, 1989 - С 79-93

17 Чеботарев П Ю Метод строчных сумм и приводящие к нему модели II Сб тр ВНИИ системных исследований — 1989 — № 3 — С 94-110

18 Чеботарев П Ю Обобщение метода строчных сумм для неполных парных сравнений // Автоматика и телемеханика — 1989 — № 8 — С 125-137

19 Чеботарев П Ю Ранжирование объектов в аддитивной модели парных сравнений со случайными факторами // IV Всес конф "Применение многомерного стат анализа в экономике и оценке качества продукции" Тезисы докладов -41 — Тарту Тартуский университет, 1989 — С 33-34

20 Чеботарев П Ю Агрегирование предпочтений регрессионная модель // Методы математической статистики в кибернетике и информатике — Томск ТГУ, 1990 — Т 2 - С 541-550

21 Чеботарев П Ю Алгоритмы выбора параметра е в методе обобщенных строчных сумм // III Всесоюзная школа-семинар "Комбинаторно-статистические методы ана-чиза и обработки информации, экспертное оценивание" Тезисы докладов — Одесса 1990 - С 104

22 Чеботарев П Ю О некоторых оптимизационных методах агрегирования предпочтений // Сб тр ВНИИ системных исследований — 1990 — № 8 — С 67-72

23 Чеботарев П Ю О некоторых оптимизационных методах агрегирования предпочтений // Всес научно-практический семинар "Интеллектуальное программное обеспечение ЭВМ" Тезисы докладов -41— Ростов-на-Дону-Терскол 1990 — С 95-97

24 Чеботарев П Ю Об одном прогнозном подходе к агрегированию экспертных оценок // Всесоюзное совещание "Пути повышения качества прогнозов" Тезисы докладов — Москва-Ленинград Союз научных и инженерных обществ СССР, 1990 — С 60-62

25 Чеботарев П Ю Уточненный пример обобщенной немонотонности метода Кемени-Слейтера // IV Всес школа-семинар "Статистический и дискретный анализ данных и экспертное оценивание" Тезисы докладов — Одесса 1991 — С 136-138

26 Чеботарев П Ю Новые меры связности графов и их применение в анализе социального поведения // Информационный бюллетень РФФИ — 1996 — Т 4, № 1 — С 430

27 Чеботарев П Ю Анализ социальных сетей основные подходы // Тезисы докладов

I Всероссийского Социологического Конгресса "Общество и социология новые реалии и новые идеи" /Под ред Ю В Асочакова, И Д Демидовой — Санкт-Петербург СПбГУ, 2000 - С 510-511

28 Чеботарев П Ю , Митъкин А Н, Шмерлинг Д С Об оценивании вклада ведомственных целевых программ в достижение целей правительства // Проблемы управления - 2007 - № 4 - С 43-50

29 Чеботарев П Ю , Шамис Е В Матричная теорема о лесах и измерение связей в малых социальных группах // Автоматика и Телемеханика — 1997 — № 9 — С 124-136

30 Чеботарев П Ю , Шамис ЕВ О двойственности метрик и ^-близостей // Автоматика и Телемеханика — 1998 — № 4 — С 204-209

31 Чеботарев IT Ю , Шамис Е В О мерах близости вершин графов // Автоматика и Телемеханика - 1998 — № 10 — С 113-133

32 Чеботарев П Ю , Шамис Е В Некоторые свойства лесной метрики графа // Автоматика и Телемеханика. — 2000 — № 8 — С 137-146

33 Agaev R , Chebotarev Р On the spectra of nonsymmetnc Laplacian matrices I I Linear Algebra and its Applications — 2005 — Vol 399 — Pp 157-168

34 Chebotarev P Constructing extensions of utility functions // International Conference "Logic, Game Theory and Social Choice" — Saint-Petersburg Saint-Petersburg State University, 2001 — Pp 49-55

35 Chebotarev P Outforests of a digraph, the Kirchhoff matrix, and Markov chain probabilities // Second Euroworkshop on Algebraic Graph Theory — Edinburgh University of Edinburgh, 2001 - P 5

36 Chebotarev P Extending utility representations of partial orders without continuity requirements // Abstracts of the Int conference "Utility Theory and Applications" — Trieste University of Theste, Faculty of Economics, 2002 — Pp 12-13

37 Chebotarev P On the extension of utility functions // Constructing and Applying Objective Functions/Ed by A S Tangian, J Gruber — Berlin Springer-Verlag, 2002 — Vol 510 of Lecture Notes in Economics and Mathematical System — Pp 63-74

38 Chebotarev P Spanning forests of digraphs and limiting probabilities of Markov chains

II Electronic Notes m Discrete Mathematics - 2002 - Vol 11 - Pp 108-116

39 Chebotarev P On of the spectrum of the digraph Laplacian // International Conference on Matrix Analysis and Applications — Fort Lauderdale Nova Southeastern University, 2003 — Pp 4-5 http //www resnet wm edu/~cklixx/novabs pdf

40 Chebotarev P Laplacian matrices and essentially cyclic weighted digraphs // Abstracts of the 13th Conference of the International Linear Algebra Society — Amsterdam Free University of Amsterdam, 2006 — Pp 60-61

41 Chebotarev P A graph theoretic interpretation of the mean first passage times arXiv paper math PR/0701359 arXiv, 2007 http //arxiv org/abs/math/0701359

42 Chebotarev P The Laplacian matrix, spanning forests, and the golden ratio I I Abstracts of the 14th Conference of the International Linear Algebra Society — Shanghai Shanghai University, 2007 - P 12

43 Chebotarev P Spanning forests and the golden ratio I I Discrete Applied Mathematics — 2008 - Vol 156, no 5 - Pp 813-821

44 Chebotarev P , Agaev R Forest matrices around the Laplacian matrix // Linear Algebra and its Applications — 2002 — Vol 356 - Pp 253-274

45 Chebotarev P, Agaev R Matrices of forests and the analysis of digraphs arXiv paper math co/0508171 arXiv, August 2005 http //arnv org/abs/math/0508171

46 Chebotarev P, Shamis E The forest metrics for graph vertices // Electronic Notes in Discrete Mathematics — 2002 - Vol 11 - Pp 98-107

47 Chebotarev P Y Aggregation of preferences by the generalized row sum method I I Mathematical Social Sciences - 1994 - Vol 27 - Pp 293-320

48 Chebotarev P Y On ridge regression techniques as applied to the Scheffe-Noether paired comparison model I I9 European Meeting of the Psychometric Society — Leiden Leiden University, 1995 - P 20

49 Chebotarev P Y Out forests of a digraph and Markov chain probabilities //International Linear Algebra Conference — Haifa Institute of Advanced Studies in Mathematics, Techmon, 2001 - Pp 20-21

50 Chebotarev P Y, Agaev R P The matrix of maximum out forests and structural properties of systems modeled by digraphs // Modelling and Simulation of Systems, MOSIS-2000, 34th Spring Int Conf - Vol 1 - Ostrava Umv of Ostrava, 2000 — Pp 101-106

51 Chebotarev P Y, Shamis E Incomplete preferences and indirect scores Working Paper 365 97 — Barcelona Universitat Autonoma de Barcelona and Institut d'Analisi Economica, CSIC, 1997

52 Chebotarev P Y, Shamis E Characterizations of scoring methods for preference aggregation // Annals of Operations Research — 1998 — Vol 80 — Pp 299-332

53 Chebotarev P Y, Shamis E V Matrix-forest theorems arXiv paper math со/0602575 arXiv, 1995 http //arxiv org/abs/math co/0602575

54 Chebotarev P Y, Shamis В К On optimization models for aggregating incomplete preferences // International Conference on Ordinal and Symbolic Data Analysis — Pans INRIA Rocquencourt, 1995 - Pp 148-151

55 Chebotarev P Y, Shamis E V On optimization models for aggregating incomplete preferences // Ordinal and Symbolic Data Analysis I Ed by E Diday, Y Lechevallier, О Opitz — Berlin Springer-Verlag, 1996 — Studies in Classification, Data Analysis and Knowledge Organization - Pp 328-338

56 Chebotarev P Y, Shamis E V Preference fusion when the number of alternatives exceeds two Indirect scoring procedures // Proceedings of Workshop on Information / Decision Fusion /Ed by N S V Rao, V Protopopescu, J Bernen, G Seetharaman — Lafayette, LA Acadiana, 1996 - Pp 20-32

57 Chebotarev P Y, Shamis E V Constructing an objective function for aggregating incomplete preferences I I Econometric Decision Models, Lecture Notes in Economics and Mathematical Systems, Vol 453 / Ed by A Tangian, J Gruber — Berlin Springer, 1997 - Pp 100-124

58 Chebotarev P Y, Shamis E V Graph proximity functions and linear aggregation of incomplete preferences // Труды международной конференции по проблемам управления - Т 2 - Москва Синтег, 1999 - С 271-278

59 Chebotarev Р Y, Shamis Е V Preference fusion when the number of alternatives exceeds two Indirect scoring procedures // Journal of the Franklin Institute — 1999 — Vol 336 - Pp 205-226 - Erratum, J Franklin Inst , 1999, vol 336, pp 747-748

Вклад автора в работы, опубликованные в соавторстве В работах ¡5,6,7,8] автором получены результаты и написаны разделы, относящиеся к агрегированию предпочтений В [29,31,32,46] автору принадлежат постановки задач, формулировки и доказательства свойств мер достижимости вершин графов, свойств лесных метрик графов, выражений и графовых интерпретаций обобщенно обратных матриц, в [51,56,59] — аксиома самосогласованной монотонности и теоремы о необходимых и достаточных условиях ее выполнения, в ¡54,55,57) — систематизация оптимизационных процедур агрегирования предпочтений и доказательство их свойств, в [58] — аксиоматизация линейных процедур агрегирования, в [52] — систематизация позиционных методов агрегирования предпочтений и доказательство теоремы об эквивалентности условия самосогласованности и существования монотонной неявной формы процедуры агрегирования,

в (30) — определение мер сигма-близости, формулировка и доказательство результатов о соответствии метрик и функций сигма-близости для произвольных множеств, в [53| - доказательство матричной теоремы о лесах В (1,2,3,4,33,44,45,50] автору принадлежат постановки задач, а также результаты, относящиеся к теории графов, теории цепей Маркова, мерам близости вершив графов, матричной теореме о лесах, характеристическим многочленам нормированных лапласовских матриц, асимптотическим свойствам их спектров и агрегированию предпочтений В (28] автором разработана методика оценивания целевых программ

Зак. 71 Тир 120 ИПУ РАН

Оглавление автор диссертации — доктора физико-математических наук Чеботарев, Павел Юрьевич

Введение

Глава 1. Матричная теорема о лесах

1.1. Необходимые определения и простые факты.

1.1.1. Общие понятия теории графов.

1.1.2. Структура орграфа.

1.1.3. Деревья и леса.

1.1.4. Лапласовская матрица и матрица Кирхгофа.

1.2. Матричная теорема о деревьях и связанные с ней исследования

1.2.1. Некоторые направления в исследовании лапласовских матриц графов

1.2.2. Матричные теоремы о деревьях для неориентированных и ориентированных графов.

1.3. Матричная теорема о лесах.

1.4. Доказательства матричной теоремы о лесах.

1.4.1. Первое доказательство.

1.4.2. Второе доказательство.

Глава 2. О нахождении собственного проектора и компонент матрицы

2.1. Введение

2.1.1. О приложениях обобщенно обратной матрицы по Дразину, собственного проектора и компонент матрицы.

2.1.2. Определения.

2.1.3. Вспомогательные утверждения.

2.1.4. О задачах, решаемых в данной главе

2.2. Характеризации собственного проектора.

2.3. Вычисление собственного проектора А с помощью аннулирующего многочлена для Аи.

2.4. Нахождение компонент матрицы и ее минимального многочлена.

2.5. Собственный проектор и компоненты матрицы, собственные значения которой известны

Глава 3. Исследование матрицы максимальных исходящих лесов орграфа

3.1. Введение

3.2. Простейшие свойства остовных исходящих лесов.

3.3. Максимальные исходящие леса, базы и недоминируемые узлы

3.4. Конструктивное описание максимальных исходящих лесов.

3.5. Матричные теоремы о лесах в параметрической форме.

3.6. Матрица максимальных исходящих лесов

3.7. Цепи Маркова, связанные с орграфом, и матричная теорема о деревьях для цепей Маркова.

3.8. Матрицы лесов и задача структурирования орграфа.

Глава 4. Остовные леса орграфа и связанные с ними матрицы

4.1. Введение

4.2. Некоторые свойства исходящих и входящих лесов.

4.3. Матрицы исходящих лесов и переходные вероятности цепей Маркова

4.4. Выражение матриц лесов через матрицу Кирхгофа и его следствия

4.5. О некоторых линейных операторах, связанных с орграфом.

4.6. Псевдообратная и групповая обратная матрицы для матрицы Кирхгофа

4.7. Об области Гершгорина и аннулирующем многочлене матрицы Кирхгофа

Глава 5. Исследование лапласовского спектра орграфов

5.1. Введение

5.2. Некоторые свойства лапласовского спектра неориентированного графа

5.3. О связях лапласовских и стохастических матриц.

5.4. Связь спектров лапласовских и стохастических матриц

5.5. Область, содержащая лапласовские спектры.

5.6. Многоугольник лапласовских собственных значений.

5.7. Об асимптотических свойствах лапласовских спектров.

5.8. Согласование характеристик в многоагентных системах и спектры лапласовских матриц орграфов.

5.8.1. Децентрализованное управление многоагентными системами.

5.8.2. Непрерывная модель распределенного согласования характеристик

5.8.3. Сходимость процесса согласования.

5.8.4. Ранг лапласовской матрицы и критерий сходимости процесса согласования

5.8.5. Итерационная модель распределенного согласования характеристик

5.8.6. Другие задачи децентрализованного управления.

Глава 6. Структурные индексы графов и агрегирование результатов парных сравнений

6.1. Об агрегировании неполных предпочтений.

6.2. Понятия и обозначения, связанные с агрегированием предпочтений

6.3. Пример.

6.4. Самосогласованная монотонность.

6.5. Процедуры, основанные на индивидуальных оценках.

6.6. Совокупные процедуры оценивания.

6.6.1. Процедура Уэя.

6.6.2. Процедуры Хассе и Рамануяхариулу.

6.6.3. Процедура Каца-Томпсона-Тейлора.

6.6.4. Процедура направленных деревьев.

6.6.5. Подробнее о процедуре направленных деревьев

6.7. Класс процедур, не удовлетворяющих самосогласованной монотонности

6.8. Процедуры, однородные к победам и поражениям.

6.8.1. Процедура наименьших квадратов.

6.8.2. Обобщенная процедура суммы очков.

6.9. Достаточное условие самосогласованной монотонности.

6.10. Четыре процедуры, удовлетворяющие самосогласованной монотонности

6.11. О двух дополнительных аксиомах

6.11.1. Независимость от макровершины.

6.11.2. Сохранение баланса при разбиении.

Глава 7. Агрегирование предпочтений обобщенным методом суммы очков

7.1. Введение

7.2. Обобщение метода суммы очков.

7.3. Свойства обобщенных сумм очков.

7.4. Статистические модели.

7.4.1. Гребневые оценки для модели Шеффе.

7.4.2. Байесовская модель

7.5. Случай парных сравнений с ограниченным результатом.

7.6. Использование обобщенного метода суммы очков для агрегирования числовых оценок объектов.

7.7. О выборе параметра г.

7.8. Примеры

Глава 8. Меры связанности вершин графов, их свойства и характеристические условия

Введение 2008 год, диссертация по информатике, вычислительной технике и управлению, Чеботарев, Павел Юрьевич

10.2. Изменение приведенного лесного расстояния между вершинами при усилении их связи.266

10.3. Соотношение лесных расстояний для пары графов, отличающихся одним ребром.268

10.4. Интерпретация лесной метрики графа.271

10.5. О связи лесной метрики и резисторной метрики графа.273

Заключение 277

Список литературы. .280

Введение

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

Два основных направления в этой теории связаны с исследованием матрицы смежности графа и его лапласовской1 матрицы, по существу, отличающейся от матрицы смежности своей главной диагональю. Первое направление наиболее полезно при анализе маршрутно-циклической структуры графов, второе — при анализе их древесной (лесной) структуры. Первое направление развилось раньше, но к 90-м годам XX века всё больше исследователей стало заниматься лапласовской алгебраической теорией графов; уже в 60-70-е гг. существенные продвижения в ней были получены работавшим тогда в Институте проблем управления А.К.Кельмансом [31,32,253,254].

К настоящему времени лапласовская теория неориентированных графов доволь

1 Своим названием она обязана процессу дискретизации оператора Лапласа, приводящему к матрицам такого рода. но хорошо разработана. Еще в 90-е годы вышли обзоры Р. Мерриса с соавторами [228,229,297,298,301] и Б. Мохара [308-310], а также монография Ф.Р.К.Чанг [183], в которых были систематизированы более ранние результаты и представлены оригинальные результаты авторов этих работ; см. также [223].

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

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

2. Химическая информатика. Задачи идентификации сложных органических молекул и поиска связей между их структурными инвариантами и физико-химическими свойствами веществ требуют анализа графов, представляющих молекулы, методами теории матриц. Лапласовские матрицы используются в этой области уже более четверти века.

3. Кластер-анализ. Один из подходов к кластеризации на графах связан с нахождением спектров и собственных подпространств их лапласовских матриц. Этот подход используется также для распознавания образов.

4. Построение алгебраических индексов графов. Во многих приложениях необходимо сопоставлять вершинам графов, парам и наборам вершин, ребрам, а также графам в целом значения числовых характеристик, выражающих те или иные структурные свойства. Приведем несколько примеров. В задачах анализа социальных сетей элементу сети ставят в соответствие значения центральности/периферийности, совокупной силы связи с другими элементами, баланса входящих и исходящих связей и др.; пару элементов характеризуют показателями силы, длины, направления связей между ними, индексами сходства их профилей связности и "ролей" в сети; дуги и пути характеризуют пропускной способностью по отношению к информации и управляющим воздействиям, критичностью разрыва по отношению к связности сети; сеть в целом оценивают степью связности, сплоченности, однородности, взаимности связей и т. д. Потребность в "оцифровке" возникает и при анализе/синтезе транспортных, компьютерных, организационных, семантических и других сетей, а также баз данных. Другой класс задач, требующий специальной оцифровки вершин графов, — агрегирование экспертных оценок, оценка силы участников турнира, если турнир — некруговой или данные неполные, или план парных сравнений не сбалансирован. Далее, следует упомянуть популярную в последнее время задачу ранжирования интернет-страниц, найденных поисковой машиной но пользовательскому запросу (PageRank problem): ранжирование производится с использованием орграфа ссылок страниц друг на друга. Наконец, задачи такого типа нужно решать при разработке алгоритмов работы распределенных компьютерных рекомендательных систем, где каждый пользователь, указав свои музыкальные, литературные, кинематографические и т. п. предпочтения, получает рекомендации — что еще послушать (почитать, посмотреть), сформированные на основе предпочтений пользователей, имеющих близкие вкусы.

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

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

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

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

Предмет исследования. Взаимосвязи между структурными свойствами ориентированных и неориентированных графов, свойствами определяемых ими матриц и особенностями функционирования систем, моделируемых графами и орграфами.

Цель работы: разработать основы лапласовской теории ориентированных графов и ее применений. Достижение поставленной цели требует решения следующих основных задач:

• Исследование лапласовских спектров орграфов;

• Разработка методов классификации остовных2 лесов (ор)графов;

• Разработка методов анализа (ор)графов с помощью классификации остовных лесов и с использованием матриц лесов;

• Разработка основ применения полученных результатов к построению структурных индексов графов, агрегированию экспертных предпочтений, управлению мно-гоагентными системами.

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

Научная новизна. В работе разработаны основы лапласовской теории ориентированных графов и ее применений, в том числе:

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

2 Остовным называют подграф, множество вершин которого совпадает с множеством вершин графа; лес — граф без циклов. графов. Введен класс лесных метрик графа и изучены его свойства; установлены связи между лесными метриками и резисторной метрикой графа.

2. Получены выражения для собственного проектора, компонент и псевдообратной по Дразину произвольной вырожденной матрицы через аннулирующий многочлен для любой степени матрицы, большей или равной ее индексу.

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

4. Локализована область спектров лапласовских матриц орграфов. Полученные результаты анализа лапласовских спектров орграфов применены к исследованию моделей согласования характеристик в децентрализованном управлении много-агентными системами.

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

6. Разработан нормативный подход к анализу мер близости вершин графов и орграфов. Введено понятие функций Е-близости и установлена их двойственность метрикам.

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

В диссертации наиболее подробно разработаны приложения, связанные с построением структурных индексов графов и агрегированием экспертных предпочтений.

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на научных семинарах в Институте проблем управления РАН, ЦЭМИ РАН, Институте вычислительной математики РАН, ИСЭП РАН, в университетах Барселоны, Кана, Ванкувера, Тампере, на общемосковском семинаре "Математические методы в экспертных оценках и анализ данных", на 6 Всесоюзной школе-семинаре по непараметрическим и робастным методам статистики в кибернетике и информатике (Томск, 1987 г.), 3 Всесоюзной школе-семинаре "Программно-алгоритмическое обеспечение прикладного многомерного статистического анализа" (Цахкадзор, 1987 г.), Всесоюзной научно-практической школе-семинаре "Программное обеспечение ЭВМ: индустриальная технология, интеллектуализация разработки и применения" (Ростов-на-Дону, 1988 г.), 3 Всесоюзной конференции "Методы социологических исследований" (Звенигород, 1989 г.), 7 Всесоюзной школе-семинаре по непараметрическим и робастным методам статистики в кибернетике и информатике (Иркутск, 1990 г.), Всесоюзном совещании "Пути повышения качества прогнозов" (Ленинград, 1990 г.), 3 Всесоюзной школе-семинаре "Комбинаторно-статистические методы анализа и обработки информации, экспертное оценивание" (Одесса, 1990 г.), Всесоюзном научно-практическом семинаре "Интеллектуальное программное обеспечение ЭВМ" (Терскол, 1990 г.), 4 Всесоюзной школе-семинаре "Статистический и дискретный анализ данных и экспертное оценивание" (Одесса, 1991 г.), 5 Международной конференции "Статистический и дискретный анализ данных и экспертные оценки" (Одесса, 1995 г.), Международной конференции по анализу порядковых и символьных данных (Париж, 1995 г.), 5 Конференции Международного общества по линейной алгебре (Атланта, 1995 г.), 9 Европейском симпозиуме психометрического общества (Лейден, 1995 г.), 3 Международной конференции "Эконометрические модели принятия решений: конструирование целевых функций" (Хаген, 1995 г.), Российско-испанском семинаре по групповому выбору (Барселона, 1995 г.), Международном семинаре по агрегированию информации и решений (Вашингтон, 1996 г.), 3 Международном симпозиуме Общества социального выбора и благосостояния (Маастрихт, 1996 г.), Международной научно-практической конференции "Управление большими системами" (Москва, 1997 г.), 7 Конференции Международного общества по линейной алгебре (Мэдисон, 1998 г.), 1 Международной конференции по проблемам управления (Москва, 1999 г.), 20 Международной конференции по социальным сетям (Ванкувер, 2000 г.), 5 Международном симпозиуме Общества социального выбора и благосостояния (Аликанте, 2000 г.), Международной конференции по анализу порядковых и символьных данных (Брюссель, 2000 г.), 7 Конференции Международной федерации обществ классификации (Намюр, 2000 г.), 4 Международной конференции "Эконометрические модели принятия решений: конструирование и применение целевых функций" (Хаген, 2000 г.), 2 Международной конференции "Логика, теория игр и социальный выбор" (Санкт-Петербург, 2001 г.), Международной конференции по линейной алгебре (Хайфа, 2001 г.), 2 Европейском семинаре по алгебраической теории графов (Эдинбург, 2001 г.), Международной конференции "Теория полезности и ее применения" (Триест, 2002 г.), Международной конференции по матричному анализу и его применениям (Форт Лодердейл, 2003 г.), 13 Конференции Международного общества по линейной алгебре (Амстердам, 2006 г.), Международной конференции обществ GAMM и SIAM по прикладной линейной алгебре (Дюссельдорф, 2006 г.).

Публикации. Материал диссертации опубликован в 77 работах, среди которых 43 - статьи [3-6,45-48,63,64,66,68-72,74,76,87,89,91-93,97,142,145,146,149,151-153,157,159, 162,164-167,170-172,175,176] и 34 — тезисы докладов (объемом не более 3 страниц) [65,67,73,75,77-81,84,88,90,96,143,144,148,150,147,154-156,158,160,161,163,168,169,173, 174,177-180,354,178]. Основное содержание диссертации опубликовано в 22 статьях в ведущих рецензируемых журналах (список ВАК России) [3-6,71,72,76,87,89,91-93,97, 145,151,152,157,159,162,165,172,176]. Кроме того, 18 работ опубликовано по смежной теме — кооперативному принятию решений, четыре из них [12,62,83,86] — в журналах из списка ВАК России.

Объем и структура работы. Диссертация состоит из введения, десяти глав, заключения и списка литературы, число наименований в котором — 408. Основное содержание работы изложено на 279 страницах.

Заключение диссертация на тему "Методы лапласовской теории орграфов в структурном анализе систем"

Заключение

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

Основные научные результаты, полученные в диссертационной работе, состоят в следующем:

1) Получена матричная теорема о лесах.

2) Разработан подход к нахождению собственного проектора и компонент квадратной матрицы А с помощью произвольного ненулевого аннулирующего многочлена для Аи, где и ^ тс1Л

3) Изучены структура и свойства множеств остовных корневых лесов графов и орграфов и связанных с ними матриц. Установлено, что матрица максимальных входящих лесов орграфа является собственным проектором лапласовской матрицы. Из последнего факта выведена матричная теорема о деревьях для цепей Маркова. Эти результаты составляют основу анализа моделей распределенного согласования характеристик в многоагентных системах.

4) Впервые исследованы свойства лапласовского спектра орграфов. Потребность в таком исследовании неоднократно высказывалась специалистами по децентрализованному управлению в связи с анализом моделей функционирования многоагентных систем.

5) Введена аксиома самосогласованной монотонности для процедур агрегирования предпочтений. Ряд известных алгебраических методов агрегирования предпочтений и их классов протестирован на выполнение этой аксиомы. Классы методов при этом определялись в терминах свойств индуцируемых ими алгебраических индексов на орграфах предпочтений.

6) Аксиоматически построен и исследован новый метод агрегирования неполных предпочтений — обобщенный метод суммы очков, обобщающий процедуры Борда, Коупленда и турнирную процедуру агрегирования. Показано, что метод эквивалентен нахождению гребневых оценок параметров статистической модели парных сравнений Шеффе и что назначаемые методом итоговые баллы можно трактовать как прогнозные значения сумм очков после пополнения массива предпочтений.

7) Предложена система нормативных требований к показателям близости вершин графов. Изучены свойства ряда известных показателей близости. Область применения этих результатов — построение алгебраических индексов графов и анализ сетей различной природы.

8) Аксиоматически введен класс функций Е-близости. Доказана теорема о двойственности понятий Е-близость и расстояние. Область приложения этих результатов — анализ данных.

9) На основе матричной теоремы о лесах введен новый показатель близости вершин графов — относительная достижимость по лесам. Изучены его свойства и на его основе построено семейство структурных индексов графов. Область применения — анализ социальных, семантических и других сетей.

10) Введен класс лесных метрик графов. Исследованы свойства этих метрик, дана вероятностная интерпретация лесного расстояния, установлены соотношения между лесными метриками и резисторной метрикой графа. Области применения — анализ сетей, химическая информатика.

Библиография Чеботарев, Павел Юрьевич, диссертация по теме Системный анализ, управление и обработка информации (по отраслям)

1. Агаев Р. П. Об исследовании и применении лапласовских спектров орграфов кольцевой структуры // Автоматика и телемеханика. — 2008. — № 2. — С. 3-16.

2. Агаев Р. П., Никифоров С. В., Андрюшина Н. А. О спектре матрицы смежности орграфа кольцевой структуры и его применении // Проблемы управления. — 2008. — № 4. — С. 11-15.

3. Агаев Р. П., Чеботарев П. Ю. Матрица максимальных исходящих лесов орграфа и ее применения // Автоматика и Телемеханика. — 2000. С. 15-43.

4. Агаев Р. П., Чеботарев П. Ю. Остовные леса орграфа и их применение // Автоматика и Телемеханика. — 2001. — № 3. — С. 108-133.

5. Агаев Р. П., Чеботарев П. Ю. О нахождении собственного проектора и компонент матрицы с помощью аннулирующего многочлена // Автом,атика и Телемеханика. 2002. - № 10. - С. 3-12.

6. Агаев Р. П., Чеботарев П. Ю. Лапласовские спектры орграфов и их приложения IIА втоматика и Телемеханика. — 2005. — № 5. — С. 47-62.

7. Белкин А. Р., Левин М. Ш. Принятие решений: комбинаторные модели аппроксимации информации. — Москва: Наука, 1990.

8. Бианки В. А. Психологические аспекты функционирования власти в сетевых структурах II Труды Международной научной конференции "Психология власти", Санкт-Петербург, 11-12 января 2005.— Санкт-Петербург: СПбГУ, 2005.

9. Блюмин С. Л. Мультиагентные системы: проблемы и протоколы согласия, псевдообращение лапласианов графов // Системы управления и информационные технологии. 2007. - № 2(28). - С. 4-9.

10. Блюмин С. Л. Теоретико-множественные и векторно-алгебраические аспекты проблем согласия в многоагентных системах // Труды Международной научно-практической конференции "Теория активных систем-2007". — Москва, ИПУ РАН: 2007.

11. Блюмин С. Л., Миловидов С. П. Явное выражение псевдообратной лапласиана двудольного графа //Управление большими системами / Сборник трудов. Выпуск 18! М.: ИПУ РАН, 2007. - Рр. 24-29.

12. Борзенко В. И., Чеботарев П. Ю., Лезина 3. М., Логинов А. К., Цодикова Я. Ю. Стратегии при голосовании в стохастической среде: эгоизм и коллективизм // Автоматика и телемеханика. — 2006. — № 2. — С. 140-152.

13. Бурков В. Н., Новиков Д. А. Стимулирование в активных системах: целевые функции и метризованные отношения // Автоматика и Телемеханика. — 2000. — №9.-С. 138-146.

14. Варшавский В. П., Поспелов Д. А. Оркестр играет без дирижера: размышления об эволюции некоторых технических систем и управлении ими. — М.: Наука. Главная редакция физико-математической литературы, 1984.

15. Вентцель А. Д., Фрейдлин М. И. О малых случайных возмущениях динамических систем // Успехи математических наук. — 1970. — Т. 25. — С. 3-55.

16. Вентцель А. Д., Фрейдлин М. И. Флуктуации в динамических системах под действием малых случайных возмущений. — Москва: Наука, 1979.

17. Вересков А. И. Обобщенные методы регрессионного анализа в задачах идентификации нелинейных моделей: Диссертация. кандидата техн. наук по специальности 01.01.11 /ВНИИСИ,-Москва, 1986.

18. Вольский В. И. Правила выбора лучших вариантов на ориентированных графах и графах-турнирах //Автоматика и телемеханика. — 1987. — № 3. — С. 3-17.

19. Вольский В. И. Турнирные функции в задачах коллективного и многокритериального выбора // Исследования по теории структур. — 1988. — С. 119-123.

20. Гантмахер Ф. Р. Теория матриц. — 3 изд. — Москва: Наука, 1988.

21. Гельфанд И. М. Лекции по линейной алгебре. — М.: Наука, 1971.

22. Гиновкер В. Д. Об одном подходе к оцениванию объектов по результатам парных сравнений: Деп. в ВИНИТИ 3431-81ДБИ: Горьковский университет, 1981.

23. Гривко И. Л., Левченков В. С. Нормативные свойства правила самосогласованного выбора // Автоматика и Телемеханика. — 1994.— С. 89-99.

24. Дмитриев Н., Дынкин Е. О характеристических числах стохастической матрицы //Доклады Академии Наук СССР. 1945. - Т. 49. - С. 159-162.

25. Дмитриев И., Дынкин Е. Характеристические корни стохастических матриц //Известия Академии наук СССР. 1946. - Т. 10. - С. 167-184.

26. Дрейпер IT., Смит Г. Прикладной регрессионный анализ. — Москва: Финансы и статистика, 1987.

27. Заславский А. А. Геометрия парных сравнений //Автоматика и телемеханика. — 2007. № 3. - С. 181-186.

28. Зыков А. А. Теория конечных графов. — Новосибирск: Наука (Сибирское отделение), 1969.

29. Кельманс А. К. О числе деревьев графа. I // Автоматика и Телемеханика.— 1965. Т. 26, № 12. - С. 2194-2204.

30. Кельманс А. К. О числе деревьев графа. II // Автоматика и Телемеханика.—1966. Т. 27, № 2. - С. 56-65.

31. Кельманс А. К. О свойствах характеристического многочлена графа //Кибернетику — на службу коммунизму / Под ред. акад. А. И. Берга, — M.-JL: Энергия,1967,- С. 27-41.

32. Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. — М.: Наука, 1972.

33. Ланкастер П. Теория матриц. — Москва: Наука, 1978.

34. Левченков В. С. Энтропийный анализ правила большинства // Автоматика и телемеханика. — 1990. — № 4. — С. 115-124.

35. Левченков В. С. Выбор без аксиомы Эрроу о независимости от посторонних альтернатив //Доклады РАН. 1992. - Т. 322, № 4. - С. 651-655.

36. Левченков В. С. Аксиоматический подход к самосогласованному выбору //Доклады РАН. 1993. - Т. 330, № 2. - С. 173-176.

37. Левченков В. С. Самосогласованное описание процесса манипулирования вариантами //Доклады РАН 1993. - Т. 331, № 5. - С. 567-570.

38. Левченков В. С. Выбор по турнирным отношениям // Доклады РАН. — 1994. — Т. 336, № 3. С. 324-327.

39. Левченков В. С. Стратегическое описание группового выбора //Доклады РАН,— 1995. Т. 341, № 3. - С. 320-323.

40. Мак-Миллан В. Д. Динамика твердого тела. — Москва: ИЛ, 1951.

41. Паниотто В. И. Анализ структуры межличностных отношений // Математические методы анализа и интерпретации социологических данных. — М.: Наука, 1989.- С. 121-162.

42. Плинер В. М. Об одном методе неполных парных сравнений // Применение многомерного статистического анализа в экономике и оценке качества продукции. 4 Всесоюзная конференция. — Тарту: 1989. — С. 29-30.

43. Пригарина Т. А., Чеботарев П. Ю. Методы экспертных оценок на примере определения предпочтительности объектов: Препринт. — Москва: ЦЭМИ АН СССР, 1989.

44. Пригарина Т. А., Чеботарев П. Ю. Методы экспертных оценок и определение предпочтительности объектов //Экспертные оценки в социологических исследованиях. Гл. VIII / Под ред. В. И. Паниотто. Киев: Наукова думка, 1990. - С. 190-225.

45. Пригарина Т. А., Чеботарев П. Ю., Шмерлинг Д. С. Анализ нечисловой информации // Математические методы в социально-экономических исследованиях / Под ред. С. М. Ермакова, В. Б. Меласа. СПб: Петрополис, 1996. - С. 123-138.

46. Пригарина Т. А., Чеботарев П. Ю., Шмерлинг Д. С. Парные сравнения объектов (аналитический обзор) // Научно-техническая информация. Серия 2. Информационные процессы и системы. — 1996. — № 2.— С. 20-25, 32.

47. Pao С. Р. Линейные статистические методы и их применения. — Москва: Наука, 1968.

48. Розенблит А. Б., Голендер В. Е. Логико-комбинаторные методы в конструировании лекарств. — Рига: Зинатне, 1983. — С. 150-163.

49. Себер Д. Линейный регрессионный анализ, — М.: Мир, 1980.

50. Станкевич М. П., Станкевич И. В., Зефиров Н. С. Топологические индексы в органической химии // Успехи химии. — 1988. — Т. 57, № 3. — С. 337-366.

51. Tamm У. Теория графов. — М.: Мир, 1988.

52. Толстова Ю. Н. Измерение в социологии. — Москва: ИНФРА-М, 2003.

53. Ушаков И. А. Задача о выборе предпочтительного объекта //Известия АН СССР. Техническая кибернетика. — 1971. — № 4. —■ С. 3-7.

54. Фаддеев Д. К., Фаддеева В. Н. Вычислительные методы линейной алгебры, — 2 изд. — Москва-Ленинград: Физматгиз, 1963.

55. Харари Ф. Теория графов, — М.: Мир, 1973.

56. Харари Ф., Палмер Э. Перечисление графов. — Москва: Мир, 1977.

57. Хорн Р., Джонсон Ч. Матричный анализ. — Москва: Мир, 1989.

58. Цветкович Д., Дуб М., Захс X. Спектры графов: теория и применение. — Киев: Наукова думка, 1984.

59. Чеботарев П. Ю. Некоторые свойства траекторий в динамической задаче голосования // Автоматика и телемеханика. — 1986.— № 1,— С. 133-138.

60. Чеботарев П. Ю. Аксиоматическое задание одного метода оценивания объектов по результатам экспертного опроса // Труды науч.- техн. конф. молодых ученых и спец. Моск. ин-та нефти и газа. 1987. - С. 27-32. - Деп. в ВИНИТИ 24.07.87, № 5369-В87.

61. Чеботарев П. Ю. Байесовское оценивание качества объектов по результатам парных сравнений // Материалы X конф. Молодых ученых Ун-та дружбы народов,-Ч. 2. 1987. - С. 35-38. - Деп. в ВИНИТИ 29.12.87, № 9152-В87.

62. Чеботарев П. Ю. Обобщение метода строчных сумм для неполных парных сравнений // III Всес. школа-семинар "Программно-алгоритмическое обеспечение прикладного многомерного статистического анализа". Тезисы докладов,- Ч. 2. — М.: ЦЭМИ, 1987. С. 249-250.

63. Чеботарев П. Ю. Два метода упорядочения объектов по произвольному множеству парных сравнений. 1988. - Деп. в ВИНИТИ 22.07.88, № 5879-В88.

64. Чеботарев П. Ю. Неполные парные сравнения и метод строчных сумм. — 1988. — Деп. в ВИНИТИ 26.02.88., № 1576-В88.

65. Чеботарев П. Ю. Агрегирование неполных предпочтений //III Всесоюзная конференция "Методы социологических исследований". — Т. 5. — Москва: ИС АН СССР, 1989. С. 59-62.

66. Чебот,арев П. Ю. Метод оценивания объектов по неполному набору парных сравнений // Комплексный подход к анализу данных в социологии. — Москва: ИС АН СССР, 1989. С. 79-93.

67. Чеботарев П. Ю. Метод строчных сумм и приводящие к нему модели // Сб. тр. ВНИИ системных исследований. — 1989. — № 3. — С. 94-110.

68. Чеботарев П. Ю. Обобщение метода строчных сумм для неполных парных сравнений // Автоматика и телемеханика. — 1989.— № 8. — С. 125-137.

69. Чеботарев П. Ю. Агрегирование предпочтений: регрессионная модель // Методы математической статистики в кибернетике и информатике. — Томск: ТГУ, 1990. — Т. 2. С. 541-550.

70. Чеботарев П. Ю. Алгоритмы выбора параметра е в методе обобщенных строчных сумм // III Всесоюзная школа-семинар "Комбинаторно-статистические методы анализа и обработки информации, экспертное оценивание". Тезисы докладов. — Одесса: 1990. С. 104.

71. Чеботарев П. Ю. О некоторых оптимизационных методах агрегирования предпочтений // Сб. тр. ВНИИ системных исследований. — 1990. — № 8. — С. 67-72.

72. Чеботарев П. Ю. О некоторых оптимизационных методах агрегирования предпочтений // Всес. научно-практический семинар "Интеллектуальное программное обеспечение ЭВМ". Тезисы докладов,- Ч. 1.— Ростов-на-Дону-Терскол: 1990.— С. 95-97.

73. Чеботарев П. Ю. Об одном прогнозном подходе к агрегированию экспертных оценок // Всесоюзное совещание "Пути повышения качества прогнозов". Тезисы докладов. — Москва-Ленинград: Союз научных и инженерных обществ СССР, 1990. — С. 60-62.

74. Чеботарев П. Ю. Уточненный пример обобщенной немонотонности метода Кемени-Слейтера //IV Всес. школа-семинар "Статистический и дискретный анализ данных и экспертное оценивание". Тезисы докладов. — Одесса: 1991. — С. 136-138.

75. Чеботарев П. Ю. Новые меры связности графов и их применение в анализе социального поведения // Информационный бюллетень РФФИ. — 1996.— Т. 4, № 1,-С. 430.

76. Чеботарев П. Ю. Работа М.А. Айзермана по динамическому голосованию //Марк Аронович Айзерман (1913-1993). Москва: Физматлит, 2003. — С. 240-243.

77. Чеботарев П. Ю. Аналитическое выражение ожидаемых значений капиталов при голосовании в стохастической среде // Автоматика и телемеханика. — 2006.— № 3. С. 57-68.

78. Чеботарев П. Ю., Агаев Р. П. Псевдообратная матрица для матрицы Кирхгофа ориентированного графа // Труды 14 Международного Симпозиума "Управление большими системами", СОМТШЬ'2000. Тбилиси: 2000. - С. 23-25.

79. Чеботарев П. Ю., Кочубей Б. А. Маленькие хитрости демократии // Век XX и мир. 1990. - № 6. - С. 2-3.

80. Чеботарев П. Ю., Логинов А. К., Цодикова Я. Ю., Левина 3. М., Борзенко В. И. Анализ феноменов коллективизма и эгоизма в контексте общественного благосостояния // Проблемы управления. — 2008. — № 4. — С. 30-37.

81. Чеботарев П. Ю., Митькин А. Н., Шмерлинг Д. С. Об оценивании вклада ведомственных целевых программ в достижение целей правительства // Проблемы управления. — 2007. — № 4. — С. 43-50.

82. Чеботарев П. Ю., Шамис Е. В. Матричная теорема о лесах и измерение связей в малых социальных группах // Автоматика и Телемеханика. — 1997. № 9. -С.124-136.

83. Чеботарев П. Ю., Шамис Е. В. Характеризации очковых процедур агрегирования предпочтений // Материалы Межд. Научно-практич. Конф. "Управление большими системами". — Москва: Синтег, 1997. — С. 241.

84. Чеботарев П. Ю., Шамис Е. В. О двойственности метрик и Е-близостей // Автоматика и Телемеханика. — 1998. — № 4. — С. 204-209.

85. Чеботарев П. Ю., Шамис Е. В. О мерах близости вершин графов // Автоматика и Телемеханика. — 1998. — № 10. — С. 113-133.

86. Чеботарев П. Ю., Шамис Е. В. Некоторые свойства лесной метрики графа // Автоматика и Телемеханика. — 2000. — № 8. — С. 137-146.

87. Шмерлинг Д. С., Дубровский С. А., Аржанова Т. Д., Френкель А. А. Экспертные оценки. Методы и применение (обзор) // Статистические методы анализа экспертных оценок, — Москва: Наука, 1977.— С. 290-382.

88. Abdesselam A. The Grassmann-Berezin calculus and theorems of the matrix-tree type I I Advances in Applied Mathematics. — 2004. — Vol. 33, no. 1. — Pp. 51-70.

89. Agaev R., Chebotarev P. On the Faddeev matrix and the generalized inverses //international Conference on Matrix Analysis and Applications. — Fort Lauderdale: Nova Southeastern University, 2003. — P. 1. http://www.resnet.wm.edu/~cklixx/novabs.pdf.

90. Agaev R., Chebotarev P. On the spectra of nonsymmetric Laplacian matrices // Linear Algebra and its Applications. — 2005. — Vol. 399. — Pp. 157-168.

91. Aleskerov F. Categories of arrovian voting schemes // Handbook of Social Choice and Welfare / Ed. by K. J. Arrow, A. K. Sen, K. Suzumura. — Elsevier, 2002,— Vol. 1 of Handbook of Social Choice and Welfare. — Pp. 95-129.

92. Altmann M. Reinterpreting network measures for models of disease transmission // Social Networks. 1993. - Vol. 15. - Pp. 1-17.

93. Anantharam V., Tsoucas P. A proof of the Markov chain tree theorem // Statistics & Probability Letters. 1989. - Vol. 8. - Pp. 189-192.

94. Anderson Jr. W. N., Morley T. D. Eigenvalues of the Laplacian of a graph // Linear and Multilinear Algebra. — 1985. — Vol. 18. — Pp. 141-145.

95. Andrews D. M., David H. A. Nonparametric analysis of unbalanced paired comparison or ranked data // Journal of the American Statistical Association. — 1990. — Vol. 85. — Pp. 1140-1146.

96. Arrow K. J. Social Choice and Individual Values. — N.Y.: Willey, 1963.

97. Baharad E., Nitzan S. Ameliorating majority decisiveness through expression of preference intensity // American Political Science Review. — 2002. — Vol. 96. — Pp. 745-754.

98. Baharad E., Nitzan S. The costs of implementing the majority principle: The golden voting rule // Economic Theory. — 2007. — Vol. 31, no. 1. — Pp. 69-84.

99. Baigent N., Klamler C. Transitive closure, proximity and intransitivities: Working paper: Institute of Public Economics, Graz University, October 2001.

100. Baigent N., Klamler C. Transitive closure, proximity and intransitivities // Economic Theory. 2003. - Vol. 23, no. 1. - Pp. 175-181.

101. Bapat R. B. Linear estimation in models based on a graph // Linear Algebra and its Applications. 1999. — Vol. 302-303. - Pp. 223-230.

102. Bapat R. B. Resistance distance in graphs //Mathematical Student. — 1999. — Vol. 12. — Pp. 87-98.

103. Bapat R. B., Constantine G. An enumerating function for spanning forests with color restrictions //Linear Algebra and its Applications. — 1992. — Vol. 173. — Pp. 231-237.

104. Bapat R. B., Grossman J. W., Kulkarni D. M. Matrix tree theorem //Encyclopaedia of Mathematics / Ed. by M. Hazewinkel. — Berlin, Heidelberg, New York: Springer, 2001,-Vol. 31,- Pp. 7-22.

105. Bapat R. B., Kurkarni D. M. Minors of some matrices associated with a tree // Algebra and its Applications / Ed. by D. V. Huynh, S. K. Jain, S. R. Lopez-Permouth. — Providence, RI: American Mathematical Society, 2000. — Pp. 45-66.

106. Bapat R. B., Pati S. Algebraic connectivity and the characteristic set of a graph // Linear and Multilinear Algebra. — 1998. — Vol. 45. — Pp. 247-273.

107. Barabási A.-L. Linked: The New Science of Networks.— Cambridge, MA: Perseus Publishing, 2002.

108. Ben-Israel A., Chames A. Contributions to the theory of generalized inverses // Journal of the Society for Industrial and Applied Mathematics. — 1963.— Vol. 11, no. 3.— Pp. 667-699.

109. Ben-Israel A., Greville T. N. E. Generalized Inverses: Theory and Applications. — New York: Wiley, 1974.

110. Berman A., Plemmons R. Nonnegative Matrices in the Mathematical Sciences. — New York: Academic Press, 1979.

111. Berman A., Zhang X.-D. A note on degree antiregular graphs //Linear and Multilinear Algebra. 2000. - Vol. 47. - Pp. 307-311.

112. Berman K. A. A graph theoretical approach to handicap ranking of tournaments and paired comparisons // SIAM Journal on Algebraic and Discrete Methods. — 1980. — Vol. 1, no. 3.- Pp. 359-361.

113. Bollobás B. Modern Graph Theory. — New York: Springer, 1998.

114. Borchardt C. W. Ueber eine der Interpolation entsprechende Darstellung der Eliminations-Resultante // Journal für die reine und angewandte Mathematik.— I860.— Vol. 57.-Pp. 111-121.

115. Borda J. C. Mémoire sur les élection au scrutin // Histoire de 1 Academie Royale des Sciences. — 1781.

116. Borgatti S. P. Identifying sets of key players in a network // Proceedings of the Conference on Integration of Knowledge Intensive Multi-Agent Systems. — 2003. — Pp. 127-131.

117. Borkar V., Varaiya P. Asymptotic agreement in distributed estimation // IEEE Trans. Automatic Control. — 1982,- Vol. 27. Pp. 650-655.

118. Borrelli F., Keviczky T. Distributed LQR design for dynamically decoupled systems // Proceedings of the 45th IEEE Conference on Decision & Control. — San Diego, CA, USA, December 13-15, 2006: 2006. Pp. 5639-5644.

119. Bouyssou D., Vincke P. Introduction to topics on preference modelling // Annals of Operations Research. — 1998. — Vol. 80, no. 1. — Pp. i-xiv.

120. Bradley R. A., Terry M. E. The rank analysis of incomplete block designs. 1. The method of paired comparisons // Biometrika. — 1952. — Vol. 39. — Pp. 324-345.

121. Brozos-Vázquez M., Campo-Cabana M. A., Diaz-Ramos J. C., González-Díaz J. Ranking participants in tournaments by means of rating functions: arXiv paper math.GM/0601053v2: 2006. http://arxiv.org/pdf/math/0601053v2.

122. Buchanan M. Nexus: Small Worlds and the Groundbreaking Science of Networks. — New York, NY: W. W. Norton, 2002.

123. Buckley F., Harary F. Distance in Graphs. — Redwood City, CA: Addison-Wesley, 1990.

124. Campbell S. L., Meyer, Jr. C. D. Generalized Inverses of Linear Transformations.— London: Pitman, 1979.

125. Campbell S. L., Meyer, Jr. C. D., Rose N. J. Applications of the Drazin inverse to linear systems of differential equations with singular constant coefficients // SIAM Journal on Applied Mathematics. 1976. - Vol. 31. - Pp. 411-425.

126. Catral M., Neumann M., Xu J. Proximity in group inverses of M-matrices and inverses of diagonally dominant M-matrices // Linear Algebra and its Applications. — 2005. — Vol. 409. Pp. 32-50.

127. Caughman J. S., Lafferriere G., Veerman J. J. P., Williams A. Decentralized control of vehicle formations // Systems and Control Letters. — 2005. — Vol. 54, no. 9. — Pp. 899910.

128. Caughman J. S., Veerman J. J. P. Kernels of directed graph Laplacians: Working paper. — Portland, OR: Portland State University, 2005.

129. Caughman J. S., Veerman J. J. P. Kernels of directed graph Laplacians // The Electronic Journal of Combinatorics. — 2006. — Vol. 13, no. 1-R39.

130. Chaiken S. A combinatorial proof of the all minors matrix tree theorem //SIAM Journal on Algebraic and Discrete Methods. — 1982. — Vol. 3, no. 3. — Pp. 319-329.

131. Chaiken S., Kleitman D. J. Matrix tree theorems // Journal of Combinatorial Theory, Series A. 1978. - Vol. 24. - Pp. 377-381.

132. Chebotarev P. Constructing extensions of utility functions // International Conference "Logic, Game Theory and Social Choice". — Saint-Petersburg: Saint-Petersburg State University, 2001.- Pp. 49-55.

133. Chebotarev P. Outforests of a digraph, the Kirchhoff matrix, and Markov chain probabilities // Second Euroworkshop on Algebraic Graph Theory. — Edinburgh: University of Edinburgh, 2001. P. 5.

134. Chebotarev P. Extending utility representations of partial orders without continuity requirements // Abstracts of the Int. conference "Utility Theory and Applications". — Trieste: University of Trieste, Faculty of Economics, 2002. — Pp. 12-13.

135. Chebotarev P. On the extension of utility functions // Constructing and Applying Objective Functions / Ed. by A. S. Tangian, J. Gruber. — Berlin: Springer-Verlag,2002. — Vol. 510 of Lecture Notes in Economics and Mathematical System. — Pp. 6374.

136. Chebotarev P. Spanning forests of digraphs and limiting probabilities of Markov chains //Electronic Notes in Discrete Mathematics. — 2002. — Vol. 11. — Pp. 108-116.

137. Chebotarev P. On of the spectrum of the digraph Laplacian // International Conference on Matrix Analysis and Applications. — Fort Lauderdale: Nova Southeastern University,2003. — Pp. 4-5. http://www.resnet.wm.edu/~cklixx/novabs.pdf.

138. Chebotarev P. Laplacian matrices and essentially cyclic weighted digraphs // Abstracts of the 13th Conference of the International Linear Algebra Society. — Amsterdam: Free University of Amsterdam, 2006. — Pp. 60-61.

139. Chebotarev P. A graph theoretic interpretation of the mean first passage times: arXiv paper math.PR/0701359: arXiv, 2007. http://arxiv.org/abs/math/0701359.

140. Chebotarev P. The Laplacian matrix, spanning forests, and the golden ratio // Abstracts of the 14th Conference of the International Linear Algebra Society. — Shanghai: Shanghai University, 2007. P. 12.

141. Chebotarev P. Spanning forests and the golden ratio // Discrete Applied Mathematics. — 2008. Vol. 156, no. 5. - Pp. 813-821.

142. Chebotarev P., Agaev R. Forest matrices around the Laplacian matrix //Linear Algebra and its Applications.- 2002,- Vol. 356.- Pp. 253-274.

143. Chebotarev P., Agaev R. Matrices of forests and the analysis of digraphs: arXiv paper math.co/0508171: arXiv, August 2005. http://arxiv.org/abs/math/0508171.

144. Chebotarev P., Agaev R. When is the Laplacian spectrum of a weighted digraph real? // International GAMM-SIAM Conference on Applied Linear Algebra. — Düsseldorf: University of Düsseldorf, 2006,- P. 29.

145. Chebotarev P., Agaev R., Shamis E. The out forests of a (di)graph and the investigation of its structure // International Conference on Ordinal and Symbolic Data Analysis. — Bruxelles: Universite Libre de Bruxelles, 2000. — P. 8.

146. Chebotarev P., Shamis E. A theorem on the extension of an objective function // International Conference on Ordinal and Symbolic Data Analysis. — Bruxelles: Universite Libre de Bruxelles, 2000. — P. 9.

147. Chebotarev P., Shamis E. The forest metrics for graph vertices // Electronic Notes in Discrete Mathematics. — 2002. — Vol. 11. — Pp. 98-107.

148. Chebotarev P., Shamis E., Agaev R. A new metric for graph vertices and its properties // Abstracts of the 7th Conference of the International Federation of Classification Societies. — Namur: University of Namur, 2000. — P. 46.

149. Chebotarev P. Y. Aggregation of preferences by the generalized row sum method // Mathematical Social Sciences. — 1994. — Vol. 27. — Pp. 293-320.

150. Chebotarev P. Y. On ridge regression techniques as applied to the Scheffe-Noether paired comparison model //9 European Meeting of the Psychometric Society. — Leiden: Leiden University, 1995. P. 20.

151. Chebotarev P. Y. Out forests of a digraph and Markov chain probabilities //International Linear Algebra Conference. — Haifa: Institute of Advanced Studies in Mathematics, Technion, 2001,- Pp. 20-21.

152. Chebotarev P. Y., Agaev R. P. The matrix of maximum out forests and structural properties of systems modeled by digraphs // Modelling and Simulation of Systems, MOSIS-2000, 34th Spring Int. Conf. Vol. 1,- Ostrava: Univ. of Ostrava, 2000,-Pp. 101-106.

153. Chebotarev P. Y., Shamis E. Incomplete preferences and indirect scores: Working Paper 365.97. — Barcelona: Universität Autonoma de Barcelona and Institut d'Analisi Economica, CSIC, 1997.

154. Chebotarev P. Y., Shamis E. Characterizations of scoring methods for preference aggregation // Annals of Operations Research. — 1998. — Vol. 80. — Pp. 299-332.

155. Chebotarev P. Y., Shamis E. V. Matrix-forest theorems: arXiv paper math.co/0602575: arXiv, 1995. http://arxiv.org/abs/math.co/0602575.

156. Chebotarev P. Y., Shamis E. V. On optimization models for aggregating incomplete preferences // International Conference on Ordinal and Symbolic Data Analysis. — Paris: INRIA Rocquencourt, 1995.- Pp. 148-151.

157. Chebotarev P. Y., Shamis E. V. On the proximity measure for graph vertices provided by the inverse Laplacian characteristic matrix // 5th Conference of the International Linear Algebra Society. — Atlanta: Georgia State University, 1995. — Pp. 30-31.

158. Chebotarev P. Y., Shamis E. V. From incomplete preferences to ranking via optimization // The Third International Meeting of the Society for Social Choice and Welfare. — Maastricht: Univ. of Maastricht, 1996. — P. 5.

159. Chebotarev P. Y., Shamis E. V. A graph interpretation of the Moore-Penrose inverse of the Laplacian matrix // 7th Conference of the International Linear Algebra Society. — Madison: University of Wisconsin, 1998. — P. 31.

160. Chebotarev P. Y., Shamis E. V. On a duality between metrics and sigma-proximities // 7th Conference of the International Linear Algebra Society. — Madison: University of Wisconsin, 1998. P. 102.

161. Chebotarev P. Y., Shamis E. V. Graph proximity functions and linear aggregation of incomplete preferences // Труды международной конференции по проблемам управления. Т. 2. - Москва: Синтег, 1999. - С. 271-278.

162. Chebotarev P. Y., Shamis E. V. An approach to the visualization of hierarchical networks // Abstracts of the XX Sunbelt International Social Network Conference. — Vancouver: Simon Fraser University, 2000. — P. 78.

163. Chebotarev P. Y., Shamis E. V. A comparative study of closeness measures for the nodes of social networks I I Abstracts of the XX Sunbelt International Social Network Conference. — Vancouver: Simon Fraser Univ., 2000. — P. 84.

164. Chebotarev P. Y., Shamis E. V. The matrix-forest theorem and new structure measures for social networks // Abstracts of the XX Sunbelt International Social Network Conference. — Vancouver: Simon Fraser University, 2000. — P. 28.

165. Chen W. K. Applied Graph Theory, Graphs and Electrical Networks. — 2 edition.— Amsterdam: North-Holland, 1976.

166. Chipman J. S. Estimation and aggregation in econometrics: An application of the theory of generalized inverses // Generalized Inverses and Applications / Ed. by M. Nashed. — New York: Academic Press, 1976. — Pp. 549-769.

167. Chung F. R. K. Spectral Graph Theory. — Providence, RI: American Mathematical Society, 1994. — Vol. 17 of Colloquium Publications.

168. Coates C. Flow-graph solutions of linear algebraic equations // IRE Transactions on Circuit Theory. 1959. - Vol. 6. - Pp. 170-187.

169. Conner G., Grant C. An extension of Zermelo's model for ranking by paired comparisons // European Journal of Applied Mathematics. — 2000. — Vol. 11. — Pp. 225-247.

170. Cook W. D., Doyle J., Green R., Kress M. Ranking players in multiple tournaments // Computers and Operations Research. — 1996. — Vol. 23, no. 9. — Pp. 869-880.

171. Cook W. D., Kress M. Ordinal Information and Preference Structures: Decision Models and Applications. — Englewood Cliffs: Prentice-Hall, 1992.

172. Copeland A. H. A reasonable social welfare function // Seminar on Application of Mathematics to the Social Sciences. — Mimeo, Univ. of Michigan: Ann Arbor, 1951.

173. Cowden D. J. A method of evaluating contestants // American Statistician. — 1975. — Vol. 29, no. 2. Pp. 82-84.

174. Cristobal J. A. C., Roca P. F., Manteiga W. G. A class of linear regression parameter estimators constructed by nonparametric estimation // Annals of Statistics. — 1987. — Vol. 15, no. 2. Pp. 603-609.

175. Crowell R. H. Forests and determinants // Bulletin of the American Mathematical Society.- 1956. Vol. 62, no. 2. - Pp. 149-150.

176. Cucker F., Smale S. On the mathematics of emergence // Japanese Journal of Mathematics. 2007. - Vol. 2, no. 1. - Pp. 197-227.

177. Cvetkovic D. M., Doob M., Sachs H. Spectra of Graphs. — New York: Academic Press, 1980.

178. Daley D. J. Markov chains and a pecking order problem // Interactive Statistics / Ed. by D. M. Neil. Amsterdam: North-Holland, 1979,- Pp. 247-254.

179. Dalkey N. C., Helmer 0. An experimental application of the Delphi method to the use of experts // Management Science. — 1963. — Vol. 9. — Pp. 458-467.

180. Daniels H. E. Round-robin tournament scores //Biometrika. — 1969. — Vol. 56, no. 2. — Pp. 295-299.

181. David H. A. Ranking from unbalanced paired-comparison data //Brometrika. — 1987. — Vol. 74, no. 2. Pp. 432-436.

182. David H. A. The Method of Paired Comparisons. — Second edition. — London: Griffin, 1988.

183. David H. A., Andrews D. M. Nonparametric methods of ranking from paired comparisons // Probability Models and Statistical Analyses for Ranking Data / Ed. by M. A. Fligner, J. S. Verducci. New York: Springer, 1993. — Pp. 20-36.

184. DeGroot M. H. Reaching a consensus // Journal of American Statistical Association. — 1974. Vol. 69, no. 345. - Pp. 118-121.

185. Doyle P. G., Snell J. L. Random Walks and Electric Networks. — Washington D. C.: Mathematical Association of America, 1984. —

186. Available at URL http://arxiv.org/abs/math/0001057 (version 2000).

187. Duan H.-G., Wang Y., Fan Y.-Z. On Laplacian spectral radius of a digraph // College Mathematics. — 2007. — Vol. 23, no. 4. Pp. 24-28.

188. Erdôs P. L. A new bijection on rooted forests // Discrete Mathematics. — 1993. — Vol. 111.-Pp. 179-188.

189. Eriksson K. An easy bijective proof of the matrix-forest theorem // Australasian Journal of Combinatorics. 1995. - Vol. 12. - Pp. 301-303.

190. Fiedler M. Algebraic connectivity of graphs // Czechoslovak Mathematical Journal. — 1973. Vol. 23, no. 98. - Pp. 298-305.

191. Fiedler M. A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory // Czechoslovak Mathematical Journal. — 1975. — Vol. 25, no. 100,- Pp. 619-633.

192. Fiedler M. Moore-Penrose involutions in the classes of Laplacians and simplices //Linear and Multilinear Algebra. 1995. - Vol. 39. - Pp. 171-178.

193. Fiedler M., Sedlâcek J. O VF-basich orientovanych grafû // Casopis Pest. Mat.— 1958. Vol. 83. - Pp. 214-225.

194. Forman R. Determinants of Laplacians on graphs // Topology.— 1993.— Vol. 32, no. 1.- Pp. 35-46.

195. Fouss F., Yen L., Pirotte A., Saerens M. An experimental investigation of graph kernels on a collaborative recommendation task // Sixth International Conference on Data Mining (ICDM'06). 2006. - Pp. 863-868.

196. Freidlin M. L, Wentzell A. D. Random Perturbations of Dynamical Systems. — New York: Springer-Verlag, 1984.

197. Friedkin N. E. Theoretical foundations for centrality measures // American Journal on Sociology. 1991. - Vol. 96. - Pp. 1478-1504.

198. Galaskiewicz J., Wasserman S. Social networks analysis. Concepts, methodology, and directions for the 1990s // Sociological Methods & Research. — 1993. — Vol. 22, no. 1. — Pp. 3-22.

199. Garcia-Lapresta J. L., Marley A. A. J., Martinez-Panero M. Characterizing best-worst voting systems in the scoring context // The Annual Meeting of the European Public Choice Society, EPCS2006. Turku, Finland: 2006. - Pp. 1-15.

200. Garrison W. Connectivity of the interstate highway system // Papers and Proceedings of the Regional Science Association. — 1960. — Vol. 6. — Pp. 121-137.

201. Garrison W. L., Marble D. F. The structure of transportation networks: Tech. rep.— Washington D.C.: US Department of Commerce. Office of Technical Services, 1961.

202. Gibbons D. G. A simultaneons study of some ridge estimators // Journal of the American Statistical Association. — 1981. — Vol. 76, no. 373. — Pp. 131-139.

203. Goddard S. T. Ranking in tournaments and group decisionmaking // Management Science. 1983. - Vol. 29, no. 12. - Pp. 1384-1392.

204. Godsil C., Royle G. Algebraic Graph Theory. — Springer, 2001.

205. Goldfeld S. M., Quandt R. E. Nonlinear Methods in Econometrics. — Amsterdam: North-Holland, 1972.

206. Golender V. E., Drboglav V. V., Rosenblit A. B. Graph potentials method and its application for chemical information processing // Journal of Chemical Information and Computer Sciences. 1981. - Vol. 21. - Pp. 196-204.

207. Grone R. On the geometry and Laplacian of a. graph // Linear Algebra and its Applications. 1991. — Vol. 150. - Pp. 160-178.

208. Grone R., Merris R. The Laplacian spectrum of a graph II // SIAM Journal on Discrete Mathematics. 1994. - Vol. 7, no. 2. - Pp. 221-229.

209. Grone R., Merris R., Sunder V. S. The Laplacian spectrum of a graph // SIAM Journal on Matrix Analysis and Applications. — 1990. — Vol. 11, no. 2. — Pp. 218-238.

210. Gulliksen H. A least squares solution for paired comparisons with incomplete data // Psychometrika. 1956. - Vol. 21, no. 2. - Pp. 125-134.

211. Hage P., Harary F. Structural Models in Anthropology. — Cambridge: Cambridge Univ. Press, 1983.

212. Hall K. M. An r-dimensional quadratic placement algorithm // Management Science. — 1970.-Vol. 17, no. 3.- Pp. 219-229.

213. Harary F., Norman R. Z., Cartwright D. Structural Models: An Introduction to the Theory of Directed Graphs. — New York London - Sydney: John Wiley & Sons, 1965.

214. Harte R. E. Spectral projections // Irish Mathematical Society Newsletter. — 1984. — Vol. 11.-Pp. 10-15.

215. Hartwig R. E. More on the Souriau-Frame algorithm and the Drazin inverse // SIAM Journal on Applied Mathematics. — 1976. — Vol. 31. — Pp. 42-46.

216. Hartwig R. E., Levine J. Applications of the Drazin inverse to the Hill cryptographic system, Part, III // Cryptologia. 1981,- Vol. 5.- Pp. 67-77.

217. Hasse M. Uber die Behanglung graphentheoretischer Probleme unter Verwendung der Matrizenrechnung // Wissenschaftliche Zeitschrift Techniscen Universität Dresden. — 1961.-Vol. 10.-Pp. 1313-1316.

218. Hilliard-Lomas J. L., Litvine I. N. Poisson model for paired comparisons applied to soccer tournaments // South African Statistical Journal. — 1998. — Vol. 32, no. 2. — Pp. 185-199.

219. Ho N., van Dooren P. On the pseudo-inverse of the Laplacian of a bipartite graph //Applied Mathematics Letters. 2005. - Vol. 18, no. 8. — Pp. 917-922.

220. Horn R. A., Johnson C. R. Matrix Analysis. — Cambridge: Cambridge Univ. Press, 1986.

221. Horton F. E. Geographic Studies of Urban Transportation and Networks Analysis. — Evanston, 111: Dept. of Geography, Northwestern University, 1968.

222. Ibarra H., Andrews S. B. Power, social-influence, and sense making — effects of network centrality and proximity on employee perceptions // Administrative Science Quarterly. 1993. - Vol. 38. - Pp. 277-303.

223. Ito T. Link Analysis with Kernel Metrics: Ph.D. thesis /Dept. of Information Processing, Graduate School of Information Science, Nara Institute of Science and Technology. — 2007.

224. Jadbabaie A. On geographic routing without location information //Proc. IEEE Conf. on Decision and Control. — The Bahamas: 2004.

225. Jadbabaie A., Lin J., Morse A. S. Coordination of groups of mobile autonomous agents using nearest neighbor rules // IEEE Trans. Automatic Control. — 2003. — Vol. 48, no. 6.™ Pp. 988-1001.

226. Johns J., Mahadevan S. Constructing basis functions from directed graphs for value function approximation // Proceedings of the 24th International Conference on Machine Learning (ICML). 2007.

227. Jones B. D., Pittel B. G., Verducci J. S. Tree and forest weights and their application to nonuniform random graphs // The Annals of Applied Probability. — 1999.— Vol. 9, no. 1,- Pp. 197-215.

228. Kaiser H. F., Serlin R. C. Contributions to the method of paired comparisons // Applied Psychological Measurement. — 1978. — Vol. 2. — Pp. 421-430.

229. Kasteleyn P. W. Graph theory and crystal physics // Graph Theory and Theoretical Physics / Ed. by F. Harary. — London: Academic Press, 1967. — Pp. 43-110.

230. Katz L. A new status index derived from sociometric analysis // Psychometrika. — 1953. Vol. 18, no. 1. - Pp. 39-43.

231. Keener J. P. The Perron-Frobenius theorem and the ranking of football teams // SIAM Review. 1993. - Vol. 35, no. 1. - Pp. 80-93.

232. Kelma,ns A., Pak I., Postnikov A. Tree and forest volumes of graphs: Rutcor Research Report 47-99. — Piscataway: Rutgers Center for Operations Research, Rutgers University, December 1999.

233. Kelmans A. K., Chelnokov V. M. A certain polynomial of a graph and graphs with an extremal number of trees // Journal of Combinatorial Theory, Series B. — 1974. — Vol. 16. Pp. 197-214.

234. Kendall M. G. Further contributions to the theory of paired comparisons // Biometrics. — 1955. Vol. 11, no. 1. - Pp. 43-62.

235. Keviczky T., Borrelli F., Balas G. J. Distributed predictive control: Synthesis, stability and feasibility //Cooperative Control of Distributed Multi-Agent Systems /Ed. by J. S. Shamrna. John Wiley & Sons, Ltd., 2007. - Pp. 79-108.

236. Kim Y. M. M. On maximizing the second smallest eigenvalue of a state-dependent graph Laplacian //IEEE Trans. Automatic Control. 2006. - Vol. 51.- Pp. 116-120.

237. Kirchhoff G. Uber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird // Annalen Physik Chemie. — 1847. Vol. 72. - Pp. 497-508.

238. Kirchhoff G. On the solution of the equations obtained from the investigation of the linear distribution of Galvanic currents // IRE Transactions on Circuit Theory. — 1958.-Vol. 5. — Pp. 4-8.

239. Kirkland S. J., Molitierno J. J., Neumann M. The sharpness of a lower bound on the algebraic connectivity for maximal graphs // Linear and Multilinear Algebra. — 2001. — Vol. 48. Pp. 237-246.

240. Kirkland S. J., Neumann M. On group inverses of M-rnatrices with uniform diagonal entries // Linear Algebra and its Applications. — 1999. — Vol. 296, no. 1-3. — Pp. 153— 170.

241. Kirkland S. J., Neumann M., Shader B. L. Distances in weighted trees and group inverse of Laplacian matrices // SIAM Journal on Matrix Analysis and Applications. — 1997. — Vol. 18, no. 4,- Pp. 827-841.

242. Klein D. J. Graph geometry, graph metrics & Wiener // Communications in Mathematical and Computer Chemistry. — 1997. — Vol. 35. — Pp. 7-27.

243. Klein D. J., Randic M. Resistance distance //Journal of Mathematical Chemistry.— 1993.-Vol. 12,- Pp. 81-95.

244. Koliha J. J. Block diagonalization // Mathematica Bohemica.— 2001.— Vol. 126,— Pp. 237-246.

245. Koliha J. J., Straskraba I. Power bounded and exponentially bounded matrices // Applications of Mathematics. 1999. - Vol. 44, no. 4. - Pp. 289-308.

246. Kunz M. On topological and geometrical distance matrices // Journal of Mathematical Chemistry.- 1993, —Vol. 13.-Pp. 145-151.

247. L. M. Stability of continuous-time distributed consensus algorithms //Proc. IEEE Conf. Decision Control. — Paradise Island, Bahamas: 2004. — Pp. 3998-4003.

248. Laffond G., Laslier J. F., Breton M. L. Condorcet choice correspondences: A set-theoretical comparison // Mathematical Social Sciences. — 1995.— Vol. 30.— Pp. 2335.

249. Laffond G., Laslier J.-F., Lebreton M. The bipartisan set of a tournament game // Games and Economic Behavior. — 1993. — Vol. 15. — Pp. 182-201.

250. Laffont G., Laine J., Laslier J.-F. Composition-consistent tournament solutions and social choice functions // Social Choice and Welfare. — 1996. — Vol. 13. — Pp. 75-93.

251. Langville A. N., Meyer C. D. Google's PageRank and Beyond: The Science of Search Engine Rankings. — Princeton University Press, 2006.

252. Lannes A. Phase calibration on interferometric graphs // Journal of the Optical Society of America A. — 1999. - Vol. 16. - Pp. 443-454.

253. Laslier J. F. Tournament Solutions and Majority Voting. — Berlin: Springer, 1997.

254. Lawton J. R., Beard R. W., B. Y. A decentralized approach to formation maneuvers //IEEE Trans. Robotics and Automation. 2003. — Vol. 19, no. 6. - Pp. 933-941.

255. Leake R. J. A method for ranking teams: With an application to college football //Management Science in Sports /Ed. by R. E. Machol, S. P. Ladany, D. G. Morrison. — Amsterdam: North-Holland, 1976. Pp. 27-46.

256. Leeflang P. S., van Praag B. M. S. A procedure to estimate relative powers in binary contacts and application to Dutch football league results // Statistica Neerlandica. — 1971. Vol. 25. - Pp. 63-80.

257. Leighton T., Rivest R. L. Estimating a probability using finite memory //Foundations of Computation Theory. — Berlin / Heidelberg: Springer Berlin / Heidelberg, 1983. — Vol. 158/1983,- Pp. 255-269.

258. Leighton T., Rivest R. L. The Markov chain tree theorem: Computer Science Technical Report MIT/LCS/TM-249. — Cambridge, Mass.: Laboratory of Computer Science, MIT, 1983.

259. Leighton T., Rivest R. L. Estimating a probability using finite memory // IEEE Transactions on Information Theory. — 1986. — Vol. 32, no. 6. — Pp. 733-742.

260. Lenart C. A generalized distance in graphs and centered partitions // SI AM Journal on Discrete Mathematics. — 1998. — Vol. 11, no. 2. — Pp. 293-304.

261. Levin J., Nalebuff B. An introduction to vote-counting schemes // Journal of Economic Perspectives. — 1995. — Vol. 9, no. 1. — Pp. 3-26.

262. Lin Z., Francis B., Maggiore M. Necessary and sufficient graphical conditions for formation control of unicycles // IEEE Trans. Automatic Control. — 2005. — Vol. 50, no. l.-Pp. 121-127.

263. Lindley D. V., Smith A. F. M. Bayes estimetes for the linear model (with discussion) // Journal of the Royal Statistical Society (ser. B).— 1972. — Pp. 1-41.

264. Liu C. J., Chow Y. Enumeration of forests in a graph // Proceeding of the American Mathematical Society. 1981. - Vol. 83, no. 3. - Pp. 659-663.

265. Mackiewicz A., Ratajczak W. Towards a new definition of topological accessibility // Transpn. Res. B. - 1996. - Vol. 30, no. 1. - Pp. 47-79.

266. Mantrach A., Saerens M. Yen L. The sum-over-paths covariance: A novel covariance measure between nodes of a graph: Working paper. — Louvain School of Management, Université catholique de Louvain: 2008.

267. Markovski J., Trcka N. Lumping Markov chains with silent steps //Third International Conference on the Quantitative Evaluation of Systems (QEST'06).— Riverside, CA, USA: IEEE Computer Society, 2006. - Pp. 221-232.

268. Markovski J., Trcka N. Aggregation methods for Markov reward chains with fast and silent transitions: Tech. Rep. CS 07/08: Technische Universiteit Eindhoven, 2007.

269. Marsaglia G., Styan G. P. H. Equalities and inequalities for ranks of matrices // Linear and Multilinear Algebra. 1974. - Vol. 2. - Pp. 269-292.

270. Marshall J. A., Fung T., Broucke M. E., D'Eleuterio G. M. T., Francis B. A. Experiments in multirobot coordination // Robotics and, Autonomous Systems. — 2006. Vol. 54, no. 3. - Pp. 265-275.

271. Maxwell J. C. Electricity and Magnetism. — 3 edition. — London/New York: Oxford Univ. Press, 1892, — vol. 1, part. II, p. 409.

272. Maybee J. S., Olesky D. D., van den Driessche P., Wiener G. Matrices, digraphs, and determinants //SIAM Journal on Matrix Analysis and Applications. — 1989. — Vol. 10, no. 4,- Pp. 500-519.

273. Mendonça D., Raghavachari M. Comparing the efficacy of ranking methods for multiple round-robin tournaments // European Journal of Operational Research. — 2000. — Vol. 123. Pp. 593-605.

274. Merlin V. The axiomatic characterizations of majority voting and scoring rules // Mathématiques & Sciences Humaines Mathematics and Social Science. — 2003. — Vol. 41, no. 163.-Pp. 87-109.

275. Merris R. An edge version of the matrix-tree theorem and the Wiener index // Linear and Multilinear Algebra. 1989. — Vol. 25. - Pp. 291-296.

276. Merris R. Laplacian matrices of graphs: A survey // Linear Algebra and its Applications. 1994. - Vol. 197-198. - Pp. 143-176.

277. Merris R. A survey of graph Laplacians // Linear and Multilinear Algebra. — 1995.— Vol. 39.-Pp. 19-31.

278. Merris R. Doubly stochastic graph matrices // Publikacije Elektrotehnickog Fakulteta Univerzitet U Beogradu, Serija: Matematika.— 1997.— Vol. 8. — Pp. 64-71.

279. Merris R. Doubly stochastic graph matrices II // Linear and Multilinear Algebra. — 1998. Vol. 45. - Pp. 275-285.

280. Merris R. Laplacian graph eigenvectors // Linear Algebra and its Applications.— 1998. Vol. 278. - Pp. 221-236.

281. Meyer, Jr. C. D. Limits and the index of a square matrix // SIAM Journal on Applied Mathematics. — 1974. Vol. 26. - Pp. 469-478.

282. Meyer, Jr. C. D. The role of the group generalized inverse in the theory of finite Markov chains // SIAM Review. 1975. - Vol. 17, no. 3. - Pp. 443-464.

283. Meyer, Jr. C. D., Stadelmaier M. W. Singular M-matrices and inverse positivity // Linear Algebra and its Applications. — 1978. — Vol. 22. — Pp. 139-156.

284. Milman B., Gavrilova Y. Analysis of citation and cocitation in chemical-engineering // Scientometrics. 1993. - Vol. 27. - Pp. 53-74.

285. Mizruchi M. S. Social network analysis: Recent achievements and current controversies //Acta Sociologica. 1994. - Vol. 37. - Pp. 329-343.

286. Mizruchi M. S., Galaskiewicz J. Networks of interorganizational relations //Sociological Methods & Research. 1993. - Vol. 22, no. 1. - Pp. 46-70.

287. Mohar B. The Laplacian spectrum of graphs // Graph Theory, Combinatorics and Applications / Ed. by Y. Alavi, G. Chartrand, O. Oellermann, A. Schwenk. — New York: Wiley, 1991.- Pp. 871-898.

288. Mohar B. Laplace eigenvalues of graphs — a survey // Discrete Mathematics. — 1992. — Vol. 109. Pp. 171-183.

289. Mohar B. Some applications of laplace eigenvalues of graphs // Graph Symmetry: Algebraic Methods and Applications /Ed. by G. Hahn, G. Sabidussi. — Kluwer, 1997. — Pp. 225-275.

290. Monsuur H. Characterizations of the 3-cycle count and backward length of a tournament // European Journal of Operational Research. — 2005. — Vol. 164, no. 3. — Pp. 778-784.

291. Monsuur H. Stable and emergent network topologies: A structural approach // European Journal of Operational Research. — 2007. — Vol. 183, no. 1. — Pp. 432-441.

292. Monsuur H., Storcken T. Centrality orderings in social networks // Chapters in Game Theory, in honor of Stef Tijs / Ed. by P. Borm, H. J. M. Peters. — Dordrecht: Kluwer Academic Publishers, 2002,- Pp. 157-181.

293. Monsuur H., Storcken T. Centers in connected undirected graphs: An axiomatic approach // Operations Research. — 2004.— Vol. 52, no. 1. — Pp. 54-64.

294. Monsuur H., Storcken T. Centrality orderings in social networks // Chapters in Game Theory, in honor of Stef Tijs / Ed. by P. Borm, H. J. M. Peters. — Berlin, Heidelberg: Springer, 2004, — Vol. 31 of Theory and Decision Library C.— Pp. 157-181.

295. Moon J. W. Counting Labelled Trees. — Montreal: Canadian Mathematical Congress, 1970.

296. Moon J. W. Some determinant expansions and the matrix-tree theorem // Discrete Mathematics. 1994. - Vol. 124. - Pp. 163-171.

297. Moon J. W. On the adjoint of a matrix associated with trees // Linear and Multilinear Algebra. 1995. - Vol. 39, no. 1-2. - Pp. 191-194.

298. Moon J. W., Pullman N. J. Tournaments and handicaps // Information Processing 68 (Proc. IFIP Congress, Edinburgh, 1968).- Amsterdam: North-Holland, 1969.— Pp. 219-223. — vol. 1: Mathematics, Software.

299. Moon J. W., Pullman N. J. On generalized tournament matrices // SIAM Review.— 1970. Vol. 12. - Pp. 384-399.

300. Moreau L. Stability of multiagent systems with time-dependent communication links H IEEE Trans. Automatic Control- 2005,- Vol. 50, no. 2. Pp. 169-182.

301. Myerson R. B. Axiomatic derivation of scoring rules without the ordering assumption //Social Choice and Welfare.- 1995,- Vol. 12,- Pp. 59-74.

302. Myrvold W. Counting /c-component forests of a graph // Networks. — 1992. — Vol. 22. — Pp. 647-652.

303. Myrvold W., Wood K. L. B. Counting spanning out-trees in multidigraphs. — 2000.— Working paper of Department of Computer Science, University of Victoria, B.C., Canada, http://citeseer.ist.psu.edu/296109.html.

304. Navigli R., Lapata M. Graph connectivity measures for unsupervised word sense disambiguation // Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI-07). 2007. - Pp. 1683-1688.

305. Newman M. W. — The Laplacian Spectrum of Graphs. — Master's thesis, Department of Mathematics, University of Manitoba, Winnipeg, Canada, July 2000.

306. Noether G. E. Remarks about a paired comparison model // Psychometrika. — 1960. — Vol. 25. Pp. 357-367.

307. Nystuen J., Dacey M. A graph theory interpretation of nodal regions // Papers and Proceedings of the Regional Science Association. — 1961. — Vol. 7. — Pp. 29-42.

308. Olfati-Saber R., Fax J. A., Murray R. M. Consensus and cooperation in networked multi-agent systems // Proceedings of the IEEE. — 2007.— Vol. 95, no. 1.— Pp. 215— 233.

309. Olfati-Saber R., Murray R. M. Consensus problems in networks of agents with switching topology and time-delays // IEEE Transactions on Automatic Control. — 2004. — Vol. 49, no. 9. Pp. 1520-1533.

310. Pattison P. Algebraic Models for Social Networks. — Cambridge: Cambridge University Press, 1993.- Pp. xi-xi, 172-179, 300-301.

311. Pattison T. Graph representation, centrality and partitioning based on Cohen distance: Preprint. — Salisbury, Australia: Defence Sci. & Technol. Organisation, January 2000.

312. Pick G. Uber die Wurzeln der charakteristischen Gleichungen von Schwingungsproblemen // Zeitschrift fur angewandte Mathematik und Mechanik. — 1922. — Vol. 2. — Pp. 353-357.

313. Ponstein J. Self-avoiding paths and the adjacency matrix of a graph // SIAM Journal on Applied Mathematics. 1966. - Vol. 14. - Pp. 600-609.

314. Preciado V. M., Verghese G. C. Synchronization in generalized erdos-renyi networks of nonlinear oscillators // Proc. IEEE Conf. Decision Control, European Control Conf. — Seville, Spain: 2005. Pp. 4628-4633.

315. Propp J. G., Wilson D. B. How to get a perfectly random sample from a generic Markov chain and generate a random spanning tree of a directed graph // Journal of Algorithms. 1998. - Vol. 27. - Pp. 170-217.

316. Pucci A., Gori M., Maggini M. A random-walk based scoring algorithm applied to recommender engines // Advances in Web Mining and Web Usage Analysis, Lecture Notes in Computer Science, Vol. 4811.— Berlin / Heidelberg: Springer, 2007.— Pp. 127-146.

317. Ramanujacharyulu C. Analysis of preferential experiments //Psychometrika. — 1964. — Vol. 29.-Pp. 257-261.

318. Read M. J., Edwards J. S., Gear A. E. Group preference aggregation rules: The results of a comparative analysis with in situ data // Journal of the Operational Research Society. 2000. - Vol. 51, no. 5. - Pp. 557-563.

319. RegmiA., Sandoval R., Byrne R., Tanner H., Abdallah C. Experimental implementation of flocking algorithms in wheeled mobile robots // Proc. American Control Conf. — Portland, OR: 2005. Pp. 4917-4922.

320. Ren W., Atkins E. Second-order consensus protocols in multiple vehicle systems with local interactions // Proc. AIAA Guidance, Navigation, Control Conf. — San Francisco, CA: 2005. Paper AIAA-2005-6238.

321. Ren W., Beard R. W. Distributed consensus in multi-vehicle cooperative control.— London: Springer, 2008.

322. Ren W., Beard R. IV, Atkins E. M. Information consensus in multivehicle cooperative control //IEEE Control Systems Magazine. 2007. — Vol. 27, no. 2, — Pp. 71-82.

323. Ren W. Beard R. W. K. D. Multi-agent Kalman consensus with relative uncertainty //Proc. American Control Conf. — Portland, OR: 2005. Pp. 1865-1870.

324. Reynolds C. W. Flocks, herds, and schools: A distributed behavioral model // Computer Graphics. 1987. - Vol. 21, no. 4. - Pp. 25-34.

325. Rothblum U. G. A representation of the Drazin inverse and characterizations of the index // SIAM Journal on Applied Mathematics. 1976. — Vol. 31, no. 4. - Pp. 646-648.

326. Rothblum U. G. Expansions of sums of matrix powers // SIAM Review. — April 1981. — Vol. 23, no. 2. Pp. 143-164.

327. Roy S. Complexity Theoretic Aspects of Planar Restrictions and Obliviousness: Ph.D. thesis / The State University of New Jersey. — New Brunswick, Rutgers, New Jersey, 2006.

328. Saari D. G. Capturing the "will of the people" //Ethics. 2003. - Vol. 113. - Pp. 333349.

329. Sanni M., Bouyssou D. Essai d'axiomatization de la méthode généralisée de copeland // Proceedings of lere Rencontre Bénino-Brésilienne de Recherche Opérationnelle et Calculs Variationnels Ouidah (Bénin). — Porto-Novo, Bénin: 2007.

330. Scheffe H. An analysis of variance for paired comparisons // Journal of the American Statistical Association. — 1952. Vol. 47, no. 259. — Pp. 381-400.

331. Schmerling D. S., Prigarina T. A., Chebotarev P. Y. A review of some papers on paired comparisons in Russia // 9 European Meeting of the Psychometric Society. — Leiden: Leiden University, 1995.— P. 106.

332. Schwartz T. The Logic of Collective Choice. — New York: Columbia Univ. Press, 1986.

333. Schwenk A. J. The adjoint of the characteristic matrix of a graph // Journal of Combinatorics, Information & System Sciences.— 1991.— Vol. 16, no. 1.— Pp. 8792.

334. Seary A. J., Richards W. D. Partitioning networks by eigenvectors //Proc. Int. Conf. on Social Networks. — Vol. 1. — London: Univ. of Greenwich Press, 1996. — Pp. 47-58.

335. Shamis E. V. Graph-theoretic interpretation of the generalized row sum method // Mathematical Social Sciences. 1994. - Vol. 27. — Pp. 321-333.

336. Sharpe G. E., Sty an G. P. H. Circuit duality and the general network inverse // IEEE Transactions on Circuit Theory. — 1965. — Vol. 12. — Pp. 22-27.

337. Shier D. R. Network Reliability and Algebraic Structures. — New York: Oxford Univ. Press, 1991.

338. Shimbo M., Ito T., Matsumoto Y. Evaluation of kernel-based link analysis measures on research paper recommendation //Proceedings of the 7th ACM/IEEE joint conference on Digital libraries. ACM Press, N.Y., 2007.

339. Simeon B., Führer G., Rentrop P. The Drazin inverse in multibody system dynamics // Numerische Mathematik. 1993. — Vol. 64, no. 4. — Pp. 521-539.

340. Simon H. D., Sohn A., Biswas R. HARP: A dynamic spectral partitioner // Journal of Parallel and Distributed Computing. — 1998. — Vol. 50. — Pp. 88-103.

341. Slutzki G., Volij O. Ranking participants in generalized tournaments // International Journal of Game Theory. 2005. - Vol. 33, no. 2. - Pp. 255-270.

342. Slutzki G., Volij O. Scoring of web pages and tournaments-axiomatizations // Social Choice and Welfare. 2006. - Vol. 26, no. 1. - Pp. 75-92.

343. Smith J. H. Adjusting baseball stadings for stregth of teams played // American Statistician. 1956. - Vol. 10. - Pp. 23-24.

344. So W. Rank one perturbation and its application to the Laplacian spectrum of a graph // Linear and Multilinear Algebra. 1998. - Vol. 46. — Pp. 193-198.

345. Stephenson K., Zelen M. Rethinking centrality: Methods and examples // Social Networks. 1989. - Vol. 11. - Pp. 1-37.

346. Stern H. Are all linear paired comparison models empirically equivalent? //Mathematical Social Sciences. — 1992. Vol. 23. - Pp. 103-117.

347. Sty an G. P. H., Subak-Sharpe G. E. Inequalities and equalities associated with the Campbell-Youla generalized inverse of the indefinite admittance matrix of resistive networks // Linear Algebra and its Applications. — 1997. — Vol. 250. — Pp. 349-370.

348. Switalski Z. General transitivity conditions for fuzzy reciprocal preference matrices // Fuzzy Sets and Systems. 2003. — Vol. 137, no. 1. - Pp. 85-100.

349. Sylvester J. J. On the change of systems of independent variables // Quarterly Journal of Pure and Applied Mathematics. — 1857.— Vol. 1.— Pp. 42-56.— Reprinted in Collected Mathematical Papers, Cambridge, 2: 65-85 (1908).

350. Taaffe E. J., Gauthier H. L. Geography of Transportation. — Englewood Cliffs, New Jersey: Prentice Hall, 1973.

351. Takacs L. Enumeration of rooted trees and forests // Mathematical Scientist. — 1993. — Vol. 18. Pp. 1-10.

352. Tang J., Liang D., Wang N., Fan Y. Z. A Laplacian spectral method for stereo correspondence // Pattern Recognition Letters. — 2007. — Vol. 28, no. 12. — Pp. 1391— 1399.

353. Taylor M. Graph-theoretic approaches to the theory of social choice // Public Choice. — 1968. Vol. 4. - Pp. 35-47.

354. Teranishi Y. Laplacian spectra and invariants of graphs // Discrete Mathematics. — November 2002. Vol. 257, no. Issue 1. — Pp. 183 - 189.

355. Teranishi Y. The number of spanning forests of a graph // Discrete Mathematics. — 2005.-Vol. 290, no. 2-3. Pp. 259-267. http://dx.doi.Org/10.1016/j.disc.2004.10.014.

356. Thompson G. L. Lectures on Game Theory, Markov Chains and Related Topics, Monograph. SCR-11.— Albuquerque, New Mexico: Sandia Corporation, 1958.

357. Thompson M. On any given Sunday: Fair competitor orderings with maximum likelihood methods // Journal of the American Statistical Association. — 1975. — Vol. 70. — Pp. 536-541.

358. Tsitsiklis J. N., Athens M. Convergence and asymptotic agreement in distributed decision problems // IEEE Trans. Automatic Control. — 1984. — Vol. 29. — Pp. 690696.

359. Tutte W. T. The dissection of equilateral triangles into equilateral triangles // Proceedings of the Cambridge Philosophical Society. — 1948. — Vol. 44. — Pp. 463-482.

360. Veerman J. J. P., Lafferriere G., Caughman J., Williams A. Flocks and formations // Journal of Statistical Physics. 2005. - Vol. 121, no. 5-6. - Pp. 901-936.

361. Veerman J. J. P., Stosic B. D., Tangerman F. M. Automated traffic and the finite size resonance: Preprint. — Portland State University: May 2008. — Submitted to Journal of Statistical Physics.

362. Washburn A. Excess games // Naval Research Logistics.— 1989.— Vol. 36, no. 4.— Pp. 383-388.

363. Wasserraan S., Faust K. Social Network Analysis: Methods and Application. — Cambridge: Cambridge University Press, 2004.

364. Wei T. H. The algebraic foundations of ranking theory: Ph.D. thesis / Cambridge University. — 1952.

365. Wei Y. A characterization and representation of the Drazin inverse // SIAM Journal on Matrix Analysis and Applications. — 1996. — Vol. 17, no. 4. — Pp. 744-747.

366. Welsch H. Constructing meaningful sustainability indices // Applied Research in Environmental Economics / Ed. by C. Bôhringer, A. Lange. — Berlin, Heidelberg: Physica-Verlag HD, 2005. Vol. 31 of ZEW Economic Studies. - Pp. 7-22.

367. Wentzell A. D., Freidlin M. I. On small random perturbations of dynamical systems // Russian Mathematical Surveys. — 1970.— Vol. 25, no. 1.— Pp. 1-55.

368. Wilkinson J. H. Note on the practical significance of the Drazin inverse // Recent Applications of Generalized Inverses / Ed. by S. Campbell. — London: Pitman, 1982. — Pp. 82-99.

369. Wu C. W. Algebraic connectivity of directed graphs //Linear and Multilinear Algebra. — 2005. Vol. 53, no. 3. - Pp. 203-223.

370. Wu C. W. On Rayleigh-Ritz ratios of a generalized Laplacian matrix of directed graphs // Linear Algebra and its Applications. — 2005. — Vol. 402. — Pp. 207-227.

371. Wu C. W. Synchronization in Complex Networks of Nonlinear Dynamical Systems. — World Scientific, 2007.

372. Xiao L., Boyd S. Fast linear iterations for distributed averaging // Systems and Control Letters. 2004. - Vol. 53. - Pp. 65-78.

373. Yen L., Fouss F., Decaestecker C., Francq P., Saerens M. Link-based community detection with the sigmoid commute-time kernel: A comparative study: Working paper. — Louvain-la-Neuve, Belgium: Université catholique de Louvain, 2008.

Похожие работы

Информатика, вычислительная техника и управление
05.13.00