Czy sieci społecznościowe są zwykle dobrymi ekspansorami?

11

Interesują mnie kombinatoryczne właściwości sieci społecznościowych w postaci grafów. Ludzie patrzyli na takie rzeczy, jak rozkład stopni, współczynnik grupowania i ściśliwość tych wykresów. Jedno podstawowe pytanie brzmi: czy te wykresy są zazwyczaj dobrymi wykresami ekspanderów?

Czy ktoś sprawdził, powiedzmy, lukę spektralną wykresu na Facebooku? Lub luka widmowa innych dużych sieci w świecie rzeczywistym? Mam nadzieję, że ktoś może skierować mnie we właściwym kierunku, aby dowiedzieć się na ten temat.

graph-theory application-of-theory expanders Zur Luria
źródło
Ponieważ każdy krok w iteracyjnym algorytmie wartości własnej dla macierzy przez n zwykle wymaga c n 2 kroków, wykresy, dla których możemy łatwo zdecydować, czy są to ekspandery, są znacznie mniejsze niż wykresy o skali sieci, o które pytasz. Nawet n = 10 5 jest wyzwaniem. Jednak sieci społecznościowe są wyjątkowe. Zasadniczo pytasz, czy możliwe jest przybliżenie wartości własnej w czymś takim jak czas quasilinearny i przestrzeń quasilinearna w n , jeśli wykres wejściowy jest rzadki, a jego stopnie wierzchołków są zgodne z prawem mocy. nndon2)n=105n
András Salamon,
Huh, zbyt długo koncentrowałem się na teorii. Nigdy nawet nie przyszło mi do głowy, że wykres na Facebooku może być tak duży, że obliczenie luki widmowej może być niemożliwe.
Zur Luria,

Odpowiedzi:

8

Sieci społecznościowe zazwyczaj mają wiele wierzchołków z jednym lub dwoma połączeniami z resztą wykresu. Takie wierzchołki zwykle prowadzą do złej przerwy widmowej.

Co mogłoby mieć nadzieję na dobre ekspansja vertex / EDGE dla dostatecznie dużych zestawów. Jeśli jednak masz ściśle powiązane społeczności w sieci, znowu możesz spodziewać się niskiej ekspansji.

Nie jestem pewien, czy całkiem odpowiada na twoje pytanie, ale poniższy artykuł empiryczny analizuje dokładnie takie same właściwości ekspansji w sieciach społecznościowych. Odpowiedź wydaje się różnić w zależności od sieci. http://fragkiskos.me/papers/expansion_SNSMW11.pdf

Jestem pewien, że istnieją inne prace w tym zakresie, prawdopodobnie ukryte przy użyciu alternatywnej terminologii („struktura społeczności”, rozmiary cięcia itp.).

Adam Smith
źródło
1

Wykresy mocy są prawdopodobnie dobrymi modelami dla wykresów sieci społecznościowych. Artykuł Gkantsidisa, Mihaila i Saberi pokazuje, że wykresy prawa mocy są ekspansorami.

Thatchaphol
źródło
Pomysł, że sieci społecznościowe są dystrybuowane jak przepisy dotyczące władzy, został ostatnio zakwestionowany przez bardzo rygorystyczną analizę danych: nature.com/articles/s41467-019-08746-5
Stella Biderman