Диссертация (1104904), страница 14

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 14)

Эффективность алгоритма будет продемонстрирована для несколькихмоделей полимерной упаковки.3.3.1. Детектирование иерархической организации в доменах макромолекулЯсно, что для любой структуры можно однозначно построить матрицу контактовмежду субъединицами, вопрос обратного преобразовании неизменно связан снеопределенностью итоговой структуры как целого, однако, некоторые устойчивыеатрибуты системы, такие как консервативные вложенные доменные организации, могутбыть зафиксированы с хорошей точностью.

Более того структура таких организацийвполне может быть индикатором состояния стартовой системы.Матрицу контактов W мы рассматриваем как матрицу смежности некоторогослучайного графа, что дает возможность использовать методы обнаружения сообществ,разработанные в рамках комплексной теории сетей [98]. Действительно, мономеры,принадлежащие одному сетевому домену, будут локализованы в пространственно72гораздо чаще, чем мономеры разных доменов, то есть, такие топологические областиконтактирующих субъединиц могут рассматриваться как сообщество связных узлов врамках теории сетей. Проблема оптимального разделения сети на множество сообществнекорректна и не может быть решена однозначно, однако, существуют количественныетехники её решения, основанные на анализе спектральных плотностей матриц смежности[99], необратимых матрицах [100], синхронизации сетей [101]. Здесь мы пользуемсяметодом модульной оптимизации, разработанным в рамках [94-97], который мы сочлинаиболееподходящимдлярешенияпоставленнойзадачиввидуегомультимасштабности.Рассмотрим разделение сети, состоящей из N узлов, на набор из k кластеров (см.рис.).

Любое такое разбиение может быть описано матрицей C размером N  k с ci  1 ,если i-ый элемент сети принадлежит a-кластеру и 0 – в противном случае. Ясно, чтоc   1 для любого i, так как любой узел принадлежит хотя бы одному кластеру. Тогда,iв соответствии с [94], модульность Q[W,C] такого разбиения будет определена как:Q[W,C] ww 1wi , j  i j  ci c j ,2w i , j 2w  (3.1)где wij – элементы матрицы W, wi   wi , j – количество соседей i-ого узла, w   wi , j / 2ji, j– общее количество связей в сети. Суммирование по  в уравнении (3.1) дает 1, если iый и j-ый мономеры принадлежат одному кластеру и 0 в противном случае.

Определениепервоначальноймодульностисообществапроисходитнаосновемаксимизациифункционала Q по k и C (соответствующая максимизация считается оптимальной).Описанный метод оптимизации модулярности имеет два существенных недостатка: вопервых, он обладает, так называемым, пределом разрешения, так что кластера размераменьше ~ 2w не могут быть определены корректно [95]. Во-вторых, общее количествовозможных разделений сети по кластерам экспоненциально растет с ростом числа узловN, делая поиск оптимального разделения NP-полной задачей, то есть задачей,кратчайшее время решения которой растет экспоненциально с увеличением N [102,103].Для того чтобы решить первую проблему, следуя [96,97], вводится, так называемый,параметр сопротивления r, то есть вводится преобразованная матрица смежности W( r ) ,матричные элементы которой заданы как wi , j  wi , j для i  j , а wi ,i  r .

Далее перейдем коптимизации функционала из уравнения (3.1) для полученной матрицы W( r ) . Рост73параметра r приводит к тому, увеличению количества узлов, которые соединены сами ссобой чаще, чем с окружающими узлами. При превышении некоторого критическогозначения параметра rmax – оптимальной кластеризацией является разбиение сети на Nкластеров, состоящих из одного мономера каждый. При r меньше некоторого значенияrmin, как правило, отрицательного, оптимальное разбиение состоит в существованииодного кластера, содержащего все N узлов сети.Проблема экспоненциального роста числа возможных разбиений с увеличениемразмеров системы также может быть решена в случае рассматриваемых намиполимерных систем. Дело в том, что матрица связности определяется как некотораяматрица колокализации единиц некоторой полимерной структуры.

Следовательно, мыможем использовать тот факт, что мономеры, расположенные последовательно вдоль поцепи, являются соседними в пространстве в связи со связностью полимера. Этопозволяет предположить, что наше рассмотрение сводится к расстановке кластерныхперегородок, разделяющих цепь на фрагменты, связными вдоль по цепи (то есть, если i иj узлы принадлежат одному кластеру, то любой узел k, такой что i  k  j такжепринадлежит этому кластеру).

Такое ограничение приводит к уменьшению числавозможных реализаций кластеризации (экспоненциальный рост количества реализацийсо степенью N, при увеличении размера системы, сводится к росту N 2 , позволяяпроводить разделение сетей гораздо эффективнее).Теперь затронем вопрос зависимость итоговой кластеризации системы отзначения параметра r. Для полностью случайной сети Эрдаша-Реньи при r_min сетьбудет разбита на два кластера приблизительно одинакового размера; при r2  rmin сетьбудет разделена на три кластера, снова, примерно одинакового размера, затем, при r3  r2на четыре кластера и так далее. В отсутствии каких-либо дополнительных условийграницы кластеров сети существенно нескоррелированы: увеличение числа кластеров наединицу приводит к реорганизации всех границ кластеров. Однако если сеть обладаетбазовой структурой, например, иерархической организацией топологических доменов,увеличение параметра r не повлечет за собой полную перестройку кластернойструктуры, а разложение кластеров на меньшие части будет происходить с сохранениемдоменных стенок раскладываемых кластеров.

