[21-1] Graph using networkx

networkx 모듈을 사용해서 그래프를 컴퓨터 상에서 다루는 기초적인 방법을 알아봅니다.

 

1️⃣ 설정

 

필요한 모듈을 import 합니다.

import networkx as nx                           # NetworkX

import numpy as np                              # 선형대수를 위한 라이브러리

import matplotlib.pyplot as plt                 # 그림을 그리기 위한 라이브러리

np.set_printoptions(threshold=sys.maxsize)      

 

2️⃣ Graph basic

1) Graph init

print("###### Graph Init ######")    

G= nx.Graph()                                   # 방향성이 없는 그래프

DiGraph = nx.DiGraph()                          # 방향성이 있는 그래프

2) Add Node

Node 1을 추가합니다.

>>> print("###### Add Node to Graph ######")       

>>> print("# Add node 1")     

G.add_node(1)                                               # 정점 1 추가

>>> print("Num of nodes in G : " + str(G.number_of_nodes()))    # 정점의 수 반환

>>> print("Graph : " + str(G.nodes)+ "\n")                      # 정점의 목록 반환



###### Add Node to Graph ######
# Add node 1
Num of nodes in G : 1
Graph : [1]

Node 2 ~ 10을 추가합니다.

>>> print("# Add vertex 2 ~ 10")                                # 정점 2 ~ 10 추가

for i in range (1, 11):

    G.add_node(i)
    
>>> print("Num of nodes in G : " + str(G.number_of_nodes()))

>>> print("Graph : " + str(G.nodes) + "\n")


# Add vertex 2 ~ 10
Num of nodes in G : 10
Graph : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

3) Add Edge

Edge를 추가합니다.

>>> print("#Add edge (1, i) for i = 2 ~ 10")                    # 정점 1과 다른 정점 사이의 간선 추가

for i in range (2, 11):

    G.add_edge(1, i)
    
>>> print("Graph : " + str(G.edges) + "\n")



#Add edge (1, i) for i = 2 ~ 10
Graph : [(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10)]

4) Graph 시각화

# 정점의 위치 결정 (설정을 하지 않으면 복잡하게 그려짐)

pos = nx.spring_layout(G)    

# 정점의 색과 크기를 지정하여 출력

im = nx.draw_networkx_nodes(G, pos, node_color="red", node_size=100)    

# 간선 출력

nx.draw_networkx_edges(G, pos)   

# 각 정점의 라벨을 출력

nx.draw_networkx_labels(G, pos, font_size=10, font_color="black")   

plt.show()

 

3️⃣ Graph 표현방법

1) 인접 리스트

>>> print("###### Graph to List ######")    

ListGraph = nx.to_dict_of_lists(G)

for v in ListGraph:

    print(str(v) + " : " + str(ListGraph[v]))




###### Graph to List ######
1 : [2, 10]
2 : [1, 3]
3 : [2, 4]
4 : [3, 5]
5 : [4, 6]
6 : [5, 7]
7 : [6, 8]
8 : [7, 9]
9 : [8, 10]
10 : [9, 1]

2) 간선 리스트

>>> print("###### Graph to EdgeList ######")              

EdgeListGraph = nx.to_edgelist(G)         

for e in EdgeListGraph:

    v1, v2, w = e
    
    print(v1, v2)
    


###### Graph to EdgeList ######
1 2
1 10
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

3) 인접 행렬

간선 리스트는 list에 간선이 없는 경우 모든 데이터를 순회해야 해서 비효율적입니다.

필요한 list만 가지고 와서 확인할 수 있기 때문에 인접 행렬은 간선 리스트보다 효율적입니다.

>>> print("###### Graph to numpy array ######")

NumpyArrayGraph = nx.to_numpy_array(G)   

>>> print(NumpyArrayGraph)



###### Graph to numpy array ######
[[0. 1. 0. 0. 0. 0. 0. 0. 0. 1.]
 [1. 0. 1. 0. 0. 0. 0. 0. 0. 0.]
 [0. 1. 0. 1. 0. 0. 0. 0. 0. 0.]
 [0. 0. 1. 0. 1. 0. 0. 0. 0. 0.]
 [0. 0. 0. 1. 0. 1. 0. 0. 0. 0.]
 [0. 0. 0. 0. 1. 0. 1. 0. 0. 0.]
 [0. 0. 0. 0. 0. 1. 0. 1. 0. 0.]
 [0. 0. 0. 0. 0. 0. 1. 0. 1. 0.]
 [0. 0. 0. 0. 0. 0. 0. 1. 0. 1.]
 [1. 0. 0. 0. 0. 0. 0. 0. 1. 0.]]

