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:

$S = {\rm empty~set}$
wybierz węzeł o najwyższym indywidualnym wpływie, nazwij go ; $v_1$ $S = S\cup v_1$
usuń i wszystkie krawędzie łączące z resztą sieci $v_1$ $v_1$
powtarzaj, aż ma wierzchołków $S$ $k$

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

k

$k$

D

$D$

D

$D$

k = 1

$k = 1$

D

$D$

Rozumiem, że. Moją obawą było to, czy istnieje przynajmniej suboptymalny algorytm przybliżający optymalne rozwiązanie.

— Bob

3

Zdecentralizowane algorytmy dla wariantów tego problemu zostały opublikowane w Rozproszonym i chroniącym prywatność algorytmie do identyfikacji centrów informacyjnych w sieciach społecznościowych i analizy wpływu społecznego w sieciach na dużą skalę .

— Massimo Cafaro
źródło

2

Co powiesz na te? Przynosząc PageRank do analizy cytowań przez Ma, Guan, Zhao

PageRank za ranking autorów w sieci współcytującej Ding, Yan, Frazho, Caverlee

— vzn
źródło