64160

Разработка и исследование ускоренного алгоритма калибровки моделей больших сетей по коэффициенту кластеризации

Дипломная

Информатика, кибернетика и программирование

Целью работы является изучение алгоритмов генерации случайных графов, разработка нового алгоритма, его реализация, проведение необходимых испытаний. В работе изложены необходимые понятия из теории случайных графов, подробно разбираются методы генерации графов Барабаши-Альберт, Эрдеша-Реньи, Уатса-Строгатса...

Русский

2014-07-02

1.56 MB

28 чел.

Министерство образования и науки РФ

ФГБОУ ВПО «Омский государственный технический университет»

Кафедра «Автоматизированные системы обработки информации и управления»

     

Допускается к защите      

        Зав. кафедрой АСОИУ,    

    док-р техн. наук, проф.    

__________ А. В. Никонов  

«19» июня 2013 г.      

БАКАЛАВРСКАЯ РАБОТА

на тему «Разработка и исследование ускоренного алгоритма калибровки моделей больших сетей по коэффициенту кластеризации»

студентки Овчинниковой Елены Владимировны группы ИВТ-449

Пояснительная записка

Шифр работы: БР–02068999–43–08 ПЗ

Направление 230100.62       

                                                                                                                                         Научный руководитель,

док-р техн. наук                        

 ____________ В.Н. Задорожный

«19» июня 2013 г.

Разработала студентка

____________ Е.В. Овчинникова

«19» июня 2013 г.

Нормоконтролёр:

____________ В.Н. Задорожный

             «19» июня 2013 г.

Омск 2013




Аннотация

Целью работы является изучение алгоритмов генерации случайных графов,  разработка нового алгоритма, его реализация, проведение необходимых испытаний.

В работе изложены необходимые понятия из теории случайных графов, подробно разбираются методы генерации графов Барабаши-Альберт, Эрдеша-Реньи, Уатса-Строгатса,  графов с нелинейным правилом предпочтительного связывания. Делаются выводы о возможностях калибровки генераторов по коэффициенту кластеризации. Приводится описание разработанного ускоренного алгоритма для генерации графов с нелинейным правилом предпочтительного связывания, с помощью предложенного алгоритма возможна калибровка графов, как по распределению степени связности вершин, так и по коэффициенту кластеризации. В конце работы проведён анализ разработанного генератора. Полученный алгоритм реализован на языке Java и внедряется в систему имитационного моделирования Simbigrph.


Определения, обозначения, сокращения

АС – автономная сеть

БС – большие сети

БСВ – большая случайная величина

БСС – большая стохастическая сеть

граф БА – граф Барабаши-Альберт

граф с НППС – граф с нелинейным правилом предпочтительного связывания

ДСВ – дискретная случайная величина

ПС – предпочтительное связывание

РСС – распределение степени связности

сл.г. – случайный граф


Содержание

Введение 6

1 Аналитический обзор и постановка задачи 8

1.1 Структурные характеристики случайных графов 8

1.2 Некоторые модели случайных графов 9

1.2.1 Модель графа Барабаши  Альберт 9

1.2.2 Модель графа Уаттса – Строгатца 10

1.3 Модель графа с НППС 12

1.4 Обзор аналогов 13

1.4.1 Ускоренный метод генерации графа БА и графа с НППС 13

1.4.2 Метод сепарабельной реконфигурации по коэффициенту кластеризации 21

1.5 Выводы по главе и постановка задачи ВКР 22

2 Разработка алгоритма генератора графа с НППС с возможностью калибровки по коэффициенту кластеризации 24

2.1 Алгоритм генерации графа с НППС с возможностью калибровки по коэффициенту кластеризации 24

2.2. Модификация разработанного алгоритма 27

2.3 Демонстрация работы алгоритма 29

3 Аспекты программной реализации в системе имитационного моделирования Simbigraph 31

Заключение 36

Список использованных источников 38

Приложение А 40


Введение

В современном мире можно обнаружить множество различных сетей. Это и биологические сети, сети дорог, телефонные сети, нейронные сети, сети интернет.

С геометрической точки зрения, сеть представляет собой граф, т.е. множество вершин, связанных друг с другом рёбрами, поэтому исследование сетей неразрывно связано с теорией графов. Теория графов возникла в восемнадцатом веке в работе Леонарда Эйлера, которого в основном интересовали небольшие графы с высокой степенью регулярности.

В двадцатом веке в область интересов ученых вошли так называемые случайные графы, т.е. графы, которые генерируются в результате некоторого случайного процесса. Теория случайных графов была представлена Полом Эрдешом и Альфредом Реньи, после того, как Эрдеш открыл, что вероятностные методы часто оказываются полезными в проблемах теории графов. Генерация графа Эрдеша-Реньи очень проста: нужно с некоторой вероятностью p распределить рёбра между всеми вершинами. Тем не менее, эта модель активно использовалась в теории перколяции и теории критических явлений, поскольку обладает критическими свойствами, например, существует такая критическая вероятность pc связывания вершин, ниже которой сеть распадается на множество несвязных компонент, а выше – образуется так называемый стягивающий кластер. Граф Эрдеша-Реньи, по существу, являлся самым популярным и единственным случайным графом с 50-х годов прошлого века.

Ситуация поменялась за последние десятилетия. Причиной этому стал тот факт, что большое значение приобрели сеть интернет и «всемирная паутина», сеть ссылок веб-страниц, имеющая английскую аббревиатуру WWWWorld Wide Web. В то же время возможности вычислительной техники значительно возросли, позволив обрабатывать большие массивы данных, и тем самым строить модели таких сетей как сеть белковых взаимодействий, сеть генных последовательностей, социальные сети и т.д. А поскольку стало возможным получить мгновенный снимок сети, например, подсети WWW и представить его в виде графа (каждый отдельный сайт будет вершинной графа, а ссылки между ними будут являться его рёбрами2), то встал вопрос анализа этих графов.  Однако интернет и WWW являются постоянно изменяющейся структурой, появилось желание исследовать их с помощью случайных графов. Но детальное исследование перечисленных сетей показало, что, вопреки ожиданиям, эти сети очень сильно отличаются от графа Эрдеша-Реньи.

В результате стали появляться графовые модели сетей с различной степенью адекватности моделирующие динамику, рост и структурные характеристики сетей. Так, широко распространенное степенное распределение вероятностей степени связности узлов, а также некоторые свойства динамики сетей предложили А.Барабаши и Р.Альберт (1999), их граф генерируется на основе правила «предпочтительного связывания». Также действующие модели предложили Д. Уаттс и С. Строгатц (1998), М. Ньюман (2000), С. Н. Дороговцев, Дж. Мендес и А. Н. Самухин (2001), К. Купер и   А. Фрези (2002), B. Боллобас (2001), Ф. Чанг и Л. Лу (2006), Ю. Лесковец (2006), В. Н. Задорожный (2010). Но, несмотря на большое разнообразие моделей, ни одна из них не даёт полного соответствия с реальной сетью. В частности, почти все модели отличаются от моделируемых сетей по коэффициенту кластеризации графа. Получение случайных графов с заданной характеристикой является основной задачей данной работы.

Следует также отметить, что программы для анализа графов и их генерации оказываются весьма медлительными, поскольку приходится генерировать большие графы, состоящие из сотен тысяч вершин и ребер. Поэтому большое значение имеет необходимость разработки ускоренных алгоритмов.


1 Аналитический обзор и постановка задачи

В данном разделе производится обзор существующих методов и по итогам ставится задача исследования.

В первом параграфе этого раздела описаны основные понятия теории сетей. Приводятся их необходимые описания и определения.

Во втором параграфе производится обзор существующих графовых моделей, вводятся понятия случайных графов Барабаши-Альберт, Эрдеша-Реньи, Уаттса-Строгатца, описаны правила их генерации.

В третьем параграфе вводится понятие случайного графа с нелинейным правилом предпочтительного связывания (НППС), который был предложен Задорожным В.Н. в 2010 году.

В четвёртом параграфе обсуждаются алгоритмы ускоренной генерации графов с НППС, калибровки графовых моделей для реализации заданного коэффициента кластеризации.

В конце раздела, исходя из представленной информации, ставится задача данного исследования.

1.1 Структурные характеристики случайных графов

В математической теории графов граф – это совокупность непустого множества вершин и набор пар вершин (связей между вершинами).

Объекты представляются как вершины, или узлы графа, а связи  как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах [1].

Степень связности одной вершины равна количеству рёбер присоединённых к этой вершине. Также часто используется понятие средней степени связности графа. Данное значение можно получить, если поделить число рёбер в графе на число вершин это же графа и умножить на два, поскольку одно ребро связывает два узла.

Большие сети – это сети, содержащие тысячи вершин и связей между ними.

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

Рассмотрим первую характеристику – диаметр графа. Диаметр графа определяет максимальное расстояние (измеряемое в числе ребер) между вершинами в неориентированном графе, полученное в результате анализа расстояний между всеми парами вершин. С понятием диаметра графа связан эффект «Тесного мира», также известный, как  правило «шести рукопожатий». Это правило означает, что перебирая круг своих ближайших знакомых, затем людей, знающих наших ближайших знакомых и т.д. любой человек опосредовано знаком с любым другим человеком в мире. Причём, как правило, число элементов в цепи не превышает 6.

