Zdecentralizowany algorytm do określania wpływowych węzłów w sieciach społecznościowych

13

W tym artykule Kempe-Kleinberg-Tardos autorzy proponują zachłanne algorytmy oparte na funkcjach submodularnych w celu określenia najbardziej wpływowych węzłów na wykresie, z zastosowaniem do sieci społecznościowych.k

Zasadniczo algorytm wygląda następująco:

  1. S=empty set
  2. wybierz węzeł o najwyższym indywidualnym wpływie, nazwij go ; S = S v 1v1S=Sv1
  3. usuń i wszystkie krawędzie łączące v 1 z resztą sieciv1v1
  4. powtarzaj, aż ma k wierzchołkówSk

Mam dwa pytania dotyczące wpływowych węzłów w sieciach społecznościowych.
a) Czy istnieje algorytm do znalezienia rozwiązania lub jego przybliżenia w sposób zdecentralizowany?
b) Czy ktoś zastosował inne algorytmy, takie jak Page-Rank i podobne, aby rozwiązać ten sam problem?

Kok
źródło
Jak zdefiniować „wpływowy” węzeł?
Timothy Sun
2
zgodnie z dokumentem, każde łącze jest zdefiniowane z prawdopodobieństwem pomyślnego przesłania wiadomości z jednego węzła do drugiego. Celem jest znalezienie podzbioru węzłów, które dostarczą komunikat do największej liczby węzłów, zgodnie z oczekiwaniami.
Bob
kDDk=1D
Rozumiem, że. Moją obawą było to, czy istnieje przynajmniej suboptymalny algorytm przybliżający optymalne rozwiązanie.
Bob

Odpowiedzi: