• Теоретическая часть
• Использование программы
• Логика программы
• Тесты
• Оценка сложности

Для запуска необходим python версии не менее 2.7. Команда:

python markov_clustering.py <input_file.csv> <output>

Обязательным параметром для запуска является <input_file.csv>, прочий необязателен. По умолчанию файл вывода будет создан в корневой папке проекта с именем output. Также в консоль выводится краткая информация о выполненной программе.

Пример использования:

input_file.csv - это граф, заданный матрицей смежности взвешенного графа в виде таблицы формата *.csv.

Файл выхода программы, по умолчанию output, содержит полученные кластеры графа, выведенные в виде ассоциативного массива: индекс кластера -> список содержащихся в нем вершин по индексам, взятым из матрицы смежности. (см. пример из двух кластеров)

Точность создания кластеров алгоритмом регулируется задаваемыми константами, которые можно найти в файле config.py. Среди них:

• inflate_factor - фактор накачивания - константа, использующаяся в операторе накачивания алгоритма как степень r (см. формула операции накачивания). При значениях inflate_factor > 1 накачивание преобразует элементы матрицы, являющиеся вероятностями перехода из одного состояния в другое для конкретной вершины (соответующей столбцу матрицы), в элементы более вероятных прогулок. Чем выше параметр, тем больше находится кластеров.
• max_loop - максимальное количество итераций, по умолчанию стоит 100, для более высокой точности можно выставить больше итераций, но оптимально иметь 100. В действительности в большинстве случаев количество итераций будет меньше, так как будет достигнуто устойчивое состояние матрицы (разница двух подряд идущих матриц при заданной точности accuracy будет равна 0).
• loop_value - константа, задающая значения диагональных элементов матрицы, говоря понятием графа: вес петли в графе. Если верить автору алгоритма, оптимально иметь значение, равное 1. Увеличение приведет к более высокой гранулярности графа (степени разбиения).
• accuracy - точность - константа задает порядок, которым можно пренебречь при расчете вероятности. Используется в подсчете разницы двух подряд идущих матриц. Чем выше точность, тем больше итераций алгоритма, и наоборот.

Точка входа программы - функция main файла markov_clustering.py. Она считывает с входного потока имя входного и выходного файлов и передает их в функцию mcl_manager, попутно обрабатывая исключения ввода имен файлов и исключения работы алгоритма.

Модуль mcl_manager.py состоит из функций:

• reader(filename) - принимает на вход файл формата *.csv и преобразует его в питоновский лист листов, по сути в матрицу.
• mcl_manager(input_file, output_file) - функция-менеджер алгоритма: считывает матрицу из файла (функция reader), запускает алгоритм кластеризации на полученной матрице (функция mcl) и записывает результат в файл (функция clusters_to_output). Также выводит информацию о ходе программы.

Далее программа переходит в модуль mcl.py. В ней реализованы алгоритмы, специфичные для кластеризации Маркова. Это подразумевает, что в этом же файле реализован и сам алгоритм кластеризации. Этот модуль также активно использует операции над матрицами, реализованные в модуле matrix.py Соотвественно состоит из функций:

• expansion(matrix) - реализует оператор распространения, необходимый для вычисления алгоритма (см. распространение)
• inflation(matrix, inflate_factor) - реализует оператор накачивания (см. накачивание)
• mcl(matrix, inflate_factor, max_loop, loop_value, accuracy) - главная функция, реализующая алгоритм. По сути алгоритм представляет собой следующие шаги:

1. Добавить в matrix петли с весом LOOP_VALUE.
2. Нормализовать matrix: привести к стохастическому виду.
3. Накачивание с INFLATE_FACTOR
4. Распространение.
5. Посмотреть изменения текующей матрицы с предыдущей с заданной точностью ACCURACY, если 0 или число итераций превысило MAX_LOOP - завершить алгоритм, иначе - перейти к шагу 3.
6. Получить кластеры из получившейся устойчивой матрицы.

