ЧИСЛЕННОЕ МОДЕЛИРОВАНИЕ ПЕРЕХОДНЫХ ПРОЦЕССОВ В ЭВОЛЮЦИОНИРУЮЩИХ ПО ГЕНЕТИЧЕСКИМ АЛГОРИТМАМ СЕТЯХ
ЧИСЛЕННОЕ МОДЕЛИРОВАНИЕ ПЕРЕХОДНЫХ ПРОЦЕССОВ …
УДК 519.179.2
ЧИСЛЕННОЕ МОДЕЛИРОВАНИЕ ПЕРЕХОДНЫХ ПРОЦЕССОВ В ЭВОЛЮЦИОНИРУЮЩИХ ПО ГЕНЕТИЧЕСКИМ АЛГОРИТМАМ СЕТЯХ
А.А. Короновский, А.А. Косицын, О.И. Москаленко, А.Е. Храмов
Представлены результаты исследования кооперативных явлений в сетях со сложной топологией. Для моделирования процессов эволюции разработан генетический алгоритм эволюции сложных сетей. Проанализированы переходные процессы, наблюдающиеся в ходе эволюции. Обнаружены определенные закономерности при оптимизации сети. Ключевые слова: сети со сложной топологией, генетический алгоритм, центральность, переходной процесс, перемежаемость.
Введение
Исследование кооперативных явлений в сетях со сложной топологией представляется в настоящее время одной из актуальных задач нелинейной динамики [1]. Интерес к подобным системам обусловлен, прежде всего, наличием большого числа объектов в природе и технике, которые можно описать с помощью сетевых моделей. Энергетические сети, железнодорожные сети, сети авиаперевозок, метро, всемирная сеть Интернет, социальные сети, сети соавторства, компьютерные сети – вот далеко не полный список объектов, к которым может быть применено понятие сети [2]. Понятно, что ни одна из вышеперечисленных сетей не является постоянной, характеристики каждой из них меняются с течением времени.
Поэтому в последнее время значительное внимание исследователей привлечено к изучению эволюционных процессов в сетях [3]. Эта проблема касается, прежде всего, биологических и экологических объектов, для которых понятие эволюции кажется очевидным. Большая часть систем в биологии и экологии эволюционирует по генетическим алгоритмам. Идея генетических алгоритмов состоит в организации эволюционного процесса, конечной целью которого является получение оптимального результата. Длительность эволюционных процессов является достаточно большой, а достижение оптимального результата зависит от ряда критериев. Понятно, что предсказание результата эволюции является нетривиальной задачей, поэтому возможна постановка задачи оптимизации тех или иных характеристик сети в процессе эволюции. На решение этой задачи как раз и направлена настоящая работа. В рамках исследования коопера-
40 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 1(65)
А.А. Короновский, А.А. Косицын, О.И. Москаленко, А.Е. Храмов
тивных явлений в эволюционирующих сетях разработан генетический алгоритм эволюции сложных сетей и исследованы переходные процессы при эволюции.
Понятие сети и ее основные характеристики
Перед тем, как перейти непосредственно к описанию самого генетического алгоритма, введем в рассмотрение понятия сети и ее основных характеристик.
Традиционно под сетью понимается совокупность объектов, объединенных при помощи связей, причем каждый объект должен обладать определенными свойствами и содержать конкретную информацию [4]. Математическим образом сети является граф. Он не содержит никакой информации об элементах сети, а просто передает структуру ее связей. Считается, что любая система, предполагающая наличие дискретных состояний или наличие узлов и переходов между ними, может быть описана графом. Соединения между узлами графа называются ребрами.
Для математического описания графов обычно используют следующие понятия [5]. Во-первых, граф может быть рассмотрен как структура G = (V, E), где V – множество вершин, E – множество ребер, причем ребра являются элементами вида e = (vi, vj), где vi, vj принадлежат множеству вершин. Во-вторых, для его описания достаточно часто используется матрица смежности, представляющая собой квадратную матрицу, все элементы которой, лежащие на главной диагонали, равны нулю. В зависимости от того, является граф ориентированным или нет, матрица смежности будет несимметричной или симметричной. В рамках настоящей работы мы остановимся на рассмотрении неориентированных графов. В этом случае элемент матрицы смежности S sij = 1, если существует ребро из i-ой в j-ую вершину, и sij = 0, если такого ребра нет.
Следует отметить, что приведенные выше понятия введены для так называемых невзвешенных графов (все ребра равноправны). Существует также понятие взвешенного графа [5], каждому ребру которого соответствует некий параметр – вес. Однако в данной работе взвешенные графы рассмотрены не будут.
Каждый узел сети характеризуется некоторой величиной ki, называемой степенью узла (node degree) [2]. Степень узла – это количество связей у данного узла или, с математической точки зрения, сумма элементов в i-той строке (столбце) матрицы смежности S. Понятно, что не все узлы сети имеют одинаковое число ребер, поэтому для характеристики сети целесообразно ввести в рассмотрение совокупность степеней узлов или их распределение [2]. Для случайного графа такое распределение описывается распределением Пуассона. В то же время большинство реальных сетей подчиняется степенному распределению степеней узлов (scale-free networks, или свободно масштабируемые сети), известны также сети с экспоненциальным распределением степеней узлов [1, 2].
Далее в работе мы будем рассматривать случайные графы, предполагая, что именно с таких объектов начинается процесс эволюции. Предполагается интересным исследовать вопрос о трансформации топологии сети с течением времени в случае оптимизации ее по различным характеристикам: к каким качественным и количественным изменениям приведет этот процесс, в частности, как трансформируется распределение степеней узлов в данном случае?
Генетический алгоритм эволюции сложных сетей и его численная реализация
Для исследования эволюционных процессов в сложных сетях при помощи среды разработки GNU/Linux с использованием языков программирования C, C++ и GNUутилиты make был разработан программный продукт, реализующий генетический алго-
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 1(65)
41
ЧИСЛЕННОЕ МОДЕЛИРОВАНИЕ ПЕРЕХОДНЫХ ПРОЦЕССОВ …
ритм эволюции сложных сетей, суть которого заключается в следующем. Имеется популяция, состоящая из M = 10 отдельных сетей (графов), каждая из которых состоит из N элементов. Изначально генерируются M/2 случайных графов, состоящих из N узлов и связей K = Np, где p = 0,05 – заданная вероятность наличия связей в случайном графе. Для каждого из них считается характеристика , по которой будет проводиться оптимизация.
Из построенных таким образом сетей случайным образом выбирается одна, для которой будет моделироваться дальнейший процесс эволюции. Предполагается, что на каждом шаге эволюции один из M/2 случайных графов начинает мутировать. При этом появляется M/2 дочерних графов, структура межэлементных связей которых отличается от исходной на заданную вероятность p. Для полученных сетей также считается оптимизируемая характеристика . Из полученных таким образом M графов (M/2 исходных и M/2 дочерних) выбираются M/2 графов с лучшими значениями характеристики . Остальные M/2 графов отбрасываются. Один из оставшихся графов, выбираемых случайным образом, снова начинает мутировать. Процесс продолжается до тех пор, пока не будет получена сеть с оптимальным значением характеристики .
В роли оптимизируемой характеристики может выступать одна из таких величин, как центральность, уязвимость, кластеризация, синхронизуемость, кратчайшее расстояние между элементами сети и др. [5]. В рамках настоящей работы мы остановимся на процессе оптимизации сети по характеристике, называемой центральностью (в англоязычной литературе – eigenvector centrality). Эта величина характеризует важность элемента в структуре сети и используется, например, при осуществлении web-поиска в системе Google для упорядочивания информации [6]. C математической точки зрения центральность – это дисперсия распределения координат собственного вектора x матрицы смежности S, соответствующего максимальному значению собственного числа
Для расчета собственных чисел матрицы смежности S использовался QRалгоритм с неявным сдвигом (перенесен из библиотеки LAPACK с внесением изменений, касающихся специфики задачи) [7]. Принципиальными достоинствами этого метода являются возможности работы с матрицами произвольного вида, поиска не только действительных, но и комплексных собственных чисел, а также поиска собственных векторов. В то же время этот метод характеризуется рядом существенных недостатков, одним из которых является относительно низкая скорость расчета. Более того, возможно возникновение и других трудностей реализации алгоритма. В частности, процесс эволюции сети является достаточно длительным, причем величина переходного процесса, как было показано нами, растет с увеличением количества элементов сети согласно экспоненциальному закону (эти результаты будут описаны в следующем разделе). Процесс эволюции является последовательным, а, следовательно, не может быть распараллелен. Вычисление оптимизируемой характеристики, в частности, дисперсии распределения координат собственного вектора, соответствующего максимальному собственному числу , требует также значительных временных затрат, особенно для сетей больших размеров. В то же время вычисление оптимизируемой характеристики осуществляется M/2=5 раз на каждом шаге эволюции, что говорит о возможности распараллеливания процесса вычислений.
В настоящее время удалось оптимизировать процесс эволюции сложных сетей. В частности, применение средств оптимизации, имеющихся в компиляторах gcc, g++, icc, icpc вплоть до третьего уровня, позволило увеличить скорость расчета примерно в 4 раза. Кроме того, скорость расчета увеличилась еще на 25% за счет использования процедуры векторизации (в силу свойств компиляторов icc, icpc).
42 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 1(65)
А.А. Короновский, А.А. Косицын, О.И. Москаленко, А.Е. Храмов
Основные результаты Коротко остановимся на основных результатах, полученных при оптимизации алгоритма эволюции сложных сетей, касающихся, прежде всего, исследования переходных процессов, имеющих место в процессе эволюции. При проведении расчетов анализировались сети, состоящие из различного числа элементов N[50; 1000]. На рис. 1, а, представлены зависимости оптимизируемой характеристики (центральности ) от шага эволюции для сетей различных размеров.
0,8
0,6
0,4
0,2
аб Рис. 1. Переходные процессы при эволюции сложных сетей: а – зависимость оптимизируемой характеристики от шага эволюции k для сетей из 100, 150, 200, 325, 500, 1000 элементов (в логарифмическом масштабе по оси абсцисс); б – зависимость времени выхода оптимизируемой характеристики на уровень насыщения от размера
сети N (точки) и ее аппроксимация Ttrans = 16,37e0.045N (сплошная линия)
Нетрудно заметить, что в процессе эволюции сети оптимизируемая характеристика меняется по логарифмическому закону, причем по завершении переходного процесса эта характеристика выходит на один и тот же уровень, независимо от размера сети. Указанная особенность позволяет определить длительность переходного процесса даже для тех сетей, процесс эволюции которых оказывается еще не завершенным. Зависимость длительности переходного процесса от размера сети представлена на рис. 1, б. Из рисунка видно, что величина переходного процесса растет с увеличением количества элементов сети по экспоненте (соответствующая аппроксимация показана сплошной линией).
Следует отметить, что в процессе эволюции сети оптимизируемая характеристика не меняется постоянно, а может оставаться неизменной в течение достаточно длительного промежутка времени. Интересным представляется вопрос о характере распределения длительностей участков, на которых оптимизируемая характеристика не меняется, в частности, прослеживается ли какая-либо закономерность в указанных распределениях или они оказываются различными для сетей разных размеров. На рис. 2, а, представлены распределения длительностей таких участков для сетей из N = 100, N = 500 и N = 1000 элементов и соответствующие аппроксимации. Видно, что независимо от размера сети подобные распределения подчиняются степенному закону с показателем степени «минус 1,5», характерным для перемежаемости типа «on–off» [8]. В этом случае
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 1(65)
43
ЧИСЛЕННОЕ МОДЕЛИРОВАНИЕ ПЕРЕХОДНЫХ ПРОЦЕССОВ …
можно говорить, что обнаружен аналог перемежающегося поведения в процессе эволюции сложных сетей.
аб Рис. 2.. Распределения длительностей участков, на которых оптимизируемая характеристика не меняется, для сетей из 100 (▲), 500 () и 1000 () элементов и соответствующие аппроксимации N(l) ~ l-1.5 (а).. Трансформация распределения степеней узлов
сети из 1000 элементов в процессе эволюции: 0 шаг (), 59814 шаг () и 74163 шаг (▲). Сплошной линией показана аппроксимация соответствующего распределения
распределением Пуассона (б)
Не менее важным является вопрос о трансформации топологии сети в процессе эволюции. На рис. 2, б, представлены распределения степеней узлов сети из 1000 элементов на 0 (), 59814 () и 74163 (▲) шагах эволюции. Эволюционный процесс, как отмечалось выше, начался со случайного графа, распределение степеней узлов которого подчиняется распределению Пуассона (показано на рисунке сплошной линией справа). Нетрудно заметить, что в процессе эволюции топология сети заметно трансформируется: из случайного графа получается сеть, характеристики которой сильно отличаются от характеристик случайной сети.
Заключение
В настоящей работе проведено исследование кооперативных явлений в сложных сетях, эволюционирующих по генетическому алгоритму. С этой целью разработан алгоритм эволюции сложных сетей и проведена его оптимизация, в результате которой удалось увеличить скорость расчета примерно в 5 раз. При помощи разработанного алгоритма исследованы также переходные процессы в ходе эволюции сложных сетей (в роли критерия отбора выступает оптимизация центральности сети). В то же время ряд результатов удалось получить только для сетей относительно малых размеров, что говорит о необходимости дальнейшей оптимизации алгоритма.
В ходе проведения исследований установлено, что вычисление оптимизируемой характеристики требует больших вычислительных мощностей и занимает много времени. Однако подобные вычисления осуществляются несколько раз на каждом шаге эволюции, что говорит о возможности распараллеливания вычислений.
Планируется проведение дальнейшей оптимизации алгоритма. Одним из наиболее существенных моментов в данном случае является замена алгоритма расчета собственных чисел и соответствующих им собственных векторов. Следует отметить, что ис-
44 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 1(65)
А.А. Короновский, А.А. Косицын, О.И. Москаленко, А.Е. Храмов
пользуемый QR-алгоритм не принимает во внимание симметрию матрицы, что значительно замедляет расчет оптимизируемой характеристики (особенно для матриц достаточно больших размеров). Поэтому предполагается апробировать и использовать в дальнейшем один из следующих алгоритмов расчета собственных чисел симметричной матрицы: алгоритм с использованием LU-разложения прямоугольной матрицы (из библиотеки LAPACK), RRR-алгоритм (из библиотеки LAPACK), Sevd-алгоритм с использованием QL/QR алгоритма (из библиотеки BLAS). Вторым этапом в этом отношении является распараллеливание алгоритма, которое можно осуществить либо с использованием MKL для Intel C под Linux, либо с использованием библиотеки IMSL для GNU C и Intel C под Linux, либо средствами автоматического распараллеливания при помощи SunStudio, либо с использованием библиотек OpenMP и MPI.
Авторы выражают благодарность профессору С. Боккалетти за полезные обсуждения и критические замечания, а также доктору Д.У. Хвангу за помощь в реализации алгоритма.
Работа выполнена при поддержке РФФИ (07-02-00044, 09-02-92421-КЭ), Президентской программы поддержки ведущих научных школ РФ (НШ-355.2008.2), молодых кандидатов (МК-465.2009.2) и докторов (МД-448.2009.2) наук, НОЦ «Нелинейная динамика и биофизика» при СГУ (CRDF REC-006), АВЦП «Развитие научного потенциала высшей школы», ФЦП «Научные и научно-педагогические кадры инновационной России», а также ФНП «Династия» и МЦФФ.
Литература
1. Boccaletti S. Complex networks: Structure and dynamics / S. Boccaletti, V. Latora, V. Moreno, M. Chavez, D. U. Hwang // Physics Reports. – 2006. – V. 424. – P. 175–308.
2. Barabasi A. Statistical mechanics of complex networks / A. Barabasi, R. Albert // Rev. Mod. Phys. – 2002. – V. 74. – P. 47–97.
3. Dorogovtesev S.N. Evolution of networks / S.N. Dorogovtesev, J.F.F. Mendes. – Oxford
University Press, 2003.
4. Nooy W. Exploratory Social Network Analysis with Pajek / W. Nooy, A. Mrvar, V. Batagelj. – Cambridge University Press, 2005.
5. Godsil C. Algebraic Graph Theory / C. Godsil, G. Royle. – New York: Springer-Verlag,
2001.
6. Newman M.E.J. The structure and function of complex networks / M. E. J. Newman // SIAM Review. – 2003. – V. 45. – P. 167–256.
7. Stoer J. Introduction to Numerical Analysis / J. Stoer, R. Burlisch. – New York: Springer
Verlag, 1980.
8. Kim C. Mechanism of chaos synchronization and on-off intermittency / C. Kim // Physical Review E. – 1997. – V. 56. – № 3. – Part B. – P. 3697–3700.
Короновский Алексей Александрович – Саратовский государственный университет имени Н.Г.
Чернышевского, доктор физ.-мат. наук, профессор,
Косицын Андрей Александрович
alkor@nonlin.sgu.ru – Саратовский государственный университет имени Н.Г.
Москаленко Ольга Игоревна
Чернышевского, студент, kositzyn@gmail.com – Саратовский государственный университет имени Н.Г.
Чернышевского, кандидат физ.-мат. наук, ассистент,
Храмов Александр Евгеньевич
o.i.moskalenko@gmail.com – Саратовский государственный университет имени Н.Г.
Чернышевского, доктор физ.-мат. наук, профессор,
aeh@nonlin.sgu.ru
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 1(65)
45
УДК 519.179.2
ЧИСЛЕННОЕ МОДЕЛИРОВАНИЕ ПЕРЕХОДНЫХ ПРОЦЕССОВ В ЭВОЛЮЦИОНИРУЮЩИХ ПО ГЕНЕТИЧЕСКИМ АЛГОРИТМАМ СЕТЯХ
А.А. Короновский, А.А. Косицын, О.И. Москаленко, А.Е. Храмов
Представлены результаты исследования кооперативных явлений в сетях со сложной топологией. Для моделирования процессов эволюции разработан генетический алгоритм эволюции сложных сетей. Проанализированы переходные процессы, наблюдающиеся в ходе эволюции. Обнаружены определенные закономерности при оптимизации сети. Ключевые слова: сети со сложной топологией, генетический алгоритм, центральность, переходной процесс, перемежаемость.
Введение
Исследование кооперативных явлений в сетях со сложной топологией представляется в настоящее время одной из актуальных задач нелинейной динамики [1]. Интерес к подобным системам обусловлен, прежде всего, наличием большого числа объектов в природе и технике, которые можно описать с помощью сетевых моделей. Энергетические сети, железнодорожные сети, сети авиаперевозок, метро, всемирная сеть Интернет, социальные сети, сети соавторства, компьютерные сети – вот далеко не полный список объектов, к которым может быть применено понятие сети [2]. Понятно, что ни одна из вышеперечисленных сетей не является постоянной, характеристики каждой из них меняются с течением времени.
Поэтому в последнее время значительное внимание исследователей привлечено к изучению эволюционных процессов в сетях [3]. Эта проблема касается, прежде всего, биологических и экологических объектов, для которых понятие эволюции кажется очевидным. Большая часть систем в биологии и экологии эволюционирует по генетическим алгоритмам. Идея генетических алгоритмов состоит в организации эволюционного процесса, конечной целью которого является получение оптимального результата. Длительность эволюционных процессов является достаточно большой, а достижение оптимального результата зависит от ряда критериев. Понятно, что предсказание результата эволюции является нетривиальной задачей, поэтому возможна постановка задачи оптимизации тех или иных характеристик сети в процессе эволюции. На решение этой задачи как раз и направлена настоящая работа. В рамках исследования коопера-
40 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 1(65)
А.А. Короновский, А.А. Косицын, О.И. Москаленко, А.Е. Храмов
тивных явлений в эволюционирующих сетях разработан генетический алгоритм эволюции сложных сетей и исследованы переходные процессы при эволюции.
Понятие сети и ее основные характеристики
Перед тем, как перейти непосредственно к описанию самого генетического алгоритма, введем в рассмотрение понятия сети и ее основных характеристик.
Традиционно под сетью понимается совокупность объектов, объединенных при помощи связей, причем каждый объект должен обладать определенными свойствами и содержать конкретную информацию [4]. Математическим образом сети является граф. Он не содержит никакой информации об элементах сети, а просто передает структуру ее связей. Считается, что любая система, предполагающая наличие дискретных состояний или наличие узлов и переходов между ними, может быть описана графом. Соединения между узлами графа называются ребрами.
Для математического описания графов обычно используют следующие понятия [5]. Во-первых, граф может быть рассмотрен как структура G = (V, E), где V – множество вершин, E – множество ребер, причем ребра являются элементами вида e = (vi, vj), где vi, vj принадлежат множеству вершин. Во-вторых, для его описания достаточно часто используется матрица смежности, представляющая собой квадратную матрицу, все элементы которой, лежащие на главной диагонали, равны нулю. В зависимости от того, является граф ориентированным или нет, матрица смежности будет несимметричной или симметричной. В рамках настоящей работы мы остановимся на рассмотрении неориентированных графов. В этом случае элемент матрицы смежности S sij = 1, если существует ребро из i-ой в j-ую вершину, и sij = 0, если такого ребра нет.
Следует отметить, что приведенные выше понятия введены для так называемых невзвешенных графов (все ребра равноправны). Существует также понятие взвешенного графа [5], каждому ребру которого соответствует некий параметр – вес. Однако в данной работе взвешенные графы рассмотрены не будут.
Каждый узел сети характеризуется некоторой величиной ki, называемой степенью узла (node degree) [2]. Степень узла – это количество связей у данного узла или, с математической точки зрения, сумма элементов в i-той строке (столбце) матрицы смежности S. Понятно, что не все узлы сети имеют одинаковое число ребер, поэтому для характеристики сети целесообразно ввести в рассмотрение совокупность степеней узлов или их распределение [2]. Для случайного графа такое распределение описывается распределением Пуассона. В то же время большинство реальных сетей подчиняется степенному распределению степеней узлов (scale-free networks, или свободно масштабируемые сети), известны также сети с экспоненциальным распределением степеней узлов [1, 2].
Далее в работе мы будем рассматривать случайные графы, предполагая, что именно с таких объектов начинается процесс эволюции. Предполагается интересным исследовать вопрос о трансформации топологии сети с течением времени в случае оптимизации ее по различным характеристикам: к каким качественным и количественным изменениям приведет этот процесс, в частности, как трансформируется распределение степеней узлов в данном случае?
Генетический алгоритм эволюции сложных сетей и его численная реализация
Для исследования эволюционных процессов в сложных сетях при помощи среды разработки GNU/Linux с использованием языков программирования C, C++ и GNUутилиты make был разработан программный продукт, реализующий генетический алго-
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 1(65)
41
ЧИСЛЕННОЕ МОДЕЛИРОВАНИЕ ПЕРЕХОДНЫХ ПРОЦЕССОВ …
ритм эволюции сложных сетей, суть которого заключается в следующем. Имеется популяция, состоящая из M = 10 отдельных сетей (графов), каждая из которых состоит из N элементов. Изначально генерируются M/2 случайных графов, состоящих из N узлов и связей K = Np, где p = 0,05 – заданная вероятность наличия связей в случайном графе. Для каждого из них считается характеристика , по которой будет проводиться оптимизация.
Из построенных таким образом сетей случайным образом выбирается одна, для которой будет моделироваться дальнейший процесс эволюции. Предполагается, что на каждом шаге эволюции один из M/2 случайных графов начинает мутировать. При этом появляется M/2 дочерних графов, структура межэлементных связей которых отличается от исходной на заданную вероятность p. Для полученных сетей также считается оптимизируемая характеристика . Из полученных таким образом M графов (M/2 исходных и M/2 дочерних) выбираются M/2 графов с лучшими значениями характеристики . Остальные M/2 графов отбрасываются. Один из оставшихся графов, выбираемых случайным образом, снова начинает мутировать. Процесс продолжается до тех пор, пока не будет получена сеть с оптимальным значением характеристики .
В роли оптимизируемой характеристики может выступать одна из таких величин, как центральность, уязвимость, кластеризация, синхронизуемость, кратчайшее расстояние между элементами сети и др. [5]. В рамках настоящей работы мы остановимся на процессе оптимизации сети по характеристике, называемой центральностью (в англоязычной литературе – eigenvector centrality). Эта величина характеризует важность элемента в структуре сети и используется, например, при осуществлении web-поиска в системе Google для упорядочивания информации [6]. C математической точки зрения центральность – это дисперсия распределения координат собственного вектора x матрицы смежности S, соответствующего максимальному значению собственного числа
Для расчета собственных чисел матрицы смежности S использовался QRалгоритм с неявным сдвигом (перенесен из библиотеки LAPACK с внесением изменений, касающихся специфики задачи) [7]. Принципиальными достоинствами этого метода являются возможности работы с матрицами произвольного вида, поиска не только действительных, но и комплексных собственных чисел, а также поиска собственных векторов. В то же время этот метод характеризуется рядом существенных недостатков, одним из которых является относительно низкая скорость расчета. Более того, возможно возникновение и других трудностей реализации алгоритма. В частности, процесс эволюции сети является достаточно длительным, причем величина переходного процесса, как было показано нами, растет с увеличением количества элементов сети согласно экспоненциальному закону (эти результаты будут описаны в следующем разделе). Процесс эволюции является последовательным, а, следовательно, не может быть распараллелен. Вычисление оптимизируемой характеристики, в частности, дисперсии распределения координат собственного вектора, соответствующего максимальному собственному числу , требует также значительных временных затрат, особенно для сетей больших размеров. В то же время вычисление оптимизируемой характеристики осуществляется M/2=5 раз на каждом шаге эволюции, что говорит о возможности распараллеливания процесса вычислений.
В настоящее время удалось оптимизировать процесс эволюции сложных сетей. В частности, применение средств оптимизации, имеющихся в компиляторах gcc, g++, icc, icpc вплоть до третьего уровня, позволило увеличить скорость расчета примерно в 4 раза. Кроме того, скорость расчета увеличилась еще на 25% за счет использования процедуры векторизации (в силу свойств компиляторов icc, icpc).
42 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 1(65)
А.А. Короновский, А.А. Косицын, О.И. Москаленко, А.Е. Храмов
Основные результаты Коротко остановимся на основных результатах, полученных при оптимизации алгоритма эволюции сложных сетей, касающихся, прежде всего, исследования переходных процессов, имеющих место в процессе эволюции. При проведении расчетов анализировались сети, состоящие из различного числа элементов N[50; 1000]. На рис. 1, а, представлены зависимости оптимизируемой характеристики (центральности ) от шага эволюции для сетей различных размеров.
0,8
0,6
0,4
0,2
аб Рис. 1. Переходные процессы при эволюции сложных сетей: а – зависимость оптимизируемой характеристики от шага эволюции k для сетей из 100, 150, 200, 325, 500, 1000 элементов (в логарифмическом масштабе по оси абсцисс); б – зависимость времени выхода оптимизируемой характеристики на уровень насыщения от размера
сети N (точки) и ее аппроксимация Ttrans = 16,37e0.045N (сплошная линия)
Нетрудно заметить, что в процессе эволюции сети оптимизируемая характеристика меняется по логарифмическому закону, причем по завершении переходного процесса эта характеристика выходит на один и тот же уровень, независимо от размера сети. Указанная особенность позволяет определить длительность переходного процесса даже для тех сетей, процесс эволюции которых оказывается еще не завершенным. Зависимость длительности переходного процесса от размера сети представлена на рис. 1, б. Из рисунка видно, что величина переходного процесса растет с увеличением количества элементов сети по экспоненте (соответствующая аппроксимация показана сплошной линией).
Следует отметить, что в процессе эволюции сети оптимизируемая характеристика не меняется постоянно, а может оставаться неизменной в течение достаточно длительного промежутка времени. Интересным представляется вопрос о характере распределения длительностей участков, на которых оптимизируемая характеристика не меняется, в частности, прослеживается ли какая-либо закономерность в указанных распределениях или они оказываются различными для сетей разных размеров. На рис. 2, а, представлены распределения длительностей таких участков для сетей из N = 100, N = 500 и N = 1000 элементов и соответствующие аппроксимации. Видно, что независимо от размера сети подобные распределения подчиняются степенному закону с показателем степени «минус 1,5», характерным для перемежаемости типа «on–off» [8]. В этом случае
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 1(65)
43
ЧИСЛЕННОЕ МОДЕЛИРОВАНИЕ ПЕРЕХОДНЫХ ПРОЦЕССОВ …
можно говорить, что обнаружен аналог перемежающегося поведения в процессе эволюции сложных сетей.
аб Рис. 2.. Распределения длительностей участков, на которых оптимизируемая характеристика не меняется, для сетей из 100 (▲), 500 () и 1000 () элементов и соответствующие аппроксимации N(l) ~ l-1.5 (а).. Трансформация распределения степеней узлов
сети из 1000 элементов в процессе эволюции: 0 шаг (), 59814 шаг () и 74163 шаг (▲). Сплошной линией показана аппроксимация соответствующего распределения
распределением Пуассона (б)
Не менее важным является вопрос о трансформации топологии сети в процессе эволюции. На рис. 2, б, представлены распределения степеней узлов сети из 1000 элементов на 0 (), 59814 () и 74163 (▲) шагах эволюции. Эволюционный процесс, как отмечалось выше, начался со случайного графа, распределение степеней узлов которого подчиняется распределению Пуассона (показано на рисунке сплошной линией справа). Нетрудно заметить, что в процессе эволюции топология сети заметно трансформируется: из случайного графа получается сеть, характеристики которой сильно отличаются от характеристик случайной сети.
Заключение
В настоящей работе проведено исследование кооперативных явлений в сложных сетях, эволюционирующих по генетическому алгоритму. С этой целью разработан алгоритм эволюции сложных сетей и проведена его оптимизация, в результате которой удалось увеличить скорость расчета примерно в 5 раз. При помощи разработанного алгоритма исследованы также переходные процессы в ходе эволюции сложных сетей (в роли критерия отбора выступает оптимизация центральности сети). В то же время ряд результатов удалось получить только для сетей относительно малых размеров, что говорит о необходимости дальнейшей оптимизации алгоритма.
В ходе проведения исследований установлено, что вычисление оптимизируемой характеристики требует больших вычислительных мощностей и занимает много времени. Однако подобные вычисления осуществляются несколько раз на каждом шаге эволюции, что говорит о возможности распараллеливания вычислений.
Планируется проведение дальнейшей оптимизации алгоритма. Одним из наиболее существенных моментов в данном случае является замена алгоритма расчета собственных чисел и соответствующих им собственных векторов. Следует отметить, что ис-
44 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 1(65)
А.А. Короновский, А.А. Косицын, О.И. Москаленко, А.Е. Храмов
пользуемый QR-алгоритм не принимает во внимание симметрию матрицы, что значительно замедляет расчет оптимизируемой характеристики (особенно для матриц достаточно больших размеров). Поэтому предполагается апробировать и использовать в дальнейшем один из следующих алгоритмов расчета собственных чисел симметричной матрицы: алгоритм с использованием LU-разложения прямоугольной матрицы (из библиотеки LAPACK), RRR-алгоритм (из библиотеки LAPACK), Sevd-алгоритм с использованием QL/QR алгоритма (из библиотеки BLAS). Вторым этапом в этом отношении является распараллеливание алгоритма, которое можно осуществить либо с использованием MKL для Intel C под Linux, либо с использованием библиотеки IMSL для GNU C и Intel C под Linux, либо средствами автоматического распараллеливания при помощи SunStudio, либо с использованием библиотек OpenMP и MPI.
Авторы выражают благодарность профессору С. Боккалетти за полезные обсуждения и критические замечания, а также доктору Д.У. Хвангу за помощь в реализации алгоритма.
Работа выполнена при поддержке РФФИ (07-02-00044, 09-02-92421-КЭ), Президентской программы поддержки ведущих научных школ РФ (НШ-355.2008.2), молодых кандидатов (МК-465.2009.2) и докторов (МД-448.2009.2) наук, НОЦ «Нелинейная динамика и биофизика» при СГУ (CRDF REC-006), АВЦП «Развитие научного потенциала высшей школы», ФЦП «Научные и научно-педагогические кадры инновационной России», а также ФНП «Династия» и МЦФФ.
Литература
1. Boccaletti S. Complex networks: Structure and dynamics / S. Boccaletti, V. Latora, V. Moreno, M. Chavez, D. U. Hwang // Physics Reports. – 2006. – V. 424. – P. 175–308.
2. Barabasi A. Statistical mechanics of complex networks / A. Barabasi, R. Albert // Rev. Mod. Phys. – 2002. – V. 74. – P. 47–97.
3. Dorogovtesev S.N. Evolution of networks / S.N. Dorogovtesev, J.F.F. Mendes. – Oxford
University Press, 2003.
4. Nooy W. Exploratory Social Network Analysis with Pajek / W. Nooy, A. Mrvar, V. Batagelj. – Cambridge University Press, 2005.
5. Godsil C. Algebraic Graph Theory / C. Godsil, G. Royle. – New York: Springer-Verlag,
2001.
6. Newman M.E.J. The structure and function of complex networks / M. E. J. Newman // SIAM Review. – 2003. – V. 45. – P. 167–256.
7. Stoer J. Introduction to Numerical Analysis / J. Stoer, R. Burlisch. – New York: Springer
Verlag, 1980.
8. Kim C. Mechanism of chaos synchronization and on-off intermittency / C. Kim // Physical Review E. – 1997. – V. 56. – № 3. – Part B. – P. 3697–3700.
Короновский Алексей Александрович – Саратовский государственный университет имени Н.Г.
Чернышевского, доктор физ.-мат. наук, профессор,
Косицын Андрей Александрович
alkor@nonlin.sgu.ru – Саратовский государственный университет имени Н.Г.
Москаленко Ольга Игоревна
Чернышевского, студент, kositzyn@gmail.com – Саратовский государственный университет имени Н.Г.
Чернышевского, кандидат физ.-мат. наук, ассистент,
Храмов Александр Евгеньевич
o.i.moskalenko@gmail.com – Саратовский государственный университет имени Н.Г.
Чернышевского, доктор физ.-мат. наук, профессор,
aeh@nonlin.sgu.ru
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 1(65)
45