Zasadniczo celem klastrowania grafów i metod wykrywania społeczności jest obliczanie klastrów. Czy jest jakaś różnica między nimi?
Zasadniczo celem klastrowania grafów i metod wykrywania społeczności jest obliczanie klastrów. Czy jest jakaś różnica między nimi?
Odpowiedzi:
Nie. Cytując na przykład z wykrycia społeczności na wykresach , niedawną i bardzo dobrą ankietę przeprowadzoną przez Santo Fortunato, „Ta funkcja prawdziwych sieci nazywa się strukturą społeczności (Girvan i Newman, 2002) lub klastrowaniem”. Naprawdę nie ma sensu dalej go omawiać. Mam wrażenie, że we wczesnych dokumentach analizujących sieci społecznościowe sieci były zwykle proste (nieważone), ale nie chciałbym się z tym kłócić, ani nie jest to ważne. Odpowiedź na twoje pytanie brzmi: nie.
W wykrywaniu struktur społecznościowych w sieci M.Newman definiuje grupowanie grafów jako specyficzny problem zdefiniowany w kontekście informatyki.
Rozważmy kilka obliczeń, które można podzielić na kilka prostszych operacji. Są one reprezentowane jako węzły w naszej sieci. Łącza odpowiadają zależnościom między operacjami, tzn. Wynik jednej operacji jest potrzebny drugiej. Problem polega na rozdzieleniu operacji na kilka procesorów w celu przetwarzania równoległego. Innymi słowy, chcemy przypisać każdy węzeł (operację) do konkretnej klasy (procesora), tzn. Chcemy podzielić wykres.
Istnieją jednak trzy ograniczenia. Pierwszym z nich jest uzyskanie z góry określonej liczby społeczności, ponieważ liczba procesorów jest oczywiście znana z góry. Drugim jest uzyskanie zrównoważonego obciążenia: chcemy, aby każdy procesor z grubsza wykonywał tę samą liczbę operacji. Pod względem graficznym chcemy, aby społeczności zawierały w przybliżeniu taką samą liczbę węzłów. Trzecim jest uzyskanie możliwie najniższej komunikacji między procesorami, ponieważ spowalnia proces. Zatem pod względem graficznym chcemy zminimalizować liczbę połączeń między społecznościami.
Z tego punktu widzenia wykrywanie społeczności można uznać za bardziej ogólny problem niż grupowanie wykresów. Trzecie ograniczenie jest egzekwowane w obu problemach, ale liczba i wielkość społeczności nie jest z góry znana w wykrywaniu społeczności.
Te dwie różne nazwy są nadawane tej samej rzeczy przez różne społeczności naukowców, w zależności od tego, czy ktoś chciałby podkreślić motywację sieci społecznościowych, czy nie. Być może ktoś definiuje grupowanie i wykrywanie społeczności jako różne rzeczy, ale większość osób, które badają jedną z nich, nie byłaby w stanie powiedzieć, dlaczego nie używa drugiego terminu.
Jeśli duża sieć jest podzielona na dwie części, co gwarantuje, że ta dwie części to dwie społeczności? Dwa klastry mają niskie połączenie, co nie oznacza, że każdy klaster ma podobny rodzaj węzłów lub węzły mają podobny rodzaj połączeń (dlatego społeczność). Pomyśl o wykresie sieci społecznościowych. Na pewno jest wiele społeczności. Również za pomocą algorytmów klastrowania można podzielić go na dwie części. W takim przypadku nazwałbyś każdy element wspólnotą. ? Moja odpowiedź brzmi nie. Ponieważ te dwa klastry mogą być ludźmi z dwóch regionów geograficznych. A na pewno nie są to społeczności.
Algorytmy klastrowania dbają tylko o minimalne odcięcie, a nie o podobieństwo węzłów lub podobieństwo połączeń lub gęste połączenie. Dodatkowo w algorytmach klastrowania liczba klastrów powinna być z góry określona.
Algorytmy wykrywania społeczności, dbają o gęstość, znajdują gęstszą część sieci i tego rodzaju algorytmy (do tej pory widziałem) nie muszą z góry określać liczby społeczności.
Jednak do znalezienia społeczności można użyć algorytmu klastrowania, ponieważ ponieważ nie gwarantuje to, że każdy klaster ma dobrą strukturę społeczności, każdy klaster powinien zostać dokładnie zbadany.
„nie można w sposób trywialny zastosować odnajdywania społeczności w celu rozwiązania klastrowania i odwrotnie. pomimo podobieństw w podejściach istnieją istotne różnice. Odkrywanie społeczności zakłada rzadkie połączenia, podczas gdy klastrowanie może pracować z gęstymi zbiorami danych; w grupowaniu zwykle mamy do czynienia z atrybutami o wielu typach , podczas gdy odkrywanie społeczności zwykle zajmuje się jednym typem atrybutu - krawędziami - często binarnymi, w przypadku nieważonych sieci ”, aby uzyskać więcej informacji, przeczytaj następujący artykuł:„ W sprawie równoważności odkrywania i klastrowania społeczności ”Riccardo Guidotti i Michele Coscia