Հայաստանի ատենախոսությունների բաց մատչելիության պահոց = Open Access Repository of the Armenian Electronic Theses and Dissertations (Armenian ETD-OA) = Репозиторий диссертаций Армении открытого доступа

Պատահական բլոկ-հիերարխիկ ցանցերի տոպոլոգիական բնութագրիչների ավտոմատացված հետազոտության համակարգի մշակում

Քոչարյան, Անի Գագիկի (2018) Պատահական բլոկ-հիերարխիկ ցանցերի տոպոլոգիական բնութագրիչների ավտոմատացված հետազոտության համակարգի մշակում. PhD thesis, Հայաստանի ազգային պոլիտեխնիկական համալսարան.

[img]
Preview
PDF (Abstract)
Available under License Creative Commons Attribution Non-commercial.

Download (870Kb) | Preview
    [img]
    Preview
    PDF (Thesis)
    Available under License Creative Commons Attribution Non-commercial.

    Download (6Mb) | Preview

      Abstract

      Ատենախոսությունը նվիրված է բլոկ-հիերարխիկ պատահական ցանցերի տոպոլոգիական բնութագրիչների հաշվարկի էֆեկտիվ ալգորիթմների և xRandNet (Extended Random Networks) ավտոմատացման համակարգի մշակմանը, որը թույլ է տալիս կատարել պատահական ցանցերի տարբեր հետազոտություններ։ Բարդ ցանցային կառուցվածքների միջոցով նկարագրվում է բարձր տեխնոլոգիական և ինտելեկտուալ համակարգերի լայն սպեկտր։ Բարդ ցանցերի տոպոլոգիայի և ժամանակի ընթացքում դրանց փոփոխության դինամիկայի հետազոտման հարցերով զբաղվում է պատահական ցանցերի տեսությունը, որը հիմնադրվել է հունգարացի մաթեմատիկոսներ Պոլ Էրդյոշի և Ալֆրեդ Ռենյիի կողմից: 1959թ-ին նրանք առաջարկեցին պատահական ցանցի Erdős-Rényi մոդելը՝ ենթադրելով, որ բարդ համակարգերի համար ադեկվատ մաթեմատիկական մոդել է հանդիսանում պատահական ցանցը, որում հանգույցների միջև կապերը առաջանում են պատահական ձևով, որոշակի հավանականային կանոնով։ Պատահական ցանցերի տեսության զարգացմանը զուգահեռ այլ հեղինակների կողմից առաջարկվեցին նաև ուրիշ մոդելներ՝ Watts-Strogatz և Barabási-Albert։ Պատահական ցանցերի բոլոր թվարկված մոդելները համարվում են դասական։ Հետագայում այնպիսի իրական պատահական ցանցերի ուսումնասիրությունը, ինչպիսիք են ուղեղի նեյրոնների ցանցը, ԴՆԹ-ի կառուցվածքը, բջջում սպիտակուցների փոխազդեցությունները և այլն, ցույց տվեց, որ դրանցից որոշները ունեն յուրահատուկ կառուցվածք, որի հիման վրա սահմանվեց պատահական ցանցերի նոր դաս՝ բլոկ-հիերարխիկ, և առաջարկվեցին RBH (Regular Block-Hierarchical) և NRBH (Non Regular Block-Hierarchical) մոդելները։ Պատահական ցանցերի հետազոտման համար կարևոր է ունենալ ծրագրային միջոցներ դրանց տոպոլոգիական բնութագրիչների հաշվարկի համար, որոնք են հանգույցների միջին աստիճանը և հանգույցների աստիճանների բաշխումը, միջին ճանապարհային երկարությունը և տրամագիծը, կլաստերացման գործակիցը, կապակցվածության կոմպոնենտների բաշխումը և այլն։ Հատուկ տեղ է զբաղեցնում ցանցի զարգացման դինամիկայի ուսումնասիրությունը։ Բարդ ցանցային կառուցվածքները, որպես կանոն, ունեն մեծ քանակով հանգույցներ և կապեր, ինչը լուրջ խոչընդոտ է հանդիսանում հաշվարկային ծրագրային միջոցների մշակման հարցում։ Քանի որ պատահական ցանցերի հետազոտությունները կատարվում են ցանցերի հավաքածուի վրա, խնդիր է առաջանում մշակել բարձր էֆեկտիվություն ունեցող ալգորիթմներ տոպոլոգիական բնութագրիչների հաշվարկի համար։ Բլոկ-հիերարխիկ ցանցերի կառուցվածքը ունի մի շարք առանձնահատկություններ, ինչը մեզ թույլ է տվել դրանց տոպոլոգիական բնութագրիչների հաշվարկի համար մշակել ավելի նոր և էֆեկտիվ ալգորիթմներ։The thesis is dedicated to the development of xRandNet (Extended Random Networks) automated system which allows conducting different researches on random networks. A wide variety of high technological and intellectual systems is described through complex network structures. The topology of complex networks and the dynamics of their change over time are studied by random network theory which was introduced by Hungarian mathematicians Paul Erdős and Alfréd Rényi. In 1959 they offered the Erdős–Rényi random network model assuming that for complex systems random network is a suitable mathematical model where the occurrence of connections between nodes is random according to a certain probability law. Parallel to the development of the random network theory other models, i.e. Watts-Strogatz and Barabási-Albert, were put forward by other authors. All of the mentioned models of random networks are considered classical. Later on, the research of such real random networks as brain neural network, DNA structure, cell protein interactions and others has shown that some of these have a unique structure on the basis of which a new class of random networks has been defined, block-hierarchical, and RBH (Regular Block-Hierarchical) and NRBH (Non Regular Block-Hierarchical) models were put forward. For research of random networks there should be software tools for the computation of their topological properties which are average node degree and node degree distribution, average path length and diameter, clustering coefficients, connected component distribution and others. The study of the dynamics of the network development plays a special role. Complex network structures, as a rule, have a great number of nodes and connections which is a serious obstacle in developing computation software tools. As researches of random networks are conducted on a set of networks, the problem to develop highly efficient algorithms for the computation of topological properties arises. The structure of block-hierarchical networks has a number of specificities which has allowed us to develop new effective algorithms for the computation of their topological properties. The above-mentioned conditions make the development of xRandNet automated system relevant as similar existing systems are directed at working with classical models and do not have special tools intended for researches on random networks. The aim of the dissertation is the development of an automated system intended for the efficient analysis of block-hierarchical random networks, the study of their topological properties and the comparison with the famous behavior of classical models. The dissertation pursues the following objectives: Development of efficient algorithms for the computation of topological properties of block-hierarchical random networks; Development of an automated system intended for the automation of the generation, analysis and research of both classical and block-hierarchical random networks; Research on main topological properties of regular block-hierarchical random networks through the developed automated system. The main results of the dissertation are the following: A new data structure, connectivity tree, has been developed for the efficient representation of block-hierarchical random networks in memory [1]. For the computation of topological properties of block-hierarchical random networks new efficient algorithms have been developed [1-3, 5]. The xRandNet automated system has been developed which serves as a universal tool for the automation of research on random networks [4].Диссертационная работа посвящена разработке эффективных алгоритмов для вычисления топологических характеристик блочно-иерархических сетей и автоматизированной системы xRandNet (Extended Random Networks), позволяющей проводить различные исследования случайных сетей. Сложные сетевые структуры описывают широкий спектр высокотехнологических и интеллектуальных систем. Вопросами изучения топологии сложных сетей и динамики их изменений в течение времени занимается теория случайных сетей, которая была основана венгерскими математиками Полом Эрдешем и Альфредом Реньи. В 1959 году они предложили модель случайной сети Erdős-Rényi , предположив, что адекватной математической моделью для сложных систем является случайная сеть, в которой связи между узлами появляются случайным образом, по определенному вероятностному правилу. С развитием теории случайных сетей другими авторами были предложены также модели Watts-Strogatz и Barabási-Albert. Перечисленные модели случайных сетей считаются классическими. Изучение реальных случайных сетей, таких как сети нейронов мозга, структура ДНК, взаимосвязи между белками внутри клетки и т.д., показало, что некоторые из них имеют специфичную структуру, на основе чего был определен новый класс случайных сетей – блочно-иерархический, и предложены модели RBH (Regular Block-Hierarchical) и NRBH (Non Regular Block-Hierarchical) . При изучении случайных сетей важно иметь программные средства для вычисления их топологических характеристик, таких как средняя степень узлов и распределение степеней, средняя длина пути и диаметр сети, коэффициент кластеризации, распределение связных компонент и т.д. Особое место занимает изучение динамики развития сетей. Сложные сетевые структуры, как правило, имеют большое число узлов и связей, что является серьезной проблемой для разработки программных вычислительных средств. Так как исследуются ансамбли случайных сетей, то возникает проблема создания эффективных алгоритмов для вычисления топологических характеристик. Структура блочно-иерархических сетей имеет ряд особенностей, что дало нам возможность разработать новые эффективные алгоритмы для вычисления их топологических характеристик. Исходя из выше изложенного, разработка программной системы xRandNet, предназначенной для генерации случайных сетей как блочно-иерархических, так и классических моделей, проведения анализа топологических характеристик и исследования динамики развития сетей, является актуальной проблемой. Существующие автоматизированные системы, которые работают со случайными сетями, в основном ориентированы на классические модели и не имеют средств для проведения специальных исследований над ними. Целью диссертационной работы является разработка программной системы для эффективного анализа блочно-иерархическиx случайныx сетeй, проведения исследований топологических свойств и их сравнения с уже известным поведением классических моделей. Исходя из указанной цели, в работе поставлены и решены следующие задачи: Разработка эффективных алгоритмов для вычисления топологических характеристик блочно-иерархических сетей. Разработка автоматизированной системы для генерации, анализа и исследования случайных сетей как классических, так и блочно-иерархических моделей. Исследование основных топологических характеристик регулярных блочно-иерархических случайных сетей, с использованием разработанной автоматизированной системы. Теоретической основой диссертационной работы послужили работы ведущих специалистов в области теории сетей и её применения в различных областях науки. При разработке алгоритмов были использованы методы дискретной математики и теории графов, а также основные методы временных оценок алгоритмов. При разработке автоматизированной системы xRandNet применен метод сравнительного анализа находящихся в свободном доступе программных решений, изучены их преимущества и недостатки. Научная новизна. Разработаны новые эффективные алгоритмы для вычисления топологических свойств блочно-иерархических случайных сетей. Разработана программная система, которая автоматизирует процесс генерации, анализа и проведения комплекса исследований классических и блочно-иерархических случайных сетей. Исследованы основные топологические характеристики регулярных блочно-иерархических случайных сетей, с использованием разработанной автоматизированной системы. Практическая ценность и внедрение результатов исследования. Разработанная программная система xRandNet используется для исследования топологических характеристик случайных сетей, а также динамики развития случайной сети. Автоматизированная система xRandNet внедрена в Институте химической физики им. Н.Н. Семенова РАН. Основные положения, выносимые на защиту. Разработанные эффективные алгоритмы для вычисления топологических характеристик блочно-иерархических случайных сетей. Разработанная автоматизированная система xRandNet для генерации, анализа и исследования случайных сетей. Экспериментальные результаты исследования основных топологических характеристик регулярных блочно-иерархических случайных сетей, полученные с использованием системы xRandNet. Апробация результатов работы. Основные результаты диссертации были представлены на: международной конференции "Computer science and Information Technologies" – CSIT - 2013 (Ереван, Армения, 2013); "Научной школе-семинаре" – Цмакаог - 2013 (Цмакаог, Республика Арцаха, 2013); "Молодежном научно-образовательном форуме" – Цмакаог - 2017 (Цмакаог, Республика Арцаха, 2017); семинаре кафедры Программирования и информационных технологий, ЕГУ (Ереван, Армения, 2018); Публикации. Основные результаты диссертационной работы отражены в семи научных трудах, список которых представлен в конце автореферата. Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, основных выводов, списка использованной литературы из 104 наименований и 3 приложений. Основной объем работы составляет 138 страниц, включая 27 рисунков, 7 графиков и 13 таблиц. Диссертация написана на армянском языке. Во введении обоснована актуальность темы, сформулированы цель и основные задачи диссертационной работы, представлены научная новизна, практическая ценность, основные научные положения, выносимые на защиту. Также кратко описаны некоторые примеры сложных систем и их представление случайными сетями. В первой главе представлены теоретические основы данной работы и основы теории случайных сетей. В разделе 1.1 дано определение случайной сети, описаны некоторые известные сложные системы и их представление случайными сетями. В разделе 1.2 определены основные топологические характеристики сетей – степень узла, средняя степень и распределение степеней узлов, средняя длина пути, диаметр и распределение расстояний между узлами, распределения полных и связанных компонент в сети, распределения циклов и поддеревьев в сети, глобальный коэффициент кластеризации и распределение локальных коэффициентов кластеризации в сети. В разделе 1.3 изучены известные модели случайных сетей – модель Erdős-Rényi (подраздел 1.3.1), модель Watts-Strogatz (подраздел 1.3.2) и модель Barabási-Albert (подраздел 1.3.3), а также особенности поведения топологических характеристик этих моделей. В разделе 1.4 описаны рассмотренные в данной работе виды исследований, которые проводятся над сетями в рамках теории случайных сетей. Исследование развития или эволюции случайной сети предполагает рассмотрение процесса направленной эволюции сетей по выбранному глобальному свойству, например, числа циклов порядка 3, при "замораживании" одной из степеней свободы. Как правило, для семплирования используется алгоритм Метрополиса–Гастингса. Для некоторой модели случайной сети вероятностным назовем параметр, с помощью которого определяется вероятность появления связей между узлами сети. В теории случайных сетей одним из актуальных вопросов является нахождение порогового значения вероятностного параметра, при котором в сети появляется выбранное свойство Такое значение вероятностного параметра также называется критическим. Нахождение критического значения вероятностного параметра является целью исследования порогового значения. При моделировании некоторых систем, например сетей нейронов, с помощью случайных сетей возникает интерес к исследованию распространения некоторого свойства узлов, например активности нейронов, в сети. Для проведения такого исследования каждому узлу в сети приписывается некоторое состояние – активное или неактивное, и предполагается, что это состояние меняется в течение времени путем простого угасания или передачи активного состояния некоторому множеству соседей. Исследование многих реальных сетей, от социальных до биологических, показало, что они имеют структурную особенность –появление сообществ. Сообщество определяется как связанная подсеть, которая имеет высокую локальную плотность –число внутренних связей в сообществе намного больше числа связей, соединяющих узлы сообщества с остальными узлами сети. В структурном смысле, сообщества являются отдельными и самостоятельными объектами внутри сети, имеющими такое поведение топологических характеристик, которое сильно отличается от поведения тех же характеристик для всей сети. В теории случайных сетей одним из актуальных вопросов является выявление таких сообществ в сети и изучение их топологических характеристик. В разделе 1.5 перечислены и кратко описаны существующие программные системы, которые работают с сетями вообще и со случайными сетями в частности. Основные из них следующие: GraphCrunch, mfinder, MAVisto. Во второй главе даны определения регулярных и нерегулярных блочно-иерархических случайных сетей и соответствующих им моделей RBH и NRBH. В разделе 2.1 для заданных натуральных чисел и определяется класс регулярных блочно-иерархических случайных сетей . Число узлов сети равно . В процессе конструирования сети используется действительное число. На каждом уровне формируются новые кластеры (подсети) посредством объединения уже построенных на предыдущем уровне кластеров и связывания некоторых из них с вероятностью, определенной формулой , в результате чего образуются новые связи сети. Определяется модель RBH с параметрами и типом связи кластеров – "все со всеми" или " -связей". Процесс построения сети этой модели представляет собой вышеописанное конструирование по уровням регулярной блочно-иерархической сети с учетем типа связи кластеров.

      Item Type: Thesis (PhD)
      Additional Information: Разработка системы автоматизированного исследования топологических характеристик блочно-иерархических сетей. Development of the system of automated research on topological properties of block-hierarchical networks.
      Uncontrolled Keywords: Кочарян Ани Гагиковна, Kocharyan Ani G.
      Subjects: Earth Science
      Divisions: UNSPECIFIED
      Depositing User: NLA Circ. Dpt.
      Date Deposited: 26 Sep 2018 16:48
      Last Modified: 27 Sep 2018 15:58
      URI: http://etd.asj-oa.am/id/eprint/7660

      Actions (login required)

      View Item