2

Phân tích biểu đồ chỉ có giá trị nếu bạn có kỹ năng sử dụng chúng và nếu chúng có thể nhanh chóng cung cấp những hiểu biết bạn cần. Do đó, các thuật toán đồ thị tốt nhất là dễ sử dụng, nhanh chóng thực hiện và tạo ra kết quả mạnh mẽ.

Neo4j bao gồm một thư viện mở, mở ra các thuật toán đồ thị hiệu suất cao, tiết lộ các mẫu và cấu trúc ẩn trong dữ liệu được kết nối của bạn.

Trong loạt bài về thuật toán đồ thị này, chúng tôi sẽ thảo luận về giá trị của thuật toán đồ thị và những gì chúng có thể làm cho bạn. Trước đây, chúng tôi đã khám phá cách kết nối dữ liệu thúc đẩy các khám phá trong tương laicách hợp lý hóa các khám phá dữ liệu đó bằng các phân tích biểu đồ .

Tuần này, chúng ta sẽ xem xét chi tiết nhiều thuật toán đồ thị có sẵn trong Neo4j và những gì chúng làm.

Sử dụng thuật toán đồ thị Neo4j, bạn sẽ có phương tiện để hiểu, mô hình hóa và dự đoán các động lực phức tạp như dòng tài nguyên hoặc thông tin, các con đường lây lan hoặc lỗi mạng lan rộng và ảnh hưởng và khả năng phục hồi của các nhóm.

Và bởi vì Neo4j tập hợp các hoạt động phân tích và giao dịch trong nền tảng đồ thị gốc , bạn sẽ không chỉ khám phá bản chất bên trong của các hệ thống trong thế giới thực cho những khám phá mới mà còn phát triển và triển khai các giải pháp dựa trên biểu đồ nhanh hơn và dễ sử dụng, sắp xếp công việc hợp lý. Đó là sức mạnh của một cách tiếp cận tối ưu.

Dưới đây là danh sách nhiều thuật toán mà Neo4j sử dụng trong nền tảng phân tích biểu đồ của nó, cùng với lời giải thích về những gì họ làm.

Thuật toán truyền tải và tìm đường

1. Tìm kiếm song song chiều rộng (BFS)

Những gì nó làm : Đi qua một cấu trúc dữ liệu cây bằng cách quạt ra để khám phá những người hàng xóm gần nhất và sau đó là hàng xóm cấp dưới của họ. Nó được sử dụng để xác định vị trí các kết nối và là tiền thân của nhiều thuật toán đồ thị khác .

BFS được ưa thích khi cây kém cân bằng hoặc mục tiêu gần điểm bắt đầu hơn. Nó cũng có thể được sử dụng để tìm đường đi ngắn nhất giữa các nút hoặc tránh các quá trình đệ quy của tìm kiếm theo chiều sâu.

Cách sử dụng : Tìm kiếm đầu tiên có thể được sử dụng để xác định vị trí các nút lân cận trong các mạng ngang hàng như BitTorrent, hệ thống GPS để xác định vị trí gần đó và các dịch vụ mạng xã hội để tìm người trong một khoảng cách cụ thể.

2. Tìm kiếm theo chiều sâu song song (DFS)

Những gì nó làm : Đi qua một cấu trúc dữ liệu cây bằng cách khám phá càng nhiều càng tốt xuống từng nhánh trước khi quay lại. Nó được sử dụng trên dữ liệu phân cấp sâu sắc và là tiền thân của nhiều thuật toán đồ thị khác. Tìm kiếm theo chiều sâu được ưu tiên khi cây cân bằng hơn hoặc mục tiêu gần với điểm cuối hơn.

Cách sử dụng : Tìm kiếm theo chiều sâu thường được sử dụng trong các mô phỏng chơi trò chơi trong đó mỗi lựa chọn hoặc hành động dẫn đến một lựa chọn khác, mở rộng thành một biểu đồ khả năng hình cây. Nó sẽ đi qua cây lựa chọn cho đến khi phát hiện ra một đường dẫn giải pháp tối ưu (tức là thắng).

3. Đường dẫn ngắn nhất một nguồn

