BDI302c - Phần 12: Đồ thị và các dạng phân tích đồ thị

Đáp án đúng gồm hai ý: "A set of nodes which can reach (almost) all other nodes" và "Which nodes' removal will maximally disrupt the network". Bài toán "người chơi chủ chốt" (key player problem) trong phân tích độ trung tâm (centrality) có hai dạng kinh điển: tìm một tập nút từ đó lan tới được gần như toàn mạng, hữu ích khi muốn khuếch tán thông tin hay chọn người ảnh hưởng, và tìm những nút mà gỡ bỏ thì mạng bị chia cắt hoặc suy giảm kết nối nhiều nhất, hữu ích khi cần bảo vệ hạ tầng hay chặn lây lan. Phương án "What is the shortest path through a network" thuộc nhóm phân tích đường đi (path analytics), giải bằng thuật toán như Dijkstra, chứ không phải bài toán xác định nút chủ chốt. Phương án "Which nodes have the highest ratio of out-degree nodes to in-degree nodes" chỉ là một chỉ số tính từ bậc vào và bậc ra của từng nút, không trả lời câu hỏi nút nào phủ được mạng hay nút nào làm mạng tan rã.

Đáp án đúng: "Euler". Lý thuyết đồ thị khởi đầu năm 1736 khi Leonhard Euler giải bài toán bảy cây cầu Königsberg: ông mô hình hoá mỗi vùng đất là một đỉnh, mỗi cây cầu là một cạnh, rồi chứng minh không thể đi qua mỗi cầu đúng một lần vì có quá nhiều đỉnh bậc lẻ. Cách trừu tượng hoá thành đỉnh và cạnh đó là nền móng của phân tích đồ thị dùng trong dữ liệu lớn hôm nay, từ mạng xã hội tới định tuyến đường đi. "Einstein" nổi tiếng với thuyết tương đối trong vật lý, không liên quan tới đồ thị. "Newton" đặt nền cho cơ học cổ điển và giải tích, sống trước Euler nhưng không xây dựng lý thuyết đồ thị. "Darwin" là nhà sinh học với thuyết tiến hoá bằng chọn lọc tự nhiên.

Đáp án đúng: "a node which can reach all other nodes quickly". Trong phân tích mạng, người có ảnh hưởng (influencer) được hiểu là nút có vị trí cho phép thông tin từ nó lan tới mọi nút khác qua ít bước nhất; điều này gắn với độ trung tâm gần (closeness centrality), đo bằng nghịch đảo tổng khoảng cách ngắn nhất từ nút đó tới mọi nút còn lại, khoảng cách càng nhỏ thì ảnh hưởng lan càng nhanh. "the biggest gossip in the network" là cách nói dân dã về người nói nhiều nhất, nhưng gửi nhiều thông điệp không bảo đảm thông điệp tới được cả mạng nhanh, nên không phải định nghĩa dựa trên cấu trúc đồ thị. "a node which has heavy weight edges to at least 1/2 of the nodes in the network" đặt ra ngưỡng một nửa số nút và trọng số cạnh lớn một cách tùy tiện; một nút có thể nối mạnh với nhiều nút lân cận mà vẫn ở xa phần còn lại của mạng, nên tiêu chí này không phản ánh khả năng lan tỏa.

Đáp án đúng: "True". Diameter (đường kính) của đồ thị là độ dài lớn nhất trong số các đường đi ngắn nhất giữa mọi cặp nút, tức khoảng cách xa nhất giữa hai nút khi luôn đi theo lối ngắn nhất. Vì vậy muốn tính đường kính phải bắt đầu bằng việc tìm đường đi ngắn nhất cho từng cặp nút, chẳng hạn chạy BFS từ mọi nút với đồ thị không trọng số hoặc dùng thuật toán Floyd-Warshall với đồ thị có trọng số, rồi lấy giá trị lớn nhất trong ma trận khoảng cách thu được. Ví dụ một đồ thị đường thẳng gồm bốn nút nối tiếp có khoảng cách ngắn nhất giữa hai đầu là 3, và đó là đường kính. "False" không đúng vì không có cách nào xác định khoảng cách lớn nhất này mà bỏ qua bước tính đường đi ngắn nhất giữa các cặp nút.

