Chińskie szepty (metoda grupowa)
Chińskie szepty to metoda grupowania używana w nauce o sieciach, nazwana na cześć słynnej gry szeptanej . Metody klastrowania służą zasadniczo do identyfikowania społeczności węzłów lub łączy w danej sieci. Algorytm ten został zaprojektowany przez Chrisa Biemanna i Svena Teresniaka w 2005 roku. Nazwa pochodzi od faktu, że proces ten można modelować jako rozdzielanie społeczności, w których węzły wysyłają do siebie informacje tego samego typu.
Chińskie szepty to metoda twardego partycjonowania, losowego, płaskiego grupowania (brak hierarchicznych relacji między klastrami ). Właściwość losowości oznacza, że kilkakrotne uruchomienie procesu w tej samej sieci może prowadzić do różnych wyników, podczas gdy ze względu na twarde partycjonowanie jeden węzeł może należeć tylko do jednego klastra w danym momencie. Oryginalny algorytm ma zastosowanie do grafów nieskierowanych, ważonych i nieważonych. Chińskie szepty są liniowe w czasie, co oznacza, że są niezwykle szybkie, nawet jeśli liczba węzłów i łączy w sieci jest bardzo duża.
Algorytm
Algorytm działa w następujący sposób w nieskierowanym grafie nieważonym:
- Wszystkie węzły są przypisane do odrębnej klasy (liczba początkowych klas jest równa liczbie węzłów).
- Następnie wszystkie węzły sieci są wybierane jeden po drugim w losowej kolejności. Każdy węzeł przechodzi do klasy, którą dany węzeł łączy z największą liczbą linków. W przypadku równości klaster jest wybierany losowo z równo powiązanych klas.
- Krok drugi powtarza się do określonej z góry liczby iteracji lub do momentu zbieżności procesu. Ostatecznie powstające klasy reprezentują klastry sieci.
Z góry określony próg liczby iteracji jest potrzebny, ponieważ możliwe jest, że proces nie będzie zbieżny. Z drugiej strony w sieci z około 10000 węzłów klastry nie zmieniają się znacząco po 40-50 iteracjach, nawet jeśli nie ma zbieżności.
Mocne i słabe strony
Główną siłą chińskich szeptów jest ich liniowość czasowa. Ponieważ czas przetwarzania rośnie liniowo wraz z liczbą węzłów, algorytm jest w stanie bardzo szybko zidentyfikować społeczności w sieci. Z tego powodu chińskie szepty są dobrym narzędziem do analizy struktur społeczności na grafie z bardzo dużą liczbą węzłów. Skuteczność metody wzrasta dalej, jeśli sieć ma właściwość małego świata .
Z drugiej strony, ponieważ algorytm nie jest deterministyczny w przypadku małej liczby węzłów, otrzymane klastry często znacznie różnią się od siebie. Dzieje się tak dlatego, że w przypadku małej sieci większe znaczenie ma to, od którego węzła zaczyna się proces iteracji, podczas gdy w dużych sieciach zanika trafność punktów startowych. Z tego powodu dla małych wykresów zalecane są inne metody grupowania.
Aplikacje
Chińskie szepty są używane w wielu dziedzinach nauki o sieciach. Najczęściej wspomina się o tym w kontekście z przetwarzaniem języka naturalnego . Z drugiej strony algorytm ma zastosowanie do każdego rodzaju problemu identyfikacji społeczności, który jest związany z ramami sieciowymi. Chińskie szepty są dostępne do użytku osobistego jako pakiet rozszerzeń dla Gephi , który jest programem typu open source przeznaczonym do analizy sieci.