Những gì nó làm : Tính toán một đường dẫn giữa một nút và tất cả các nút khác có giá trị tổng (trọng số của các mối quan hệ như chi phí, khoảng cách, thời gian hoặc dung lượng) đến tất cả các nút khác là tối thiểu.

Cách sử dụng : Đường dẫn ngắn nhất một nguồn thường được áp dụng để tự động lấy chỉ đường giữa các vị trí thực, chẳng hạn như chỉ đường lái xe qua Google Maps. Nó cũng rất cần thiết trong định tuyến logic, chẳng hạn như định tuyến cuộc gọi điện thoại (định tuyến chi phí thấp nhất).

4. Đường đi ngắn nhất

Những gì nó làm : Tính toán một rừng đường dẫn ngắn nhất (nhóm) chứa tất cả các đường dẫn ngắn nhất giữa các nút trong biểu đồ. Nó thường được sử dụng để hiểu định tuyến thay thế khi tuyến ngắn nhất bị chặn hoặc trở thành tối ưu phụ.

Cách sử dụng : Đường dẫn ngắn nhất cho tất cả các cặp được sử dụng để đánh giá các tuyến đường thay thế cho các tình huống, chẳng hạn như sao lưu đường cao tốc hoặc dung lượng mạng. Đó cũng là chìa khóa trong định tuyến logic để cung cấp nhiều đường dẫn; ví dụ, gọi các phương án định tuyến.

5. Cây Spanning Trọng lượng tối thiểu (MWST)

Những gì nó làm : Tính toán các đường dẫn dọc theo cấu trúc cây được kết nối với giá trị nhỏ nhất (trọng số của mối quan hệ, chẳng hạn như chi phí, thời gian hoặc công suất) liên quan đến việc truy cập tất cả các nút trong cây. Nó cũng được sử dụng để ước tính một số vấn đề NP-cứng như vấn đề nhân viên bán hàng du lịch và làm tròn ngẫu nhiên hoặc lặp lại.

Cách sử dụng : Cây bao trùm trọng lượng tối thiểu được sử dụng rộng rãi cho các thiết kế mạng: định tuyến logic hoặc vật lý với chi phí thấp nhất như cáp đặt, tuyến thu gom rác nhanh nhất, công suất cho hệ thống nước, thiết kế mạch hiệu quả và hơn thế nữa. Nó cũng có các ứng dụng thời gian thực với tối ưu hóa cuộn, chẳng hạn như các quy trình trong nhà máy lọc hóa chất hoặc điều chỉnh tuyến đường lái xe.

Thuật toán trung tâm

6. TrangRank

Những gì nó làm : Ước tính tầm quan trọng của một nút hiện tại từ các hàng xóm được liên kết của nó và sau đó một lần nữa từ các hàng xóm của họ. Thứ hạng của một nút được lấy từ số lượng và chất lượng của các liên kết bắc cầu của nó để ước tính ảnh hưởng. Mặc dù được Google phổ biến , nhưng nó được công nhận rộng rãi như một cách phát hiện các nút có ảnh hưởng trong bất kỳ mạng nào.

Cách sử dụng : PageRank được sử dụng theo nhiều cách để ước tính tầm quan trọng và tầm ảnh hưởng. Nó được sử dụng để đề xuất các tài khoản Twitter để theo dõi và phân tích tình cảm chung.

PageRank cũng được sử dụng trong học máy để xác định các tính năng có ảnh hưởng nhất để trích xuất. Trong sinh học, nó được sử dụng để xác định loài tuyệt chủng nào trong lưới thức ăn sẽ dẫn đến phản ứng dây chuyền lớn nhất về cái chết của loài.

7. Bằng cấp trung tâm

Nó làm gì : Đo số lượng mối quan hệ mà một nút (hoặc toàn bộ biểu đồ) có. Nó bị phá vỡ thành indegree (chảy vào) và outdegree (chảy ra) nơi mối quan hệ được hướng.

Cách thức sử dụng : Tính trung tâm của mức độ xem xét tính kết nối ngay lập tức đối với việc sử dụng, chẳng hạn như đánh giá rủi ro trong thời gian ngắn của một người bị nhiễm vi-rút hoặc nghe thông tin. Trong các nghiên cứu xã hội, sự đồng nhất của tình bạn có thể được sử dụng để ước tính mức độ phổ biến và vượt trội như tính tập thể.

