NetAnalisys

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

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

Содержание

• Что делает проект
• Текущие возможности
• Требования
• Установка и запуск
• Как пользоваться программой
• Поддерживаемые форматы графов
• Как устроен анализ
• Интерактивный режим landmarks
• Выходные файлы
• Структура проекта
• Проверки качества и разработка
• Ограничения и известные проблемы
• Направления улучшения

Что делает проект

Приложение загружает граф из файла и вычисляет набор структурных метрик сети:

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

После основного анализа программа также может открыть интерактивный режим для landmark-оценки расстояний и простого accuracy-бенчмарка относительно точного BFS.

Текущие возможности

Текущая реализация уже поддерживает:

• загрузку графов из txt, csv и mtx
• обработку ориентированных и неориентированных графов
• переназначение внешних ID вершин во внутренние компактные ID
• построение графиков распределения степеней в терминале и в PNG
• поиск компонент слабой связности
• поиск SCC через алгоритм Тарьяна для ориентированных графов
• подсчет треугольников
• вычисление среднего и глобального коэффициентов кластеризации
• несколько стратегий приближенного вычисления диаметра
• анализ устойчивости к удалению вершин
• интерактивные запросы расстояний через landmarks
• accuracy-бенчмарк для landmark-оценок

Что реализовано только частично:

• пункт меню speed_benchmark в landmark-режиме пока является заглушкой
• автоматизация качества существует только как ручные команды, без CI
• тестовое покрытие по сути отсутствует

Требования

Для запуска проекта нужны:

• стабильный toolchain Rust
• cargo
• терминал с поддержкой интерактивного ввода через crossterm

Рекомендуемая проверка:

rustc --version
cargo --version

Установка и запуск

Клонируйте репозиторий и запустите приложение из корня проекта:

cargo run

Программа откроет интерактивное текстовое меню.

Если в репозитории уже есть примерные графы в каталоге graphs/, их можно использовать сразу. В текущем репозитории есть, например:

• graphs/Directed/web-Google.txt
• graphs/Directed/Wiki-Vote.txt
• graphs/Directed/soc-wiki-Vote.mtx
• graphs/Undirected/musae_git_edges.csv
• graphs/Very Big Graphs/vk.csv

Как пользоваться программой

Основной сценарий

1. Запустите программу командой cargo run.
2. В стартовом меню выберите Load graph from file.
3. В файловом меню выберите датасет из репозитория.
4. Выберите метод вычисления диаметра:
   • Double BFS
   • Random 500 BFS
   • Snowball sampling
   • All methods simultaneously
5. Дождитесь завершения парсинга и анализа.
6. Просмотрите построенные графики в терминале и PNG-файлы.
7. В меню после анализа выберите один из вариантов:
   • View analysis results
   • Interactive landmark distance estimation
   • Exit

Управление

Большинство меню поддерживает:

• стрелки Up / Down для навигации
• Enter для выбора
• q или Esc для выхода/возврата
• прямой числовой выбор в некоторых меню

Что происходит во время анализа

После загрузки графа программа:

1. Парсит выбранный файл.
2. Строит представление графа в памяти с внутренними компактными ID.
3. Вычисляет ряд метрик параллельно там, где это реализовано.
4. Печатает графики распределения степеней в терминале.
5. Сохраняет PNG-графики на диск.
6. Записывает замеры производительности в лог-файлы.
7. Открывает меню результатов для дальнейшей работы.

Поддерживаемые форматы графов

Парсер сейчас поддерживает три расширения файлов:

• .txt
• .csv
• .mtx

txt

Ожидаемый формат:

u v
v w
x y

Поведение:

• поля разделяются ASCII-пробелами
• строки, начинающиеся с #, игнорируются
• пустые строки игнорируются

csv

Ожидаемый формат:

u,v
v,w
x,y

Поведение:

• поля разделяются запятой
• пробелы по краям полей обрезаются
• строки, начинающиеся с #, игнорируются
• пустые строки игнорируются