Для количественной оценки такогопроцесса вводится понятие спектр границ.Пусть H i ( r )(i,..., N  1) – функция Хевисайда, значение которой показывает,является ли связь между i-ым и (i+1)-ым мономерами границей кластеров при74фиксированном r (то есть, H i ( r )  1 , в случае если связь является границей и H i ( r )  0 , впротивоположном случае). Тогда суммарная доля разбиений сети, когда заданная связьявляется границей кластера внутри диапазона (rmin, rmax), задается как:fi  (rmax  rmin )1 rmaxrmin(3.2)H (r) drЧем больше fi, тем более стабильной является кластерная граница (i, i  1) .

Полныйнабор fi для всех i будем называть спектром границ. Анализ такого спектра позволяетоценитьстабильностькластернойструктурысети,атакжесуществованиеиерархического порядка в организации внутриструктурных доменов. При отсутствиичетких кластеров спектр границ содержит равномерное распределение линий спектра, вто время как существование некоторого количества fi, значительно превышающихостальные значения, показывает, что сеть стабильна и имеет хорошо определеннуюкластерную структуру.Рис. 3.11. Пример деления связанной сети из 8 узлов на кластеры.Для более наглядной демонстрации удобно использовать модель сети из 8-мипоследовательных узлов (см. Рис.

3.11а). Пусть вдоль всего интервала сеть разбиваетсяровно на два кластера с границей в узле 4 (см. Рис. 3.11б):751, дляi  4;fi  0, дляi  4.(3.3)Это значит, что на всем интервале r существует только одна граница между двумякластерами и эта граница не смещается, то есть, кластера всегда содержат ровно 4 узла(то есть, если разделение, показанное на Рис. 3.11б выполняется для любого r, спектрграниц, график показан на Рис. 3.12а).

Если появляется область, внутри которой этикластера равны нулю и оптимальное разбиение состоит из единственного кластера (см.Рис. 3.11б), амплитуда f4 становится меньше 1 (см. Рис.3.11б).Рис. 3.12. Спектры границ сети, приведенной на рис. 28, в рамках каждой изпредложенных кластеризаций.Далее предположим, что выше определенного значения r2  ( rmin , rmax ) первый из двухкластеров распадается на два меньших, размером по 2 узла каждый (см. Рис. 3.12в): 1, при i  4;f i   f , при i  2;0, при i  2, 4.(3.4)где76f rmax  r2, 0  f  1.rmax  rmin(3.5)Если граница на связи 4 пропадает, формируя новый набор из трех кластеров, например,(1,2), (3,4,5,6) и (7,8) (см. Рис.3.11(г)).

Тогда множество амплитуд границ спектров будетзаписано как:1  f , при i  4;f i   f , при i  2,6;0, при i  2, 4,6.(3.6)Соответствующие спектры границ показаны на Рис. 3.12в и Рис. 3.12г, соответственно.Таким образом, случайное расположение кластерных стенок вдоль по цепиприводит к тому, что спектр границ состоит из набора низких пиков, примерно,одинаковой высоты, что характерно для сетей с нечеткой доменной структурой. Приразбиении больших кластеров с сохранением собственных границ, приводит к наборупиков, существенно отличающихся по высоте. Такое поведение соответствует сетям счеткой иерархией в доменной организации.3.3.2. Спектральный анализ матриц связности полимерных системДля проверки работы алгоритма применим его к серии матриц смежности длянескольких полимерный структур, а именно: кривой Пеано, складчатой и равновеснойглобулам.

Элементы матриц смежности wij принимаются равными за 1 в случаепространственного расстояния между звеньями i и j составляет ri , j  a  3 единицрешетки. Диапазон параметра сопротивления r был выбран от rmin= –20 до rmax= 80.Анализ кривой Пеано, как и ожидалось, позволяет выявить иерархическивложенные кластера: при значениях r  20.7 существует единственный кластер из 4096узлов, при r  20.7 два кластера, содержащие по 2048 узлов каждый. С дальнейшимростом r кластера продолжают биться на 2 кластера одинакового размера и так далее доrmax.

При этом границы, установленные на предыдущих шагах разбиения, остаютсянеизменными. Таким образом, f2048 соответствует самому высокому пику для кривойПеано, следующие по высоте пики приходятся на узлы f1024 и f3072. В итоге, мы получаемспектр границ, соответствующий иерархическому набору эквидистантных пиков, какпоказано на Рис. 3.13а, где мы можем наблюдать 6 уровней организации кривой Пеано.Каждый большой кластер имеет полностью детерминированную внутреннюю структуру,например, кластер второго уровня, содержащий узлы с 2048 по 3072, разбивается на узле772560 и содержит два домена по 512 узлов каждый.

Характеристики

Список файлов диссертации