Другой, не менее важной характеристикой графа является коэффициент кластеризации. Коэффициент кластеризации C в общем случае определяется как утроенное отношение среднего числа n «треугольников» (три вершины, связанные тремя рёбрами) в графе к среднему числу nV «вилок» (число путей длины 2).

Калибровка графа позволяет  построить модель графа так, чтобы сохранить распределение степени связности (РСС) вершин, путём подбора других параметров, в зависимости от поставленных целей.

1.2 Некоторые модели случайных графов

В данной главе рассматриваются три основных модели случайных графов.

Первая модель была предложена в 1999 г. Альбертом Барабаши и Реки Альберт, которые независимо открыли процесс предпочтительного присоединения.

Другой рассмотренной моделью является модель Дункана Уаттса и Стивена Строгатца предложенная ими в 1998 г. Ими был обнаружен эффект, названный «тесным миром».

Третьей описанной моделью является модель Эрдеша-Реньи для генерации случайных графов. Она была предложена на рубеже 50-х и 60-х годов.

1.2.1 Модель графа Барабаши  Альберт

Модель графа Барабаши – Альберт (граф БА) представляет собой алгоритм генерации случайных безмасштабных сетей с использованием правила предпочтительного связывания (ПС).

Правило предпочтительного связывания говорит, что чем большую степень связности имеет вершина, тем выше вероятность присоединения к ней новых вершин. Если для присоединения выбирать вершину случайным образом, то вероятность выбора определённой вершины будет пропорциональна её степени связности. Данное правило соответствует принципу «богатый становится богаче».

Данный граф выращивается из небольшого графа-затравки, у которого степень связности каждой вершины должны быть не меньше единицы.

Каждая новая вершина присоединяется к уже существующим вершинам с вероятностью пропорциональной степени связности этих вершин. Вероятность pi того, что вершина присоединится к i-ой вершине равна:

,  (1)

где ki –степень i-ой вершины [2].

1.2.2 Модель графа Уаттса – Строгатца

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

Д.Уаттс и С. Строгатц обнаружили феномен, характерный для многих реальных сетей, названный эффектом «тесного мира».

Модель «тесного мира» состоит в том, что перебирая круг своих ближайших знакомых, затем людей, знающих наших ближайших знакомых (но не знающих нас непосредственно), и т.д. легко убедиться в следующем: достаточно проследить за небольшим числом цепочек таких знакомств, чтобы понять, что любой из нас опосредовано знаком с любым членом общества. В этом смысле наш мир является тесным, откуда и пошло название этой модели [3].

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

При исследовании этого феномена ими была предложена процедура построения наглядной модели сети, которой присущ этот феномен.

Чтобы построить сеть «тесного мира», следует начать с регулярной циклической решётки с N вершинами, каждая из которых соединена с k ближайшими соседями в каждом направлении. Для каждой вершины задаётся 2k связей, где >> log2 (N) >> 1. Затем каждое ребро пересоединяется со случайной парой вершин с вероятностью p.

При условии p = 0 получается упорядоченная решётка с большим количеством циклов и большими расстояниями, а при условии p → 1 сеть становится случайным графом с короткими расстояниями, и малым количеством циклов.

Данная сеть может иметь три состояния:

− регулярная сеть, каждый узел которой соединён с четырьмя соседними;

− та же сеть, у которой некоторые «ближние» связи случайным образом заменены более «дальними» (именно в этом случае возникает феномен «тесного мира»);

− случайная сеть, в которой количество подобных замен превысило некоторый установленный порог [4].

На рисунке 1 представлена иллюстрация данной модели.

Рисунок 1 – Модель графа Уаттса-Строгатса [4]

Параметр p в данной модели отвечает за переброс рёбер в случайные положения. Так по рисунку 1 можно увидеть трансформацию из регулярной цепочки в модель «тесного мира», а затем в случайный граф.

Компьютерная модель «малого мира» была разработана Уаттсом и Строгатсом несколькими годами позже.

Модель Уаттса-Строгатса представляет собой модель генерации случайного графа, имеющего высокий коэффициент кластеризации вершин [3] и относительно небольшую среднюю длину пути.

1.2.3 Модель графа Эрдеша-Реньи

В теории графов модель Эрдеша – Реньи представляет собой модель для генерации случайного графа с постоянной вероятностью появления ребра между двумя вершинами независимо от других ребер. Согласно данной модели, граф конструируется с помощью соединения пар вершин случайным образом. Каждое ребро включается в граф с вероятностью p независимо для каждой пары вершин. С ростом p от 0 до 1 граф становится все более насыщенным ребрами. При p = 0 имеем пустой граф (граф, не имеющий ребер), при p = 1 – полносвязный граф. При фиксированном количестве вершин в графе вероятность p – единственный входной параметр модели Эрдеша – Реньи.

Простота модели Эрдеша – Реньи случайного графа позволяет получать различные аналитические оценки. Однако стоит отметить, что модель в среднем не воспроизводит такие типичные свойства реальных сетей, как степень вершин, величина коэффициента кластеризации и длины пути. [5]

1.3 Модель графа с НППС

Случайные графы с НППС были впервые предложены В.Н. Задорожным в 2010 году в статье [6]. Данные графы генерируются на основе правила «предпочтительного связывания» («богатый становится богаче»). Граф с НППС выращивается из графа-затравки итерационно, путём добавления вершин со случайным числом рёбер r, с заданной функцией предпочтения f ≥0, зависящей от степени связности ki вершины. Вероятность pi присоединения свободным концом нового ребра к уже существующей вершине графа зависит от функции предпочтения и вычисляется по формуле (2):

.  (2)

Модели графов с НППС в последнее время получили широкое развитие. В работе [7] были найдены эффективные способы генерации графа. В [6, 8] представлены такие способы калибровки графов, которые позволяют при заданном распределении вероятностей r, путём подбора функции предпочтения f(k) генерировать граф с требуемым распределением степени связности вершин.

Но, не смотря на точное совпадение средней степени связности графа, данная модель во многих случаях не может обеспечить достаточно точное совпадение всех остальных структурных характеристик.

1.4 Обзор аналогов

В данном разделе производится небольшой обзор существующих алгоритмов построения графовых моделей и их калибровки.

Рассматриваются алгоритм генерации графа БА и ускоренный метод генерации графа с НППС, а также метод сепарабельной реконфигурации. Представляются графики распределения степени связности графов. Описываются результаты сравнений различных характеристик реальных сетей и графовых моделей.

1.4.1 Ускоренный метод генерации графа БА и графа с НППС

Алгоритм данного метода был представлен в [9].

Граф БА генерируется из небольшого графа-затравки путём добавления новых вершин с фиксированным числом рёбер m ≥ 1. Свободный конец нового ребра присоединяется в соответствии с формулой (3):

, j = 1,…, N,  (3)

где N – текущее число вершин в графе.

Из формулы видно, что чем больше степень связности у вершины, тем выше вероятность её выбора.

На рисунке 2 представлена блок схема этого алгоритма.

Рисунок 2 – Схема программы генерации графа БА [9]

Выбор вершин для присоединения может быть выполнен на основе стандартного подхода разыгрывания дискретной случайной величины (ДСВ). Данный подход можно описать так. Пусть задана некоторая система непересекающихся событий {А1, … , Аn}, заключающихся в выборе очередной вершины (всего в графе n вершин). Вероятности выбора вершин события {А1, …, Аn} равны соответственно p1, … , pn, (p1 + p2 + … + pn = 1). При построении алгоритма отрезок [0,1) необходимо разбить на n интервалов длиной p1, … , pn, и отслеживать попадание сгенерированного значения большой случайной величины (БСВ) z в соответствующий интервал. Программная реализация данного алгоритма в [10] была названа БА_ДСВ (m, N, G).

В генератор БА_ДСВ (m, N, G) передаётся параметр m, определяющий число рёбер, добавляемых на каждом шаге, и число вершин N в генерируемом графе. При генерации передаётся также граф-затравка G, содержащий M вершин (MN).

На каждом шаге генерации добавляется новая вершина vi (Mi < N) c m рёбрами. Добавления m рёбер являются независимыми событиями, поэтому каждая следующая выбранная для присоединения вершина добавляется в специальный список lst, пока не будут выбраны все m вершин. После выбора всех m вершин (выход из цикла) в граф G «одновременно» добавляются m новых рёбер e = (vi, vlst[h]), между добавленной вершиной vi и вершинами из списка vlst[h] (p = 1, … , m). Далее список lst очищается, и алгоритм переходит к очередному шагу добавления новой вершины, пока не будут добавлены все (N M) вершин.

Основная трудоёмкость рассмотренного алгоритма заключается в количестве итераций при выборе вершины для присоединения, поскольку в исследуемых сетях таких вершин сотни тысяч. Среднее число итераций при выборе вершин в графе, содержащем n вершин при условии, что степени вершин при их переборе распределены случайно, равно n / 2 [10].

Данный алгоритм можно ускорить, если разбить всё его множество вершин на отдельные слои. Слой – это подмножество вершин, которые имеют одинаковую степень связности.

После того, как всё множество вершин разбито на слои, происходит выбор новой вершины для присоединения. Сначала случайным образом выбирается номер слоя, а затем из этого слоя равновероятно выбирается вершина.

Схема данного алгоритма представлена на рисунке 3.

Рисунок 3 – Схема программы ускоренного метода генерации графа БА и графа с НППС [10]

