Wyszukiwanie pośredników

Uruchomienie algorytmu

Aplikacja CAST pozwala na analizę wizualizowanych danych np. za pomocą algorytmu wyszukiwania pośredników. Aby uruchomić algorytm „Wyszukiwania pośredników” należy:

  1. Wybrać z menu Narzędzia -> Wyszukiwanie pośredników.
  2. Otwarte zostanie wówczas okno dialogowe umożliwiające wyszukiwanie pośredników. Zostało ono przedstawione na rysunku poniżej.
     Okno wyszukiwania pośredników

W okienku dialogowym możemy określić parametry, według których zostaną wyszukani pośrednicy. Parametry te są zdefiniowane w sposób następujący:

  • liczba węzłów - oznacza minimalną liczbę podejrzanych, z którymi dany węzeł musi być połączony,
  • liczba powiązań - oznacza minimalną liczbę połączeń, jaka musi wystąpić między danym węzłem, połączonymi podejrzanymi,
  • opcja do wyboru definiuje w jaki sposób liczba powiązań jest liczona:
    • minimum liczby połączeń oznacza, że pomiędzy danym węzłem a każdym połączonym podejrzanym musi być co najmniej równa określonej liczbie powiązań
    • suma liczby połączeń oznacza, że suma połączeń danego węzła z wszystkimi połączonymi podejrzanymi musi być co najmniej równa określonej liczbie powiązań

Przykłady

Przykładowy diagram dla ilustracji algorytmu

Zakładamy, że zaznaczone są wszystkie węzły.

Przykład 1

Załóżmy, że wybrano opcje:

  • liczba węzłów = 2,
  • liczba powiązań = 2,
  • opcja = minimum liczby połączeń

Wynik:

  • zostanie zaznaczony podejrzany nr 1, bo:
    • jest połączony z dwoma pośrednikami (podejrzani 2 i 4)
    • z każdym z nich ma ponad dwa połączenia (z podejrzanym 2 ma 2 połączenia, a z podejrzanym 4 ma 3 połączenia)
  • nie zostanie zaznaczony podejrzany nr 5, bo:
    • nie jest połączony z dwoma pośrednikami
  • nie zostanie zaznaczony podejrzany nr 3, bo:
    • ani z podejrzanym 2 ani z 4 nie jest połączony co najmniej dwoma połączeniami (z każdym z nich po jednym połączeniu)

Przykład 2

Załóżmy, że wybrano opcje:

  • liczba węzłów = 2,
  • liczba powiązań = 2,
  • opcja = suma liczby połączeń

Wynik:

  • zostanie zaznaczony podejrzany nr 1, bo:
    • jest połączony z dwoma pośrednikami (podejrzani 2 i 4)
    • w sumie ma 5 połączeń z pośrednikami
  • nie zostanie zaznaczony podejrzany nr 5, bo:
    • nie jest połączony z dwoma pośrednikami
  • zostanie zaznaczony podejrzany nr 3, bo:
    • jest połączony z dwoma pośrednikami (podejrzani 2 i 4)
    • w sumie ma 2 połączenia z pośrednikami

Szczegóły algorytmu

Specyfikacja algorytmu

Działanie algorytmu wyszukiwania pośredników wygląda następująco:

Dla każdego z zaznaczonych węzłów

1. Weź kolejny węzeł
2. Jeśli aktualny węzeł jest podejrzanym, to przejdź do 1.
3. Dodaj do listy wszystkie połączone (z danym) węzły podejrzanych i liczbę połączeń z nimi.
4. Jeżeli liczba podejrzanych, z którymi połączony jest aktualny węzeł, to przejdź do 1.
5. Jeżeli liczba powiązań z podejrzanymi jest mniejsza od wymaganej liczby (w zależności od wybranej opcji - suma/minimum) to przejdź do 1.
6. Oznacz węzeł jako pośrednika (podejrzanego).
7. Jeśli są jeszcze węzły to przejdź do 1.

Złożoność

W chwili obecnej algorytm ma złożoność n^2, gdzie n jest liczbą zaznaczonych węzłów. Można byłoby zoptymalizować jego działanie rozpoczynając przeszukiwanie od podejrzanych. Równocześnie można zastosować tutaj algorytmy do przeszukiwania grafów.

Uwagi

  • Kierunek połączeń nie ma znaczenia.
  • Algorytm działa na zaznaczonych węzłach, przy czym bierze pod uwagę niezaznaczonych podejrzanych. Innymi słowy przeszukiwane są tylko zaznaczone węzły nie będące podejrzanymi, ale jeśli chodzi o powiązania z podejrzanymi to brani są pod uwagę wszyscy podejrzani. Chcąc wykluczyć podejrzanego (tak, aby powiązanie do niego nie było liczone) należy zmienić status podejrzanego dla tego węzła.