mtx

Формат интерпретируется как пары ребер после заголовка:

%%MatrixMarket matrix coordinate pattern symmetric
% comment
5 5 4
1 2
2 3
3 4
4 5

Поведение:

• строки, начинающиеся с %, игнорируются
• дополнительно пропускается первая непустая строка после комментариев как строка размерности/заголовка
• остальные строки парсятся как пары вершин, разделенные пробелами

Как определяется тип графа

Это важный момент: программа сейчас не определяет направленность графа по содержимому файла.

Вместо этого она смотрит на имя родительской папки выбранного файла:

• если родительская папка называется Directed, граф считается ориентированным
• если родительская папка называется Undirected, граф считается неориентированным
• во всех остальных случаях граф по умолчанию считается неориентированным

Примеры:

• graphs/Directed/web-Google.txt -> ориентированный граф
• graphs/Undirected/CA-GrQc.txt -> неориентированный граф
• любой файл вне этих названий папок -> по умолчанию неориентированный

Как устроен анализ

Представление графа

Основная структура графа хранит:

• списки смежности по внутренним ID вершин
• отображение внешних ID датасета во внутренние ID
• обратное отображение внутренних ID в исходные ID
• флаг типа графа

Это позволяет программе работать с произвольными ID вершин из датасета и при этом использовать компактное внутреннее представление для обходов.

Вычисляемые метрики

Базовая информация о графе

Программа всегда вычисляет:

• тип графа
• число вершин
• число ребер
• плотность

Для неориентированных графов плотность вычисляется как:

2E / (V * (V - 1))

Для ориентированных графов:

E / (V * (V - 1))

Связность

В анализ входят:

• компоненты слабой связности
• число компонент слабой связности
• доля вершин в крупнейшей слабой компоненте

Для ориентированных графов дополнительно вычисляются:

• компоненты сильной связности через алгоритм Тарьяна
• число компонент сильной связности
• доля вершин в крупнейшей сильной компоненте

Анализ степеней

Приложение вычисляет:

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

Создаются два визуальных результата:

• обычный график распределения степеней
• log-log график распределения степеней

Приближенное вычисление диаметра

Доступны следующие стратегии:

• Double BFS
  • выбирается стартовая вершина
  • ищется максимально удаленная достижимая вершина
  • затем выполняется второй BFS из этой вершины
  • максимальное найденное расстояние используется как оценка
• Random 500 BFS
  • многократно выбираются случайные стартовые вершины
  • из каждой запускается BFS
  • сохраняется максимальное найденное расстояние
• Snowball sampling
  • строится BFS-подобная выборка части графа
  • диаметр оценивается на этой выборке
• All methods simultaneously
  • запускаются все методы и выводятся все результаты

Текущая реализация ориентирована на практические приближения, а не на точное вычисление диаметра через полный all-pairs подход.

Перцентиль расстояний

Программа вычисляет 90 percentile of distance of the graph, то есть практическую сводную характеристику наблюдаемых расстояний в графе.

Треугольники и кластеризация

В анализ входят:

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

Анализ устойчивости

Измеряются два сценария устойчивости:

• случайное удаление 5%..100% вершин
• удаление вершин наибольшей степени с шагом 5%

Для каждого шага программа выводит долю активных вершин, которая остается в крупнейшей слабой компоненте.

Интерактивный режим landmarks

После завершения основного анализа выберите:

Interactive landmark distance estimation

Это открывает отдельный TUI-режим для приближенных запросов кратчайших путей.

Доступные пункты меню

• Query distance between two vertices
• Accuracy benchmark (vs exact BFS)
• Speed benchmark (landmarks only)
• Change number of landmarks
• Change strategy of landmarks samples
• Back to main menu

Стратегии выбора landmarks

Сейчас поддерживаются:

• Random
• Highest degree
• Farthest-first coverage

Запрос расстояния