Đáp án đúng: "Find the best possible path given two or more optimization criteria where neither constraint can be fully optimized simultaneously.". Bài toán tối ưu Pareto xuất hiện khi chọn đường trong đồ thị theo nhiều tiêu chí cùng lúc, ví dụ vừa ngắn nhất về quãng đường vừa rẻ nhất về chi phí: đường ngắn nhất chưa chắc rẻ nhất, nên không có lời giải nào tối ưu mọi tiêu chí. Tập Pareto gồm những đường mà không thể cải thiện một tiêu chí mà không làm xấu tiêu chí khác, và người dùng chọn trong tập đó theo ưu tiên của mình. "Find the shortest path from source node to target node." là bài toán đường đi ngắn nhất một tiêu chí, giải bằng thuật toán Dijkstra. "Find the optimal path that requires going through specific nodes given by the user." là bài toán đường đi có ràng buộc phải qua các nút cho trước, chỉ thêm điều kiện vào bài toán tối ưu một tiêu chí chứ không có sự đánh đổi giữa nhiều tiêu chí.

Đáp án đúng: "A dense amount of edge connections between nodes in a community and a few connections across communities.". Trong phân tích đồ thị, community (cộng đồng) là một nhóm nút liên kết chặt với nhau: số cạnh bên trong nhóm nhiều hơn hẳn số cạnh nối sang nhóm khác, và các thuật toán phát hiện cộng đồng như tối ưu modularity đều đo đúng chênh lệch này. "High density of nodes at a certain location." nói về mật độ nút theo vị trí không gian, trong khi cộng đồng được xác định bằng cấu trúc cạnh chứ không bằng toạ độ. Mảnh "defined by an integer constant K around a specific node" mô tả vùng lân cận k bước quanh một nút (ego network), một khái niệm cục bộ chứ không phải cộng đồng, và việc nút ở bước K+1 thuộc cộng đồng khác là không có căn cứ. "Many anomalous neighborhoods within the same vicinity." thuộc về phát hiện bất thường trên đồ thị, không phải định nghĩa cộng đồng.

Đáp án đúng: "Closeness". Closeness centrality (độ trung tâm gần) của một nút được tính từ tổng độ dài các đường đi ngắn nhất từ nút đó tới mọi nút khác, thường lấy nghịch đảo; nút có closeness cao là nút trung bình gần mọi nút nhất, nên thông tin bơm vào từ đó đi theo đường ngắn nhất sẽ phủ toàn mạng nhanh nhất. "Degree" chỉ đếm số láng giềng trực tiếp, đo ảnh hưởng cục bộ trong một bước; nút nhiều bạn vẫn có thể nằm ở rìa mạng và xa phần còn lại. "Between-ness" đo số đường ngắn nhất giữa các cặp nút khác đi qua một nút, cho biết nút đóng vai trò cầu nối hay người gác cổng có thể kiểm soát hoặc chặn dòng thông tin, chứ không phải điểm xuất phát lan nhanh nhất. "Group" là độ trung tâm tính cho cả một nhóm nút, mở rộng các chỉ số trên cho tập nút chứ không phải loại chỉ số trả lời câu hỏi này.

Đáp án đúng: "Routing to avoid using the same bridge or road.". Trong đồ thị, trail là đường đi không lặp lại cạnh nhưng được phép quay lại đỉnh cũ; nếu thành phố là đỉnh và cầu, con đường là cạnh thì yêu cầu không đi lại cùng một cây cầu hay con đường chính là ràng buộc không lặp cạnh, giống bài toán bảy cây cầu Königsberg. "Routing to avoid visiting the same city." là ràng buộc không lặp đỉnh, ứng với khái niệm path (đường đi đơn) chứ không phải trail. "An email network tracing frequency of emails from one person to another." quan tâm trọng số trên cạnh, tức số email giữa hai người, không cần khái niệm đường đi không lặp cạnh. "An email network tracing email replies." lần theo chuỗi trả lời qua lại, trong đó cùng một cặp người gửi và nhận có thể xuất hiện nhiều lần, nên việc cấm lặp cạnh không có ý nghĩa ở đây.

Đáp án đúng: "A dense amount of edge connections between nodes in a community and a few connections across communities.". Trong phân tích đồ thị, cộng đồng (community) là tập đỉnh liên kết chặt với nhau: mật độ cạnh bên trong nhóm cao, còn số cạnh nối ra các nhóm khác thì ít; các thuật toán phát hiện cộng đồng, ví dụ tối ưu modularity, tìm cách chia đồ thị sao cho cạnh trong nhóm nhiều hơn hẳn mức ngẫu nhiên và cạnh liên nhóm ít. "Many anomalous neighborhoods within the same vicinity." sai vì vùng lân cận bất thường (anomalous) là chủ đề phát hiện bất thường, không phải định nghĩa cộng đồng. "A neighborhood defined by an integer constant K around a specific node. All K+1 nodes belong to another community." lẫn với khái niệm lân cận K bước quanh một đỉnh; lân cận đó là khái niệm khác, và chuyện các đỉnh ở bước K+1 thuộc cộng đồng khác là không có căn cứ. "High density of nodes at a certain location." sai vì đồ thị không có toạ độ vị trí; điều quyết định là mật độ cạnh giữa các đỉnh chứ không phải số đỉnh dồn ở một chỗ.

