Phân tích biểu đồ mạng: Trực quan hóa các nhân vật Hamilton như một mạng xã hội

Một vài năm trước, tôi say sưa đọc sách Game of Thrones và thấy mình gặp khó khăn trong việc theo dõi tất cả các nhân vật trong đầu. (Điều này không có gì đáng ngạc nhiên - có hơn 150 nhân vật được đặt tên trong bộ truyện!) Tôi đã xem đi xem lại giữa các chương hoặc liên tục tra cứu wiki A Song of Ice and Fire để ghi nhớ cốt truyện. Tôi cần một bản đồ tinh thần - chắc chắn có cách nào tốt hơn để hình dung những nhân vật này?

Những thứ cơ bản

Trong ảnh là biểu đồ mạng mẫu từ Wikipedia minh họa sự đóng góp của các biên tập viên Wikipedia cho các ngôn ngữ khác nhau. Sử dụng ví dụ này, đây là một số điều cơ bản (hoặc ôn lại nhanh, nếu bạn đã quen thuộc) về các khái niệm lý thuyết đồ thị:

• Các vòng tròn biểu thị ngôn ngữ mà bài viết được viết là “đỉnh” của biểu đồ (có thể thay thế cho nhau là “nút”).

• Các “cạnh” là các đường nối mỗi cặp đỉnh. Mỗi cạnh trong đồ thị được xác định thông qua hàm tỷ lệ ánh xạ một cặp đỉnh tới một cạnh.

  
  

Trong ví dụ này, mỗi cạnh biểu thị (theo độ dày của dòng hoặc độ dày) số lượng biên tập viên đã đóng góp cho cả hai ngôn ngữ mà dòng kết nối. Đây là cái mà chúng ta gọi là đồ thị đơn giản vô hướng. “Không bị định hướng” có nghĩa là {en--> fr} và {fr --> en} giống hệt nhau và “đơn giản” có nghĩa là không có nhiều hơn một cạnh nối mỗi cặp đỉnh. Biểu đồ cũng được “có trọng số”, nghĩa là độ dày của các cạnh có liên quan đến cường độ mối quan hệ giữa các đỉnh. Trong ví dụ này, hàm tỷ lệ có trọng số có thể trông giống như sau:

Mặc dù cách trình bày trực quan của biểu đồ theo cách này là một cách tiếp cận trực quan để nhanh chóng hiển thị các mối quan hệ sao cho chúng dễ hiểu, thậm chí còn có những hiểu biết sâu sắc hơn mà chúng ta có thể rút ra từ việc biểu diễn tập dữ liệu dưới dạng đối tượng biểu đồ.

Lấy dữ liệu cho tập dữ liệu Hamilton

“Trong khoa học dữ liệu, 80% thời gian dành cho việc chuẩn bị dữ liệu, 20% thời gian dành để phàn nàn về nhu cầu chuẩn bị dữ liệu.”

Các nhà khoa học dữ liệu có thể không đồng ý về mọi thứ - nhưng chúng tôi đồng ý rằng phần khó nhất của bất kỳ dự án nào là lấy dữ liệu. Thật may mắn cho chúng tôi, phần đó nằm phía sau chúng tôi trong bài viết này. Có một tập dữ liệu rõ ràng về lời bài hát Hamilton có sẵn trên Kaggle mà bạn có thể chỉ cần tải xuống và bắt đầu vẽ đồ thị.

Phân tích thăm dò

Đây là giao diện của tập dữ liệu Hamilton .

Có một dòng ghi âm cho mỗi ký tự/bài hát/dòng lời bài hát.

• Tiêu đề - đề cập đến tên của bài hát.
• Người nói - dùng để chỉ nhân vật đang hát một dòng nhất định.
• Dòng - đề cập đến dòng lời cụ thể trong bài hát.

Xây dựng ma trận kề

Để xây dựng biểu đồ mạng của tất cả những người nói Hamilton , phải xác định những điều sau:

• Nút (danh sách người phát biểu)

• Cạnh (để kết nối từng cặp loa)

• Hàm tỷ lệ để ánh xạ từng cặp đỉnh vào một cạnh (với trọng số tùy chọn)

  
  

Hàm tỷ lệ tôi đã chọn là Số lượng bài hát mà mỗi cặp loa xuất hiện cùng nhau . Giả định của tôi là hai nhân vật xuất hiện cùng nhau trong nhiều bài hát thì mối quan hệ của họ càng bền chặt.

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

Bằng cách sử dụng dplyr của R, tôi có thể chuyển đổi tập dữ liệu ban đầu của mình thành thực thể **{src, dest, weight}** , sau đó chuyển đổi tập dữ liệu đó thành ma trận kề. Sau đó, tôi có thể sử dụng graph.adjacency trong gói igraph của R để tạo một “đối tượng đồ thị” từ ma trận kề này, sau đó tôi có thể sử dụng ma trận này để vẽ đồ thị và các phân tích khác.

Trực quan hóa sơ đồ mạng

Có thể hiển thị graph_obj bằng cách sử dụng hàmplot.igraph . Vì hàm này có nhiều bố cục tùy chỉnh để lựa chọn nên tôi bắt đầu bằng cách hiển thị cùng một biểu đồ bằng cách sử dụng bố cục “ngôi sao”.

Kết quả về mặt kỹ thuật là một sơ đồ mạng. Nhưng liệu có thể làm tốt hơn nữa không? Biểu đồ trên dường như gợi ý rằng tất cả các đỉnh và cạnh đều có tầm quan trọng như nhau - nhưng điều đó làm suy yếu toàn bộ quan điểm hình dung một mạng xã hội. Một số nhân vật thực sự “có ý nghĩa” hơn và một số diễn giả có mối quan hệ chặt chẽ hơn so với những người khác.

Làm thế nào biểu đồ này có thể phản ánh điều đó?

Đây là lúc trọng lượng cạnh và mức độ đỉnh phát huy tác dụng. Tôi bắt đầu bằng cách thử nghiệm các tham số của plot.igraph để tạo ra edge.width (tức là độ dày của cạnh trong biểu đồ) tương ứng với trọng lượng và vertex.label.cex (tức là kích thước phông chữ của đỉnh) so với bậc.

Tốt hơn nhiều! Các nhân vật có cấp độ cao hơn sẽ lớn hơn về mặt hình ảnh và sự khác biệt giữa các mối quan hệ mạnh và yếu cũng được thể hiện rõ ràng từ bóng tối của các đường nét. Sự lặp lại này trực quan hơn nhiều và cho phép người xem nắm bắt ngay mối quan hệ giữa các nhân vật. Cũng phù hợp khi Vua George là một nút đơn độc, vì các bài hát của ông luôn là những đoạn độc thoại (rất hài hước).

Bạn cũng có thể sử dụng thư viện visNetwork trong R để tạo biểu đồ mạng tương tác . Thư viện cho phép phóng to và thu nhỏ nhiều phần của biểu đồ (đặc biệt hữu ích với biểu đồ đặc biệt lớn) và có hỗ trợ cho Shiny.

Các biện pháp tập trung

Tính trung tâm là một khái niệm quan trọng trong lý thuyết đồ thị để xác định tầm quan trọng của các nút:

• Mức độ trung tâm : Đây là thước đo số cạnh được kết nối với mỗi nút.

• Tính trung tâm của Eigen : Điều này thể hiện thước đo mức độ “kết nối tốt” của một nút, số lượng liên kết được chia sẻ, v.v. thông qua mạng. Nó xác định các nút có ảnh hưởng trên toàn bộ mạng, không chỉ những nút được kết nối trực tiếp với nó.

• Tính trung tâm giữa: Đây thực sự là mức độ của một nút nhất định giữa các nút khác và hoạt động như một “cầu nối” giữa các cụm mạng khác nhau. Đó là thước đo “ảnh hưởng” của từng đỉnh trên phần còn lại của mạng.

  
  

Tôi có thể sử dụng các hàm Degree(), betweenness() và eigen_centrality() của igraph để lấy vị trí trung tâm cho biểu đồ được tạo:

Có vẻ như Aaron Burr có tính trung tâm giữa cao nhất (“cầu nối”) trong biểu đồ của chúng tôi, trong khi Hamilton có tính trung tâm của vectơ riêng cao nhất (“người có ảnh hưởng”). Hãy làm những gì bạn muốn về điều đó.

Phần kết luận

Ứng dụng kinh doanh của đồ thị mạng rất nhiều:

• Các trang mạng xã hội sử dụng biểu đồ mạng để tạo cộng đồng gồm những người dùng tương tự và đưa ra các đề xuất được nhắm mục tiêu. Việc triển khai sơ bộ thuật toán đằng sau tính năng “gợi ý bạn bè” có thể trông giống như thế này: “Chín trong số mười người bạn trực tiếp của Alice cũng là bạn của Bob -> giới thiệu Bob làm bạn tiềm năng cho Alice”.

  
  

• Các ứng dụng lập bản đồ khoảng cách ngắn nhất từ địa điểm X đến địa điểm Y (chẳng hạn như bản đồ, dịch vụ đi chung xe, chuỗi cung ứng và hậu cần cho xe tải giao hàng, v.v.) có thể sử dụng các biến thể của thuật toán “đường đi ngắn nhất”, được biết đến phổ biến trong khoa học máy tính như vấn đề nhân viên bán hàng du lịch .

  
  

• Lý thuyết mạng là một thành phần quan trọng của quá trình xử lý từ vựng và ngữ nghĩa trong xử lý ngôn ngữ tự nhiên (NLP), lần lượt được sử dụng trong các chatbot và trợ lý ảo như Alexa, Cortana, Siri và thậm chí cả Watson của IBM đã chiến thắng Jeopardy! , một trò chơi chữ và chơi chữ không hề đơn giản.

  
  

• Các trò chơi tiệc tùng có tên như Six Degrees của Kevin Bacon sử dụng biểu đồ mạng.

  
  

• Trong dịch tễ học, các thước đo trung tâm có thể được sử dụng để xác định nguồn gốc của đại dịch hoặc các sự kiện “siêu lây lan”.

  
  

• Nếu bạn nghĩ về điều đó, Internet chỉ đơn giản là một mạng lưới khổng lồ gồm nhiều trang web khác nhau. Công cụ tìm kiếm sử dụng các biện pháp biểu đồ tri thức để trả về các trang phù hợp nhất cho một truy vấn tìm kiếm cụ thể.

  
  

Dù thú vị nhưng điều quan trọng cần lưu ý là đồ thị mạng không phải không có nhược điểm khi sử dụng trong sản xuất. Ví dụ, chúng có thể tốn nhiều tài nguyên. Như trường hợp của bất kỳ hoạt động ma trận nào, khả năng mở rộng và hiệu suất đôi khi bị ảnh hưởng. Ngoài ra còn có vấn đề “khởi đầu nguội” — nếu tập dữ liệu của bạn quá thưa thớt hoặc thực sự không có nhiều mối quan hệ giữa các thực thể thì biểu đồ mạng không phải là giải pháp hiệu quả. Tuy nhiên, được sử dụng đúng cách và đúng ngữ cảnh, chúng có thể có giá trị cho doanh nghiệp.