Основная трудоёмкость данного алгоритма заключается в количестве итераций, которые необходимо выполнить для выбора слоя вершин. Количество итераций зависит от числа вершин в графе: чем больше граф, тем труднее выполнить данный алгоритм.

Генерация графа БА размером 100 тыс. вершин базовым алгоритмом занимает около трёх часов.

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

  

Рисунок 4 – РСС (слева на право: РСС калиброванного графа и сети автономных систем интернет; РСС калиброванного графа и сети маршрутизаторов интернет; РСС калиброванного графа и сети участия актёров в общих фильмах) [6]

Первый график на рисунке 4 характеризует качество идентификации сети автономных систем интернет по данным [11] (число узлов и рёбер равны соответственно N = 22963, R = 48436).

Второй график на данном рисунке характеризует качество идентификации сети маршрутизаторов интернет по данным [12] (N = 124651, R = 207214). Параметры генератора: , , , , , .

Последний график характеризует идентификацию сети участия актеров в общих фильмах [13] (N = 511416 – без изолированных узлов, R = 1463331). Два соответствующих актерам узла связаны ребром, если эти актеры снимались в одном фильме. Здесь , численно фиксированы , и при k > 10 общая формула весов имеет вид .

Однако соответствие по РСС сети и ее модели не означает, что эти структуры соответствуют по другим структурным характеристикам, а модель является адекватной. Так на IV региональной научно-практической конференции был представлен доклад [14], в котором особое внимание уделялось исследованию диаметра сл.г. В данной работе был проведён следующий эксперимент. Было выбрано 7 реальных сетей с уже известными параметрами. Для каждой из этих сетей было построено несколько различных модели сл.г. и подсчитан диаметр, как реальной сети, так и моделей. Длина выборки равнялась 10. Результаты этого эксперимента представлены в таблице 1.

Таблица 1 – Сравнение диаметра у реальных сетей и их моделей

Имя сети

Вершины

Рёбра

Диаметр сети

БА

Граф Эрдеша-Реньи

Граф Уаттса-Строгатца

НППС

max

min

ср.

max

min

ср.

p=0

p=1

USAir97

332

2126

6

5

9

7

6

7

7

24

4

5

PGPgiantcomp

10680

24340

24

11

15

13

29

32

31

2470

14

8

P2p-Gnutella31

62586

147892

31

14

19

16

38

40

39

15647

16

9

Oregon2_01052

11461

32731

9

12

15

13

18

22

19

1910

10

7

My_polBlog

1491

19089

9

8

12

10

5

5

5

58

4

8

myAs

22963

48436

11

13

15

14

31

6

3

741

15

5

Email-Enron

36692

367662

13

15

17

16

8

8

8

1835

5

10

Из этой таблицы видно, что среднее значение диаметра графа БА практически совпадает только в двух случаях, в двух других случаях диаметр графа БА меньше диаметра реальной сети почти в два раза. В модели графа Эрдеша-Реньи для сети автономных систем диаметр модели меньше почти в четыре раза. Диаметр графа в моделях Уаттса-Строгантца при p = 0 имеет чрезмерно большое значение и совершенно не соответствует диаметру реальных сетей. Что касается графа с НППС, то тут значения диаметра в целом получаются значительно меньше.

Таким образом, из таблицы 1 можно сделать вывод, что ни одна из моделей не  соответствует реальным сетям по такой важной характеристики как диаметр графа.

В работе [15] производится исследование соответствия графовых моделей и их сетей на количество подграфов в виде квадрата. Квадратом назван подграф из четырёх вершин и четырёх рёбер, связанных в кольцо.

Данные, полученные в [15], показывают, что при одинаковом числе узлов N и ребер E, число квадратов в графах БА, конфигурационных графах, графах с НППС оказывается значительно меньше,  чем в реальных сетях. Эти данные представлены ниже в таблице 2.

Конфигурационная модель генерации графа БА описана в  [3]. Её можно представить следующим образом.

Пусть дано распределение Pk степени связности N вершин.

1. Помечаем степенями связности ki все N вершин Map  <vi, ki> (i = 1, N).

2. Рисуем «хвосты рёбер» в соответствии с полученными числами ki.

3. Распределяем «хвосты ребер» на пары случайно равновероятно, формируя ребра между вершинами.

Таблица 2 – Число квадратов в реальных сетях (n□реал), в графе БА (nграфБА), в конфигурационной модели (nконф.м.), в графе с НППС (nграфНППС)

Название сети

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

Теоретические величины

N

E

 n□реал

m

nграфБА 

nконф.м.

nграфНППС

Сеть маршрутизаторов

124651

207217

562687

2

2285

10107

33030

Сеть пользователей программы PGP

10680

24340

1010957

3

1070

9252

19191

Сеть автономных систем Интернет

22963

48436

3088900

2

1179

3860

21361

Сеть адресов электронной почты

36692

183831

36262047

5

61950

353547

997506

Из таблицы 2 видно, что модель графа БА содержит наименьшее число квадратов и наиболее сильно отличается от числа квадратов в реальных сетях. Число квадратов в конфигурационной модели в разы больше, но всё же достаточно. Наибольшим числом квадратов обладает граф с НППС, однако их всё равно на порядки меньше, чем в реальных сетях.

С помощью программы предложенной в [16] нетрудно рассчитать значения коэффициента кластеризации в сетях и их графовых моделях. Так в таблице 3 приводятся данные расчёта коэффициента кластеризации сети автономных систем интернет и её моделей. Графа БА сгенерирован с параметром средней степени связности m = 2. Граф с НППС был откалиброванным по заданному эмпирическому РСС. Количество вершин в данных моделях случайных графов соответствует числу узлов в реальной сети автономных систем: 22963 узла.

Таблица 3  Расчеты коэффициента кластеризации в различных сетях

Имя сети

Значение коэффициента кластеризации

Сеть автономных  систем

0.01124

Граф БА

0,00063

Граф с НППС

0.00502

Из таблицы 3 можно увидеть, что значение коэффициента кластеризации в модели графа БА отличается от значения коэффициента кластеризации в реальной сети на несколько порядков. Граф, сгенерированный в соответствии с НППС, имеет намного большее значение коэффициента кластеризации. Однако, несмотря на то, что значение параметра значительно увеличилось, оно всё равно отличается от значения этого же параметра в реальной сети более чем в два раза.

В работе [10] приведены данные об исследовании других реальных сетей  и сравнении их с моделью графа БА по коэффициенту кластеризации. Также было установлено, что в реальных сетях эта структурная характеристика на порядки больше её показателя в графах БА. Результаты данного исследования представлены в таблице 4.

Таблица 4 – Коэффициент кластеризации в реальных сетях (С∆реал) и в графе БА (СграфБАтеор) [10]

Название сети

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

Теоретические величины

С∆реал / СграфБАтеор

N

E

С∆реал

m

СграфБАтеор 

Сеть маршрутизаторов

124651

207217

0,03863

2

0,00185

20,86609994

Сеть пользователей программы PGP

10680

24340

0,37802

3

0,00232

163,0688118

Сеть автономных систем Интернет

22963

48436

0,01146

2

0,00076

14,93567203

Сеть адресов электронной почты

36692

367662

0,08531

10

0,00342

24,9348154

Сеть ссылок веб-страниц (GOOGLE)

875713

5105039

0,05523

5

0,00011

503,4293618

Сеть товаров интернет-магазина Amazon

262111

1234877

0,23608

4

0,00024

1001,232022

По таблице 4 видно, что хотя модель графа БА выращивалась для того же количества вершин N и с тем же параметром средней степени связности m значения коэффициента кластеризации в графе БА в некоторых случаях меньше на несколько порядков.

1.4.2 Метод сепарабельной реконфигурации по коэффициенту кластеризации

В исследовании [10] для решения проблемы заниженного коэффициента кластеризации в графовых моделях сетей предлагается алгоритм сепарабельной реконфигурации  по коэффициенту кластеризации. Сепарабельной реконфигурацией называется такое изменение структуры графа путём перераспределения рёбер, при котором не изменяется РСС вершин. Данный метод предполагает увеличение числа «треугольников» в графе. Иллюстрация этого алгоритма представлена на рисунке 5.

Рисунок 5 – Иллюстрация метода сепарабельной реконфигурации [10]

Для увеличения числа «треугольников» в графе циклически необходимое число раз используется следующая процедура.

1. Случайно выбираем ребро R, не входящее в треугольник. Определяем степени связности l и m вершин, инцидентных R.

2. Случайно выбираем вершину a и среди смежных ей вершин отыскиваем две несвязные вершины b и c. Если таких нет, возвращаемся к 2.

3. Определяем степени связности i и j вершин b и c соответственно. Ребро R переносим – ставим его между найденными вершинами b и c. В результате этой операции количество вершин со степенями связности l, m, i, j уменьшается, а количество вершин со степенями l – 1, m – 1, i + 1, j + 1 увеличивается (вследствие чего изменяется РСС).

4. Компенсируем изменение РСС:

− выбираем случайное ребро (отличное от R) со степенями связности i + 1, j + 1;

− находим случайные вершины со степенями связности l – 1, m – 1;

− перенося выбранное ребро, соединяем найденные вершины [9].

Данный метод позволяет изменять коэффициент кластеризации, сохраняя РСС. Одним из недостатков данного метода является то, что необходимо хранить ссылки на слои вершин в специальной структуре данных. На основе этого метода был разработан новый алгоритм, представленный в этой работе.