Đáp án đúng: "Degree". Độ trung tâm bậc (degree centrality) đếm số cạnh nối vào một nút; nút có bậc rất cao là trung tâm (hub) nối trực tiếp với nhiều nút khác, nên đây là thước đo nhận diện tính hub. "Between-ness" (độ trung tâm trung gian) đo mức độ một nút nằm trên các đường ngắn nhất giữa những cặp nút khác, nhận diện nút cầu nối hay người môi giới, có thể có bậc thấp mà vẫn rất quan trọng. "Closeness" (độ trung tâm gần) dựa trên tổng khoảng cách ngắn nhất tới mọi nút, nhận diện nút lan truyền nhanh, không đếm số láng giềng trực tiếp. "Group" (độ trung tâm nhóm) mở rộng các thước đo trên cho một tập nút, dùng cho bài toán chọn một nhóm chủ chốt chứ không đo hub của từng nút.

Đáp án đúng: "Julio’s node was reachable from Maria node". Trong đồ thị có hướng của mạng email, cạnh đi từ người gửi tới người nhận; nút B gọi là reachable (đến được) từ nút A khi tồn tại đường đi theo đúng chiều mũi tên từ A tới B, có thể qua nhiều nút trung gian. Email của Maria tới được Julio, trực tiếp hoặc qua người khác chuyển tiếp, nghĩa là có đường đi bắt đầu ở Maria, đi theo các cạnh gửi thư và kết thúc ở Julio, tức nút Julio đến được từ nút Maria. "Maria’s node was reachable from Julio’s node" đảo chiều câu hỏi: nó hỏi thư của Julio có tới được Maria hay không. Vì đồ thị có hướng nên khả năng đến được không đối xứng: Maria gửi tới được Julio không kéo theo Julio gửi tới được Maria, nên phải kiểm tra đúng chiều xuất phát từ Maria.

Đáp án đúng: "Hyperlinks". Khi mô hình hoá World Wide Web thành một mạng (đồ thị), mỗi trang web là một nút và mỗi liên kết từ trang này trỏ sang trang kia là một cạnh có hướng; đây là đồ thị mà các thuật toán như PageRank phân tích để xếp hạng trang theo số và chất lượng liên kết trỏ tới. "Webpages" là các nút của mạng chứ không phải cạnh, vì cạnh phải là quan hệ nối giữa hai đối tượng. "Google search terms" là truy vấn người dùng gõ vào công cụ tìm kiếm, không phải quan hệ giữa các trang và không thuộc cấu trúc của web. "Individual computers" là các nút trong mạng vật lý Internet, nơi cạnh là đường truyền giữa máy với máy; đó là một mạng khác với mạng các trang và liên kết của World Wide Web mà câu hỏi nói tới.

Đáp án đúng: "Pie chart". Câu hỏi dùng chữ graph theo nghĩa lý thuyết đồ thị: một tập đỉnh nối với nhau bởi các cạnh biểu diễn quan hệ. Biểu đồ tròn chỉ là cách vẽ tỷ lệ các phần của một tổng thành những lát cắt, không có đỉnh và cạnh, nên không phải đồ thị dù tiếng Anh thông thường cũng gọi nó là một kiểu chart. "Social network" là đồ thị điển hình: mỗi người là một đỉnh, quan hệ bạn bè hay theo dõi là cạnh. "Gene interaction map" cũng là đồ thị, mỗi gen hoặc protein là đỉnh và tương tác sinh học giữa chúng là cạnh, dùng để tìm các cụm gen cùng chức năng. "Road map" là đồ thị có trọng số, giao lộ hoặc thành phố là đỉnh, đoạn đường là cạnh mang độ dài, làm nền cho các bài toán tìm đường ngắn nhất.