Для работы с получением и выводом кластеров реализован модуль clusters.py.

• get_clusters(matrix) - на вход матрица в устойчивом состоянии (см. пример такой матрицы для графа из файла 2.csv), из нее получает ассоциативный массив кластеров.
• clusters_to_output(clusters, output_file) - записывает ассоциативный массив clusters кластеров в файл output_file.

В функции основного файла mcl.py алгоритма активно используются операции над матрицами, представленными в виде листа листов, реализованные в модуле matrix.py.

Среди функций этого модуля наибольший интерес представляет функция перемножения матриц. Так как стандартное перемножение на практике с графом с 300 вершинами за одну итерацию дает время выполнения в 7 секунд, было решено оптимизировать алгоритмом Штрассена strassen_multiplication(a, b, c). (теперь занимает 5 секунд) На графах с менее чем 64 вершинами используется стандартное умножение multiply(a, b).

Реализовано два блока тестов: тесты модуля matrix и тесты корректной работы программы.

Запуск тестов модуля:

python -m unittest -v tests.matrix_test

Запуск тестов программы:

python -m unittest -v tests.mcl_test

На вход тестов программы подаются файлы из директории tests/examples/*.csv. Тестовые файлы оттуда проверяют базовые случаи для графов с количеством вершин не более 7, так как для более крупных графов, начиная уже с 10 вершин, нельзя точно выявить, на какие кластеры разобьется граф и проверку тестов не получится автоматизировать.

Подробное описание каждого теста:

1. 1.csv - единичная матрица, что подразумевает под собой полный граф. Очевидно, что в таком случае кластер будет один и состоять из всех вершин.
2. 2.csv - граф, в котором интуитивно понятно, что образются два кластера: соединены между собой 1, 2, 3 вершины и отдельно 4, 5, 6, 7, а между ними соединены 3 и 4.
3. 3.csv - диагональная матрица, что означает, что это граф, в котором вершины между собой не связаны, но у всех есть петли. Соотвественно кластеров должно быть столько же, сколько и вершин.
4. 4.csv - граф, в котором связаны только первая и вторая вершины и отсутствуют петли. Очевидно, что вершины 1, 2 в одном кластере, остальные - разделены по своим собственным.
5. 5.csv - граф, практически индентичный 2.csv. Ожидается, что в итоге получится 2 кластера (как и в тесте 2, но выставлены случайные петли у вершин).

Тесты модуля matrix.py проверяют правильность выполнения содержащихся в нем функций на простых примерах.

Условимся за считать количество вершин графа.

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

Затем работает сам алгоритм. В моем случае, в конфигурации выставлено, что максимальное количество итераций равно 100. Автор алгоритма утверждает, что количество подобных итераций будет равно , где - максимальная степень вершины графа.

В алгоритме используются операции накачивания и расширения.

Накачивание - это нормализация матрицы (то есть по сути просто пройтись по матрице) и возвести в степень по правилу Адамара (тоже один проход по матрице). Итого .

Расширение - это перемножение матрицы самой на себя. Обычное перемножение матрицы самой на себя по сложности .

Однако в программе используется алгоритм Штрассена, согласно которому умножение матриц проводится рекурсивно для матриц размера , над которыми проводится 7 операций перемножения из введенных дополнительных матриц:

.

Из которых любую матрицу можно разбить на четыре соотношением:

Получается реккурентное соотношение вида: , из которого сложность будет равна .

Остаются функции converged, rounding и get_clusters, в которых опять же проходишься по матрице за .

Вывод кластеров в файл занимает и плюс количество кластеров.

Итого вычислительная сложность:

42 (нажми меня)

Хранение матрицы смежности, как в файле csv, так и в листе листов .

Функции работы с матрицами, использующие дополнительную память, выделяют не больше чем дополнительной памяти (так как просто создают новую матрицу nxn).

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

Итого .