Графы и деревья: почему социальные сети похожи на паутину

Математический фундамент и типы связей

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

Разбери разницу между ориентированными и неориентированными графами на практических примерах. ВКонтакте или ранний Facebook требуют взаимного подтверждения контакта, поэтому граф связей там ненаправленный. Платформы с механикой подписок вроде Twitter или каналов в Telegram формируют ориентированные графы, где ребро от пользователя А к пользователю Б вовсе не гарантирует обратной связи. Дополнительно объясни концепцию взвешенного графа, где вес ребра отражает число совместных сообщений или частоту взаимодействий.

Отличие сети друзей от дерева распространения информации

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

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

Топология паутины и ключевые метрики

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

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

Что преподаватель оценивает в математическом реферате

• Строгость математического аппарата при формулировании определений смежности, инцидентности, путей, циклов и связности.
• Умение записать структуру графа в матричном виде через матрицу смежности и матрицу инцидентности для демонстрационного примера из 5–7 вершин.
• Корректность сопоставления математических формул с реальными явлениями интернет-платформ без подмены определений вольными аналогиями.
• Анализ алгоритмов обхода графа в ширину и в глубину как базового инструмента поиска кратчайшего пути между двумя профилями.

Где брать данные и теоретическую базу

Теоретические определения бери из университетских учебников по дискретной математике, например из книги Фрэнка Харари «Теория графов» или учебника Оре Ойстина. Для прикладной части используй открытые коллекции реальных графов Stanford Network Analysis Project (SNAP). Там выложены анонимизированные срезы графов Facebook, Twitter и научных цитирований, пригодные для расчета средних путей и диаметров реальных сообществ.