Предложенный метод [10] реконфигурации графа позволяет изменять его коэффициент кластеризации на несколько порядков и при этом сохранять его РСС.

Иллюстрация работы этого метода представлена на рисунке 6.

a)

б)

Рисунок 6 – Иллюстрация метода сепарабельной реконфигурации [10]

На рисунке 6а представлен граф БА, а на рисунке 6б представлен этот же граф БА, но уже после сепарабельной реконфигурации.

1.5 Выводы по главе и постановка задачи ВКР

Во время анализа предметной области было выявлено следующее.

1. Модель классического случайного графа (графа Эрдеша-Реньи) плохо воспроизводит некоторые свойства реальных сетей (степени вершин, величину коэффициента кластеризации и длины пути).

2. В 1999 году был предложен случайный граф Барабаши-Альберт (граф БА). Графы БА по своим структурным свойствам оказались более адекватными моделями реальных сетей, чем графы Эрдеша-Реньи.

3. Эффект «тесного мира» был обнаружен при исследовании реальных сетей и характеризует собой «правило шести рукопожатий» т.е. перебирая круг своих ближайших знакомых, затем людей, знающих наших ближайших знакомых и т.д. любой человек опосредовано знаком с любым другим человеком в мире. Причём, как правило, число элементов в цепи не превышает 6.

4. Графы  БА имеют небольшую среднюю длину пути между вершинами и таким образом также демонстрируют собой эффект «тесного мира».

5. В 2010 модель графа БА было обобщена в виде модели графов с НППС.

6. Графы с НППС позволяют генерировать графовые модели с заданным РСС вершин, путём подбора нужной функции предпочтения.

7. Существующие модели сл.г. обычно имеют значительное отличие от реальных сетей по диаметру и частоте появления подграфов.

8. Как правило, для графов НППС коэффициенты кластеризации в среднем меньше коэффициентов кластеризации в реальной сети.

9. Единственным методом калибровки графов по коэффициенту кластеризации является метод сепарабельной реконфигурации графа, но этот метод нарушает структуру, сформированную в результате применения графа с НППС.

10. При генерации графов с НППС конкретно не оговаривается, с какой вершиной нужно соединять новое ребро. Различные способы выбора данной вершины позволяют изменять структурные характеристики графа.

Таким образом, можно сформулировать задачи, которые необходимо выполнить в данной работе.

1. Разработка нового ускоренного алгоритма калибровки по коэффициенту кластеризации.

2. Программная реализация полученного алгоритма в системе моделирования Simbigraph.

 


2 Разработка алгоритма генератора графа с НППС с возможностью калибровки по коэффициенту кластеризации

В данном разделе происходит обзор разработанного алгоритма.

Первый параграф данного раздела посвящён описанию алгоритма генерации графа с НППС с возможностью калибровки по коэффициенту кластеризации. Здесь приводится его схема и её объяснение. Также приведён пример интерпретации алгоритма.

Второй параграф описывает модифицированный алгоритм генерации графа с НППС с возможностью калибровки по коэффициенту кластеризации, представлена схема этого алгоритма

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

2.1 Алгоритм генерации графа с НППС с возможностью калибровки по коэффициенту кластеризации

В классических графах c НППС не оговаривается, к какой именно вершине необходимо присоединить новое ребро при выращивании графа (считается, что это происходит случайно, равновероятно из всех вершин из данного слоя). От способа выбора этой вершины зависят значения структурных характеристик полученного графа, хотя распределение степени связности и остаётся прежним. Поэтому выбор новой вершины обычно зависит от цели моделирования.

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

Рассмотрим модифицированный алгоритм генерации графа с НППС [17]. Ниже представлено словесное описание разработанного алгоритма калибровки моделей БС по коэффициенту кластеризации.

Начало

G – генерируемый граф, изначально является небольшим графом-затравкой.

Цикл по добавляемым вершинам n = 1, …, N 

Разыгрывается случайное число ребер rk

Цикл по добавляемым вершинам c новой вершиной ребер k = 1, rk 

1. Вначале каждое из rk новых ребер в соответствии с ускоренным алгоритмом генерации графа ПС [3] выбирает вершину для присоединения своего свободного конца с вершиной из множества вершин с заданной степенью связности i (слоя) по правилу ,  j = 1, K, где K – число слоев в G

2. Затем, если (rk > 1) выполняется процедура случайного (равновероятного) выбора ребра e в графе G, связывающего вершины из выбранных слоев. К смежным к ребру е вершинам присоединяется 2 из r новых ребер, образуя гарантированный  треугольник из вершин

3. Остальные (rk  2) ребра выбирают вершины из соответствующих слоев равновероятно.

4. Добавляется вершин и rk ребер

Конец цикла по rk

Конец цикла по n

Конец алгоритма

Схема данного алгоритма представлена на рисунке 7. Листинг программы, реализующей данный алгоритм, представлен в приложении А.

Рисунок 7 – Схема программы генерации графа с НППС с калибровкой по коэффициенту кластеризации

Вначале задаётся случайное число рёбер r для присоединения и G – граф-затравка. Потом происходит перебор по всем вершинам, которые необходимо присоединить. Присоединяется новая вершина NewNode и разыгрывается число рёбер, по которому в дальнейшем происходит перебор. Далее, внутри этого цикла, сравнивается текущее значение счётчика j и цифры 2.

При j < 2 разыгрывается первый слой k1 по правилу НППС и происходит возврат в цикл. При j = 2 разыгрывается второй слой k2 по правилу НППС. Из начального графа G, исходя из ранее полученных значений k1 и k2, выбирается ребро е. К концам этого ребра и присоединяется новая вершина и происходит возврат в цикл. Если же j > 2, то для присоединения выбирается произвольная вершина.

Когда счётчик j становится равным r, присоединение рёбер повторяется для последующей вершины. Когда перебор произошёл по всем разыгранным вершинам, алгоритм прекращается.

Представленный алгоритм можно интерпретировать следующим образом. Пусть существует некая группа людей, которая представлена в виде графа. Некоторые люди внутри этой группы знают друг друга («знакомство» двух людей является ребром в этом графе). Присоединение новой вершины к графу сравнимо с попаданием ещё одного человека в этот коллектив. Причем он старается присоединиться хотя бы к одной паре, которая знает друг друга. Таким образом, образуется новый треугольник (человек влился в коллектив). Далее алгоритм повторяется с уже другим человеком (вершиной).

2.2. Модификация разработанного алгоритма

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

Схема данного алгоритма представлена на рисунке 8. Листинг программы, реализующей данный алгоритм, представлен в приложении А.

Рисунок 8 – Модификация ускоренного алгоритма

Вначале задаётся случайное число рёбер r для присоединения и G – граф-затравка. Потом происходит перебор по всем вершинам, которые необходимо присоединить. Присоединяется новая вершина NewNode и разыгрывается число рёбер, по которому в дальнейшем происходит перебор.

Перебор по рёбрам осуществляется в цикле, счётчик j которого может принимать значения от 1 до r/2, потому что происходит обработка именно пар вершин. Разыгрываются слои kj и kj + [r/2] по ППС. Через Map из начального графа G происходит выбор ребра l. Если такое ребро было найдено, тогда вершины v1 и v2 являются инцидентными. Если же такого ребра найдено не было, тогда вершины v1 и v2 выбираются случайным образом из слоёв kj и kj + [r/2]. Новая вершина соединяется с вершинами v1 и v2 и происходит повторение всех эти действий для последующего ребра.

По завершению этого цикла происходит проверка. Если изначально разыгранное число рёбер является нечётным числом, то оставшееся ребро присоединяется к случайной вершине из слоя kr от вершины NewNode.

Когда перебор произошёл по всем разыгранным вершинам, алгоритм прекращается.

2.3 Демонстрация работы алгоритма

Для демонстрации работы данного алгоритма была взята сеть автономных сетей интернет, мгновенный снимок которой был получен в 2006 году на проекте Oregon RouteViews [18]. Данные об этой сети были взяты из [11].

По данным этой реальной сети были построены модели графов с НППС и модели с использованием предложенного алгоритма.

В данной работе особый интерес представляли такие характеристики графа как его диаметр и коэффициент кластеризации. Поэтому в таблице 5 представлены характеристики графа именно по этим структурным характеристикам сл.г.

Из полученных результатов можно сделать вывод, что данный алгоритм увеличивает коэффициент кластеризации и диаметр, то есть приближает характеристики моделей к характеристикам реальных сетей.

Полученные результаты говорят о том, что данный алгоритм выполняет поставленные задачи.

Коэффициент кластеризации и диаметр графа взяты как среднее из 100 значений. Данные параметры моделей считались в пакете R.

Таблица 5 – Сравнение диаметра графа и коэффициента кластеризации в различных моделях сети автономных систем

Сеть

Коэффициент кластеризации

Диаметр графа

Мгновенный снимок сети Автономных систем

0.0111464

11

Граф БА, = 2

0.0008704

9.13

Граф БА, = 2, с модифицированным правилом выбором вершин

0.0938698

14.19

Граф ПС с распределением ребер в приращении  rk = {0/0.0000000, 1/0.3509441, 2/0.427474478, 3/0.082815651, 4/0.038862743, 5/0.099902998}

0.0032301

8.81

