2012-09-13 35 views
7

Tôi đang cố gắng ước tính kích thước fractal của mạng phức tạp (thế giới thực). Tôi có các nút của các cạnh tạo thành mạng phức tạp trong một tệp văn bản. Tôi đã cố gắng thực hiện thuật toán Box Counting (nhưng không tìm thấy thuật toán hiệu quả của thuật toán, hoạt động tốt hơn cho các mạng lớn), nhưng sau khi tìm kiếm trang wiki trên kích thước Fractal trên mạng, tôi thấy rằng có một cách tiếp cận khác cho điều này, cụ thể là Cluster Growing Method. Thuật toán này có được thực hiện trong bất kỳ cuốn sách/giấy nào trước đây không? (Tìm kiếm nhanh trên google không mang lại lợi nhuận)ước tính kích thước fractal của mạng phức tạp, cung cấp các nút của các cạnh

Nếu không, bạn có thể giúp tôi thực hiện thuật toán này hay không. , Tôi đang bối rối làm thế nào để bắt đầu).

Trả lời

3

Bạn đề cập đến bạn không tìm thấy bất kỳ triển khai hiệu quả nào của thuật toán đếm hộp, vì vậy có thể bạn có thể xác định những triển khai nào bạn đã đánh giá. Bằng cách này, mọi người sẽ không đề xuất các giải pháp mà bạn đã biết. Hơn nữa, chính xác tiêu chí của bạn là gì để xác định hiệu quả (không gian, thời gian, độ tin cậy ...)?

Từ giấy "How to calculate the fractal dimension of a complex network: the box covering algorithm" của Bài hát et al., tôi đã tìm thấy việc triển khai Python của phương pháp đếm hộp, có sẵn here.

0

Không triển khai thuật toán Đếm hộp vì bất kỳ triển khai nào bạn đề xuất sẽ không nhanh hơn (http://repository.cmu.edu/compsci/580/). Hãy hỏi các tác giả về mã và tận hưởng sự gần đúng của bạn trên thời gian đa thức.

Trân trọng.

Các vấn đề liên quan