Python-그래프 데이터

CSGraph는 Compressed Sparse Graph, 희소 행렬 표현을 기반으로 한 빠른 그래프 알고리즘에 중점을 둡니다.

그래프 표현

우선, 희소 그래프가 무엇이며 그래프 표현에 어떻게 도움이되는지 이해하겠습니다.

희소 그래프 란 정확히 무엇입니까?

그래프는 노드 사이에 링크가있는 노드 모음 일뿐입니다. 그래프는 거의 모든 것을 나타낼 수 있습니다. 소셜 네트워크 연결, 각 노드는 사람이고 지인과 연결됩니다. 각 노드가 픽셀이고 인접 픽셀에 연결되는 이미지; 각 노드가 가장 가까운 이웃과 실제로는 상상할 수있는 모든 것에 연결되는 고차원 분포의 점입니다.

그래프 데이터를 표현하는 매우 효율적인 방법 중 하나는 희소 행렬을 사용하는 것입니다. G라고 부르겠습니다. 행렬 G는 크기 N x N이고 G [i, j]는 노드 'i'와 노드 간의 연결 값을 제공합니다. '제이'. 희소 그래프는 대부분 0을 포함합니다. 즉, 대부분의 노드에는 연결이 거의 없습니다. 이 속성은 대부분의 관심 사례에서 사실로 밝혀졌습니다.

희소 그래프 하위 모듈의 생성은 다음을 포함하는 scikit-learn에서 사용 된 여러 알고리즘에 의해 동기가 부여되었습니다.

Isomap − 그래프에서 최단 경로를 찾아야하는 다양한 학습 알고리즘.
Hierarchical clustering − 최소 스패닝 트리를 기반으로하는 클러스터링 알고리즘.
Spectral Decomposition − 희소 그래프 라플라시안에 기반한 프로젝션 알고리즘.

구체적인 예로서, 다음 무 방향 그래프를 표현하고 싶다고 상상해보십시오.

이 그래프에는 노드 0과 1이 가중치 2의 가장자리로 연결되고 노드 0과 2가 가중치 1의 가장자리로 연결되는 3 개의 노드가 있습니다. 다음 예제와 같이 조밀하고 마스킹 된 희소 표현을 구성 할 수 있습니다. , 무 방향 그래프는 대칭 행렬로 표현된다는 점을 명심하십시오.

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가 가중치가 0 인 모서리로 연결된다는 점을 제외하면 이전 그래프와 동일합니다. 이 경우 위의 조밀 한 표현은 모호함으로 이어집니다. 0이 의미있는 값인 경우 가장자리가 아닌 것을 어떻게 표현할 수 있습니까? 이 경우 모호성을 제거하기 위해 마스크 또는 희소 표현을 사용해야합니다.

다음 예를 살펴 보겠습니다.

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.])