8. Trung tâm gần gũi

Những gì nó làm : Đo lường mức độ trung tâm của một nút đối với tất cả các lân cận của nó trong cụm của nó. Các nút có đường dẫn ngắn nhất tới tất cả các nút khác được giả định là có thể đến toàn bộ nhóm nhanh nhất.

Cách sử dụng : Tính trung tâm gần gũi được áp dụng trong một số tài nguyên, giao tiếp và phân tích hành vi, đặc biệt là khi tốc độ tương tác là đáng kể. Nó đã được sử dụng để xác định vị trí tốt nhất của các dịch vụ công cộng mới để tiếp cận tối đa.

Trong phân tích mạng xã hội, nó được sử dụng để tìm những người có vị trí mạng xã hội lý tưởng để phổ biến thông tin nhanh hơn.

9. Giữa trung tâm

Những gì nó làm : Đo số lượng đường dẫn ngắn nhất (lần đầu tiên được tìm thấy với tìm kiếm đầu tiên theo chiều rộng) đi qua một nút. Các nút thường xuyên nằm trên các con đường ngắn nhất có điểm trung tâm giữa cao hơn và là cầu nối giữa các cụm khác nhau. Nó thường được liên kết với việc kiểm soát dòng tài nguyên và thông tin.

Cách sử dụng : Tính trung tâm áp dụng cho một loạt các vấn đề trong khoa học mạng và được sử dụng để xác định các tắc nghẽn hoặc các mục tiêu có khả năng tấn công trong các mạng truyền thông và giao thông. Trong genomics, nó đã được sử dụng để hiểu sự kiểm soát một số gen nhất định trong mạng lưới protein để cải thiện như nhắm mục tiêu thuốc / bệnh tốt hơn.

Betweenness Centrality cũng đã được sử dụng để đánh giá luồng thông tin giữa các game thủ trực tuyến nhiều người chơi và cộng đồng chia sẻ chuyên môn của các bác sĩ.

Thuật toán phát hiện cộng đồng

Thể loại này còn được gọi là thuật toán phân cụm hoặc thuật toán phân vùng .

10. Tuyên truyền nhãn

Những gì nó làm : Truyền bá nhãn dựa trên đa số khu phố như là một phương tiện suy ra các cụm. Phân vùng đồ thị cực nhanh này đòi hỏi ít thông tin trước và được sử dụng rộng rãi trong các mạng quy mô lớn để phát hiện cộng đồng. Đây là một phương pháp chính để hiểu cách tổ chức biểu đồ và thường là bước chính trong phân tích khác.

Cách sử dụng : Tuyên truyền nhãn có các ứng dụng đa dạng, từ tìm hiểu sự hình thành đồng thuận trong cộng đồng xã hội đến xác định các bộ protein có liên quan với nhau trong một quy trình (mô-đun chức năng) cho các mạng hóa sinh. Nó cũng được sử dụng trong học máy bán và không giám sát như một bước tiền xử lý ban đầu.

11. Kết nối mạnh mẽ

Nó làm gì: Định vị các nhóm nút trong đó mỗi nút có thể truy cập được từ mọi nút khác trong cùng một nhóm theo hướng của các mối quan hệ. Nó thường được áp dụng từ tìm kiếm theo chiều sâu.

Cách sử dụng : Kết nối mạnh thường được sử dụng để cho phép chạy các thuật toán khác một cách độc lập trên một cụm xác định. Là một bước tiền xử lý cho đồ thị có hướng, nó giúp nhanh chóng xác định các nhóm bị ngắt kết nối. Trong các đề xuất bán lẻ, nó giúp xác định các nhóm có ái lực mạnh mẽ sau đó được sử dụng để đề xuất các mặt hàng thường được ưa thích cho những người trong nhóm chưa mua mặt hàng đó.

12. Liên kết-Tìm / Các thành phần được kết nối / Kết nối yếu