Граф ПС с распределением ребер в приращении  rk ={0/0.0000000, 1/0.442421898, 2/0.457278271, 3/0, 0.033445638, 4/0.01771394, 5/0.009795921, 6/0.005440743, 7/0.003764738, 8/0.00143948, 9/0.001057483, 10/0.001174982, 11/0.00129248, 12/0.001409978, 13/0.023764444}

0.0045669

9.07

Граф ПС с распределением ребер в приращении  rk = {0/0.0000000, 1/0.3509441, 2/0.427474478, 3/0.082815651, 4/0.038862743, 5/0.099902998}. Используется модифицированное правило выбора вершин.

0.0090506

11.97

Первый столбец таблицы 5 представляет собой описание характеризуемой сети.

Вначале идёт реальная сеть. Именно данные из этой строки являются образцом для сравнения.

Граф БА со средней степенью связности равной двум, это модель, построенная полностью по правилу построения графа БА.

Далее данный граф строился с применением разработанного алгоритма.

Последующие сети – это графы с НППС с различным распределением рёбер в приращении. Были получены разные графы путём изменения функции предпочтения. В фигурных скобках указанно, какое количество рёбер с какой вероятностью будет присоединяться.


3 Аспекты программной реализации в системе имитационного моделирования Simbigraph

Разработанный алгоритм реализован в системе моделирования SIMBIGRAPH, ориентированный на моделирование больших сетей. Ориентированность системы согласуется с выводами Европейского сообщества по развитию агентных вычислений AgentLink III, в соответствии с которыми приоритетным направлением развития теории агентного моделирования является разработка сетевых структур взаимодействия между агентами. В SIMBIGRAPH такие структуры реализуются и поддерживаются разнообразными графовыми моделями среды взаимодействия агентов. Система SIMBIGRAPH используется  для анализа сложных процессов в сетях. Архитектура системы основывается на имеющихся в области имитационного моделирования подходах и разработках российских и зарубежных исследователей. Аналогами системы моделирования SIMBIGRAPH являются такие известные системы имитационного моделирования, как SWARM, ASCAPE (Бруклинский институт, США), МАSON (Университет Джорджа Мейсона), NETLOGO (Северо-западный университет, США), RepastLogo (Чикагский университет, Аргонская национальная лаборатория, США), а также система имитационного моделирования AnyLogic (XJ Technologic, Россия). Все перечисленные аналоги обеспечивают некоторый уровень работы со структурами взаимодействия агентов, как правило, позволяя задавать такие структуры, как случайные графы и решетки.

Как и большинство перечисленных систем моделирования языком написания системы, а также внутренним языком разработки агентных моделей в разрабатываемой системе имитационного моделирования Simbigraph является язык программирования высокого уровня Java. Для программирования агентов приложений пользователю доступны классы сторонних библиотек: JAVA3D, JUNG, JFreeChart.

В отличие от перечисленных систем агентного моделирования сетевых структур SIMBIGRAPH предоставляет:

– широкий набор средств моделирования решёток (реализованы взаимодействия агентов в гексагональной, квадратной, треугольной, кубической решетках);

– широкий набор генераторов случайных графов,  средства калибровки генерируемых графовых моделей по имеющимся статистическим данным о моделируемых реальных сетях;

– импорт/экспорт файлов с использованием широко  распространенных форматов представления графов,  широкий набор методов для анализа характеристик графов.

На рисунке 9 представлена диаграмма пакетов системы имитационного моделирования системы Simbigraph. Представлены следующие пакеты:

1) engine – пакет, содержащий календарь событий для управления модельным временем имитации;

2) graphs – пакет для поддержки моделирования случайных графов;

3) gui – пакет, реализующий основные графические интерфейсы;

4) core – пакет для реализации базовых математических функций (случайные величины);

5) projections – пакет для реализации иерархий проекций.

Рисунок 9 – Диаграмма классов (пакет projection) в системы Simbigraph,
сгенерированная в среде разработки
BlueJ

На рисунке 10 представлена диаграмма, сгенерированная для пакета, содержащего Проекции системы Simbigraph. Интерфейс Projection отвечает за конкретное представление структуры взаимодействия, с которым работает система. Это Проекции для работы с сетевыми структурами, генерируемыми в результате триангуляции Делоне (TriangulationDelaneyProjection), для работы с решетками (Lattice2D, Lattice3D), графами Кроннекера (KronnekerGraphProjection), графами предпочтительного связывания (ProjGraphPA) и другими типами случайных графов (NetworkProjection).

Рисунок 10 – Диаграмма классов (пакет projection) в системы Simbigraph,
сгенерированная в среде разработки
BlueJ

Разработанный алгоритм можно внедрить  как отдельный тип генератора в проекцию ProjGraphPA или путем модификации ProjGraphPA, с заменой используемого генератора графов предпочтительного связывания на новый генератор, который использует калибровку по коэффициенту кластеризации, а в остальном работает как оригинальный генератор. Был выбран 2-й вариант. На рис. 11 представлена диаграмма классов пакета graph.generators, в котором содержатся классы основных генераторов графов в системе Simbigraph.

Рисунок 11 – Диаграмма классов Simbigraph пакета generators

Класс GeneratorClastPA, который реализует алгоритм генерации графа представлен на рисунке 12. Интерфейс Factory передается в конструктор класса GeneratorClastPA и используется для создания узлов и рёбер. Интерфейс Map используется для хранения значений пар смежных узлов, со степенями связности, которые хранятся в объектах класса Para.


Рисунок 12 – Диаграмма классов
Simbigraph для разработанного класса

Моделирование сетей в SIMBIGRAPH удобно описать с позиций двухэтапного подхода: на первом этапе формируется графовая модель, а на втором сформированная графовая модель используется для организации имитационного моделирования, т.е. моделирования передачи информации, ресурсов и так далее.

Первый этап – генерация графовых моделей сетей осуществляется путем генерации случайных графов и задания размеров и типов грида (рисунок 13). Именно здесь представлены модели сл.г. с НППС, граф Эрдеша–Реньи, граф Эпштейна и т.д. На втором этапе происходит непосредственное моделировани.

Правило предпочтительного связывания инкапсулируется в реализациях интерфейса PrefferentialAttachment. Пример правила предпочтительного связывания для реализации линейного правила представлено ниже.

class prefRule implements PrefferentialAttachment {

 public double f(int k) {

  return k;

}

}

Рисунок 13 – Диаграмма классов Simbigraph для разработанного класса


Заключение

В ходе работы были получены следующие результаты.

1. При исследовании сетей было выявлено, что задача моделирования сети решается на основе различных подходов, предлагаемых на данном этапе развития теории случайных графов. Так, графы БА и графы с НППС по способу построения соответствуют таким сетям, которые неограниченно растут за счет добавления новых узлов и связей (сетям типа интернет). Эти графы можно калибровать по РСС узлов моделируемых сетей. Графы Уатса-Строгатса, достаточно близкие по способу построения к сл.г. Эрдеша-Реньи, успешно калибруются по коэффициенту кластеризации. Иерархические сл.г., граф Кронекера и др. отражают механизмы генезиса сетей других классов и калибруются по другим структурным характеристикам.

2. Проведено исследование существующих моделей построения графов с НППС.

Использование графов с НППС позволяет генерировать графовые модели с заранее заданным распределением степени связности вершин, это достигается с помощью подбора функции предпочтения, и распределения случайного числа рёбер в приращении.

Известны эффективные способы генерации графов с НППС и методы их калибровки, которые позволяют выращивать граф с требуемым распределением степени связности вершин. Ускоренный метод генерации графов с НППС реализуется разбиением множества вершин графа на слои (подмножества вершин с одинаковыми степенями). Методы калибровки графов по распределению степени связности вершин, основанны на известной методике калибровки графов

2. Исследован метод сепарабельной реконфигурации

Данный метод изменяет структуру графа путём перераспределения рёбер, при этом распределение степени связности вершин не изменяется.

Недостатком метода является то, что при генерации нарушается структура, полученная в результате применения графа с НППС.

3. Предложены два алгоритма генерации графов с НППС с калибровкой по коэффициенту кластеризации.

 Алгоритм с гарантированным появлением хотя бы одного треугольника при присоединении новой вершины.

 Алгоритм с разбиением вершин для присоединения на пары, из которых производится поиск двух связных вершин (что обеспечивает образование треугольника при присоединении).

4. Разработанный алгоритм был реализован на языке Java для системы моделирования Simbigraph.

5. Разработанный алгоритм был представлен на V Всероссийской научно-практической конференции студентов, аспирантов, работников образования и промышленности в 2013 и был напечатан в сборнике [17].


Список использованных источников

1 Граф (математика) // ru.wikipedia.org: Википедия – свободная энциклопедия. URL: http://ru.wikipedia.org/wiki/Граф_(математика) (дата обращения 26.05.2013)

2 Albert R., Barabasi A. Statistical mechanics of complex networks // Rev. Mod. Phys. 2002. V. 74 P. 47–97

3 Олемской А.И. Статистика сложных сетей (обзор) / А.И. Олемской, И.А. Олемской // «Вiсник СумДУ». – 2006. – №6 (90). – С.21-47

4 Автоматическая обработка текстов на естественном языке и компьютерная лингвистика: учебн. пособие / Большакова Е.И., Клышинский Э.С., Ландэ Д.В., Носков А.А., Пескова О.В., Ягунова Е.В. — М.: МИЭМ, 2011. — 272 с.

