네트워크 그래프 분석: 해밀턴 캐릭터를 소셜 네트워크로 시각화

몇 년 전, 나는 왕좌의 게임 책을 폭로하고 있었는데 내 머릿속에 있는 모든 캐릭터를 추적하는 데 어려움을 겪고 있음을 깨달았습니다. (이것은 놀라운 일이 아닙니다. 시리즈에는 150명이 넘는 이름이 붙은 캐릭터가 있습니다!) 저는 줄거리를 기억하기 위해 장 사이를 오가거나 얼음과 불의 노래 위키를 끊임없이 찾아보고 있었습니다. 나는 정신 지도가 필요했습니다. 확실히 이러한 캐릭터를 시각화 하는 더 좋은 방법이 있었을까요?

기본 사항

다음 그림은 Wikipedia 편집자의 다양한 언어에 대한 기여를 보여주는 Wikipedia의 샘플 네트워크 그래프 입니다. 이 예를 사용하여 그래프 이론 개념에 대한 몇 가지 기본 사항(또는 이미 익숙하다면 간단히 복습)은 다음과 같습니다.

• 기사가 작성된 언어를 나타내는 원은 그래프의 "꼭지점"("노드"라고도 함)입니다.

• "가장자리"는 각 정점 쌍을 연결하는 선입니다. 그래프의 각 모서리는 한 쌍의 정점을 모서리에 매핑하는 입사 함수를 통해 결정됩니다.

  
  

이 예에서 각 가장자리는 선이 연결하는 두 언어 모두 에 기여한 편집자의 수를 선 두께 또는 두께로 나타냅니다. 이것이 우리가 방향이 없는 단순 그래프라고 부르는 것입니다. "방향이 지정되지 않음"은 {en--> fr}과 {fr --> en}이 동일함을 의미하고, "단순"은 각 정점 쌍을 연결하는 가장자리가 하나만 있음을 의미합니다. 그래프에는 "가중치"도 적용됩니다. 즉, 가장자리의 두께가 정점 간 관계의 강도 에 상대적이라는 의미입니다. 이 예에서 가중 발생률 함수는 다음과 같습니다.

이러한 방식으로 그래프를 시각적으로 표현하는 것은 이해하기 쉽도록 관계를 신속하게 표시하는 직관적인 접근 방식이지만, 데이터세트를 그래프 개체로 표현하면 훨씬 더 풍부한 통찰력을 얻을 수 있습니다.

Hamilton 데이터 세트에 대한 데이터 가져오기

"데이터 과학에서는 데이터를 준비하는 데 80%의 시간이 소요되고, 데이터 준비의 필요성에 대해 불평하는 데 20%의 시간이 소요됩니다."

데이터 과학자들은 모든 것에 동의하지 않을 수도 있습니다. 하지만 우리는 모든 프로젝트에서 가장 어려운 부분이 데이터를 얻는 것이라는 데 동의합니다. 다행스럽게도 이 기사에서는 그 부분이 사라졌습니다. Kaggle에는 쉽게 다운로드하여 그래프를 작성할 수 있는 깔끔하고 멋진 Hamilton 가사 데이터세트 가 있습니다.

탐색적 분석

이것이 해밀턴 데이터세트의 모습입니다.

캐릭터/노래/가사 한 줄당 한 줄의 녹음이 있습니다.

• 제목 - 노래의 이름을 나타냅니다.
• 화자 - 주어진 대사를 노래하는 캐릭터를 나타냅니다.
• 라인 - 노래 내 특정 가사 라인을 나타냅니다.

인접 행렬 구축

모든 Hamilton 스피커의 네트워크 그래프를 작성하려면 다음을 정의해야 합니다.

• 노드(발표자 목록)

• 모서리(각 스피커 쌍 연결용)

• 각 정점 쌍을 가장자리에 매핑하는 발생률 함수(선택적 가중치 포함)

  
  

내가 선택한 발생 함수는 각 스피커 쌍이 함께 나타나는 노래 수 입니다. 내 가정은 두 캐릭터가 함께 등장하는 노래가 많을수록 관계가 더 강해진다는 것입니다.

Weight {speaker,x, speaker,y} = #songs that feature both speaker,x and speaker,y

R의 dplyr을 사용하면 원본 데이터 세트를 **{src, dest, weight}** 엔터티로 변환한 다음 이를 인접 행렬로 변환할 수 있습니다. 그런 다음 R의 igraph 패키지 에서 graph.adjacency를 사용하여 이 인접 행렬에서 "그래프 개체"를 생성할 수 있으며, 이를 플로팅 및 기타 분석에 사용할 수 있습니다.

네트워크 플롯 시각화

graph_obj는 plot.igraph 함수를 사용하여 시각화할 수 있습니다. 이 기능에는 선택할 수 있는 사용자 정의 레이아웃이 많기 때문에 "별표" 레이아웃을 사용하여 동일한 그래프를 렌더링하는 것으로 시작합니다.

결과는 기술적으로 네트워크 플롯입니다. 하지만 이보다 더 나은 일이 가능할까요? 위의 차트는 모든 정점과 가장자리가 동일한 중요성을 갖고 있음을 시사하는 것처럼 보이지만 이는 소셜 네트워크를 시각화하는 전체 요점을 약화시킵니다. 일부 등장인물은 실제로 더 "중요"하고 일부 화자는 다른 인물에 비해 더 강한 관계를 가지고 있습니다.

이 그래프가 이를 어떻게 반영할 수 있나요?

여기에서 가장자리 가중치 와 정점 각도가 작용합니다. 먼저 plot.igraph 함수의 매개변수를 사용하여 가중치에 상대적인 edge.width (즉, 플롯의 가장자리 두께)와 vertex.label.cex (즉, 플롯의 글꼴 크기)를 만듭니다. 정점) 정도에 상대적입니다.

훨씬 낫다! 등급이 높을수록 캐릭터는 시각적으로 더 커지고, 선의 어두움을 통해 강한 관계와 약한 관계의 구분도 분명해집니다. 이 반복은 훨씬 더 직관적이며 시청자가 캐릭터 간의 관계를 즉시 파악할 수 있습니다. King George가 그의 노래가 항상 (매우 재미있는) 독백이라는 점을 고려하면 고독한 노드라는 것도 적절합니다.

R에서 visNetwork 라이브러리를 사용하여 대화형 네트워크 그래프를 만들 수도 있습니다. 라이브러리를 사용하면 그래프의 여러 부분을 확대 및 축소할 수 있으며(특히 큰 그래프에 유용함) Shiny를 지원합니다.

중심성 측정

중심성은 노드의 중요성을 식별하는 그래프 이론의 핵심 개념입니다.

• 정도 중심성 : 각 노드에 연결된 간선의 수를 측정합니다.

• 고유 중심성(Eigen Centrality) : 노드가 얼마나 잘 연결되어 있는지, 네트워크를 통해 얼마나 많은 링크 연결이 공유되는지 등에 대한 척도를 나타냅니다. 이는 네트워크에 직접 연결된 노드뿐만 아니라 전체 네트워크에 영향을 미치는 노드를 식별합니다.

• 매개 중심성(Betweenness Centrality): 말 그대로 특정 노드가 다른 노드 사이에 위치하며 다양한 네트워크 클러스터 사이에서 "브리지" 역할을 하는 정도입니다. 이는 네트워크의 나머지 부분에 대한 각 정점의 "영향력"을 측정한 것입니다.

  
  

igraph의 Degree(), betweenness() 및 eigen_centrality() 함수를 사용하여 생성된 그래프의 중심성을 얻을 수 있습니다.

그래프에서 Aaron Burr는 가장 높은 매개 중심성 ("브리지")을 갖고 있는 반면 해밀턴은 가장 높은 고유 벡터 중심성 ("영향력자")을 갖는 것으로 보입니다. 당신이 원하는 것을 만드십시오.

결론

네트워크 그래프의 비즈니스 응용 프로그램은 다양합니다.

• 소셜 네트워킹 사이트는 네트워크 그래프를 활용하여 유사한 사용자로 구성된 커뮤니티를 만들고 타겟에 맞는 추천을 제공합니다. "친구 추천" 기능 뒤에 있는 알고리즘의 기본적인 구현은 다음과 같이 보일 수 있습니다. "Alice의 직계 친구 10명 중 9명은 Bob의 친구이기도 합니다. -> Bob을 Alice의 잠재적인 친구로 추천합니다."

  
  

• X 장소에서 Y 장소까지의 최단 거리를 매핑하는 애플리케이션(예: 지도, 차량 공유 서비스, 배달 트럭의 공급망 및 물류 등)은 컴퓨터 과학에서 다음과 같이 널리 알려진 "최단 경로" 알고리즘의 변형을 사용할 가능성이 높습니다. 여행하는 세일즈맨 문제 .

  
  

• 네트워크 이론은 자연어 처리(NLP) 내 어휘 및 의미 처리의 중요한 구성 요소이며 Alexa, Cortana, Siri, 심지어 Jeopardy에서 우승한 IBM의 Watson과 같은 챗봇 및 가상 비서 사이에서도 사용됩니다! , 간단하지 않은 말장난과 말장난의 게임입니다.

  
  

• Six Degrees of Kevin Bacon 과 같은 유명 파티 게임에서는 네트워크 그래프를 사용합니다.

  
  

• 역학에서 중심성 측정은 전염병이나 "슈퍼 확산자" 사건의 원인을 식별하는 데 사용될 수 있습니다.

  
  

• 생각해 보면 인터넷은 단순히 다양한 웹사이트로 구성된 하나의 거대한 네트워크일 뿐입니다. 검색 엔진은 지식 그래프 측정값을 활용하여 특정 검색어와 가장 관련성이 높은 페이지를 반환합니다.

  
  

재미있기는 하지만, 네트워크 그래프를 프로덕션에 사용할 때 단점이 없는 것은 아니라는 점을 기억하는 것이 중요합니다. 예를 들어 리소스 집약적일 수 있습니다. 모든 행렬 연산의 경우와 마찬가지로 확장성과 성능이 저하되는 경우가 있습니다. "콜드 스타트" 문제도 있습니다. 데이터 세트가 너무 희박하거나 엔터티 간의 관계가 실제로 많지 않은 경우 네트워크 그래프는 효과적인 솔루션이 아닙니다. 그러나 올바른 상황에서 올바르게 사용하면 비즈니스에 가치가 있을 수 있습니다.