[Graph] SNAP Stanford 의 Undirected Graph data 를 Matrix data 로 변환하는 방법

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    548411
        548411    548458

      • Node의 유니크한 숫자 개수는 334863개이며 한 쪽 방향의 Edge(line)의 개수는 925872개이다.
      • 만약, 해당 Undirected Graph data를 Matrix data로 사용하고 싶다면
      • Node를 정렬해서 Node의 index를 0 ~ 334863 로 재설정하고
      • 한쪽 방향의 edge만 표현 되어있으므로 반대 방향의 edge도 추가해야한다.
      • 또한 모든 edge에 element도 할당해줘야한다.

  • Directed

    • edge에 방향이 있는 비대칭 그래프

    • 예) Directed graph data (Nodes : 1005 , Edges : 25571) 내부

        0 1
        2 3
        2 4
        .
        .
        .
        258 1003
        1003 258
        55 1004

      • Node는 0~1004로 표현 되어있으며 모든 Edge(line)의 개수는 25571개이다.
      • 만약, 해당 Directed Graph data를 Matrix data로 사용하고 싶다면
      • 모든 edge에 element도 할당해줘야한다.
      • 행,열에 해당하는 element도 할당해줘야한다.

• 즉, SNAP Stanford의 Graph data를 Matrix data로 사용하기 위해선, 추가적인 전처리가 필요하다.

Undirected Graph data를 Matrix data로 변환하는 코드

• 1) Node를 정렬해서 Node 의 index 를 0부터 재설정
• 2) 한쪽 방향의 edge 만 표현 되어있으므로 반대 방향의 edge 도 추가
• 3) 모든 edge 에 element 할당

import random

inputfile = "/Users/bdlab/Desktop/com-youtube.ungraph.txt"
outputfile = "/Users/bdlab/Desktop/com-youtube.matrix.txt"

# node 를 중복 없이 집합으로 저장
n_set = set([])

# Input : Undirected Graph data
with open(inputfile,"r") as rf:

    # 첫 4줄(head) 제거
    for i in range(4):
        next(rf)

    # head 이후부터 읽기
    for e in rf:
        # line 의 개행문자를 제거한 뒤, node 를 탭 단위로 분리하고
        # 각 node 를 node 집합에 저장한다.
        e_split = e.rstrip('\n').split("\t")
        n_set.add(int(e_split[0]))
        n_set.add(int(e_split[1]))        

# 저장 된 node 를 오름차순 정렬한 뒤, node 에 대한 idx 를 0 부터 순서대로 재할당 (node : idx)
n_dic = {}
n_idx = 0
for n in sorted(n_set):
    n_dic[str(n)] = n_idx
    n_idx += 1

# Output : Matrix data
with open(outputfile,"a+") as wf:

  # Inputfile 을 읽어 Outputfile 에 쓰기
  with open(inputfile,"r") as rf:

      # 첫 4줄(head) 제거
      for i in range(4):
        next(rf)

      # head 이후부터 읽기
      for e in rf:
        # line 의 개행문자를 제거한 뒤, node 를 탭 단위로 분리한다.
        e_split = e.rstrip('\n').split("\t")

        # 0~1 사이의 실수 element 값 생성
        element = random.random()

        # node 에 대한 새로운 idx 와 element 할당
        wf.write(str(n_dic[e_split[0]])+" "+str(n_dic[e_split[1]])+" "+str(element)+"\n")
        # Undirected graph 이기 때문에, 반대 방향의 element 도 할당
        wf.write(str(n_dic[e_split[1]])+" "+str(n_dic[e_split[0]])+" "+str(element)+"\n")