5 Т.А. Леванова, М.А. Комаров, Е.Ю. Кадина, Г.В. Осипов Структуры последовательной активности в нейронных сетях со случайными связями // Вестник Нижегородского университета им. Н.И. Лобачевского. – 2010. - №2 (1). – С. 131-139

6 Задорожный В. Н. Случайные графы с нелинейным правилом предпочтительного связывания // Проблемы управления. – 2010. – №6. – С. 2-11.

7 Юдин Е.Б. Генерация случайных графов предпочтительного связывания // Омский научный вестник. – 2010. – №2 (90). – С. 7-13.

8 Задорожный, В.Н., Юдин, Е.Б. Структурные свойства безмасштабного графа Барабаши-Альберт // Автоматика и телемеханика. – 2012. – № 4. – С. 131–150.

9 Задорожный, В.Н., Юдин, Е.Б. Точная теория графа Барабаши-Альберт // Омский научный вестник. – 2009. – №3 (83). – С.13-19

10 Юдин Е.Б. Методы структурной идентификации стохастических сетей и генерации случайных графов в задачах моделирования сложных систем: Дис. на соискание учёной степени канд. техн. наук. – Омск., 2012. – С. 47-65

11 Данные о сетях [Электронный ресурс]. – Режим доступа: http://vlado.fmf.uni-lj.si/pub/networks/data/, свободный. – Загл. с экрана. – Яз. англ.

12 Структура сети маршрутизаторов Интернет (2006 г.). URL: http://www.cise.ufl.edu/ research/sparse/mat/Pajek/internet.mat (дата обращения: 01.09.2009).

13 Структура сети участия актёров в общих фильмах. URL: http://www.nd.edu/~networks/resources/actor/actor.dat.gz (дата обращения: 03.02.2010).

14 Задорожный В.Н., Юдин Е.Б., Овчинникова Е.В., Ганеева М.И. Сравнение случайных графов с моделями сетей по диаметру // материалы IV регион. науч.-практ. конф (Омск, 2012). – ОмГТУ; 2012. – С. 100-101

15 Задорожный В.Н., Бояршинов К.Н. Структурные характеристики графов: коэффициенты кластеризации // материалы IV регион. науч.-практ. конф (Омск, 2012). – ОмГТУ; 2012. – С. 91-93

16 Юдин Е.Б., Ганеева М.И. Расчёт коэффициента кластеризации для присоединения в графай предпочтительного связывания // материалы V Всерос. науч.-практ. конф. студентов, аспирантов, работников образования и пром-сти (Омск, 23-26 апр. 2013 г.). – ОмГТУ; 2013. – С. 92-95

17 Юдин Е.Б., Овчинникова Е.В. О выборе вершины для присоединения в графах предпочтительного связывания // материалы V Всерос. науч.-практ. конф. студентов, аспирантов, работников образования и пром-сти (Омск, 23-26 апр. 2013 г.). – ОмГТУ; 2013. – С. 95-97

18 Сеть автономных систем Интернет, воссозданная на основе BGP таблиц URL: http://www-personal.umich.edu/~mejn/netdata/as-22july06.zip (дата обращения: 01.09.2009).


Приложение А

(обязательное)

Листинг алгоритма с гарантированным появлением хотя бы одного треугольника при присоединении новой вершины.

import edu.uci.ics.jung.algorithms.generators.random.BarabasiAlbertGenerator;

import edu.uci.ics.jung.graph.DirectedSparseMultigraph;

import edu.uci.ics.jung.graph.Graph;

import edu.uci.ics.jung.graph.UndirectedSparseMultigraph;

import edu.uci.ics.jung.graph.util.EdgeType;

import edu.uci.ics.jung.graph.util.Pair;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collection;

import java.util.HashMap;

import java.util.HashSet;

import java.util.Iterator;

import java.util.LinkedList;

import java.util.List;

import java.util.Map;

import java.util.Random;

import java.util.Set;

public class m6_PowerOrtGenerator<V,E> {

Para temp = new Para(0, 0);

Map<Para, List<E>> pair_matrix = new HashMap();

Map<Integer, List<V>> mapLayers = new HashMap();

 int initN = 4;// addEd1 = 3;

 Graph<V, E> graph;

 protected PrefferentialAttachment attachRule;

 protected Factory<V> vertexFactory;

 protected Factory<E> edgeFactory;

 protected double numEdgesToAttach[];

 

 public m6_PowerOrtGenerator(Factory<V> vertexFactory,

  Factory<E> edgeFactory, double[] probEdgesToAttach,PrefferentialAttachment attachRule)

{

 double s=0.;

 for (double d : probEdgesToAttach)

{

  s=s+d;

 }

 assert Math.abs(s-1.)<0.000000001 :"Сумма вероятностей по различным значениям "

  + "числа добавляемых на шаге ребер должна равняться 1";

 this.vertexFactory = vertexFactory;

 this.edgeFactory = edgeFactory;

 this.numEdgesToAttach= probEdgesToAttach;

 this.attachRule =attachRule;

 mRand = new Random();

}

 

 public Graph<V, E> evolve(int step){//, int m, double lyamda, Graph<V, E> graph)  

 graph = new UndirectedSparseMultigraph();

 int m =3;

 initN = m + 1;

 

 // инициализация полносвязного графа и добавление в слои

 mapLayers.put(m, new LinkedList());

 for (int i = 0; i < initN; i++) {

  V n = vertexFactory.create();

  graph.addVertex(n);

  List<V> list = mapLayers.get(m);

  list.add(n);

 }

 

 Object[] mass = graph.getVertices().toArray();

 for (int i = 0; i < mass.length - 1; i++)

  for (int j = i + 1; j < mass.length; j++) {

   E link = edgeFactory.create();

   graph.addEdge(link, (V) mass[i], (V) mass[j],

     EdgeType.UNDIRECTED);

  }

 

 //поместить все рёбра в матрицу рёбер

 for (E l0 : graph.getEdges())

{

  Pair<V> pa = graph.getEndpoints(l0);

  int min = graph.degree(pa.getFirst());

  int max = graph.degree(pa.getSecond());

  Para temp = null;

  add2pair(max, min, l0);

 }

   

 // Обращаемся к матрице. Находим одно из рёбер и, тем самым,

 // находим два требуемых узла. Остальные берём случайно

 for (int i = 0; i < step; i++)

{

  // разыгрываем две случайные величины, определяющие номера слоёв

  int addEd= getNumAttachToAttach();

  if(addEd==0)System.out.println("нельзя вершин без узлов");

  

  // массив выбранных индексов

  int[] indexes = new int[addEd];

  Set<E> setLink = new HashSet();

  List<V> listNodes = new LinkedList();

  Map<Pair<V>,Pair<Integer>> mapPairs = new HashMap();

  formConPairVert(indexes,mapPairs);

  Pair<V> pair= mapPairs.keySet().iterator().next();

  

  // получаем список узлов для присоединения

  listNodes.add(pair.getFirst());

  if(indexes.length>1)listNodes.add(pair.getSecond());

  

  

  for (int j = 0; j < indexes.length; j++)

{

   //из тех, чьи индексы не вошли в Map

   Iterator<Pair<Integer>> it=mapPairs.values().iterator();

   boolean isUse= false;

   while (it.hasNext()){

    Pair<Integer> pairK= it.next();

    int k1=pairK.getFirst(), k2=pairK.getSecond();

    if (j ==k1||j ==k2 )isUse = true;

   }

    if(!isUse)

  listNodes.add(mapLayers.get(indexes[j]).get(

          mRand.nextInt(mapLayers.get(indexes[j]).size())));

  }

  // формируем список рёбер, которых затронут изменения

  for (Iterator iterator = listNodes.iterator(); iterator.hasNext();)

{

   V myNode = (V) iterator.next();

   Collection<E> list_j = graph.getIncidentEdges(myNode);

   for (Iterator<E> it = list_j.iterator(); it.hasNext();) {

    E link = it.next();

    setLink.add(link);

   }

  }

// удаляем из списка вершин, те, чьи степени изменятся

  for (Iterator iterator = listNodes.iterator(); iterator.hasNext();)

{

   V myNode = (V) iterator.next();

   mapLayers.get(graph.degree(myNode)).remove(myNode);

  }

  // удаляем из списка рёбер такие, которых затронули изменения

  for (E l0 : setLink)

{

   Pair<V> pa = graph.getEndpoints(l0);

   int min = graph.degree(pa.getFirst());

   int max = graph.degree(pa.getSecond());

   Para temp = null;

   if (min > max)

    temp = new Para(max, min);

   else

    temp = new Para(min, max);

   pair_matrix.get(temp).remove(l0);

  }

  

  V new_n = vertexFactory.create();

  // добавляем ребро в граф

  Map<E, V> newEdges = new HashMap<E, V>();

  for (Iterator iterator = listNodes.iterator(); iterator.hasNext();)

{

   V myNode = (V) iterator.next();

   E l1 = edgeFactory.create();

   newEdges.put(l1, myNode);

   graph.addEdge(l1, new_n, myNode);

  }

  

  // переносим в соответв слой новую вершину и все изменённые  вершины

  listNodes.add(new_n); // добавляем к числу удалённых вершин новую и заносим всё в слои 

  for (Iterator iterator = listNodes.iterator(); iterator.hasNext();)

{

   V myNode = (V) iterator.next();

   addToLayer(myNode, graph.degree(myNode));

  }

  // Добавляем новые рёбра в матрицу рёбер

  for (E li : newEdges.keySet()) {

   int min = addEd;

   int max = graph.degree(newEdges.get(li));

   add2pair(min, max, li);

  }

  //Добавляем изменённые рёбра в матрицу рёбер

  for (E l0 : setLink) {

   Pair<V> pa = graph.getEndpoints(l0);

   int min = graph.degree(pa.getFirst());

   int max = graph.degree(pa.getSecond());

   add2pair(min, max, l0);

  }

 }

 return graph;

}

