Python - данные графика

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

Графические представления

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

Что такое разреженный граф?

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

Один очень эффективный способ представления данных графа - это разреженная матрица: назовем ее G. Матрица G имеет размер N x N, а G [i, j] дает значение связи между узлом 'i' и узлом 'j'. Разреженный граф содержит в основном нули, то есть большинство узлов имеют только несколько соединений. Это свойство оказывается верным в большинстве интересных случаев.

Создание подмодуля разреженного графа было мотивировано несколькими алгоритмами, используемыми в scikit-learn, которые включали следующее:

Isomap - Алгоритм обучения многообразию, который требует нахождения кратчайших путей в графе.
Hierarchical clustering - Алгоритм кластеризации на основе минимального связующего дерева.
Spectral Decomposition - Алгоритм проектирования, основанный на лапласиане разреженных графов.

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

Этот граф имеет три узла, где узел 0 и 1 соединены ребром веса 2, а узлы 0 и 2 соединены ребром веса 1. Мы можем построить плотное, замаскированное и разреженное представления, как показано в следующем примере. , имея в виду, что неориентированный граф представлен симметричной матрицей.

G_dense = np.array([ [0, 2, 1],
                     [2, 0, 0],
                     [1, 0, 0] ])
                     
G_masked = np.ma.masked_values(G_dense, 0)
from scipy.sparse import csr_matrix

G_sparse = csr_matrix(G_dense)
print G_sparse.data

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

array([2, 1, 2, 1])

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

Рассмотрим следующий пример.

from scipy.sparse.csgraph import csgraph_from_dense
G2_data = np.array
([
   [np.inf, 2, 0 ],
   [2, np.inf, np.inf],
   [0, np.inf, np.inf]
])
G2_sparse = csgraph_from_dense(G2_data, null_value=np.inf)
print G2_sparse.data

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

array([ 2., 0., 2., 0.])