Эволюция случайных графов в системе «Малых миров»

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

случае SC-модуль на n идентифицирующих переменных строится на 0,5n (n-1) последовательно соединенных по переключательным каналам ран-герах, каждый из которых содержит один компаратор и n!-разрядный коммутатор.
Заключение
Предложенный подход позволяет путем коммутационного программирования воспроизводить полные классы ситуационных функций (2), порождаемых инвариантными преобразованиями (3).
Научная новизна: поставлена и решена задача синтеза СК с самообучением распознаванию состояний ОУ, заданных в виде отношений между наблюдаемыми случайными аналоговыми сигналами с произвольными распределениями мгновенных значений.
Сравнение с аналогом. По сравнению со схемными решениями, описанными в работе [7], рассмотренный подход обеспечивает более широкие функциональные возможности за счет воспроизведения полных классов инвариантных преобразований (2).
Практическая значимость. Наличие элементного базиса рангеров позволяет заменить широкую номенклатуру специализированных функциональ-
ных, логических, вычислительных, коммутационных, управляющих и измерительных преобразователей одним универсальным SC-модулем ситуационной обработки аналоговых сигналов.
Литература: 1. Васильев В. И. Распознающие системы. К.: Наук. думка, 1983. 424 с. 2. Плотников В. Н. Речевой диалог в системах управления. М: Машиностроение, 1988. 224 с. 3. Руденко О. Г., Бодянский Е. В. Основы теории искусственных нейронных сетей. Харьков: ТЕЛЕТЕХ, 2002. 317 с. 4. Бондарев В. Н, Аде Ф. Г. Искусственный интеллект. Севастополь: Изд-во Сев НТУ, 2002. 615 с. 5. Полонский А. Д. Инвариантная алгебра ранговых предикатов для синтеза классификаторов аналоговых сигналов / / АСУ и приборы автоматики. 2003. Вып. 124. С. 99−106. 6. ПолонскийА.Д. Синтез инвариантных классификаторов / / Радиоэлектроника и информатика. 2003. Вып. 4. С. 51−55. 7. Шимбирев П. Н. Еибридные непрерывно-логические устройства. М.: Энергоатомиздат, 1990. 174 с.
Поступила в редколлегию 10. 09. 2004
Рецензент: д-р физ. -мат. наук, проф. Воробьев F. С.
Полонский Александр Дмитриевич, канд. техн. наук, докторант кафедры искусственного интеллекта ХНУ-РЭ. Научные интересы: инвариантные системы. Адрес: Украина, 40 001, Сумы, ул. Кирова-165, д. 140, кв. 41, тел. (0542) 627−950.
УДК 719. 21
ЭВОЛЮЦИЯ СЛУЧАЙНЫХ ГРАФОВ В СИСТЕМЕ «МАЛЫХ МИРОВ»
ШЕРШЕНЬ В.Н. _____________________________
Рассматриваются известные и новые методы исследования систем, поведение которых описывается в терминах графов (детерминированных и случайных). Предлагаются способы вычисления такой характеристики системы, как вероятность реализации путей между двумя произвольными узлами системы.
1. Актуальность исследования
В последнее время возрос интерес к исследованию сложных комплексных структур. С помощью таких структур описываются различные технические, информационные и биологические системы. Для моделирования таких систем используют случайные графы.
Наибольший интерес представляют разнообразные сети, которые описываются в терминах комплексных структур. Перечислим некоторые из них:
— сеть Internet — глобальная всемирная сеть, которая состоит из маршрутизаторов и компьютеров, соединенных между собой физическими и беспроводными линиями связи-
-WWW (World Wide Web — всемирная паутина) — собрание гипертекстовых, графических и прочих документов, доступных по всему миру через сеть Internet-
— «Единая энергосистема» — система из линий электропередач, охватывающая несколько государств (регионов), объединенных общими экономическими интересами-
РИ, 2004, № 4
— «Сеть ссылок» — множество источников, которые содержат информацию о работах в определенной области знаний
Не всегда удается для всех систем выбрать универсальные показатели, по которым можно было бы производить их синтез и сравнивать друг с другом. Важной характеристикой связей в указанных сетях является средняя длина пути — среднее число звеньев, соединяющих один адрес (вершину, узел, центр) с другим. В этой работе исследуются вероятности реализации путей между двумя произвольными узлами сети. При этом используется терминология случайных графов.
За последнее время были предложены различные подходы для решения поставленной задачи. Эти подходы во многом основываются на следующих понятиях: кластеризация- распределение порядка и «малые миры».
В большинстве случаев при решении таких задач применяются знания из области случайных графов. Опишем вкратце приведенные выше понятия.
Кластеризация — наиболее типичное свойство для социальных сетей: в любом социальном обществе образуются группы людей, в каждой из которых любой член группы знаком со всеми остальными членами этой же группы. Это свойство определяется коэффициентом кластеризации — отношением количества присутствующих в системе связей к максимально возможному числу связей, которые могут возникнуть:
C =
2 • E
N • (N -1) •
55
Здесь E — количество имеющихся связей- N — количество узлов. Реальные сети имеют значительно больший коэффициент кластеризации, чем соответствующие случайные графы.
Одной из важнейших характеристик случайных графов является распределение порядка — функция распределения P (k), которая определяет вероятность того, что из произвольно выбранной вершины исходит ровно k ребер. Для случайных графов, в отличие от реальных сетей, эта функция совпадает с распределением Пуассона [ 1 ].
«Малые миры» — системы, в которых, независимо от их размера, существует относительно короткий путь между двумя произвольными вершинами, принадлежащими малому миру. Большинство реальных сетей являются «малыми мирами». В качестве примера можно привести тот факт, что в США два произвольно выбранных человека знакомы друг с другом через цепочку, в среднем, из пяти человек [2]. Примером может служить и глобальная всемирная сеть Internet [2]. В связи с этим отметим, что расстояние между двумя любыми вершинами в случайном графе, в котором появление любого ребра имеет одну и ту же вероятность, пропорционально логарифму количества вершин графа, поэтому случайный граф в каком-то смысле является «малым миром» [1].
В настоящее время существует много различных моделей, которые описывают системы, являющиеся «малыми мирами». Например, однопараметрическая модель, которая представляет собой нечто среднее между упорядоченной одномерной бесконечной решеткой и случайным графом [2]. Такая модель была предложена ^айв'ом и Strogatz’ом (WS-модель). Своими корнями она уходит в социологические системы — сети, которые изначально применялись при изучении возникновения связей (знакомств) между людьми и организациями, тяготеющими к объединению в силу общности их интересов. Другая известная модель основана на вероятностях предпочтения и актуальна при рассмотрении растущих сетей. В этой модели расширение сети происходит за счет добавления новых связей к «наиболее популярным» узлам существующей сети [2]. В качестве абстрактной модели малого мира также используют случайные графы [2].
2. Постановка задачи
Целью настоящей работы является исследование вероятностных характеристик возникновения путей в сети с заданной топологией.
Предложен подход, позволяющий найти вероятность возникновения путей, соединяющих два произвольных узла (вершины) исследуемой сети. Вероятности реализации ребер, соединяющих любые две вершины, предполагаются известными.
Пусть Г0 — случайный граф с множеством вершин Q. о, |о0 = N0 — предположим, что задана вероят-
ность ро & gt- 0 возникновения ребер в случайном графе для множества всех его вершин Оо. Пусть эта вероятность ро одинакова для любой пары вершин
(юа, Юр)є Qo, а, Р = 1. N0.
Необходимо найти вероятность возникновения пути между двумя произвольными узлами описанной системы.
3. Решение поставленной задачи
Как известно из [1], сконструированный таким способом граф является «малым миром». Обозначим л о — вероятность реализации пути между двумя вершинами графа Го. Очевидно л о & gt- Ро. Пусть ло = Ро +§ о, где 5о включает в себя все вероятности существования путей между двумя узлами системы. Каждый из этих путей должен содержать не менее двух ребер (т.е. не должен соединять рассматриваемые вершины непосредственно). Для вычисления значения 5 о нужно учесть все пути между двумя рассматриваемыми вершинами.
Предположим, что существует некоторая система Г = {Г-}, состоящая из N независимых случайных графов Г-, i = о,…, N -1, каждый из которых устроен, как описано выше (для графа Го). В каждой паре графов Г- и Tj из Г (i, j = 1,…, N, i ф j) случайным образом выберем по одной вершине ю^ и ropj и зададим вероятность Pij возникновения ребра между ними (Pij не зависит от выбора юа- и ropj, а зависит только от Г-, Tj).
При исследовании вероятностных связей между любыми вершинами из множества {Г}, любые два графа Гі и Tj которого связаны указанным выше образом, наибольший интерес представляет вычисление л — вероятности существования пути из произвольного узла системы Г в любую другую вершину этой же системы. Нами установлено следующее равенство: Лу = л- • p-j — лj +5-j. Здесь Лу — вероятность существования пути между произвольно выбранными узлами в графах Г- и Tj- S-j — соответствующая «поправочная» вероятность, которая учитывает существование путей, отличных от пути, соединяющего юа- и opj непосредственно. Величина 8-j может быть вычислена аналитически. Отметим, что для ее определения для всех значений i, j следует вычислить математическое ожидание всех Лу, которое в силу равной вероятности выбора вершин і и j будет одинаково для всех i, j. Описанная выше система графов Г = {Г-} является статичной (вероятностные связи между ее элементами не зависят от времени).
4. Альтернативная формулировка задачи
Иная формулировка поставленной задачи состоит в следующем. Рассмотрим поверхность q и зада-
56
РИ, 2004, № 4
дим на q непрерывную, положительно определенную функцию P (Q), определенную в каждой точке Q. Будем считать, что функция P (M) задает вероятность в каждой точке M efi. Пусть для определенности фазовым пространством q является поверхность шара в R3. Выберем произвольным образом N точек, лежащих на Q: Aj. An є Q. Считаем, что: в A- (i = 1. N) могут быть расположены некоторые информационные или технические центры, нуждающиеся в обмене данными друг с другом- между всеми A- (i = 1. N) существуют информационные каналы, позволяющие осуществлять обмен информацией. Для описания этих связей выберем случайным образом некоторый центр А-о и вычислим значение вероятности в точке А-о: ро = Р (А0). Также предположим, что с узлом, А -о связана некоторая область-0 (Q-0 cQ)
— «область влияния» этого узла. Считаем, что ^ -0
— выпуклая область. Пусть все точки А-, А- Ф А-о соединяются с центром А-о с вероятностью Ро. Так задаются связи со всеми А- eQ-о информационными центрами, т. е. со всеми вершинами из-0. Указанные связи определяются географической близостью друг к другу рассматриваемых центров
и функцией P (Q), заданной на фазовом пространстве q. Такую операцию задания вероятностей необходимо повторить для каждой точки А- б = 1. N), которая еще не входит ни в одну из выбранных областей Q j, с той лишь разницей, что каждая область Q- не должна содержать точек более чем из одной областиj, отличающейся от текущей Q- (- ф j). Это требование является естественным, так как не имеет смысла связывать один центр с другим, если они уже имеют связь между собой через какой-либо промежуточный центр. Таким образом, построенная система связей между центрами А- б = 1. N) в достаточной степени аппроксимирует реальные информационные сети и происходящие в них процессы.
Зададим на Q случайный процесс. Состояниями | будут рассматриваемые узлы А- б = 1. N), а вероятности перехода из одного состояния в другое с точностью до некоторого постоянного множителя (нормирующий множитель) будут совпадать с вероятностями р- = Р (А-), описанными выше. Нормирующий множитель выбирается равным отношению единицы к сумме всех возможных вероятностей перехода из текущего центра во все осталь-
, 1
ные: к j =---.
j? Р j-
Из изложенного следует, что для всех вершин а, Р вероятность Рар равна рар = Ра^р.
Стохастическая матрица, построенная на основе указанных выше связей? , является блочной матрицей порядка N — каждый ее блок отвечает области Q-, а пересечения блоков — состояниям, которые принадлежат двум областям Q-, Оj одновременно, т. е. находящимся в их пересечении.
Случайный процесс % является марковским [3]. Следовательно, применяя технику, описанную в [4], можно сделать вывод: независимо от начальных условий описанная система через конечное время может быть стабилизирована [4].
5. Выводы
Предложен вероятностный подход для оценки связности системы посредством вычисления вероятностей реализации путей между произвольно выбранными точками системы, что определяет научную новизну данного исследования.
Практическая значимость. Для изучения систем, эволюция которых определена как детерминированными факторами, так и случайной составляющей, подходит модель, основанная на теории случайных графов. Предложенный подход, основанный на вычислении вероятностей, позволяет исследовать сетевые системы с достаточной степенью точности.
Сравнение с лучшими аналогами. Как правило, для построения и последующего анализа математической модели таких систем используются конструкции, реализованные на случайных графах, как предложено в [2]. К числу недостатков настоящей работы следует отнести тот факт, что случайные графы не всегда достаточно точно отражают динамику развития исследуемых систем.
Литература: 1. Erdos P. and Renyi A. On the strength of connectedness of random graphs, Acta Math. Acad. Sci. Hungar. 1961. № 12. P. 261−267. 2. Kochen M. (ed.) The Small World (Ablex, Norwood, NJ). 1989. 184 p. 3. Розанов Ю. А. Теория вероятностей, случайные процессы и математическая статистика. М.: Наука, 1989. 320с. 4. Дикарев В. А. Точки фокусировки и теоремы о существовании предельных вероятностей. Харьков, 1995. Деп. В ГНТБ Украины 28. 02. 95, № 526 — Ук95, 136 — 145 c.
Поступила в редколлегию 13. 11. 2004
Рецензент: д-р техн. наук, проф. Кривуля Г. Ф.
Шершень Владислав Николаевич, аспирант кафедры прикладной математики ХНУРЭ. Научные интересы: программирование, стохастический анализ и его приложения. Адрес: Украина, 61 000, Харьков, ул. Целиноградская, 36.
РИ, 2004, № 4
57

ПоказатьСвернуть
Заполнить форму текущей работой