Python/NetworkX를 사용한 그래프 데이터 과학

우리는 데이터로 넘쳐납니다. 계속 확장하는 데이터베이스와 스프레드시트에는 숨겨진 비즈니스 통찰력이 가득합니다. 데이터가 너무 많은데 어떻게 데이터를 분석하고 결론을 추출할 수 있습니까? 그래프(막대 그래프가 아닌 네트워크)는 우아한 접근 방식을 제공합니다.

우리는 일반적으로 정보를 나타내기 위해 종종 테이블을 사용합니다. 그러나 그래프는 특수 데이터 구조를 사용합니다. 테이블 행 대신 노드 가 요소를 나타냅니다. 에지 는 두 노드를 연결하여 관계를 나타냅니다.

이 그래프 데이터 구조를 사용하면 고유한 각도에서 데이터를 관찰할 수 있습니다. 이것이 그래프 데이터 과학이 분자 생물학에서 사회 과학에 이르기까지 모든 분야에서 사용되는 이유입니다.

그렇다면 개발자는 그래프 데이터 과학을 어떻게 활용할 수 있습니까? 가장 많이 사용되는 데이터 과학 프로그래밍 언어인 Python을 살펴보겠습니다.

Python에서 "그래프 이론" 그래프 시작하기

Python 개발자는 NetworkX, igraph, SNAP 및 graph-tool과 같은 여러 그래프 데이터 라이브러리를 사용할 수 있습니다. 장단점을 제외하고는 Python 그래프 데이터 구조를 처리하고 처리하기 위한 인터페이스가 매우 유사합니다.

우리는 널리 사용되는 NetworkX 라이브러리를 사용할 것입니다. 설치 및 사용이 간단하고 우리가 사용할 커뮤니티 감지 알고리즘을 지원합니다.

NetworkX로 새 그래프를 만드는 것은 간단합니다.

 import networkx as nx G = nx.Graph()

그러나 G 는 노드와 간선이 없기 때문에 아직 그래프가 아닙니다.

그래프에 노드를 추가하는 방법

Graph() 의 반환 값을 .add_node() (또는 목록의 여러 노드에 대한 .add_nodes_from() )로 연결하여 네트워크에 노드를 추가할 수 있습니다. node 4 와 node 5 에서 볼 수 있듯이 사전을 매개변수로 전달하여 노드에 임의의 특성이나 속성을 추가할 수도 있습니다.

 G.add_node("node 1") G.add_nodes_from(["node 2", "node 3"]) G.add_nodes_from([("node 4", {"abc": 123}), ("node 5", {"abc": 0})]) print(G.nodes) print(G.nodes["node 4"]["abc"]) # accessed like a dictionary

그러면 다음이 출력됩니다.

 ['node 1', 'node 2', 'node 3', 'node 4', 'node 5'] 123

그러나 노드 사이에 에지가 없으면 격리되고 데이터 세트는 단순한 테이블보다 나을 것이 없습니다.

그래프에 간선을 추가하는 방법

노드에 대한 기술과 유사하게 두 노드의 이름과 함께 .add_edge() 를 매개변수로 사용할 수 있습니다(또는 목록의 여러 가장자리에 대해 .add_edges_from() ). 선택적으로 속성 사전을 포함할 수 있습니다.

 G.add_edge("node 1", "node 2") G.add_edge("node 1", "node 6") G.add_edges_from([("node 1", "node 3"), ("node 3", "node 4")]) G.add_edges_from([("node 1", "node 5", {"weight" : 3}), ("node 2", "node 4", {"weight" : 5})])

NetworkX 라이브러리는 각 에지가 가중치를 가질 수 있는 이와 같은 그래프를 지원합니다. 예를 들어, 노드가 사용자이고 에지가 상호작용인 소셜 네트워크 그래프에서 가중치는 관련성이 높은 지표인 지정된 사용자 쌍 간에 발생하는 상호작용의 수를 나타낼 수 있습니다.

NetworkX는 G.edges 를 사용할 때 모든 에지를 나열하지만 속성은 포함하지 않습니다. 에지 속성을 원하면 G[node_name] 을 사용하여 노드에 연결된 모든 것을 가져오거나 G[node_name][connected_node_name] 을 사용하여 특정 에지의 속성을 얻을 수 있습니다.

 print(G.nodes) print(G.edges) print(G["node 1"]) print(G["node 1"]["node 5"])