Пользователь вводит два ID вершин в том виде, в котором они были в исходном датасете.

После этого программа показывает:

• точное расстояние через BFS
• оценку Basic LM
• оценку BFS LM
• время работы каждого метода

Если вершина отсутствует в графе, интерфейс выводит предупреждение.

Accuracy benchmark

Бенчмарк:

• выбирает заданное пользователем число случайных пар вершин
• считает точный BFS и обе landmark-оценки
• сравнивает число точных совпадений и среднюю/максимальную ошибку
• показывает среднее время работы точного BFS и обоих landmark-подходов

Speed benchmark

Текущее состояние:

• пункт меню существует
• реализация не завершена
• функция пока выводит сообщение-заглушку и завершает работу

Это следует считать незавершенной функциональностью.

Выходные файлы

После анализа программа может создать в корне проекта следующие файлы:

• degree_data1.png
  • PNG-график распределения степеней
• log_degree_data.png
  • PNG-график логарифмированного распределения степеней
• performance.log
  • лог длительности основных этапов анализа
• trace.log
  • лог стартов ключевых этапов пайплайна

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

Структура проекта

Текущая структура исходников:

src/
  analysis/
  graph/
  interactive_landmarks/
  landmarks/
  parser/
  ui/
  main.rs

src/analysis

Содержит реализации метрик графа:

• связность
• степени
• диаметр
• устойчивость
• подсчет треугольников
• оценка кластеризации

src/graph

Содержит структуру графа и вспомогательные функции обхода, такие как BFS/DFS и связанные утилиты.

src/parser

Содержит:

• обработку типа файла
• enum для directed/undirected
• логику парсинга файлов

src/ui

Содержит основной terminal UI:

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

src/interactive_landmarks

Содержит TUI-сценарий для интерактивного исследования landmark-оценок расстояний и бенчмарков.

src/landmarks

Содержит два текущих landmark-подхода:

• LandmarkBasic
• LandmarkBFS

Проверки качества и разработка

Полезные команды:

cargo build
cargo run
cargo test
cargo fmt
cargo clippy --all-targets --all-features

Текущее фактическое состояние проверок

На момент подготовки этого README:

• cargo test завершается успешно
• в проекте сейчас 0 тестов
• cargo clippy --all-targets --all-features -- -D warnings пока не проходит

Это означает, что проект запускается, но инженерные quality gate'ы пока не доведены до нормального состояния.

Ограничения и известные проблемы

Текущие ограничения проекта:

• нет автоматического тестового покрытия публичного поведения
• clippy -D warnings сейчас падает
• во многих runtime-сценариях используются unwrap / expect
• парсинг достаточно мягкий и может молча пропускать некорректные строки
• тип графа определяется по имени родительской папки, а не по содержимому файла или явному CLI-параметру
• speed_benchmark в landmark-режиме не реализован
• основной бинарник смешивает UI, orchestration, logging и вычисления в одном потоке
• проект сейчас работает как бинарное приложение, а не как переиспользуемая библиотека

Возможные практические последствия:

• неожиданная ошибка терминала или входных данных может привести к panic
• рефакторинг рискован, потому что нет regression-test сетки
• часть поведения на поврежденных датасетах недостаточно прозрачно видна пользователю

Направления улучшения

Наиболее важные следующие шаги:

1. Добавить автотесты для parser, graph structure, connectivity, diameter и triangle counting.
2. Довести cargo clippy --all-targets --all-features -- -D warnings до зеленого состояния.
3. Заменить unwrap / expect в критичных runtime-путях на нормальную обработку ошибок.
4. Разбить крупные UI и orchestration-модули на более мелкие и сфокусированные.
5. Выделить движок анализа в библиотечный crate помимо TUI-бинарника.
6. Сделать тип графа явным параметром, а не зависимостью от имени папки.
7. Нормально реализовать отсутствующий landmark speed benchmark.

Примечание

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