 private void formConPairVert(int[] indexes, Map<Pair<V>,Pair<Integer>> map) {

 

 int k1 = 0,  k2 = 0;

 V n1 = null, n2 = null;

 E p = null;

 do {

  for (int j = 0; j < indexes.length; j++) {

   indexes[j] = getK();

  }

  Arrays.sort(indexes);

  // на основе индексов обращаемся к матрице и формируем список

  // рёбер для выбора

  List<E> listLink_ = new LinkedList();

  for (int j = 0; j < indexes.length - 1; j++) {

   for (int k = j + 1; k < indexes.length; k++) {

    Para pr = new Para(indexes[j], indexes[k]);

    if (pair_matrix.get(pr) != null

      && pair_matrix.get(pr).size() > 0)

     listLink_.addAll(pair_matrix.get(pr));

   }

  }

  n1 = null;

  n2 = null;

  if ((listLink_.size() > 0)) {

   p = listLink_.get(mRand.nextInt(listLink_.size()));

   if (p == null)

    System.out.println("ff");

   Pair<V> par = graph.getEndpoints(p);

   int i1 = graph.degree(par.getFirst());

   int i2 = graph.degree(par.getSecond());

   boolean b1 = true, b2 = true;

   for (int j = 0; j < indexes.length; j++) {

    if (indexes[j] == i1 && b1) {

     k1 = j;

     b1 = false;

     continue;

    }

    if (indexes[j] == i2 && b2) {

     k2 = j;

     b2 = false;

     continue;

    }

   }

  } else {

   int i1 = mRand.nextInt(indexes.length);

   int i2 = i1;

   do

    i2 = mRand.nextInt(indexes.length);

   while (i2 == i1&&(indexes.length>1));//пока они равны и длина >1

   k1 = i1;

   k2 = i2;

   n1 = mapLayers.get(indexes[i1]).get(

     mRand.nextInt(mapLayers.get(indexes[i1]).size()));

   n2 = mapLayers.get(indexes[i2]).get(

     mRand.nextInt(mapLayers.get(indexes[i2]).size()));

  }

  listLink_.clear();

 } while ((p == null) && (n1 == n2));

 Pair<V> pair1;

 if (p != null) {

  pair1 = graph.getEndpoints(p);

 } else

  pair1 = new Pair(n1, n2);

 

 Pair<Integer> pair2 =new Pair(k1, k2);

 map.put(pair1, pair2);

}

 private int getNumAttachToAttach() {

 double s=0.;

 double r1=mRand.nextDouble();

 int addEd =0;

 for (int j = 0; j < numEdgesToAttach.length; j++) {

   s=s+numEdgesToAttach[j];

   if(s>r1)

   {

    addEd = j;

    break;

   }

  }

 return addEd;

}

 private void add2pair(int min, int max, E link) {

 if (min > max)

  {

  int temp= max;

  max=min;

  min=temp;

  }

 Para para = new Para(min, max);

 List<E> p = pair_matrix.get(para);

 if (p == null) {

  p = new ArrayList();

  pair_matrix.put(para, p);

 }

 p.add(link);

}

 Random mRand = new Random();

 double f(int k) {

 return attachRule.f(k);

}

 private int getK() {

 // разыгрываем

 int k = 0;

 double rand = mRand.nextDouble();

 double tr = 0;

 // считаем знаменатель

 double sum = 0.0;

 for (int op : mapLayers.keySet())

  sum = sum + f(op) * mapLayers.get(op).size();

 double sum2 = 0.0;

 for (int l : mapLayers.keySet()) {

  int A = mapLayers.get(l).size();

  tr = tr + ((double) A * f(l)) / sum;

  if (rand < tr) {

   k = l;

   break;

  }

 }

 return k;

}

 private void addToLayer(V n, int i) {

 List<V> list = mapLayers.get(i);

 if (list == null) {

  list = new LinkedList();

  mapLayers.put(i, list);

 }

 if (!list.contains(n))

  list.add(n);

}

}


Листинг алгоритма с разбиением вершин для присоединения на пары, из которых производится поиск двух связных вершин (что обеспечивает образование треугольника при присоединении).

import edu.uci.ics.jung.algorithms.generators.random.BarabasiAlbertGenerator;

import edu.uci.ics.jung.graph.DirectedSparseMultigraph;

import edu.uci.ics.jung.graph.Graph;

import edu.uci.ics.jung.graph.UndirectedSparseMultigraph;

import edu.uci.ics.jung.graph.util.EdgeType;

import edu.uci.ics.jung.graph.util.Pair;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collection;

import java.util.HashMap;

import java.util.HashSet;

import java.util.Iterator;

import java.util.LinkedList;

import java.util.List;

import java.util.Map;

import java.util.Random;

import java.util.Set;

public class m7_PowerOrtGenerator<V,E> {

Para temp = new Para(0, 0);

Map<Para, List<E>> pair_matrix = new HashMap();

Map<Integer, List<V>> mapLayers = new HashMap();

 int initN = 4;// addEd1 = 3;

 Graph<V, E> graph;

 protected PrefferentialAttachment attachRule;

 protected Factory<V> vertexFactory;

 protected Factory<E> edgeFactory;

 protected double numEdgesToAttach[];

 int maxlayer=0;

 public m7_PowerOrtGenerator(Factory<V> vertexFactory,

 Factory<E> edgeFactory, double[] probEdgesToAttach,PrefferentialAttachment attachRule)

{

 double s=0.;

 for (double d : probEdgesToAttach)

{

  s=s+d;

 }

 assert Math.abs(s-1.)<0.000000001 : "Сумма вероятностей по различным значениям "

  + "числа добавляемых на шаге ребер должна равняться 1";

 this.vertexFactory = vertexFactory;

 this.edgeFactory = edgeFactory;

 this.numEdgesToAttach= probEdgesToAttach;

 this.attachRule =attachRule;

 mRand = new Random();

}

 

 

public Graph<V, E> evolve(int step){//, int m, double lyamda, Graph<V, E> graph)  

 maxlayer=0;

 graph = new UndirectedSparseMultigraph();

 int m =3;

 initN = m + 1;

 

 // Инициализация полносвязного графа. Добавление в слои

 mapLayers.put(m, new LinkedList());

 for (int i = 0; i < initN; i++) {

  V n = vertexFactory.create();

  graph.addVertex(n);

  List<V> list = mapLayers.get(m);

  list.add(n);

 }

 

 Object[] mass = graph.getVertices().toArray();

 for (int i = 0; i < mass.length - 1; i++)

  for (int j = i + 1; j < mass.length; j++) {

   E link = edgeFactory.create();

   graph.addEdge(link, (V) mass[i], (V) mass[j],

     EdgeType.UNDIRECTED);

  }

 

 //Помещаем все рёбра в матрицу рёбер

 for (E l0 : graph.getEdges()) {

  Pair<V> pa = graph.getEndpoints(l0);

  int min = graph.degree(pa.getFirst());

  int max = graph.degree(pa.getSecond());

  Para temp = null;

  add2pair(max, min, l0);

 }

 

 // Обращаемся к матрице. Находим одно из рёбер и, тем самым,

 // находим два требуемых узла. Остальные берём случайно

for (int i = 0; i < step; i++) {

  // разыгрываем две случайные величины, определяющие номера слоёв

  int addEd= getNumAttachToAttach();

  if(addEd==0)System.out.println("нельзя вершин без узлов");

  

  // массив выбранных индексов

  int[] indexes = new int[addEd];

  Set<E> setLink = new HashSet();

  List<V> listNodes = new LinkedList();

  Map<Pair<V>,Para> mapPairs = new HashMap<Pair<V>,Para>();

  for (int j = 0; j < indexes.length; j++) {

   indexes[j] = getK();

   if(indexes[j]>maxlayer)maxlayer =indexes[j];

  }

  

  formConPairVert(indexes,listNodes);

  // формируем список рёбер, которых затронут изменения

  for (Iterator iterator = listNodes.iterator(); iterator.hasNext();) {

   V myNode = (V) iterator.next();

   Collection<E> list_j = graph.getIncidentEdges(myNode);

   for (Iterator<E> it = list_j.iterator(); it.hasNext();) {

    E link = it.next();

    setLink.add(link);

   }

  }

  // удаляем из списка вершины, те, чьи степени изменятся

  for (Iterator iterator = listNodes.iterator(); iterator.hasNext();) {

   V myNode = (V) iterator.next();

   mapLayers.get(graph.degree(myNode)).remove(myNode);

  } // удаляем из списка рёбер такие, которые затронули изменения

  for (E l0 : setLink) {

   Pair<V> pa = graph.getEndpoints(l0);

   int min = graph.degree(pa.getFirst());

   int max = graph.degree(pa.getSecond());

   Para temp = null;

   if (min > max)

    temp = new Para(max, min);

   else

    temp = new Para(min, max);

   pair_matrix.get(temp).remove(l0);

  }

  

  V new_n = vertexFactory.create();

  // добавляем рёбра в граф

  Map<E, V> newEdges = new HashMap<E, V>();

  for (Iterator iterator = listNodes.iterator(); iterator.hasNext();) {

   V myNode = (V) iterator.next();

   E l1 = edgeFactory.create();

   newEdges.put(l1, myNode);

   graph.addEdge(l1, new_n, myNode);

  }

  

 // переносим в соответствующий слой новую вершину и все изменённые  вершины

listNodes.add(new_n); // добавляем к числу удаленных вершин новую и заносим всё в слои 

  for (Iterator iterator = listNodes.iterator(); iterator.hasNext();) {

   V myNode = (V) iterator.next();

   addToLayer(myNode, graph.degree(myNode));

  }

  // Добавляем новые рёбра в матрицу рёбер

  for (E li : newEdges.keySet()) {

   int min = addEd;

   int max = graph.degree(newEdges.get(li));

   add2pair(min, max, li);

  }

  //Добавляем изменённые рёбра в матрицу рёбер

  for (E l0 : setLink) {

   Pair<V> pa = graph.getEndpoints(l0);

   int min = graph.degree(pa.getFirst());

   int max = graph.degree(pa.getSecond());

   add2pair(min, max, l0);

  }

 }

 System.out.println("^^"+count);

 return graph;

} int count=0;