그러면 다음이 출력됩니다.

 ['node 1', 'node 2', 'node 3', 'node 4', 'node 5', 'node 6'] [('node 1', 'node 2'), ('node 1', 'node 6'), ('node 1', 'node 3'), ('node 1', 'node 5'), ('node 2', 'node 4'), ('node 3', 'node 4')] {'node 2': {}, 'node 6': {}, 'node 3': {}, 'node 5': {'weight': 3}} {'weight': 3}

그러나 이 방법으로 첫 번째 그래프를 읽는 것은 비현실적입니다. 고맙게도 훨씬 더 나은 표현이 있습니다.

그래프(및 가중 그래프)에서 이미지를 생성하는 방법

그래프를 시각화하는 것은 필수적입니다. 이를 통해 노드와 네트워크 구조 간의 관계를 빠르고 명확하게 볼 수 있습니다.

nx.draw(G) 를 빠르게 호출하기만 하면 됩니다.

nx.draw() 호출을 통해 더 두꺼운 가장자리를 상응하게 더 두껍게 만들어 보겠습니다.

 weights = [1 if G[u][v] == {} else G[u][v]['weight'] for u,v in G.edges()] nx.draw(G, width=weights)

결과에서 볼 수 있듯이 가중치가 없는 모서리에 대한 기본 두께를 제공했습니다.

우리의 방법과 그래프 알고리즘은 점점 더 복잡해질 것이므로 다음 단계는 더 잘 알려진 데이터 세트를 사용하는 것입니다.

영화 스타워즈: 에피소드 IV 의 데이터를 사용한 그래프 데이터 과학

결과를 더 쉽게 해석하고 이해할 수 있도록 이 데이터 세트를 사용합니다. 노드는 중요한 캐릭터를 나타내고 가장자리(여기서 가중치 없음)는 장면에서 함께 나타나는 것을 의미합니다.

참고: 데이터 세트는 Gabasova, E.(2016)에서 가져온 것입니다. 스타워즈 소셜 네트워크. DOI: https://doi.org/10.5281/zenodo.1411479.

먼저 nx.draw(G_starWars, with_labels = True) 를 사용하여 데이터를 시각화합니다.

R2-D2 및 C-3PO와 같이 일반적으로 함께 나타나는 문자는 밀접하게 연결된 것처럼 보입니다. 대조적으로, 우리는 Darth Vader가 Owen과 장면을 공유하지 않는다는 것을 알 수 있습니다.

Python NetworkX 시각화 레이아웃

각 노드가 이전 그래프의 위치에 있는 이유는 무엇입니까?

이것은 기본 spring_layout 알고리즘의 결과입니다. 스프링의 힘을 시뮬레이션하여 연결된 노드를 끌어당기고 연결이 끊긴 노드를 밀어냅니다. 이렇게 하면 중앙에서 끝나는 잘 연결된 노드를 강조 표시하는 데 도움이 됩니다.

NetworkX에는 circular_layout 과 같이 노드를 배치하기 위해 다른 기준을 사용하는 다른 레이아웃이 있습니다.

 pos = nx.circular_layout(G_starWars) nx.draw(G_starWars, pos=pos, with_labels = True)

결과:

이 레이아웃은 노드의 위치가 중요도에 의존하지 않는다는 점에서 중립적입니다. 모든 노드가 동일하게 표현됩니다. (원형 레이아웃은 또한 별도의 연결된 구성 요소 (두 노드 사이에 경로가 있는 하위 그래프)를 시각화하는 데 도움이 될 수 있지만 여기에서는 전체 그래프가 하나의 큰 연결된 구성 요소입니다.

우리가 본 두 레이아웃 모두 가장자리가 다른 가장자리와 자유롭게 교차할 수 있기 때문에 시각적으로 어수선합니다. 그러나 spring_layout 과 같은 또 다른 force-directed 알고리즘인 Kamada-Kawai는 시스템의 에너지를 최소화하도록 노드를 배치합니다.

이렇게 하면 가장자리 교차가 줄어들지만 대가가 있습니다. 다른 레이아웃보다 느리므로 노드가 많은 그래프에는 권장하지 않습니다.

여기에는 특수 그리기 기능이 있습니다.

 nx.draw_kamada_kawai(G_starWars, with_labels = True)

대신 다음과 같은 모양이 생성됩니다.

특별한 개입 없이 알고리즘은 주인공(예: Luke, Leia, C-3PO)을 중앙에 배치하고 덜 눈에 띄는 인물(예: Camie 및 General Dodonna)을 경계에 배치합니다.

특정 레이아웃으로 그래프를 시각화하면 흥미로운 질적 결과를 얻을 수 있습니다. 그러나 정량적 결과는 모든 데이터 과학 분석의 중요한 부분이므로 몇 가지 메트릭을 정의해야 합니다.

노드 분석: 등급 및 PageRank

이제 네트워크를 명확하게 시각화할 수 있으므로 노드를 특성화하는 것이 흥미로울 수 있습니다. 노드의 특성과 이 예에서는 캐릭터를 설명하는 여러 메트릭이 있습니다.

노드에 대한 기본 메트릭 중 하나는 노드의 정도입니다. 얼마나 많은 모서리가 있는지입니다. 스타워즈 캐릭터의 노드 정도는 그들이 장면을 공유한 다른 캐릭터의 수를 측정합니다.

degree() 함수는 문자 또는 전체 네트워크의 정도를 계산할 수 있습니다.

 print(G_starWars.degree["LUKE"]) print(G_starWars.degree)

두 명령의 출력:

 15 [('R2-D2', 9), ('CHEWBACCA', 6), ('C-3PO', 10), ('LUKE', 15), ('DARTH VADER', 4), ('CAMIE', 2), ('BIGGS', 8), ('LEIA', 12), ('BERU', 5), ('OWEN', 4), ('OBI-WAN', 7), ('MOTTI', 3), ('TARKIN', 3), ('HAN', 6), ('DODONNA', 3), ('GOLD LEADER', 5), ('WEDGE', 5), ('RED LEADER', 7), ('RED TEN', 2)]

한 줄의 코드로 정도에 따라 가장 높은 노드에서 가장 낮은 노드로 노드를 정렬할 수 있습니다.

 print(sorted(G_starWars.degree, key=lambda x: x[1], reverse=True))

출력:

 [('LUKE', 15), ('LEIA', 12), ('C-3PO', 10), ('R2-D2', 9), ('BIGGS', 8), ('OBI-WAN', 7), ('RED LEADER', 7), ('CHEWBACCA', 6), ('HAN', 6), ('BERU', 5), ('GOLD LEADER', 5), ('WEDGE', 5), ('DARTH VADER', 4), ('OWEN', 4), ('MOTTI', 3), ('TARKIN', 3), ('DODONNA', 3), ('CAMIE', 2), ('RED TEN', 2)]

총계이기 때문에 정도는 개별 가장자리의 세부 사항을 고려하지 않습니다. 주어진 에지가 격리된 노드 또는 전체 네트워크와 연결된 노드에 연결됩니까? Google의 PageRank 알고리즘은 이 정보를 집계하여 네트워크에서 노드가 얼마나 "중요한"지를 측정합니다.

PageRank 메트릭은 한 노드에서 다른 노드로 무작위로 이동하는 에이전트로 해석될 수 있습니다. 더 잘 연결된 노드에는 더 많은 경로가 있으므로 에이전트가 더 자주 방문하는 경향이 있습니다.

이러한 노드는 더 높은 PageRank를 가지며 NetworkX 라이브러리로 계산할 수 있습니다.

 pageranks = nx.pagerank(G_starWars) # A dictionary print(pageranks["LUKE"]) print(sorted(pageranks, key=lambda x: x[1], reverse=True))

이렇게 하면 Luke의 순위와 순위별로 정렬된 캐릭터가 인쇄됩니다.

 0.12100659993223405 ['OWEN', 'LUKE', 'MOTTI', 'DODONNA', 'GOLD LEADER', 'BIGGS', 'CHEWBACCA', 'LEIA', 'BERU', 'WEDGE', 'RED LEADER', 'RED TEN', 'OBI-WAN', 'DARTH VADER', 'CAMIE', 'TARKIN', 'HAN', 'R2-D2', 'C-3PO']

오웬은 가장 높은 등급을 받은 루크를 제치고 가장 높은 페이지랭크를 가진 캐릭터다. 분석: Owen은 다른 캐릭터와 가장 많은 장면을 공유하는 캐릭터는 아니지만 Luke 자신, R2-D2, C-3PO와 같은 많은 중요한 캐릭터와 장면을 공유하는 캐릭터입니다.

대조적으로 세 번째로 높은 등급을 가진 캐릭터인 C-3PO는 가장 낮은 PageRank를 가진 캐릭터입니다. C-3PO는 많은 인맥을 가지고 있음에도 불구하고 많은 사람들이 중요하지 않은 캐릭터와 연결되어 있습니다.

요점: 여러 메트릭을 사용하면 그래프 노드의 다양한 특성에 대한 더 깊은 통찰력을 얻을 수 있습니다.

커뮤니티 탐지 알고리즘

네트워크를 분석할 때 커뮤니티 를 분리하는 것이 중요할 수 있습니다. 서로 밀접하게 연결되어 있지만 커뮤니티 외부의 노드와 최소한으로 연결된 노드 그룹입니다.

이를 위한 여러 알고리즘이 있습니다. 대부분은 이전에 레이블을 지정할 필요 없이 노드에 레이블을 할당하기 때문에 감독되지 않은 기계 학습 알고리즘 내에서 발견됩니다.

가장 유명한 것 중 하나는 레이블 전파 입니다. 여기에서 각 노드는 하나의 커뮤니티에서 고유한 레이블로 시작합니다. 노드의 레이블은 인접 노드의 레이블 대부분에 따라 반복적으로 업데이트됩니다.

레이블은 모든 노드가 대부분의 이웃과 레이블을 공유할 때까지 네트워크를 통해 확산됩니다. 서로 밀접하게 연결된 노드 그룹은 결국 동일한 레이블을 갖게 됩니다.

NetworkX 라이브러리를 사용하면 이 알고리즘을 실행하는 데 Python 세 줄만 있으면 됩니다.

 from networkx.algorithms.community.label_propagation import label_propagation_communities communities = label_propagation_communities(G_starWars) print([community for community in communities])

출력:

 [{'R2-D2', 'CAMIE', 'RED TEN', 'RED LEADER', 'OBI-WAN', 'DODONNA', 'LEIA', 'WEDGE', 'HAN', 'OWEN', 'CHEWBACCA', 'GOLD LEADER', 'LUKE', 'BIGGS', 'C-3PO', 'BERU'}, {'DARTH VADER', 'TARKIN', 'MOTTI'}]

이 집합 목록에서 각 집합은 커뮤니티를 나타냅니다. 영화에 익숙한 독자는 알고리즘이 실제(커뮤니티) 레이블이나 메타데이터를 사용하지 않고 의미 있게 캐릭터를 구별하여 "좋은 사람"과 "나쁜 사람"을 완벽하게 분리하는 것을 알 수 있습니다.

Python에서 그래프 데이터 과학을 사용한 지능형 통찰력

그래프 데이터 과학 도구를 시작하는 것이 생각보다 간단하다는 것을 알았습니다. Python에서 NetworkX 라이브러리를 사용하여 데이터를 그래프로 나타내면 몇 줄의 코드가 빛날 수 있습니다. 커뮤니티 감지 알고리즘을 통해 데이터 세트를 시각화하고 노드 특성을 측정 및 비교하고 노드를 현명하게 클러스터링할 수 있습니다.

Python을 사용하여 네트워크에서 결론과 통찰력을 추출하는 기술을 보유하면 개발자는 데이터 과학 서비스 파이프라인에서 일반적으로 발견되는 도구 및 방법론과 통합할 수 있습니다. 검색 엔진에서 비행 일정, 전기 공학에 이르기까지 이러한 방법은 광범위한 컨텍스트에 쉽게 적용됩니다.

그래프 데이터 과학에 대한 권장 읽기

커뮤니티 탐지 알고리즘
Zhao Yang, Rene Algesheimer, Claudio Tessone. “인공 네트워크에서 커뮤니티 탐지 알고리즘의 비교 분석.” Scientific Reports, 6, 아니오. 30750(2016).

그래프 딥 러닝
토마스 키프. "그래프 컨볼루션 네트워크." 2016년 9월 30일.

그래프 데이터 과학의 응용
Albanese, Federico, Leandro Lombardi, Esteban Feuerstein, Pablo Balenzuela. "트위터에서 텍스트 마이닝 및 그래프 머신 러닝을 사용하여 개인의 변화 예측." (2020년 8월 24일): arXiv:2008.10749 [cs.SI].

코헨, 엘리어. "PyData 텔아비브 모임: Node2vec." 유튜브. 2018년 11월 22일. 비디오, 21:09. https://www.youtube.com/watch?v=828rZgV9t1g.