Thư viện đồ thị tăng cường: Có thuật toán gọn gàng được tích hợp vào BGL để phát hiện cộng đồng không?

Question

Có ai ở đó sử dụng BGL cho các máy chủ sản xuất lớn không?

• Mạng của bạn có bao nhiêu nút?
• Làm cách nào để bạn xử lý community detection
• BGL có cách nào hay để phát hiện cộng đồng không?
• Đôi khi hai cộng đồng có thể được liên kết với nhau bằng một hoặc hai cạnh, nhưng các cạnh này không đáng tin cậy và có thể biến mất. Đôi khi không có cạnh nào cả.

Ai đó có thể nói ngắn gọn về cách giải quyết vấn đề này. Hãy mở tâm trí của tôi và truyền cảm hứng cho tôi.

Cho đến nay tôi đã cố gắng tìm ra nếu hai nút trên đảo (trong cộng đồng) theo cách tốn kém nhất, nhưng bây giờ tôi cần tìm ra hai nút trên các hòn đảo riêng biệt gần nhau nhất. Chúng tôi chỉ có thể sử dụng tối thiểu dữ liệu địa lý không đáng tin cậy.

Nếu chúng tôi so sánh nó với đất liền và một hòn đảo và đưa nó ra khỏi bối cảnh khoảng cách xã hội. Tôi muốn tìm ra hai mảnh đất gần nhau nhất trên một vùng nước.

Answer 1

Tôi đã sử dụng BGL cho đồ thị với hàng triệu nút, nhưng kích thước của biểu đồ bạn có thể sử dụng phụ thuộc vào thuật toán bạn đang cố gắng chạy. Bạn có thể nhanh chóng tính toán khoảng cách giữa các nút. Có 4 thuật toán đường dẫn ngắn nhất được áp dụng nhiều nhất tùy thuộc vào dữ liệu của bạn: (các cặp điểm, cho tất cả các cặp điểm, biểu đồ thưa thớt và dày đặc, ...).

Đối với phát hiện cộng đồng, không có bất kỳ thuật toán nào được tích hợp vào BGL cụ thể cho điều đó (nhưng có thể bạn có thể đóng góp một khi bạn hoàn thành dự án của mình). Có một vài thuật toán có thể hữu ích trong việc xây dựng thuật toán phát hiện cộng đồng.Thuật toán max-flow/min-cut thường được sử dụng trong phát hiện cộng đồng (nếu có nhiều luồng có thể giữa hai nút, thì chúng có thể nằm trong cùng một cộng đồng, nếu không có nhiều lưu lượng, thì việc cắt giảm có thể đại diện đường giữa các cộng đồng). Ngoài ra còn có các chẩn đoán để sắp xếp các nút của biểu đồ để giảm bandwidth. Các nút tạo thành "cộng đồng" có khả năng ở gần nhau theo thứ tự như vậy.

Answer 2

Theo như tôi biết BGL không có bất kỳ thuật toán nào đặc biệt để phát hiện cộng đồng.

Bởi "đảo", bạn có nghĩa là biểu đồ con bị ngắt kết nối không?

Ngoài ra, biểu đồ không có bất kỳ khái niệm nào về 'khoảng cách'.

'Khoảng cách xã hội' này là thứ bạn sẽ phải xác định. Một khi bạn đã hoàn thành một phần lớn công việc được thực hiện.

Có nhiều phương pháp được liệt kê trên trang bạn đã liên kết, hầu hết các phương pháp này chỉ yêu cầu bạn xác định thứ gì đó như chỉ số 'khoảng cách' và sau đó cắm định nghĩa của bạn vào thuật toán.

@ David Nehme

Đồ thị không có cạnh trọng lượng chỉ liên quan đến nhau, chúng không có khái niệm khoảng cách. Nếu bạn muốn nói về một mạng thì bạn có thể nói về khoảng cách. Nhưng một biểu đồ không có trọng số cạnh không có bất kỳ khoảng cách nào, trừ khi bạn muốn giả định một trọng lượng cạnh ngụ ý là 1 cho tất cả các cạnh. Nhưng điều này thực sự chỉ là biến đồ thị thành một mạng.

Ngoài ra, anh ấy đang nói về khoảng cách giữa hai biểu đồ bị ngắt kết nối. Để mô hình hóa điều này, bạn phải giới thiệu một khái niệm bên ngoài cho khoảng cách giữa các nút, tách biệt với khoảng cách cạnh.