Nó làm gì : Tìm các nhóm nút trong đó mỗi nút có thể truy cập được từ bất kỳ nút nào khác trong cùng một nhóm, bất kể hướng của các mối quan hệ. Nó cung cấp các hoạt động gần thời gian không đổi (không phụ thuộc vào kích thước đầu vào) để thêm các nhóm mới, hợp nhất các nhóm hiện có và xác định xem hai nút có nằm trong cùng một nhóm không

Cách sử dụng :  Các thành phần kết nối / tìm kiếm kết nối thường được sử dụng cùng với các thuật toán khác, đặc biệt là để phân nhóm hiệu suất cao. Là một bước tiền xử lý cho các đồ thị vô hướng, nó giúp nhanh chóng xác định các nhóm bị ngắt kết nối.

13. Mô-đun Louvain

Những gì nó làm: Đo lường chất lượng (nghĩa là độ chính xác được cho là) ​​của một nhóm cộng đồng bằng cách so sánh mật độ mối quan hệ của nó với một mạng ngẫu nhiên được xác định phù hợp. Nó thường được sử dụng để đánh giá tổ chức của các mạng phức tạp và phân cấp cộng đồng nói riêng. Nó cũng hữu ích cho tiền xử lý dữ liệu ban đầu trong học máy không giám sát.

Cách sử dụng : Louvain được sử dụng để đánh giá các cấu trúc xã hội trên Twitter, LinkedIn và YouTube. Nó được sử dụng trong các phân tích gian lận để đánh giá liệu một nhóm chỉ có một vài hành vi xấu hoặc hoạt động như một vòng lừa đảo sẽ được biểu thị bằng mật độ mối quan hệ cao hơn mức trung bình. Louvain tiết lộ một hệ thống phân cấp khách hàng sáu cấp trong một mạng lưới viễn thông của Bỉ.

14. Hệ số phân cụm cục bộ / Hệ số phân cụm nút

Nó làm gì : Đối với một nút cụ thể, nó định lượng mức độ lân cận của nó với một cụm (mọi nút được kết nối trực tiếp với mọi nút khác). Ví dụ: nếu tất cả bạn bè của bạn biết trực tiếp lẫn nhau, hệ số phân cụm cục bộ của bạn sẽ là 1. Các giá trị nhỏ cho một cụm sẽ chỉ ra rằng mặc dù tồn tại một nhóm, các nút không được kết nối chặt chẽ.

Cách sử dụng : Hệ số cụm cục bộ rất quan trọng để ước tính khả năng phục hồi bằng cách hiểu khả năng kết hợp hoặc phân chia nhóm. Một phân tích về lưới điện châu Âu sử dụng phương pháp này cho thấy các cụm có các nút được kết nối thưa thớt có khả năng phục hồi tốt hơn trước các thất bại lan rộng.

15. Hệ số phân cụm tam giác và trung bình

Nó làm gì : Đo lường có bao nhiêu nút có hình tam giác và mức độ mà các nút có xu hướng tụ lại với nhau. Hệ số phân cụm trung bình là 1 khi có một cụm và 0 khi không có kết nối. Để hệ số phân cụm có ý nghĩa, nó phải cao hơn đáng kể so với phiên bản của mạng nơi tất cả các mối quan hệ đã được xáo trộn ngẫu nhiên.

Cách sử dụng : Hệ số phân cụm trung bình thường được sử dụng để ước tính liệu một mạng có thể thể hiện các hành vi "thế giới nhỏ" dựa trên các cụm được đan chặt hay không. Đó cũng là một yếu tố cho sự ổn định và khả năng phục hồi của cụm. Các nhà dịch tễ học đã sử dụng hệ số phân cụm trung bình để giúp dự đoán tỷ lệ nhiễm khác nhau cho các cộng đồng khác nhau.

Phần kết luận

Thế giới được thúc đẩy bởi các kết nối. Phân tích biểu đồ Neo4j cho thấy ý nghĩa của các kết nối đó bằng các thuật toán đồ thị được tối ưu hóa thực tế bao gồm các thuật toán chi tiết ở trên.

Điều này kết thúc loạt bài của chúng tôi về các thuật toán đồ thị trong Neo4j. Chúng tôi hy vọng các thuật toán này giúp bạn hiểu được dữ liệu được kết nối của mình theo những cách có ý nghĩa và hiệu quả hơn.

|