우노

Matrix Multiplication 을 통한 Multi Source BFS Search Directed Graph 는, 특정 노드와 인접한 노드를 Matrix Multiplcation 을 통해 찾을 수 있습니다. 전체 흐름 세부 설명 예를 들어, 아래와 같은 Directed Graph 가 주어졌을 때 해당 Directed Graph 는 아래와 같은 Matrix 로 표현할 수 있습니다. col : 시작 노드 row : 도착 노드 이때, 해당 Directed Graph 에서 3번 노드, 5번 노드와 인접한 노드를 찾고자 한다면 Directed Graph Matrix 에 아래와 같은 Matrix 를 곱해주면 됩니다. col : 시작 노드로 지정할 노드의 개수 row : 시작 노드의 번호 따라서, 아래와 같..

Matrix data SNAP Stanford는 다양한 Graph dataset을 제공한다. http://snap.stanford.edu/data/index.html 해당 포스트에서는 Networks with ground-truth communities의 하위 Graph dataset을 Matrix dataset으로 변환해 사용했으며, 변환하기 위해선 몇가지 전처리가 필요하다. https://wooono.tistory.com/177?category=914989 Matrix dataset이 준비됐다면, 이제 Matrix의 Node 별 NNZ를 계산해 볼 것이다. 위 과정에서 전처리한 Matrix dataset은 대칭행렬이기 때문에 행 기준 or 열 기준 Node 별 NNZ 값은 동일하다. Matrix의 N..

SNAP Stanford SNAP Stanford에는 다양한 Graph dataset을 제공한다. http://snap.stanford.edu/data/index.html 이 포스트에서는 Networks with ground-truth communities의 하위 데이터들을 사용했다. Graph data type SNAP Stanford에서 Graph data는, 두 가지 type(Undirected, Directed)으로 구성 되어있다. Undirected edge에 방향이 없는 대칭 그래프 예) Undirected graph data (Nodes : 334863, Edges : 925872) 내부 1 88160 1 118052 1 161555 . . . 548368 548454 548391 54841..

Graph data Graphalytics에서는 테스트 및 표준 벤치 마크에 사용되는 Graph dataset를 제공한다. https://graphalytics.org/datasets "datagen-*" 로 시작하는 데이터가 임의로 만든 Graph dataset 이다. 원하는 파일을 다운로드 후 압축을 해지하면 다양한 파일들이 존재한다. 입력 데이터 (정점 및 에지 파일) 각 알고리즘 (BFS, WCC, PR, CDLP, LCC, SSSP)에 대한 유효성 검사 데이터 및 메타 데이터 (속성 파일) Matrix data를 사용하고 싶다면 확장자명이 .e로 끝나는 파일을 사용하면 된다. Matrix data 확장자명이 .e로 끝나는 Matrix data를 활용하기 위해선 몇가지 전처리가 필요하다. 1) v..

COO(Coordinate list) Coordinate list는 좌표리스트라는 뜻으로, (행, 열, 값)의 튜플 목록으로 Matrix를 저장하는 방법이다. CSR(Compressed Sparse Row) 데이터를 행(가로)의 순서대로 정리 압축하는 방법이다. 구성요소 행 순서대로 데이터 배열(A) 행 순서대로 데이터의 열 인덱스 배열(JA) 행 압축 정보 배열(IA) 행 압축 정보 배열은 [최초 시작 행번호, 시작 행에서의 데이터 누적 개수, 두번째 행에서의 데이터 누적 개수,..., 마지막 행에서의 데이터 누적개수]이다. CSC(Compressed Sparse Column) 데이터를 열(세로)의 순서대로 정리 압축하는 방법이다. 구성요소 열 순서대로 데이터 배열 열 순서대로 데이터의 행 인덱스 배열..

참고사이트(graph500) → https://graph500.org/?page_id=12 SCALE=15 edgefactor=32 %% Set number of vertices. N = 2^SCALE; %% Set number of edges. M = edgefactor * N; %% Set initiator probabilities. [A, B, C] = deal (0.57, 0.19, 0.19); %% Create index arrays. ijw = ones (3, M); %% Loop over each order of bit. ab = A + B; c_norm = C/(1 - (A + B)); a_norm = A/(A + B); for ib = 1:SCALE, %% Compare with prob..

Definitions Graph, Vertex, Edge 그래프 이론에 대해 공부하기 위해 가장 기본이 되는 정의(definition)부터 살펴보자. 그래프(graph)와 정점(vertex or node), 그리고 에지(edge)에 대한 정의는 다음과 같다. G(V, E) : Graph G는 V(vertex set)와 E(edge set)로 이루어져있다. Undirected / Directed graph edge set을 어떻게 정해 주느냐에 따라 Undirected graph, Directed graph로 나뉘게 된다. Undirected graph 대칭 행렬이다. e = (a, b) = (b, a) edge에 방향이 없어 (a,b)를 (b,a)로 나타내도 상관 없는 그래프를 의미한다. 예) Snap ..