thuật toán k-core gia tăng

Question

Tính toán số k-core của biểu đồ bằng các đỉnh cắt tỉa lặp lại đủ dễ dàng. Tuy nhiên, đối với ứng dụng của tôi, tôi muốn có thể thêm đỉnh vào đồ thị bắt đầu và lấy lõi được cập nhật mà không cần phải tính toán lại toàn bộ k-core từ đầu. Có một thuật toán đáng tin cậy có thể tận dụng công việc được thực hiện trên các lần lặp trước không?

Đối với những người tò mò, k-core đang được sử dụng như một giai đoạn tiền xử lý trong một thuật toán tìm kiếm clique. Bất kỳ cliques nào có kích thước 5 được đảm bảo là một phần của 4 lõi của đồ thị. Trong tập dữ liệu của tôi, 4 lõi nhỏ hơn nhiều so với toàn bộ đồ thị để làm cho nó bị bạo lực. Tăng thêm đỉnh cho phép thuật toán hoạt động với dung lượng nhỏ nhất có thể. Tập hợp các đỉnh của tôi là vô hạn và được sắp xếp (số nguyên tố), nhưng tôi chỉ quan tâm đến số thấp nhất được đánh số.

Edit:

Suy nghĩ về nó một số chi tiết dựa trên câu trả lời của akappa, phát hiện việc tạo ra một vòng lặp là thực sự quan trọng. Trong đồ thị dưới đây, 2-core rỗng trước khi thêm F. Thêm F không thay đổi mức độ A nhưng nó vẫn thêm A vào 2-core. Thật dễ dàng để mở rộng điều này để xem cách đóng một vòng lặp của bất kỳ kích thước nào sẽ làm cho tất cả các đỉnh cùng tham gia vào 2 lõi.

Việc thêm một đỉnh có thể ảnh hưởng đến độ nhạy của các đỉnh một khoảng cách tùy ý, nhưng có lẽ điều này tập trung quá nhiều vào hành vi xấu nhất.

Answer 1

Dường như với tôi rằng một thuật toán cho một tính toán k-core gia tăng dựa trên thăm dò địa phương của đồ thị, thay vì một tỉa lặp đi lặp lại "toàn cầu", sẽ cần một phát hiện vòng lặp gia tăng để xem các cạnh có thể đóng góp để nhập một đỉnh trong lõi k, đó là một vấn đề khó khăn.

Tôi nghĩ rằng tốt nhất bạn có thể làm là tính toán lại thuật toán k-core ở mỗi lần truyền, chỉ cần xóa khỏi đồ thị các đỉnh đã có trong lõi k và khởi tạo, trong đỉnh bản đồ -> "k -core đỉnh liền kề "số đỉnh liền kề đã có trong lõi k.

Answer 2

Ý tưởng nhanh: Bạn có thể lưu lịch sử trong danh sách L, tức là lưu thứ tự mà các nút bị xóa. Bất cứ khi nào bạn thêm một nút v mới, bắt đầu từ nút đầu tiên w trong L tiếp giáp với v. Sau đó, chỉ cần đi qua các nút còn lại trong L từ w theo thứ tự tuyến tính. (Và kiểm tra nút v là tốt và có thể thêm nó vào L.)

Answer 3

Đây là một vấn đề khó, nhưng chắc chắn không phải NP-Hard. Cho đến nay như tôi biết, không có giải pháp chung trong các học viện về cập nhật gia tăng của K-lõi với bất kỳ số K. Nhưng hai giấy tờ sau đây chắc chắn là đáng đọc:

[1] Trích xuất phân tích và hình dung tam giác K- Họa tiết cốt lõi trong mạng. http://www.cse.ohio-state.edu/~zhangya/ICDE12_conf_full_179.pdf

[2] Thuật toán trực tuyến cho phân tích lõi k. http://www.cse.ohio-state.edu/~sariyuce/file/Publications_files/VLDB13.pdf

Chúng được xuất hiện trong các hội nghị hàng đầu trong khu vực quản lý dữ liệu, do đó phương pháp nên đáng tin cậy.