oszacować wymiar fraktalny sieci złożonej, pod warunkiem, że węzły krawędzi

Question

Próbuję oszacować wymiar fraktalny złożonej (rzeczywistej) sieci. Mam węzły krawędzi tworzące złożoną sieć w pliku tekstowym. Próbowałem zaimplementować algorytm liczenia skrzynek (ale nie znalazłem wydajnej implementacji algorytmu, który działa lepiej w przypadku dużych sieci), ale później po przejrzeniu strony wiki o wymiarze Fractal w sieciach odkryłem, że istnieje inne podejście w tym celu mianowicie Cluster Growing Method. Czy ten algorytm został wcześniej zaimplementowany w jakiejś książce/papierze? (Szybkie wyszukiwanie google nie spowodowało)

Jeśli nie, czy możesz pomóc mi w implementacji tego algorytmu (ponieważ niewiele opisu znajduje się na stronie wiki , Jestem zdezorientowany, jak zacząć).

Answer 1

Wspominasz, że nie znalazłeś skutecznej implementacji algorytmu liczenia skrzynek, więc może mógłbyś sprecyzować, które implementacje sprawdziłeś. W ten sposób ludzie nie będą proponować rozwiązań, o których już wiesz. Ponadto, jakie są dokładnie twoje kryteria definiowania efektywności (przestrzeń, czas, niezawodność ...)?

Z artykułu "How to calculate the fractal dimension of a complex network: the box covering algorithm" z utworu i in., znalazłem implementację Pythona w metodzie liczenia skrzynek, dostępnej pod adresem here.

Answer 2

Nie należy implementować algorytmu liczenia skrzynek, ponieważ dowolna implementacja, która zostanie zaproponowana, nie będzie szybsza niż ta (http://repository.cmu.edu/compsci/580/). Poproś autorów o kod i zapoznaj się z przybliżeniem czasu wielomianu.

Z poważaniem.