Введение к работе
Актуальность темы. В ряде задач управления, системного анализа и информатики (управление многоагентными системами, декомпозиция больших систем, кластеризация, агрегирование экспертных предпочтений, анализ сетей различной природы, теория баз данных, теория параллельных вычислений, химическая информатика, наукометрия и др.) графы, моделирующие соответствующие структуры, исследуют посредством анализа матриц, сопоставленных этим графам. Характеристики таких матриц — их ранги, спектры, собственные подпространства, собственные проекторы, миноры, коэффициенты характеристических многочленов, обратные и обобщенно-обратные матрицы и др. — доставляют важную информацию не только о соответствующих графах и сетях, но и о характере функционирования моделируемых систем. Посредством матричных вычислений информация такого рода может быть получена без использования трудоемких переборных алгоритмов. Анализом взаимосвязи свойств графов и соответствующих им матриц занимается алгебраическая теория графов, которая берет свое начало со знаменитой матричной теоремы о деревьях, полученной в середине XIX века в разных вариантах Кирхгофом, Сильвестром и Борхардтом.
Два основных направления в этой теории связаны с исследованием матрицы смежности графа и его лапласовской1 матрицы, по существу, отличающейся от матрицы смежности своей главной диагональю. Первое направление наиболее полезно при анализе маршрутно-циклической структуры графов, второе — при анализе их древесной {лесной) структуры. Первое направление развилось раньше, но к 90-м годам XX века всё больше исследователей стало заниматься лапласовской алгебраической теорией графов; уже в 60—70-е гг. существенные продвижения в ней были получены работавшим тогда в Институте проблем управления А.К. Кельмансом.
К настоящему времени лапласовская теория неориентированных
графов довольно хорошо разработана. Еще в 90-е годы вышли обзоры
1 Своим названием она обязана процессу дискретизации оператора Лапласа, приводящему к матрицам такого рода.
Р. Мерриса с соавторами и Б. Мохара, а также монография Ф.Р.К.Чанг, в которых были систематизированы более ранние результаты и представлены оригинальные результаты авторов этих работ.
Лапласовская теория ориентированных графов находится в начале своего развития. Укажем несколько областей системного анализа, управления и информатики, в которых ощущается сильная потребность в результатах этой теории.
1. Децентрализованное управление многоагентными системами.
Линейный оператор согласования характеристик2, входящий в большин
ство дифференциальных и дискретных моделей распределенного управ
ления, представляется лапласовской матрицей, соответствующей орграфу
коммуникаций между агентами. При этом свойства траекторий (сходи
мость, устойчивость и др.) полностью или частично определяются спектром
и собственными подпространствами этой лапласовской матрицы.
2. Химическая информатика. Задачи идентификации сложных орга
нических молекул и поиска связей между их структурными инвариантами и
физико-химическими свойствами веществ требуют анализа графов, пред
ставляющих молекулы, методами теории матриц. Лапласовские матрицы
используются в этой области уже более четверти века.
-
Кластер-анализ. Один из подходов к кластеризации на графах связан с нахождением спектров и собственных подпространств их лапла-совских матриц.
-
Построение алгебраических индексов графов. Во многих приложениях необходимо сопоставлять вершинам графов, парам и наборам вершин, ребрам, а также графам в целом значения числовых характеристик, выражающих те или иные структурные свойства. Приведем несколько примеров. В задачах анализа социальных сетей элементу сети ставят в соответствие значения центральности/периферийности, совокупной силы связи с другими элементами, баланса входящих и исходящих связей и др.; пару элементов характеризуют показателями силы, длины, направления связей между ними, индексами сходства их профилей связности и "ролей" в сети; дуги и
2 Этот оператор часто называют оператором достижения консенсуса.
пути характеризуют пропускной способностью по отношению к информации и управляющим воздействиям, критичностью разрыва по отношению к связности сети; сеть в целом оценивают степью связности, сплоченности, однородности, взаимности связей и т. д. Потребность в "оцифровке" возникает и при анализе/синтезе транспортных, компьютерных, организационных, семантических и других сетей, а также баз данных. Другой класс задач, требующий специальной оцифровки вершин графов, — агрегирование экспертных оценок, оценка силы участников турнира, если турнир — некруговой или данные неполные, или план парных сравнений не сбалансирован. Далее, следует упомянуть популярную в последнее время задачу ранжирования интернет-страниц, найденных поисковой машиной по пользовательскому запросу (PageRank problem): ранжирование производится с использованием орграфа ссылок страниц друг на друга. Наконец, задачи такого типа нужно решать при разработке алгоритмов работы распределенных компьютерных рекомендательных систем, где каждый пользователь, указав свои музыкальные, литературные, кинематографические и т. п. предпочтения, получает рекомендации — что еще послушать (почитать, посмотреть), сформированные на основе предпочтений пользователей, имеющих близкие вкусы.
Судя по результатам исследований последних лет, наиболее перспективные подходы к построению алгебраических индексов графов основаны на использовании лапласовских матриц.
5. Объект-объектная стратегия в анализе данных. В анализе данных довольно распространенным приемом стал переход от матриц "объект-признак" к матрицам "объект-объект" и "признак-признак" с последующим сопоставлением этим матрицам взвешенных графов и использованием методов алгебраической теории графов. При этом указанный переход часто производят посредством построения несимметричных взвешенных отношений (таких, как показатели доминирования), что приводит к ориентированным графам.
Лапласовские матрицы ориентированных графов и соотношения их свойств и свойств орграфов изучены пока недостаточно; работ по этой про-
блеме опубликовано немного. Отчасти это связано с тем, что из-за комплексности спектров лапласовских матриц орграфов соответствующие задачи оказываются достаточно сложными. Вместе с тем, как отмечено выше, потребность в таких исследованиях весьма велика.
Цель диссертации — частично восполнить этот пробел. Приложения, которым в работе уделяется наибольшее внимание, — построение структурных индексов графов и сетей, алгебраические методы агрегирования предпочтений и управление многоагентными системами.
Цель работы: разработать основы лапласовской теории ориентированных графов и ее применений. Достижение поставленной цели требует решения следующих основных задач:
Исследование лапласовских спектров орграфов;
Разработка методов классификации остовных3 лесов (ор)графов;
Разработка методов анализа (ор)графов с помощью классификации остовных лесов и с использованием матриц лесов;
Установление соотношений между матрицами лесов с одной стороны и лапласовской матрицей, ее собственным проектором, матрицами, обобщенно обратными к ней, и другими матрицами орграфа — с другой;
Разработка основ применения полученных результатов к построению структурных индексов графов, агрегированию экспертных предпочтений, управлению многоагентными системами.
Методы исследования. В диссертации используются методы теории графов, теории матриц, теории линейных статистических моделей, теории цепей Маркова, функционального анализа, теории управления, теории принятия решений и математической социологии.
Научная новизна. В работе разработаны основы лапласовской теории ориентированных графов и ее применений, в том числе:
1. Получена матричная теорема о лесах, обобщающая классическую матричную теорему о деревьях. На ее основе построено новое семейство
3 Остовпым называют подграф, множество вершин которого совпадает с множеством вершин графа; лес — граф без циклов.
структурных индексов графов. Введен класс лесных метрик графа и изучены его свойства; установлены связи между лесными метриками и резисторной метрикой графа.
-
Получены выражения для собственного проектора, компонент и псевдообратной по Дразину произвольной вырожденной матрицы через аннулирующий многочлен для любой степени матрицы, большей или равной ее индексу.
-
Изучена лесная структура графов и орграфов и алгебраические свойства матриц, представляющих остовные леса. Доказано, что матрица максимальных входящих лесов орграфа является собственным проектором его лапласовской матрицы. Следствие этого факта — матричная теорема о деревьях для цепей Маркова. Матрицы лесов проинтерпретированы в терминах вероятностей многошаговых переходов цепей Маркова. Получены явные выражения и топологические интерпретации для псевдообратных по Дразину и Муру-Пенроузу лапласовских матриц графов и орграфов.
-
Локализована область спектров лапласовских матриц орграфов. Полученные результаты анализа лапласовских спектров орграфов применены к исследованию моделей согласования характеристик в децентрализованном управлении многоагентными системами.
-
Аксиоматически построен и исследован новый метод агрегирования неполных предпочтений — обобщенный метод суммы очков, оценки которого выражаются с помощью матричной теоремы о лесах. Наиболее известные алгебраические методы агрегирования предпочтений проверены на выполнение аксиомы самосогласованной монотонности.
-
Разработан нормативный подход к анализу мер близости вершин графов и орграфов. Введено понятие функций S-близости и установлена их двойственность метрикам.
Практическая ценность работы. Результаты работы могут быть использованы (и в ряде случаев используются) в приложениях теории графов и сетей: при анализе социальных, семантических, транспортных и ком-
пьютерных сетей, в химической информатике, наукометрии, и особенно — в задачах управления многоагентными системами. В диссертации наиболее подробно разработаны приложения, связанные с построением структурных индексов графов и агрегированием экспертных предпочтений.
Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на научных семинарах в Институте проблем управления РАН, ЦЭМИ РАН, Институте вычислительной математики РАН, ИСЭП РАН, в университетах Барселоны, Кана, Ванкувера, Тампере, на общемосковском семинаре "Математические методы в экспертных оценках и анализ данных", на 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 работах, среди которых 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,23-27,35,36,39,40,42,48,49]. 18 работ опубликовано по смежной теме — кооперативному принятию решений, из них 4 — в журналах из списка ВАК РФ.
Объем и структура работы. Диссертация состоит из введения,
