Произвольная структура глобальной компьютерной сети в виде графа
В 1968 г. ARPA (Агентство по работе с исследовательскими проектами в области перспективных исследований военного ведомства США) открыло финансирование этого проекта.
К осени 1969г. была создана глобальная вычислительная сеть АРПА-НЕТ, состоявшая из 4 ЭВМ:
- SDS SIGMA в Калифорнийском университете Лос-Анжелеса;
- SDS 940 в Стенфордском исследовательском институте;
- IBM 360 в Калифорнийском университете Санта-Барбары;
- DEC PDP -10 в университете штата Юта.
В дальнейшем сеть быстро развивалась: в 1971г. она насчитывала 15 узлов; в 1972 г. - 37; в 1973 г. к сети подключены зарубежные узлы (Университетский колледж в Лондоне и Королевская лаборатория радиолокации в Норвегии), и глобальная вычислительная сеть стала международной. В 1987 г. количество узлов в сети составляло 10000; в 1989 г. - 100000.
Сначала сеть работала по протоколу NCP ( Network Control Protocol ).
В 1974 г. Винт Серф и Боб Кан (сотрудники National Science Foundation ) опубликовали первые спецификации протоколов TCP/IP . В 1983 г. ARPANET отказалась от NCP в пользу TCP/IP .
Internet - это " сеть сетей", не глобальная вычислительная сеть , а структура, объединяющая десятки тысяч глобальных вычислительных сетей.
Глобальная вычислительная сеть (ГВС) имеет в своей основе базовую сеть передачи данных (рис.18.1).
- символы "УС" обозначают узлы связи;
- символы "ЭВМ" - локальные ЭВМ, подключенные к глобальной вычислительной сети;
- цифры обозначают номер канала связи базовой сети передачи данных (СПД).
При создании глобальной вычислительной сети в узлах СПД устанавливаются мощные ЭВМ, называемые хост -компьютерами. Возможны различные конфигурации ГВС. Звездообразная (рис.18.2):
Звездообразная конфигурация обладает наименьшей надежностью из-за наличия единственного сетеобразующего узла.
Узловая глобальная вычислительная сеть - более надежная. Но наличие единственного центрального узла не позволяло решать задачи, поставленные перед разработчиками Министерством обороны США. Несмотря на это, примерно такая сеть реализована в нашей стране некоторыми министерствами.
Наибольшей надежностью и устойчивостью обладают сети распределенной конфигурации (рис.18.4), матричные, полносвязные и др.
В сентябре 1971 г географическая карта ARPANET представляла собой (рис.18.5):
Затем, по примеру АРПАНЕТ, стали появляться другие глобальные сети .
Одна из первых сетей США - NSFNET - выглядела аналогично (рис.18.6)
Таких сетей в США было создано много. Различные глобальные сети обслуживаются разными операторами связи : CompuServ , Prodiji, America Online , и др. Отдельные узлы сетей выделены как точки соединения сетей ( Interconnect Points ) и точки доступа к сети ( Network Access Points ).
Для объединения глобальных вычислительных сетей в единую структуру в течение 80-х годов в США был создан "магистральный хребет Интернет " ( Internet Backbone ), который лег в основу супермагистрали NSFNET .
Сначала эта суперскоростная магистраль имела пропускную способность 56 Кбит/сек. В 1988 г. ее пропускная способность была увеличена до 1,544 Мбит/сек. NSFNET перестала существовать в качестве супермагистрали в 1995 г.
Ее заменила vBNS ( very high speed Backbone Network Service - сверхвысокоскоростная Сетевая служба магистрали) с пропускной способностью 155 Мбит/сек (владельцы: Национальный научный фонд и оператор дальней связи MCI Word Com ).
24 февраля 1999г. в США параллельно с vBNS введена в эксплуатацию Интернет -2 - высокоскоростная магистраль Abilene (кольцо через всю страну из волоконно-оптического кабеля, длиной 21000 км). К Abilene было подключено 130 университетов. Вначале сеть использовалась только для научных исследований. Новая сеть обеспечивала передачу в реальном времени "видео телевизионного качества (30 кадров в секунду); транспортировку файлов терабайтного размера; телемедицину (консультации во время операций). Длина IP -адреса в новой сети увеличена с 32 до 128 бит .
Пропускная способность Abilene - 2,4 Гбит/сек. Предполагалось ее увеличить до 9,6 Гбит/сек. В перспективе Abilene должна охватить все университеты США. Обслуживание сети ведет университет штата Индиана. К сети разрешают подключаться некоторым канадским, скандинавским и голландским центрам.
В соответствии с концепцией национальной информационной инфраструктуры Альберта Гора, магистральная инфраструктура США ( Abilene + vBNS ) должна слиться со средствами массовой информации - произойдет слияние нескольких отраслей промышленности: компьютерной, телекоммуникационной, софтверной и промышленности информационного снабжения (т.е. создания и поставки информации: развлекательной, социальной, учебной, научной, медицинской, и др.), так как государству нужна связность посредством информационных сетей, выполняющих роль нервной системы страны.
В каждой ГВС применяется различная номенклатура технических средств ( SUN, IBM PC, Apple и др.).
Форматы используемой в разных ГВС информации и системы команд различны.
Для того чтобы соединить две ГВС, построенные на разных типах ЭВМ (неоднородные ГВС), необходимы специальные технические и программные средства , реализованные в виде "шлюзов" (или "маршрутизаторов").
В шлюзах осуществляется перекодировка информации из кодов, действующих в одной сети, в коды, действующие в другой (например, из КОИ-7 в ДКОИ или в ASCII и обратно), и преобразовываются другие данные (например, адреса абонентов сети) в соответствии с правилами, принятыми в каждой ГВС.
При большом количестве разнородных глобальных вычислительных сетей для связи друг с другом эти ГВС должны иметь большое количество шлюзов, что связано с большими материальными затратами .
Значительно более эффективным является разработка общих для всех правил обмена информацией и способов ее представления.
1 января 1983 года ARPANET перешла на новый протокол ( TCP/IP ). Этот день принято считать официальной датой рождения Интернета.
При создании Internet разработаны единые правила обмена информацией - протоколы TCP ( Transmission Control Protocol ) и IP ( Internet Protocol ), применяемые обычно совместно и известные под именем TCP/IP , в состав которых входила стандартная система адресации ресурсов ( URL - Uniform Resource Locator ).
URL и протоколы TCP/IP являются стандартом Internet и обязательны для использования всеми ГВС для внешнего обмена информацией в составе Internet .
URL , или доменная система адресации, позволяет адресовать не только абонентов (в качестве которых могут выступать серверы, клиентские компьютеры, абонентские пункты, сетевые принтеры , и др.), но и информационные единицы, вплоть до файлов.
Согласно протоколу TCP , передаваемая информация разбивается на маленькие фрагменты - пакеты (дейтограммы). Соединение пакетов в соответствии с этим протоколом происходит на принимающей машине после их поступления (поступать они могут на принимающую машину вразбивку и по различным маршрутам).
Протокол IP определяет наилучший маршрут от одной ЭВМ к другой и управляет передачей пакетов.
Internet реализована с ориентацией на технологию "клиент- сервер ", т.е. предусматривает наличие хост -компьютеров ( хост -компьютером называется каждая постоянно подключенная к сети ЭВМ с установленным на ней программным обеспечением как минимум одного сервера), с которыми связываются компьютеры-клиенты (локальные ЭВМ).
В Internet насчитываются миллионы хост -компьютеров, принадлежащих различным глобальным вычислительным сетям (в 1969 г. было всего 4 "хоста", в 1996 г. количество хост -компьютеров возросло до 8,3 млн).
В таком количестве хост -компьютеров хранится огромное количество информации .
Презентация на тему: " Структура данных: Деревья, сети, графы, таблицы Разработала учитель информатики МБОУ «СОШ 5 г.Азнакаево» РТ Габдуллина Ф. М." — Транскрипт:
1 Структура данных: Деревья, сети, графы, таблицы Разработала учитель информатики МБОУ «СОШ 5 г.Азнакаево» РТ Габдуллина Ф. М.
2 Граф - отображает элементный состав системы и структуру связей Описание некоторой местности: «Автомобильные дороги проложены между: Дедкино и Бабкино, Дедкино и Кошкино, Бабкино и Мышкино, Бабкино и Кошкино, Кошкино и Репкино. Д Р КМ Б Это не карта местности. На этой схеме отражен лишь факт существования пяти поселков и дорожной связи между ними. Такая схема называется графом. Составными частями графа являются вершины и ребра. вершины ребра Неориентированный граф
3 Для сети характерна возможность множества различных путей перемещения по ребрам между некоторыми парами вершин Д Р КМ Б Неориентированный граф (сеть) Как добраться из Р в М ? 1)Р-К-Б-М 2) Р-К-Д-Б-М Для сетей также характерно наличие замкнутых путей, который называются циклами Цикл К-Д-Б-К
4 Связи между вершинами данного графа несимметричны и поэтому изображаются направленными линиями со стрелками. Граф с такими свойствами называется ориентированным. Существует четыре группы крови человека. При переливании не все группы совместимы. Данный граф показывает возможные варианты переливания крови. Например, из графа видно,что кровь I группы можно переливать любому человеку. IV I IIIII Направленные линии называют дугами (в отличии от ребер неориентированных графов). Линию, выходящую и входящую в одну и ту же вершину называют петлей. Ориентированный граф Дуги Петли
5 Иерархическая структура Директор Заместители директора Учителя Ученики Система административного управления, между элементами которой установлены отношения подчиненности.
6 Граф иерархической структуры - Между любыми двумя его вершинами существует единственный путь. Дерево Деревья не содержат циклов и петель Главная вершина - корень Ветви дерева Порожденные вершины Листья – не имеют порожденных вершин
7 Примеры иерархических структур - деревьев Владимир Рюрик Игорь Святослав Олег Ярополк Мстислав Тмутараканский ГлебЯрославБорис Святополк Изяслав Полоцкий
8 Таблицы Средства ЭОРКол-во учителей в % Интерактивные лекции 63% Виртуальные экскурсии 93% Виртуальные лаборатории 41% Конструкторы формул/графиков 33% Игровые модули 67% Контрольные модули 96% Тренажеры для оттачивания различных навыков 81% В какой форме представлена информация? Табличный способ представления данных является универсальным
9 Таблица типа "объект-свойство" Датаосадкитемп 15.03снег дождь- 20 Таблица типа "объект-объект" Ученикрусскийалгебра Иванов44 Сидоров53 Таблица типа «двоичная матрица» УченикТанцыЛегкая атлетика Сидорова10 Иванов01
10 Д Р КМ Б Поселок БабкиноДедкиноКошкиноРепкиноМышкино Бабкино01101 Дедкино10100 Кошкино11010 Репкино00100 Мышкино10000 Какая связь между графом и таблицей ? Попробуйте представить информацию о дорожной связи между поселками в форме таблицы.
11 Д Р КМ Б Поселок БабкиноДедкиноКошкиноРепкиноМышкино Бабкино01101 Дедкино10100 Кошкино11010 Репкино00100 Мышкино10000 Если сеть является неориентированным графом, то матрица смежности симметрична относительно главной диагонали. Матрица смежности
12 Попробуйте представить информацию о группах крови в форме таблицы. Начальная вершина Конечная вершина IIIIIIIV I1111 II0101 III00110 IV0001 У матрицы, отражающий ориентированный граф, симметричности не будет
13 Зачем мы переводили графы в табличную форму? Вам понятнее граф или таблица? С точки зрения человека, граф гораздо нагляднее и понятнее представляет структуру системы, чем таблица. А компьютеру какую форму обрабатывать легче? Для компьютерной обработки табличная форма подходит лучше. Многие компьютерные технологии (базы данных, электронные таблицы) работают с таблицами и поэтому в компьютерном моделировании чаще работают с табличным представлением.
14 Подведем итоги Структуры данных ГрафыТаблицы ДеревьяСетиТипы таблиц Элементы дереваЭлементы сети Объект-свойство Объект-объект Двоичная матрица КореньВетвиЛистьяВершиныРебра Единственность пути между вершинами Множественность путей между вершинами
15 Выполните задания 1. Нарисуйте два варианта графа системы «Компьютер», содержащего следующие вершины: процессор, оперативная память, внешняя память, клавиатура, монитор, принтер; а) линия связи обозначает отношение «передает информацию»; б) линия связи обозначает отношение «управляет».
16 Выполните задания 2. Нарисуйте произвольную структуру глобальной компьютерной сети в виде графа, в котором вершины обозначают серверы, а ребра – линии связи. Опишите эту сеть в виде двоичной матрицы смежности.
17 Выполните задания 3. Нарисуйте родословное дерево своей семьи (только по мужской линии или только по женской) с наибольшим числом известных вам уровней. Полученной дерево приведите к табличной форме. В полях, значения которых неизвестны, поставьте прочерки.
Анализ социальных сетей – это процесс исследования различных систем с использованием теории сетей. Он начал широко применяться именно тогда, когда стало понятно, что огромное количество существующих сетей (социальных, экономических, биологических) обладают универсальными свойствами: изучив один тип, можно понять структуру и любых других сетей и научиться делать предсказания по ним.
Любые сети состоят из отдельных участников (людей или вещей в сети) и отношений между ними. Сети очень часто визуализируются с помощью графов – структур, состоящих из множества точек и линий, отображающих связи между этими точками. Участники представлены в виде узлов сети, а их отношения представлены в виде линий, их связывающих. Такая визуализация помогает получить качественную и количественную оценку сетей:
Рис. 1. Направленный граф, изображающий денежный оборот между банками, формирующими валютный рынок (1). Красным отмечены банки ЕС, синим – Северной Америки, зелёным – других стран.
Рис. 2. Граф, отображающий сотрудничество партнеров по аудиту в Дании в 2010-2014 гг (2)
С помощью анализа социальных сетей можно проанализировать самые разные взаимодействия и процессы обмена ресурсами, как материальными, так и информационными. Например, проанализировав сеть транзакций между клиентами банка (где узлами являются клиенты банка, а рёбрами – переводы между ними), можно определить круг лиц, вовлечённых в мошеннические операции, или выявить нарушения внутренних регламентов сотрудниками банка.
Также можно построить сеть рабочих взаимоотношений (на примере различных типов коммуникаций между сотрудниками), которая может помочь в понимании социальной структуры организации и позиции каждого сотрудника в этой структуре. При наличии данных о типе коммуникации для каждого работника можно даже проанализировать, как такие характеристики как лидерство, наставничество и сотрудничество влияют на его карьеру, а на основе полученных знаний определить карьерные цели и предложить учебные программы для их достижения.
Кроме того, на примере сетей можно и прогнозировать события. К примеру, существуют модели, которые оценивают вероятность сбоя программного обеспечения, некоторые из них рассматривают людей как источник для прогнозов – ведь именно люди разрабатывают и тестируют продукты до релиза. Их взаимодействия образуют сеть: можно представить разработчиков как узлы, а то, работали ли они вместе над одним и тем же файлом в рамках одного релиза, как рёбра сети. Понимание взаимодействий и информация о ранее произошедших сбоях позволит многое сказать о надёжности конечного продукта и укажет на файлы, в которых риск сбоя наиболее вероятен.
Теперь попробуем применить анализ социальных сетей на практике. Для этого мы будем использовать язык программирования Python, а точнее библиотеку networkx, предназначенную для работы с графами, библиотеку matplotlib для визуализации и библиотеку community для выделения сообществ внутри сети. Давайте их импортируем:
5. Путь, диаметр и среднее расстояние в графе
Теперь давайте определим то, насколько участники нашего графа связаны между собой. Для начала поговорим о различных типах расстояний между узлами.
Любая последовательность ребер, которая соединяет узлы, называется путь. Чаще всего в исследованиях рассматривается простой путь, то есть путь без циклов и повторяющихся узлов. Кратчайший путь между двумя узлами называют геодезическим расстоянием. Самый длинный кратчайший путь в графе называют его диаметром, однако он очень чувствителен к отклонениям (одна цепочка в многомиллионном графе может изменить его диаметр). В направленных графах понятие диаметра можно применить только для компоненты сильной связности, ведь для подсчёта диаметра необходимо, чтобы для каждой пары узлов существовал путь между ними. В ненаправленных графах достаточно того, чтобы рассматриваемая компонента была связной.
Ещё одной очень информативной характеристикой считается среднее расстояние между узлами, которое можно получить, взяв среднее значение всех кратчайших путей в графе. Среднее расстояние определяется структурой графа: если граф построен в форме цепочки, оно будет большим, но чем теснее связаны узлы, тем меньше становится и среднее расстояние. Среднее расстояние можно посчитать как для компоненты сильной связности, так и для компоненты слабой связности:
Давайте разберём полученные результаты. Диаметр в данном случае показывает нам максимальное расстояние между двумя незнакомыми людьми, и здесь, как и в известной теории о шести рукопожатиях, это расстояние равно 6. Среднее расстояние в компонентах также невелико, в среднем двум незнакомым людям достаточно 2 «рукопожатий». Здесь можно также увидеть интересный феномен: среднее расстояние в компоненте сильной связности несколько ниже, чем в компоненте слабой связности. Объяснить это можно тем, что для компоненты слабой связности не учитывается направленность связей (только сам факт её наличия). Из-за этого связь в слабой компоненте появляется там, где она отсутствовала для сильной компоненты.
Граф - отображает элементный состав системы и структуру связей
Описание некоторой местности: «Автомобильные дороги проложены между: Дедкино и Бабкино, Дедкино и Кошкино, Бабкино и Мышкино, Бабкино и Кошкино, Кошкино и Репкино.
Это не карта местности. На этой схеме отражен лишь факт существования пяти поселков и дорожной связи между ними. Такая схема называется графом. Составными частями графа являются вершины и ребра.
Связи между вершинами данного графа несимметричны и поэтому
изображаются направленными линиями со стрелками. Граф с такими свойствами называется ориентированным.
Существует четыре группы крови человека.
При переливании не все группы совместимы. Данный граф показывает возможные варианты переливания крови. Например, из графа видно,что кровь I группы можно переливать любому человеку.
Направленные линии называют дугами (в отличии от ребер неориентированных графов). Линию, выходящую и входящую в одну и ту же вершину называют петлей.
Выполните задания
3. Нарисуйте родословное дерево своей семьи (только по мужской линии или только по женской) с наибольшим числом известных вам уровней. Полученной дерево приведите к табличной форме. В полях, значения которых неизвестны, поставьте прочерки.
Аннотация: Причины структуризации локальных и глобальных сетей. Физическая и логическая структуризация. Функциональное назначение основных типов коммуникационного оборудования: повторителей, мостов, коммутаторов, маршрутизаторов, а также роль сетевых служб.
Выполните задания
1. Нарисуйте два варианта графа системы «Компьютер», содержащего следующие вершины: процессор, оперативная память, внешняя память, клавиатура, монитор, принтер; а) линия связи обозначает отношение «передает информацию»; б) линия связи обозначает отношение «управляет».
Зачем мы переводили графы в табличную форму
Вам понятнее граф или таблица? С точки зрения человека, граф гораздо нагляднее и понятнее представляет структуру системы, чем таблица. А компьютеру какую форму обрабатывать легче? Для компьютерной обработки табличная форма подходит лучше. Многие компьютерные технологии (базы данных, электронные таблицы) работают с таблицами и поэтому в компьютерном моделировании чаще работают с табличным представлением.
Физическая структуризация сети
Простейшее из коммуникационных устройств — повторитель ( repeater ) — используется для физического соединения различных сегментов кабеля локальной сети с целью увеличения общей длины сети. Повторитель передает сигналы, приходящие из одного сегмента сети, в другие ее сегменты (рис. 8.1). Повторитель позволяет преодолеть ограничения на длину линий связи за счет улучшения качества передаваемого сигнала — восстановления его мощности и амплитуды, улучшения фронтов и т. п.
Повторитель , который имеет несколько портов и соединяет несколько физических сегментов, часто называют концентратором ( concentrator ) или хабом ( hub ). Эти названия ( hub — основа, центр деятельности) отражают тот факт, что в данном устройстве сосредоточены все связи между сегментами сети.
Использование концентраторов характерно практически для всех базовых технологий локальных сетей — Ethernet , ArcNet , Token Ring , FDDI , Fast Ethernet , Gigabit Ethernet .
Нужно подчеркнуть, что в работе любых концентраторов много общего — они повторяют сигналы, пришедшие с одного из их портов, на других своих портах. Разница состоит в том, на каких именно портах повторяются входные сигналы. Так, концентратор Ethernet повторяет входные сигналы на всех своих портах, кроме того, с которого сигналы поступают (рис. 8.2).
А концентратор Token Ring (рис. 8.3) повторяет входные сигналы, поступающие с некоторого порта, только на одном порту — на том, к которому подключен следующий в кольце компьютер .
Добавление в сеть концентратора всегда изменяет физическую топологию сети, но при этом оставляет без изменений ее логическую топологию .
Как уже было сказано, под физической топологией понимается конфигурация связей, образованных отдельными частями кабеля, а под логической — конфигурация информационных потоков между компьютерами сети. Во многих случаях физическая и логическая топологии сети совпадают. Например, сеть , представленная на рис. 8.4а, имеет физическую топологию "кольцо". Компьютеры такой сети получают доступ к кабелям кольца за счет передачи друг другу специального кадра — маркера, причем этот маркер также передается последовательно от компьютера к компьютеру в том же порядке, в котором компьютеры образуют физическое кольцо , то есть компьютер A передает маркер компьютеру B, компьютер B — компьютеру С и т. д.
Сеть , показанная на рис. 8.4б, демонстрирует пример несовпадения физической и логической топологии . Физически компьютеры соединены по топологии "общая шина ". Доступ же к шине происходит не по алгоритму случайного доступа , применяемому в технологии Ethernet , а путем передачи маркера в кольцевом порядке: от компьютера A — компьютеру B, от компьютера B — компьютеру С и т. д. Здесь порядок передачи маркера уже не повторяет физические связи, а определяется логическим конфигурированием драйверов сетевых адаптеров . Ничто не мешает настроить сетевые адаптеры и их драйверы так, чтобы компьютеры образовали кольцо в другом порядке, например: В, А, С. При этом физическая структура сети не изменяется.
Рис. 8.4. а) логическая и физическая структуры сети совпадают; б) логическая структура не совпадает с физической.
Другим примером несовпадения физической и логической топологий сети является уже рассмотренная сеть на рис. 8.2; Концентратор Ethernet поддерживает в сети физическую топологию " звезда ". Однако логическая топология сети осталась без изменений — это "общая шина ". Так как концентратор повторяет данные, пришедшие с любого порта, на всех остальных портах, то они появляются на всех физических сегментах сети одновременно, как и в сети с физической общей шиной . Логика доступа к сети не меняется: все компоненты алгоритма случайного доступа — определение незанятости среды, захват среды, распознавание и обработка коллизий — остаются в силе.
Физическая структуризация сети с помощью концентраторов полезна не только для увеличения расстояния между узлами сети, но и для повышения ее надежности. Например, если какой-либо компьютер сети Ethernet с физической общей шиной из-за сбоя начинает непрерывно передавать данные по общему кабелю, то вся сеть выходит из строя, и остается только одно — вручную отсоединить сетевой адаптер этого компьютера от кабеля. В сети Ethernet , построенной с использованием концентратора , эта проблема может быть решена автоматически — концентратор отключает свой порт , если обнаруживает, что присоединенный к нему узел слишком долго монопольно занимает сеть . Концентратор может блокировать некорректно работающий узел и в других случаях, выполняя роль некоторого управляющего узла.
Для сети характерна возможность множества различных путей перемещения
по ребрам между некоторыми парами вершин
Неориентированный граф (сеть)
Для сетей также характерно наличие замкнутых путей, который называются циклами
Как добраться из Р в М ?
Иерархическая структура
Система административного управления, между элементами которой установлены отношения подчиненности.
Какая связь между графом и таблицей
Попробуйте представить информацию о дорожной связи между поселками в форме таблицы.
Подведем итоги
Единственность пути между вершинами
Единственность пути между вершинами
Единственность пути между вершинами
Множественность путей между вершинами
Множественность путей между вершинами
1. Импорт данных и преобразование их в граф
В приведённом выше коде датасет был импортирован и преобразован в граф. Затем мы последовательно вывели основные параметры графа: количество узлов, рёбер и среднее количество соседей у узлов в графе. Последний параметр отражает, насколько тесно связаны узлы между собой.
Граф иерархической структуры -
Между любыми двумя его вершинами существует единственный путь.
Деревья не содержат циклов и петель
Главная вершина - корень
Листья – не имеют порожденных вершин
Причины структуризации транспортной инфраструктуры сетей
В сетях с небольшим (10–30) количеством компьютеров чаще всего используется одна из типовых топологий — "общая шина ", "кольцо", " звезда " или полносвязная сеть . Все перечисленные топологии обладают свойством однородности, то есть все компьютеры в такой сети имеют одинаковые права в отношении доступа к другим компьютерам (за исключением центрального компьютера при соединении " звезда "). Такая однородность структуры упрощает процедуру наращивания числа компьютеров, облегчает обслуживание и эксплуатацию сети.
Однако при построении больших сетей однородная структура связей превращается из преимущества в недостаток. В таких сетях использование типовых структур порождает различные ограничения , важнейшими из которых являются:
- ограничения на длину связи между узлами;
- ограничения на количество узлов в сети;
- ограничения на интенсивность трафика, который генерируют узлы сети.
Например, технология Ethernet на тонком коаксиальном кабеле позволяет использовать кабель длиной не более 185 метров, к которому можно подключить не более 30 компьютеров. Однако если компьютеры интенсивно обмениваются информацией, иногда приходится снижать число подключенных к кабелю машин до 20, а то и до 10, чтобы каждому компьютеру доставалась приемлемая доля общей пропускной способности сети.
Для снятия этих ограничений используются особые методы структуризации сети и специальное структурообразующее оборудование — повторители , концентраторы , мосты, коммутаторы, маршрутизаторы. Такого рода оборудование также называют коммуникационным , имея в виду, что с его помощью отдельные сегменты сети взаимодействуют между собой.
- Топологию физических связей ( физическую структуру сети). В этом случае конфигурация физических связей определяется электрическими соединениями компьютеров, то есть ребрам графа соответствуют отрезки кабеля, связывающие пары узлов.
- Топологию логических связей ( логическую структуру сети). Здесь в качестве логических связей выступают маршруты передачи данных между узлами сети, которые образуются путем соответствующей настройки коммуникационного оборудования .
2. Основные характеристики графов
Для того чтобы понять, как можно работать с каждым конкретным графом, вначале нужно понять, как он устроен. Давайте кратко рассмотрим характеристики, с помощью которых можно понять структуру графа.
Прежде всего рассмотрим понятия связности и направленности. Граф называется связным, если каждая пара узлов графа связана между собой, т.е. из любого узла можно прийти в любой другой узел. Если же граф несвязный, то его можно разбить на максимально связные подграфы (называемые компонентами). Также графы могут быть направленными и ненаправленными. Это определяется наличием направленности связей между двумя участниками. Одним из примеров направленной сети являются транзакции между клиентами банка, где у каждого клиента могут быть как входящие, так и исходящие платежи.
В общем случае в направленных графах связи не взаимны, поэтому для направленных графов вместо понятия связности выделяют понятия компоненты слабой и сильной связности. Компонента считается слабо связной, если при игнорировании направления получается связный граф. Компонента сильной связности может быть таковой, если все её вершины взаимно достижимы. Давайте посмотрим, какой структурой обладает граф из нашего датасета с электронной перепиской:
Граф является направленным и состоит из нескольких компонент.
Здесь мы провели проверку на направленность и связность графа и выяснили, что граф из датасета является направленным и содержит несколько несвязных компонент. Давайте попробуем посмотреть поближе на самые крупные компоненты сильной и слабой связности:
Итак, мы получили основные характеристики для компоненты слабой связности и для входящей в неё компоненты сильной связности. Давайте посмотрим, какие выводы мы можем сделать на этом этапе. Мы видим, что из 1005 участников друг с другом общаются 986 человек, при этом 183 человека из них отправляли электронные письма другим людям в одностороннем порядке, и только 803 человека поддерживали двустороннее общение. В 823 случаях попытка наладить коммуникацию посредством электронной почты оказалась провальной. Также мы видим, что наиболее активные участники (входящие в компоненту сильной связности) поддерживают коммуникацию в среднем с 30 людьми.
Кроме того, узлы и связи могут создавать различные типы сетей: однодольные, двудольные или многоуровневые. Однодольные сети состоят из одного типа участников и связей между ними. Двудольные сети состоят из двух разных типов участников, где один из типов узлов связан только с другим типом. Многоуровневые сети также включают два типа участников, однако связи могут соединять как участников разных типов, так и однотипных участников (например, отношения между менеджерами и отношения между проектами). Взятый нами для исследования датасет представляет собой сеть однодольного типа, так как состоит только из одного типа участников и связей между ними.
Структура данных
Выполните задания
2. Нарисуйте произвольную структуру глобальной компьютерной сети в виде графа, в котором вершины обозначают серверы, а ребра – линии связи. Опишите эту сеть в виде двоичной матрицы смежности.
Если сеть является неориентированным графом, то матрица смежности
симметрична относительно главной диагонали.
Таблицы
В какой форме представлена информация?
Табличный способ представления данных является универсальным
Кол-во учителей в %
Тренажеры для оттачивания различных навыков
6. Кластеризация и выделение сообществ
C расстояниями между участниками разобрались, давайте перейдём к другим явлениям, отражающим, насколько участники в графе связаны между собой: кластеризации и сообществам.
Кластерный коэффициент показывает то, что два элемента графа, связанные через третий элемент, с высокой долей вероятности связаны и друг с другом. Даже если они не связаны, то вероятность того, что они окажутся связанными в будущем, гораздо выше, чем у двух других случайно взятых узлов. Это явление, называемое кластеризацией или транзитивностью, чрезвычайно распространено в социальных графах.
Для графов с высокой степенью кластеризации характерно присутствие значительного количества связанных троек (трёх узлов, связанных друг с другом). Они являются строительным блоком многих социальных сетей, где количество подобных треугольников очень велико. Часто возникают даже не треугольники, а целые кластерные образования, называемые сообществами, которые связаны между собой теснее, чем с остальным графом.
Посмотрим на кластеризацию и кластерный коэффициент для компоненты слабой связности:
Для компоненты сильной связности мы можем получить те же характеристики, а также определить количество центральных узлов (узлов, которые сильнее всего связаны с остальными) и количество узлов на периферии графа:
Во втором случае кластеризация и кластерный коэффициент увеличились, это отражает, что в компоненте сильной связности содержится большее количество связанных троек. Давайте попробуем вместе определить основные сообщества в компоненте слабой связности:
Итак, в графе с электронной перепиской можно выделить 8 сообществ, которые связаны между собой теснее, чем с остальным графом. Самое маленькое из сообществ содержит 54 участников, а самое крупное – 188 участников. Для сетей, содержащих перекрывающиеся или вложенные сообщества, определить оптимальное разбиение может оказаться сложнее. Поэтому при каждом запуске кода состав сообществ может различаться. Посмотрим визуализацию для полученного нами разбиения:
На изображенном выше графе мы видим распределение участников по сообществам, где цвет узлов описывает принадлежность тому или иному сообществу.
8. Универсальные свойства сетей
- Распределение степеней узлов. Во всех сетях есть много узлов с низкой степенью, в то же время есть небольшое количество огромных узлов, у которых соседей очень много. Это логично: если мы посмотрим на ссылки между различными web-сайтами, то обнаружим, что существует небольшое количество крупных сайтов, на которые в большом количестве ссылаются все остальные (Wikipedia, Microsoft). В то же время на среднестатистические сайты ссылки встречаются гораздо реже, хотя большинство сайтов относятся именно к такому типу.
- Диаметр и среднее расстояние в графе. Крупные сети имеют такое устройство, что средний диаметр у них очень небольшой, это явление в анализе социальных сетей называется явлением «малого мира». Оно хорошо описывается через теорию шести рукопожатий: несмотря на огромное количество людей, среднее расстояние между двумя незнакомыми людьми будет равным шести.
- В больших сетях, как правило, присутствуют гигантские связные компоненты: более 80% узлов связаны между собой, остальные представлены более мелкими компонентами. При этом в каждой из крупных компонент можно встретить сообщества – группы объектов, которые связаны между собой теснее, чем с остальным графом. Наличие кластеризации, то есть большого количества таких сообществ, чрезвычайно распространено в социальных графах.
- Во многих социальных графах действует принцип взаимности, когда при наличии исходящей связи очень высока вероятность встретить и входящую связь. Эта концепция специфична для направленных сетей, поскольку взаимность и обмен являются фундаментальными социальными процессами.
Структура данных:
Деревья, сети, графы, таблицы
Разработала учитель информатики МБОУ «СОШ №5 г.Азнакаево» РТ Габдуллина Ф. М.
4. Степень узла и распределение степеней узлов
Теперь, когда мы знаем структуру нашего графа и умеем его визуализировать, давайте перейдём к более детальному анализу. У каждого узла в графе есть степень – количество ближайших соседей этого узла. В направленных сетях можно различать как степень входа (количество входящих связей с узлом), так и степень выхода (количество исходящих связей с узла). Если для каждого узла графа посчитать степень, можно определить распределение степеней узлов. Давайте посмотрим на него для графа с электронной перепиской:
Примеры иерархических структур - деревьев
3. Визуализация графа
А теперь давайте попробуем визуализировать взятый нами датасет. Для этого нам понадобится библиотека matplotlib, уже импортированная нами выше:
В первой строке задаётся размер будущего изображения, которому затем присваивается определённое название. В третьей строке функции draw передаётся граф и указывается размер узлов, после чего граф выводится на экран. Давайте на него посмотрим:
На получившемся графе мы видим, что существует ряд точек, не связанных с остальными участниками коммуникации. Эти люди, не связанные с остальными участниками, попали на граф, поскольку отправляли письма исключительно сами себе. Также можно заметить, что на периферии расположен ряд точек, которые связаны с остальным графом немногочисленными входящими связями, – это участники, которые попали в компоненту слабой связности для нашего графа, но не попали в компоненту сильной связности.
Давайте также рассмотрим граф, иллюстрирующий компоненту сильной связности – людей, которые поддерживают двустороннюю коммуникацию с другими участниками исследовательского учреждения:
Таблица типа "объект-свойство"
Таблица типа "объект-объект"
Таблица типа «двоичная матрица»
Примечания
С полным текстом исследования можно ознакомиться в книге Николая Викторовича Урсул «Вся правда о Forex» (2019).
Исследование описано в статье «The Application of Social Network Analysis to Accounting and Auditing» Slobodan Kacanski, Dean Lusher (2017, ссылка).
Презентация: «Структура данных». Автор: Фарида Мирзагитовна. Файл: «Структура данных.pptx». Размер zip-архива: 1103 КБ.
7. Взаимность связей
Кроме уже описанных свойств также существует такое понятие, как взаимность в направленной сети. Эта характеристика описывает, какой процент исходящих связей имеет обратную, входящую, связь. Для того, чтобы это узнать, используем специальную функцию overall_reciprocity библиотеки networkx и посмотрим на уровень взаимности в графе и его компонентах:
У матрицы, отражающий ориентированный граф, симметричности не будет
Попробуйте представить информацию о группах крови в форме таблицы.
Читайте также: