Một vài năm trước, tôi say sưa đọc sách 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 để 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 để những nhân vật này? Game of Thrones A Song of Ice and Fire hình dung Những thứ cơ bản Trong ảnh là 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ị: biểu đồ mạng mẫu từ Wikipedia 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 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 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: cả hai cường độ 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 lời bài hát mà bạn có thể chỉ cần tải xuống và bắt đầu vẽ đồ thị. tập dữ liệu rõ ràng về Hamilton có sẵn trên Kaggle 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. - đề cập đến tên của bài hát. Tiêu đề - dùng để chỉ nhân vật đang hát một dòng nhất định. Người nói - đề cập đến dòng lời cụ thể trong bài hát. Dòng 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 , phải xác định những điều sau: Hamilton 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à . 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. Số lượng bài hát mà mỗi cặp loa xuất hiện cùng nhau 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ể , 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 để 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. **{src, dest, weight}** gói igraph của R Trực quan hóa sơ đồ mạng Có thể hiển thị graph_obj bằng cách sử dụng . 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”. hàmplot.igraph 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 và 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 để tạo ra (tức là độ dày của cạnh trong biểu đồ) tương ứng với trọng lượng và (tức là kích thước phông chữ của đỉnh) so với bậc. trọng lượng cạnh mức độ đỉnh plot.igraph edge.width vertex.label.cex 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 trong R để tạo biểu đồ mạng . 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. visNetwork tương tác Các biện pháp tập trung 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: Tính trung tâm : Đây là thước đo số cạnh được kết nối với mỗi nút. Mức độ trung tâm : Đ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 của Eigen Đây thực sự là mức độ của một nút nhất định 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ính trung tâm giữa: giữa 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ó cao nhất (“cầu nối”) trong biểu đồ của chúng tôi, trong khi Hamilton có cao nhất (“người có ảnh hưởng”). Hãy làm những gì bạn muốn về điều đó. tính trung tâm giữa tính trung tâm của vectơ riêng 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ả , một trò chơi chữ và chơi chữ không hề đơn giản. Watson của IBM đã chiến thắng Jeopardy! Các trò chơi tiệc tùng có tên như sử dụng biểu đồ mạng. Six Degrees của Kevin Bacon 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 để trả về các trang phù hợp nhất cho một truy vấn tìm kiếm cụ thể. biểu đồ tri thức 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. • Mã: https://github.com/iswaryam/hamilton/ Tín dụng bộ dữ liệu: https://www.kaggle.com/lbalter/hamilton-lyrics# Nếu bạn là Potterhead, hãy xem GitHub của tôi - Tôi cũng đã vẽ đồ thị các nhân vật trong bằng phương pháp tương tự. Harry Potter