 private void formConPairVert(int[] m, List<V> listNodes) {

 int k1,k2;

 Set<E> set = new HashSet();

 if(m.length>1){

  for (int i = 0; i < m.length/2; i++) {

   if(m[i]>m[m.length/2+i]) {k1 = m[ m.length/2+i]; k2= m[i];}

   else {k1 = m[i]; k2= m[ m.length/2+i];}

   Para pr = new Para(k1, k2);

   List<E> list =pair_matrix.get(pr);

       

   E edge = null;

   

   if(list!=null){

   count++;

    for (E e : list) {

    if(!set.contains(e))

    edge = e;

    set.add(edge);

    break;

   }

   }

   if (edge != null) {

    Pair<V> pair2= graph.getEndpoints(edge);

    listNodes.add(pair2.getFirst());

    listNodes.add(pair2.getSecond());

   } else

   {

    V n1 = mapLayers.get(k1).get(

      mRand.nextInt(mapLayers.get(k1).size()));

    V n2 = mapLayers.get(k2).get(

      mRand.nextInt(mapLayers.get(k2).size()));

    listNodes.add(n1);

    listNodes.add(n2);

   }

  }

  // если есть нечётное ребро 

 if(m.length%2==1)

  listNodes.add(mapLayers.get(m[m.length-1]).get( mRand.nextInt(mapLayers.get(m[m.length-1]).size())));

 }

 //если ребро одно

 else {

  listNodes.add(mapLayers.get(m[0]).get(

    mRand.nextInt(mapLayers.get(m[0]).size())));

 }

}

 private int getNumAttachToAttach() {

 double s=0.;

 double r1=mRand.nextDouble();

 int addEd =0;

 for (int j = 0; j < numEdgesToAttach.length; j++) {

   s=s+numEdgesToAttach[j];

   if(s>r1)

   {

    addEd = j;

    break;

   }

  }

 return addEd;

}

 private void add2pair(int min, int max, E link) {

 if (min > max)

  {

  int temp= max;

  max=min;

  min=temp;

  }

 Para para = new Para(min, max);

 List<E> p = pair_matrix.get(para);

 if (p == null) {

  p = new ArrayList();

  pair_matrix.put(para, p);

 }

 p.add(link);

}

 Random mRand = new Random();

 double f(int k) {

 return attachRule.f(k);

}

 private int getK() {

 // разыгрываем

 int k = 0;

 double rand = mRand.nextDouble();

 double tr = 0;

 // считаем знаменатель

 double sum = 0.0;

 for (int op : mapLayers.keySet())

  sum = sum + f(op) * mapLayers.get(op).size();

 double sum2 = 0.0;

 for (int l : mapLayers.keySet()) {

  int A = mapLayers.get(l).size();

  tr = tr + ((double) A * f(l)) / sum;

  if (rand < tr) {

   k = l;

   break;

  }

 }

 return k;

}

 private void addToLayer(V n, int i) {

 List<V> list = mapLayers.get(i);

 if (list == null) {

  list = new LinkedList();

  mapLayers.put(i, list);

 }

 if (!list.contains(n))

  list.add(n);

 }

}

2 Аналогично, на основе анализа BGP таблиц можно получить граф, представляющий собой мгновенный снимок сети автономных систем Интернет


 

А также другие работы, которые могут Вас заинтересовать

80881. Муниципальное регулирование занятости и трудовых отношений 45.99 KB
  Проблема муниципального регулирования занятости населения. Сложность муниципального регулирования вопросов занятости состоит в том что основное правовое регулирование этих вопросов относится к сфере федерального и регионального законодательства и реализуется через территориальные структуры федеральной службы занятости. Государственная политика и разграничение полномочий в сфере занятости.
80882. Муниципальная жилищная политика 45.91 KB
  Отсутствие жилья и плохие жилищные условия одна из главных причин снижения рождаемости семейных конфликтов детской беспризорности. в которой указаны основные задачи в области обеспечения доступности жилья и жилищного строительства разграничены функции федерального центра регионов и муниципалитетов в жилищной сфере. С начала перехода к рыночным отношениям основная часть государственного жилья в нашей стране была передана в муниципальную собственность включая ведомственный жилищный фонд передававшийся в процессе приватизации...
80883. Критерии и показатели эффективности муниципального управления 44.98 KB
  Поскольку генеральной целью муниципальной деятельности является повышение качества жизни населения на территории муниципального образования данный показатель в динамике мог бы выступать в качестве обобщающего критерия эффективности муниципального управления. Сложность выработки и измерения достаточно объективных показателей эффективности муниципального управления определяется:спецификой муниципального образования как сложного объекта управления имеющего иерархическую структуру;трудностями формализованного описания социальноэкономических...
80884. Муниципальное управление образованием 45.16 KB
  Муниципальная политика в сфере образования строится на основе гос. политики базирующейся на принципах: гуманистический характер образования приоритет общечеловеческих ценностей жизни и здоровья человека свободного развития личности; общедоступность образования адаптивность системы образования к уровням и особенностям развития и подготовки обучающихся воспитанников; светский характер образования в госных и муных образовательных учреждениях; свобода и плюрализм в образовании. актами определяющими задачи ОМС в области образования...
80885. Основы муниципальной молодежной политики 45.24 KB
  Цели и задачи государственной и муниципальной молодежной политики Муниципальная молодежная политика совокупность целей и мер по их реализации принимаемых ОМС в целях создания и обеспечения условий и гарантий для самореализации личности молодого человека и развития молодежных объединений движений и инициатив. Эта политика осуществляется на основе нормативных правовых актов представительных ОМС и в русле госной молодежной политики придавая ей логическую стройность системный и целостный характер и делая демократичными механизмы ее...
80886. Муниципальная экономика и модели муниципального хозяйства 43.46 KB
  Это объясняется тем что объекты муниципальной собственности могут быть бюджето-наполняющими приносящими доходы в бюджет и бюджето-поглощающими не приносящими доходов в бюджет или требующими бюджетных средств на их содержание в размере превышающем получаемый доход. Поэтому ключевая задача муниципальной экономической политики состоит в оптимизации соотношений между объемом бюджетных услуг и потребностью в имуществе и в финансовых средствах. Конкурентный рынок муниципальных услуг настолько развит что задачей муниципальной власти является...
80887. Порядок формирования и организация работы представительного органа местного самоуправления 43.11 KB
  ПО МС может осуществлять свои полномочия в случае избрания не менее двух третей от установленной численности депутатов. Заседание его не может считаться правомочным если на нем присутствует менее 50 от числа избранных депутатов. ПО поселения состоит из депутатов избираемых на муниципальных выборах. ПО муниципального района: 1 может состоять из глав поселений входящих в состав муниципального района и из депутатов ПО указанных поселений избираемых ПО поселений из своего состава в соответствии с равной независимо от численности населения...
80888. Организационная структура местной администрации 46.1 KB
  Организационная структура местной администрации. В современной муниципальной практике типичными звеньями организационной структуры местной администрации являются: глава администрации; его заместители по сферам муниципальной деятельности среди которых могут быть один или два первых заместителя; структурные подразделения различных типов которые могут находиться в подчинении главы администрации одного из его заместителей или в соподчинении между собой например отдел в составе управления; коллегиальные совещательные органы: коллегия...
80889. Статус, полномочия Главы Муниципального Образовния и основания прекращения его полномочий 41.75 KB
  выборах либо входит в состав ПО МО с правом решающего голоса и исполняет полномочия его председателя либо возглавляет местную администрацию; 3 в случае избрания ПО МО исполняет полномочия его председателя; 4 не может одновременно исполнять полномочия председателя ПО МО и полномочия главы местной администрации; Глава МО в пределах полномочий: 1 представляет МО в отношениях с ОМС других МО ОГВ гражданами и организациями без доверенности действует от имени МО; 2 подписывает и обнародует в порядке установленном уставом МО нормативные...