Алгоритм комбинаторной оптимизации структуры логических связей децентрализованной системы
Предложена формальная математическая модель задачи оптимизации структуры логических связей децентрализованной системы. Показано, что оптимизация позволяет получить структуры, эффективные с точки зрения затрат на реализацию логических операций в заданном сетевом окружении. Рассмотрены типичные ограни...
Збережено в:
| Дата: | 2009 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем реєстрації інформації НАН України
2009
|
| Назва видання: | Реєстрація, зберігання і обробка даних |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/50380 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Алгоритм комбинаторной оптимизации структуры логических связей децентрализованной системы / А.С. Краевой, Ю.А. Тимошенко // Реєстрація, зберігання і оброб. даних. — 2009. — Т. 11, № 2. — С. 37-44. — Бібліогр.: 12 назв. — pос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-50380 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-503802013-10-17T03:06:46Z Алгоритм комбинаторной оптимизации структуры логических связей децентрализованной системы Краевой, А.С. Тимошенко, Ю.А. Математичні методи обробки даних Предложена формальная математическая модель задачи оптимизации структуры логических связей децентрализованной системы. Показано, что оптимизация позволяет получить структуры, эффективные с точки зрения затрат на реализацию логических операций в заданном сетевом окружении. Рассмотрены типичные ограничения, позволяющие гарантировать масштабируемость и высокие показатели устойчивости системы при неоднородной нагрузке. Проведена оценка сложности задачи и предложен генетический алгоритм нахождения приближенного решения. Запропоновано формальну математичну модель задачі оптимізації структури логічних зв’язків децентралізованої системи. Показано, що оптимізація дозволяє отримати структури, які будуть ефективними з точку зору витрат на реалізацію логічних операцій у заданому мережевому середовищі. Розглянуто типові обмеження, які дозволяють гарантувати можливість масштабування та забезпечення високих показників стабільності роботи системи при нерівномірному завантаженні. Проведено оцінку складності задачі та запропоновано генетичний алгоритм знаходження наближеного розв’язку. A formal mathematical model of a problem for optimization of logical interlink structure of decentralized system is proposed. It is shown that optimization yields structures which are effective in regard to resources spent on logical operations in a predetermined network environment. Typical restrictions allowing to assure scalability and high robustness of the system under inhomogeneous load are discussed. Es92 timation of problem complexity is performed, and genetics algorithm of finding on approximate solution is proposed. 2009 Article Алгоритм комбинаторной оптимизации структуры логических связей децентрализованной системы / А.С. Краевой, Ю.А. Тимошенко // Реєстрація, зберігання і оброб. даних. — 2009. — Т. 11, № 2. — С. 37-44. — Бібліогр.: 12 назв. — pос. 1560-9189 http://dspace.nbuv.gov.ua/handle/123456789/50380 004.722 ru Реєстрація, зберігання і обробка даних Інститут проблем реєстрації інформації НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Математичні методи обробки даних Математичні методи обробки даних |
| spellingShingle |
Математичні методи обробки даних Математичні методи обробки даних Краевой, А.С. Тимошенко, Ю.А. Алгоритм комбинаторной оптимизации структуры логических связей децентрализованной системы Реєстрація, зберігання і обробка даних |
| description |
Предложена формальная математическая модель задачи оптимизации структуры логических связей децентрализованной системы. Показано, что оптимизация позволяет получить структуры, эффективные с точки зрения затрат на реализацию логических операций в заданном сетевом окружении. Рассмотрены типичные ограничения, позволяющие гарантировать масштабируемость и высокие показатели устойчивости системы при неоднородной нагрузке. Проведена оценка сложности задачи и предложен генетический алгоритм нахождения приближенного решения. |
| format |
Article |
| author |
Краевой, А.С. Тимошенко, Ю.А. |
| author_facet |
Краевой, А.С. Тимошенко, Ю.А. |
| author_sort |
Краевой, А.С. |
| title |
Алгоритм комбинаторной оптимизации структуры логических связей децентрализованной системы |
| title_short |
Алгоритм комбинаторной оптимизации структуры логических связей децентрализованной системы |
| title_full |
Алгоритм комбинаторной оптимизации структуры логических связей децентрализованной системы |
| title_fullStr |
Алгоритм комбинаторной оптимизации структуры логических связей децентрализованной системы |
| title_full_unstemmed |
Алгоритм комбинаторной оптимизации структуры логических связей децентрализованной системы |
| title_sort |
алгоритм комбинаторной оптимизации структуры логических связей децентрализованной системы |
| publisher |
Інститут проблем реєстрації інформації НАН України |
| publishDate |
2009 |
| topic_facet |
Математичні методи обробки даних |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/50380 |
| citation_txt |
Алгоритм комбинаторной оптимизации структуры логических связей децентрализованной системы / А.С. Краевой, Ю.А. Тимошенко // Реєстрація, зберігання і оброб. даних. — 2009. — Т. 11, № 2. — С. 37-44. — Бібліогр.: 12 назв. — pос. |
| series |
Реєстрація, зберігання і обробка даних |
| work_keys_str_mv |
AT kraevojas algoritmkombinatornojoptimizaciistrukturylogičeskihsvâzejdecentralizovannojsistemy AT timošenkoûa algoritmkombinatornojoptimizaciistrukturylogičeskihsvâzejdecentralizovannojsistemy |
| first_indexed |
2025-07-04T12:03:45Z |
| last_indexed |
2025-07-04T12:03:45Z |
| _version_ |
1836717836136873984 |
| fulltext |
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2009, Т. 11, № 2 37
УДК 004.722
А. С. Краевой, Ю. А. Тимошенко
ННК «Институт прикладного системного анализа» НТУУ «КПИ»
просп. Победы, 37, 03056 Киев, Украина
e-mail: iasa@akraievoy.org
Алгоритм комбинаторной оптимизации структуры
логических связей децентрализованной системы
Предложена формальная математическая модель задачи оптимиза-
ции структуры логических связей децентрализованной системы. По-
казано, что оптимизация позволяет получить структуры, эффектив-
ные с точки зрения затрат на реализацию логических операций в за-
данном сетевом окружении. Рассмотрены типичные ограничения, по-
зволяющие гарантировать масштабируемость и высокие показатели
устойчивости системы при неоднородной нагрузке. Проведена оценка
сложности задачи и предложен генетический алгоритм нахождения
приближенного решения.
Ключевые слова: децентрализованные вычислительные системы,
оверлейная сеть, спектральная теория графов, квазиоднородные сети,
Лапласиан графа, генетический алгоритм.
Введение
Задачи повышения производительности вычислительных систем (ВС) при
решении различных задач обработки данных всегда относились к числу основных.
Ранее типичные решения по повышению быстродействия и организации вычис-
лений ВС были связаны с укрупнением и усложнением конструктивных компо-
нент сосредоточенных систем: повышением рабочих частот аппаратной логики,
расширением объемов обрабатываемых и хранимых данных, использованием уни-
кальных технологий микроэлектроники. В последнее время рекорды по произво-
дительности стали демонстрировать системы, объединяющие территориально и
организационно распределенные ВС. Актуальность приобрели организация вы-
числений и обработка данных в различных сетевых (grid-системы), одноранговых
(peer-to-peer) и «облачных» (cloud computing) технологиях.
Следовательно, горизонтальное масштабирование, заключающееся в объеди-
нении вычислительных компонент, управляемых различными операционными си-
стемами, является важным и актуальным подходом в обеспечении высокой произ-
водительности. С точки зрения структуры ВС, горизонтальное масштабирование
© А. С. Краевой, Ю. А. Тимошенко
А. С. Краевой, Ю. А. Тимошенко
38
подразумевает переход от централизованных архитектур к распределенным, и в
дальнейшем к децентрализованным. Необходимо отметить, что использование де-
централизованных архитектур обусловлено значительным усложнением (в виду
большого числа компонент) централизованного сопровождения полной информа-
ции о структуре системы [1].
В обобщенных архитектурах таких децентрализованных вычислительных
систем (ДВС) структура логических взаимодействий компонент весьма динамич-
на, слабо зависит от существующей сетевой среды и значительно влияет на устой-
чивость и производительность работы системы. Следовательно, такие логические
структуры часто представляют собой актуальный и самостоятельный предмет ис-
следования и оптимизации. В частности, известны стратегии детализации пере-
груженных участков логической структуры [2]. В [3] рассмотрен способ адапта-
ции логической структуры к зависимостям хранимых данных, в [4] предложена
обобщенная стратегия балансирования нагрузки в ДВС с динамической структу-
рой. Указанные исследования основываются на рассмотрении некоторой сети ло-
гических взаимодействий в ДВС [5] и предполагают разработку децентрализован-
ных стратегий ее оптимизации, что и составляет объект рассмотрения данной ра-
боты.
Квазиоднородные сетевые структуры
В дальнейшем для оптимизации структуры логических взаимодействий ДВС
будем использовать соответствующие представления на графах. При заданной
средней степени связности графов известен ряд методов построения, которые по-
зволяют ограничить сверху следующие величины:
— число блокировок при коммутации соединений между выделенными
множествами запрашивающих и обслуживающих вершин, при этом вершины из
указанных множеств соединяются произвольно [6];
— отношение размера максимальной из несвязных компонент к размеру се-
чения по ребрам (получаемых удалением сечения) [7];
— количество шагов, необходимых для доставки сообщений между произ-
вольно назначенными парами верши (на каждом шаге каждая вершина проводит
обмен только с одной инцидентной вершиной) [8].
Минимизация этих показателей на больших размерах сети статистически эк-
вивалентна однородности структуры сети: малому отклонению степеней связно-
сти, отсутствию коротких циклов, максимизации размера окрестности произволь-
ного подграфа сети. Сети с максимальными возможными свойствами однородно-
сти называются сетями-расширителями и используются для построения эффек-
тивных и устойчивых сетевых структур в телекоммуникациях, алгоритмах стати-
стического поиска и многих других областях вероятностных вычислений [9, 10].
Весьма интересен вопрос использования свойств квазиоднородности и сетей-
расширителей в контексте оптимизации структуры логических взаимодействий
децентрализованной системы. Отметим, что существующие исследования в ос-
новном сосредоточены на эффективных построениях неориентированных сетей с
взаимозаменяемыми узлами. В представленной работе рассматриваются некото-
рые модификации стандартных методов для генерации эффективных структур ло-
Алгоритм комбинаторной оптимизации
структуры логических связей децентрализованной системы
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2009, Т. 11, № 2 39
гических взаимодействий в ДВС.
Спектральные представления свойства квазиоднородности
Проверка большинства указанных выше свойств требует значительного (экс-
поненциального от размера сети) времени для их вычисления. Поэтому в работе
для этой цели предлагается использовать другое эквивалентное квазиоднородно-
сти свойство, а именно — величину второго значения в спектре собственных чи-
сел матрицы Лапласа (упорядоченном по возрастанию), которая соответствует
структуре связности сети [11]. Такая оценка не требует вычисления полного спек-
тра, вычисляется за полиномиальное время от размера сети и позволяет ограни-
чить сверху все перечисленные выше свойства.
В [11] приведен ряд основных свойств используемого упорядоченного спек-
тра, в частности:
— сумма всех собственных чисел равна количеству вершин сети;
— количество изолированных компонент графа равно кратности первого соб-
ственного числа, которое равно 0;
— сеть связна, если и только если второе собственное число положительно.
Исходя из указанных свойств, легко установить, что все элементы спектра на-
ходятся в пределах [0–2]. При увеличении второго собственного числа повышают-
ся численные оценки других свойств квазиоднородности сети [11]. Второе собст-
венное число позволяет оценить связность сети, обнаружить ее минимальное се-
чение и оценить многие свойства однородности.
Постановка задачи
В дальнейшем для произвольной пары узлов под запросами в сетевой среде
будем понимать вызовы удаленных процедур прикладного уровня, заданных через
среднее количество запросов на интервал времени. Под затратами понимаются те
или иные оценки сложности ретрансляции сообщений-вызовов. Наиболее очевид-
ной такой аппроксимацией является количество ретрансляций в сетевой среде, не-
обходимых для передачи сообщения по логическому каналу.
Упрощенно рассматриваемую задачу можно сформулировать следующим об-
разом: на некотором множестве узлов-компонент ДВС заданы оценки запросов и
затрат на ретрансляцию сообщений между ними. Заданы пороговые значения
плотности (средней степени связности), диаметра сети логических связей и второ-
го собственного значения матрицы Лапласа. Необходимо построить такую струк-
туру логических связей между узлами ДВС, которая позволяет минимизировать
суммарные затраты на передачу запросов.
На рисунке показан пример структуры физической сети, в котором шесть вы-
деленных узлов поддерживают некоторую ДВС. Выделенные ребра представляют
собой логические каналы, передача сообщений по которым реализуется через
коммутацию пакетов в физической сети. В данном случае логическая структура
представляет собой однородную 3-регулярную сеть с минимальной длиной цикла
равной 4. При этом отметим, что логическая структура в целом эффективно ис-
пользует физические каналы связи: передача по логическому каналу требует мало-
А. С. Краевой, Ю. А. Тимошенко
40
го количества коммутаций пакетов.
Пример физической среды и структуры логических связей
Возможным развитием подобной оптимизационной модели является задача
улучшения чувствительности к неравномерности нагрузок на логические связи
(получаемых имитацией алгоритма ретрансляции и распределения запросов). Та-
кая постановка с некоторыми уточнениями может быть полезна при проектирова-
нии структуры телекоммуникационных сетей.
Приведем формальное описание математической модели указанной задачи.
Обозначим через [[ ( , )]]f s t маршрут от вершины s до вершины t , которые гене-
рируется определенным алгоритмом f , а через || ( , ) ||f s t обозначим его длину, т.е.
количество использованных ребер. Перечислим входные данные оптимизацион-
ной задачи. В частности, обозначим через N множество логических узлов сети и
на основании данных о затратах на передачу в сетевой среде построим матрицу
длин физических маршрутов между N логическими узлами системы:
|| ( , ) ||std = r s t ; s,t N . (1)
Сеть запросов в ДВС представим в виде взвешенного ориентированного гра-
фа N,R , где R обозначает множество взвешенных связей между узлами множе-
ства N , а веса равны размерам соответствующих запросов ijR .
Выполним построение оверлейной сети L , в которой множество связей меж-
ду узлами отвечает следующим ограничениям.
1. Диаметр сети ограничивается логарифмом от количества узлов сети:
2|| || logq s,t < N ; s,t N , (2)
где — настраиваемый параметр, позволяющий учесть эффективность конкретно-
Алгоритм комбинаторной оптимизации
структуры логических связей децентрализованной системы
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2009, Т. 11, № 2 41
го алгоритма ретрансляции поискового запроса в оверлейной сети, который задает
предел длины маршрута поискового запроса от логического узла s к узлу t .
2. Средний размер маршрутной таблицы логических связей узла ограничива-
ется логарифмом от количества логических узлов сети:
2logL < N N , (3)
где 1 — настраиваемый параметр, который позволяет учесть эффективность
конкретного протокола поддержки структуры оверлейной сети. Такое условие
обеспечивает разреженность оверлейной сети L , необходимую для масштаби-
руемости ДВС с точки зрения затрат на хранение данных о структуре сети.
3. Второй элемент спектра
N,L
λ графа оверлейной сети L (степень однород-
ности структуры оверлейной сети) удовлетворяет условию:
N,L
λ , (4)
где 0 1< — настраиваемый параметр, определяющий степень однородности
сети.
Введем следующую метрику, отображающую глобальную эффективность
ретрансляции запросов, взвешенную относительно объема запросов в оверлейной
сети:
1,
[[ ( , )]]
R
i
i i
s,t: s,t R q q
q q t
t
s
sE =
d
. (5)
Ставится задача по максимизации данного критерия при заданных ограничениях
(2)–(4). Нетрудно видеть, что данная целевая функция возрастает при уменьшении
общих затрат на выполнение запроса, которые являются суммой затрат на каждую
ретрансляцию запроса в логической структуре ДВС.
Анализ алгоритмов ретрансляции запросов
Известные алгоритмы построения оптимальных маршрутов с низкими пока-
зателями насыщения, в связи с отсутствием полной информации о структуре сети
в реальной ДВС, не применимы для имитации маршрута ретрансляций поисково-
го запроса в логической структуре. Поэтому самые эффективные маршруты
ретрансляции в связи с децентрализованной реализацией этого механизма будут
использоваться достаточно редко.
В этом случае, целевая функция (5) является оценкой сверху для эффективно-
сти механизмов поиска в реальной системе. В дальнейшем, можно предположить
использование неких приближений поисковых механизмов, связанных с протоко-
лом поиска в конкретной моделируемой ДВС. Также вероятно использование не-
А. С. Краевой, Ю. А. Тимошенко
42
которых вероятностных алгоритмов, усредняющих оценки затрат для некоторого
множества маршрутов. Это позволит учесть динамичность структуры сети, балан-
сирование нагрузки на логические каналы, но, в целом, может снизить чувстви-
тельность целевой функции (5) к возможным изменениям структуры.
Анализ класса сложности задачи
Существуют полиномиальные детерминированные алгоритмы построения
семейств сетей-расширителей [11]. Такие методы применимы для сетей, в которых
вершины взаимозаменяемы, что не выполняется для рассмотренной постановки.
Потому задачу можно свести к генерации сети-расширителя, которая заведомо удо-
влетворяет ограничениям (2)–(4), и поиску отображения множества вершин такой
сети на множество логических узлов, максимизирующего целевую функцию (5).
Частичное задание отображения вершин сети-расширителя на логические уз-
лы не позволяет значительно сузить границы значений целевой функции (5). Дан-
ную задачу нельзя разбить на слабо связанные подзадачи из-за гарантированно
больших минимальных сечений сети-расширителя. Потому существование высо-
коэффективного эвристического алгоритма представляется маловероятным.
Отметим, что мощность множества вариантов выбора увеличивается экспо-
ненциально с ростом количества логических узлов сети. Следовательно, данная
задача относится к классу задач комбинаторной оптимизации, для решения кото-
рых целесообразно использовать методы поиска решений, приближенных к опти-
мальным.
Описание метода решения
Для начального построения сети, близкой к однородной, можно использовать
2log N эйлеровых циклов длины N , с минимальным весом ребер, непересе-
кающихся по ребрам. Такие циклы можно строить с помощью эвристических ре-
шений задачи коммивояжера с запретами на повторное использование ребер из
уже построенных циклов. Это гарантирует высокую степень однородности полу-
ченной структуры и некоторое начальное приближение к оптимуму целевой
функции (5). Будем полагать его в качестве начальной особи следующего генети-
ческого алгоритма с описанными ниже основными операциями, изменяющими
популяцию (в качестве хромосомы предлагается рассматривать упорядоченную
последовательность из
2
N бит, задающих наличие логических связей между уз-
лами ДВС):
— операция, увеличивающая второе собственное число логической сети —
Мутация-1;
— операция, направленная на увеличение значения целевой функции — Му-
тация-2;
— операция выбора одного из решений сечения сети по вершинам, связанных
с максимальным сечением по ребрам и замене этой части структурой этой же час-
ти из другого решения — т.н. скрещивание;
— операция исключения решения с наименьшими значениями целевой функ-
Алгоритм комбинаторной оптимизации
структуры логических связей децентрализованной системы
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2009, Т. 11, № 2 43
ции в популяции после того, как на их основании проведено определенное коли-
чество улучшающих мутаций — Отбор.
Мутация-1. На основании собственного вектора для второго собственного
значения определяется минимальное сечение логической структуры по ребрам.
Далее, для увеличения второго собственного числа осуществляется перемещение
существующего ребра в минимальное сечение.
Мутация-2. Проводится операция перемещения ребра с вероятностью про-
порциональной отношению суммы объемов запросов узлов, соединяемых ребром
до и после переноса.
Скрещивание. Данная операция заключается в замене одной части структу-
ры сечения сети по вершинам, связанным с максимальным сечением по ребрам, на
эту же часть структуры из другого решения. Максимальное сечение выбирается в
качестве участка для интеграции решений, чтобы обеспечить незначительное уве-
личение диаметра сети.
Отбор. Данная операция осуществляет исключение решений с наименьшими
в популяции значениями целевой функции после того, как на их основании прове-
дено определенное количество улучшающих мутаций.
Отметим важность использования условия (3) для обеспечения разреженно-
сти матрицы Лапласа, что позволяет применять итеративные алгоритмы для на-
хождения заданного количества первых собственных чисел матрицы Лапласа [12].
Улучшение скорости сходимости генетического алгоритма обеспечивается веро-
ятностной направленностью операций мутации и малым количеством мутаций,
неприменимых по ограничениям (2)–(4). Следовательно, алгоритм может приме-
няться для сетей большого размера, содержащих сотни узлов.
Выводы
В статье представлен генетический алгоритм структурной оптимизации логи-
ческой структуры ДВС, увеличивающий эффективность и устойчивость такой
структуры. Алгоритм использует свойства спектра логической структуры для
обеспечения направленности случайного поиска и сохранения однородности по-
лучаемой структуры. На основании алгоритма решения данной задачи может быть
создана децентрализованная стратегия, обеспечивающая сходимость структуры
ДВС к оптимальной в реальном времени.
Следующим этапом исследований является разработка и сравнение несколь-
ких децентрализованных стратегий, использующих различные локальные аналоги
свойств однородности сети. Такие стратегии по аналогии с рассмотренным алго-
ритмом будут направлены на повышение эффективности ретрансляции сообще-
ний по логическим каналам ДВС при сохранении свойств однородности логиче-
ской структуры.
1. Тимошенко Ю. Огляд і класифікація програмно-апаратних засобів побудови розподілених
обчислювальних систем / Ю. Тимошенко, А. Краєвий // Наукові вісті НТУУ «КПІ». — 2006. — №
2 (46) — С. 37–49.
А. С. Краевой, Ю. А. Тимошенко
44
2. Aberer K. Multifaceted Simultaneous Load Balancing in DHT-based P2P Systems: A New
Game with Old Balls and Bins / K. Aberer, A. Datta, M. Hauswirth // Self-* Properties in Complex In-
formation Systems. — Amer. Math. Soc, 2005.
3. Schlosser M. HyperCuP — Hypercubes, Ontologies and Efficient Search on P2P Networks / M.
Schlosser, M. Sintek, S. Decker, W. Nejdl // LNCS. — 2002. — Vol. 2530. –– Р. 112–124.
4. Load Balancing in Dynamic Structured Peer-to-Peer Systems / [S. Surana, B. Godfrey, K.
Lakshminarayanan et al] // Perform. Eval. — 2006. — Vol. 63. — Р. 217–240.
5. Краевой А., Тимошенко Ю. Виртуальные топологии симметричных распределенных вы-
числительных систем // Труды III международной конференции «Параллельные вычисления и за-
дачи управления» РАСО’2006 памяти И.В. Прангишвили. — М.: Институт проблем управления
им. В.А.Трапезникова РАН, 2006.
6. Bassalygo L.A. Asymptotically Optimal Switching Circuits / L.A. Bassalygo // Problems Inform.
Transmission. — 1981. — Vol. 17. –– P. 206–211.
7. Chung F.R.K. Graham R.L. Maximum Сuts and Quasi-Random Graphs // Random Graphs. –
Frieze A. Luczak T. eds. — New York: John Wiley and Sons, 1992. — Р. 23–34.
8. Alon N. Routing Permutations on Graphs via Matchings / N. Alon, F.R.K. Chung, R.L. Graham
// SI AM J. Disc. Math. — 1994. — Vol. 7. –– Р. 513–530.
9. Краевой А. Подходы в оценке устойчивости сетевых структур // Тезисы 26-й научн.-техн.
конф. «Моделювання». — Луганск, 2007. — С. 40–42.
10. Chung F.R.K. On Concentrators, Superconcentrators, Generalizes, and Nonblocking Networks //
Bell Systems Tech. J. — 1978. — Vol. 58. –– Р. 1765–1777.
11. Chung F. Spectral Graph Theory / F. Chung // Providence: American Mathematical Society,
1994.
12. Sleijpen G.L.G. der H.A.V. A Jacobi–Davidson Iteration Method for Linear Eigenvalue Prob-
lems // SIAM Rev. — 2000. — Vol. 42. — P. 267–293.
Поступила в редакцию 15.06.2009
|