4) 희소 행렬

일반 행렬은 전체 원소를 저장하므로 정점 수의 제곱에 비례하는 저장 공간을 사용합니다.

대신, 희소 행렬은 0이 아닌 원소만을 저장하므로 간선의 수에 비례하는 저장 공간을 사용해서 속도가 빠릅니다.

하지만 희소 행렬이 항상 좋은 것만은 아닙니다.

행렬의 대부분의 원소가 0이 아닌 경우에는 일반 행렬을 사용할 때가 속도가 훨씬 빠릅니다.

>>> print("###### Graph to Spicy sparse matrix ######")

SparseMatrixGraph = nx.to_scipy_sparse_matrix(G)  

>>> print(SparseMatrixGraph)




###### Graph to Spicy sparse matrix ######
  (0, 1)	1
  (0, 9)	1
  (1, 0)	1
  (1, 2)	1
  (2, 1)	1
  (2, 3)	1
  (3, 2)	1
  (3, 4)	1
  (4, 3)	1
  (4, 5)	1
  (5, 4)	1
  (5, 6)	1
  (6, 5)	1
  (6, 7)	1
  (7, 6)	1
  (7, 8)	1
  (8, 7)	1
  (8, 9)	1
  (9, 0)	1
  (9, 8)	1

 

4️⃣ 전역 군집 계수, Graph 지름, 차수 분포

1) 전역 군집 계수

그래프의 전역 군집 계수를 찾는 함수입니다.

특정 정점 u의 정점 계수(cc)는 아래와 같이 구할 수 있습니다.

 

• cc(u) = 2T(u)/(deg(u) * (deg(u) - 1))
  
  - cc(u) : 정점 u의 군집 계수
  
  - T(u)  : 정점 u가 들어있는 삼각형 개수
  
  - deg(u): 정점 u의 차수 (degree)

그리고 전역 군집 계수 avg_cc(G)는 모든 정점의 cc(u)의 평균을 의미합니다.

 

• avg_cc(G) = sigma(u in G) cc(u) / n
  
  - avg_cc(G) : 그래프 G의 전역 군집 계수
  
  - n         : 그래프 G의 정점 개수

def getGraphAverageClusteringCoefficient(Graph):

    ccs = []
    
    for v in Graph.nodes:
    
        num_connected_pairs = 0
        
        for neighbor1 in Graph.neighbors(v):
        
            for neighbor2 in Graph.neighbors(v):
            
                if neighbor1 <= neighbor2:      # 중복되는 정점 쌍을 고려하지 않기 위해
                
                    continue
                    
                if Graph.has_edge(neighbor1, neighbor2):
                
                    num_connected_pairs = num_connected_pairs + 1
                    
        # v 이웃 쌍의 수 (Graph.degree(v) * (Graph.degree(v) - 1) 와 이웃 쌍 중 실제 간선과 연결된 수 num_connected_pairs
        
        # v는 dv만큼의 이웃을 가지고 있고, 이웃 쌍의 수는 dv x (dv-1) /2만큼 가지고 있음
        
        cc = num_connected_pairs / (Graph.degree(v) * (Graph.degree(v) - 1) / 2)
        
        ccs.append(cc)
        
    return sum(ccs) / len(ccs)

2) Graph 지름

nx의 single_source_shortest_path_length 함수를 사용하면 쉽게 구할 수 있습니다.

def getGraphDiameter(Graph):

    diameter = 0
    
    for v in Graph.nodes:
    
      # single_source_shortest_path_length는 출발점(v)와 다른 정점들 사이의 거리가 저장, vector형식으로 반환
      
      length = nx.single_source_shortest_path_length(Graph, v)
      
      max_length = max(length.values())   # max값 반환
      
      if max_length > diameter:
      
          diameter = max_length
          
    return diameter

3) 차수 분포

print("3. Degree Distribution")

degree_sequence = sorted([d for n, d in random_graph.degree()], reverse = True)

degreeCount = collections.Counter(degree_sequence)

deg, cnt = zip(*degreeCount.items())

plt.bar(deg, cnt, color="b")

plt.xlabel('degree')

plt.ylabel('number of vertices')

plt.xticks([2, 3, 4])

plt.show()