Đáp án đúng: "Solving the bridge problem". Năm 1736, Leonhard Euler giải bài toán bảy cây cầu Königsberg: có cách nào đi qua mỗi cây cầu đúng một lần hay không. Ông biến các vùng đất thành nút, cây cầu thành cạnh, rồi chứng minh không thể đi được vì có quá hai nút bậc lẻ; điều kiện đường đi Euler này được xem là khởi đầu của lý thuyết đồ thị. "Developing machine learning" sai vì học máy là lĩnh vực của thế kỷ 20, rất lâu sau thời Euler. "Creating binary search" sai vì tìm kiếm nhị phân là thuật toán trên mảng đã sắp xếp, gắn với khoa học máy tính hiện đại chứ không phải công trình đồ thị của Euler. "Building graph databases" sai vì cơ sở dữ liệu đồ thị như Neo4j là phần mềm ra đời gần đây, chỉ vận dụng lý thuyết đồ thị mà Euler đặt nền.

Đáp án đúng: "where there is an edge from a node to itself.". Trong lý thuyết đồ thị, khuyên hay vòng tự thân (loop, self-loop) là cạnh có hai đầu mút trùng nhau, nối một đỉnh với chính nó, ví dụ một trang web có liên kết trỏ về chính trang đó; khuyên được tính hai lần vào bậc của đỉnh trong đồ thị vô hướng. "where there is a edge from A->B, there is also an edge from B->A." mô tả cặp cạnh hai chiều, tức quan hệ tương hỗ giữa hai đỉnh khác nhau, chẳng hạn hai người theo dõi lẫn nhau, không phải cạnh tự nối. "where there is a path in some way from a node, through 1 or more other - nodes, back to the original node." là định nghĩa chu trình (cycle): đường đi qua ít nhất một đỉnh khác rồi quay về đỉnh xuất phát, khác với khuyên chỉ gồm đúng một cạnh và không đi qua đỉnh nào khác.

Đáp án đúng: "Multiple edges between Maria and Julio". Khi hai người có nhiều loại quan hệ cùng lúc, mô hình phù hợp là đa đồ thị (multigraph): giữ mỗi người đúng một đỉnh và vẽ nhiều cạnh song song giữa hai đỉnh, mỗi cạnh mang nhãn hoặc thuộc tính cho biết loại quan hệ như bạn đánh tennis, đồng nghiệp, người liên hệ khẩn cấp. Cách này giữ toàn bộ thông tin trong một đồ thị và vẫn truy vấn theo loại cạnh được. "Separate graphs for each kind of relationship" chia dữ liệu ra nhiều đồ thị, làm mất cái nhìn tổng thể và khó phân tích các quan hệ đan xen. "Multiple nodes for each of Maria and Julio, to capture the various relationships" sai nguyên tắc vì một thực thể phải ứng với một đỉnh; nhân bản đỉnh làm sai các phép đo như bậc của đỉnh hay số láng giềng.

Đáp án đúng: "Split". Theo dõi sự tiến hoá cộng đồng (community tracking) trên đồ thị theo thời gian thường phân biệt sáu sự kiện: birth, death, grow, contract, merge và split. Khi một công ty tách ra một start-up, một nhóm nhân sự vốn thuộc cộng đồng cũ tách thành cộng đồng riêng, nên một cộng đồng trở thành hai, đó là split. "Birth" là một cộng đồng mới xuất hiện mà không bắt nguồn từ cộng đồng có sẵn; start-up cũng mới nhưng được tách ra từ công ty mẹ. "Death" là cộng đồng tan biến hẳn, trong khi công ty mẹ vẫn tồn tại. "Grow" là cộng đồng nhận thêm thành viên, ngược với việc mất người cho start-up. "Merge" là hai cộng đồng hợp làm một, như hai công ty sáp nhập. "Contract" là cộng đồng thu hẹp do mất bớt thành viên rời đi lẻ tẻ, không hình thành một cộng đồng mới như ở đây.

Đáp án đúng: "Refers_to". Web ngữ nghĩa (semantic web) mô tả tri thức bằng bộ ba chủ thể–vị từ–đối tượng như trong RDF: đỉnh là khái niệm, tài nguyên, thực thể, còn cạnh mang quan hệ ngữ nghĩa giữa chúng, chẳng hạn một tài nguyên refers_to (tham chiếu tới) một khái niệm hay tài nguyên khác, hoặc các quan hệ như is_a, part_of. "Likes" là cạnh điển hình của đồ thị mạng xã hội, ghi việc người dùng thích một bài viết, không phải quan hệ ngữ nghĩa giữa các khái niệm. "Mentions" cũng thuộc đồ thị mạng xã hội, như một bài đăng nhắc tới một tài khoản. "Shares" ghi hành động chia sẻ nội dung của người dùng, phục vụ phân tích lan truyền trên mạng xã hội chứ không mô tả nghĩa của tài nguyên.