Sind soziale Netzwerke normalerweise gute Expander?

11

Ich interessiere mich für die kombinatorischen Eigenschaften sozialer Netzwerke als Grafiken. Die Leute haben sich Dinge wie die Verteilung der Grade, den Clustering-Koeffizienten und die Kompressibilität dieser Graphen angesehen. Eine grundlegende Frage lautet: Sind diese Diagramme normalerweise gute Expander-Diagramme?

Hat jemand beispielsweise die spektrale Lücke des Facebook-Graphen überprüft? Oder die spektrale Lücke anderer großer realer Netzwerke? Ich hoffe, dass mich jemand in die richtige Richtung weisen kann, um mehr über dieses Thema zu erfahren.

Zur Luria
quelle
Da jeder Schritt in einem iterativen Eigenwertalgorithmus für mal n Matrizen typischerweise c n 2 Schritte erfordert , sind die Graphen, für die wir leicht entscheiden können, ob sie Expander sind, viel kleiner als die von Ihnen angeforderten Web-Scale-Graphen. Auch n = 10 5 ist eine Herausforderung. Soziale Netzwerke sind jedoch etwas ganz Besonderes. Im Wesentlichen fragen Sie sich, ob es möglich ist, einen Eigenwert in so etwas wie quasilinearer Zeit und quasilinearem Raum in n zu approximieren , wenn der Eingabegraph spärlich ist und seine Scheitelpunkte einem Potenzgesetz folgen. nncn2n=105n
András Salamon
Huh, ich habe mich zu lange auf die Theorie konzentriert. Mir ist noch nie in den Sinn gekommen, dass das Facebook-Diagramm so groß sein könnte, dass es unmöglich wäre, seine spektrale Lücke zu berechnen.
Zur Luria

Antworten:

8

Soziale Netzwerke haben normalerweise viele Eckpunkte mit nur einer oder zwei Verbindungen zum Rest des Diagramms. Solche Eckpunkte führen typischerweise zu einer schlechten spektralen Lücke.

Was Sie könnte hoffen ist gut Vertex / edge Erweiterung für ausreichend große Mengen. Wenn Sie jedoch engmaschige Communities innerhalb des Netzwerks haben, würden Sie wiederum eine geringe Expansion erwarten.

Ich bin mir nicht sicher, ob es Ihre Frage ganz beantwortet, aber das folgende empirische Papier befasst sich genau mit expansionsähnlichen Eigenschaften in sozialen Netzwerken. Die Antwort scheint von Netzwerk zu Netzwerk zu variieren. http://fragkiskos.me/papers/expansion_SNSMW11.pdf

Ich bin mir sicher, dass es andere Arbeiten in dieser Richtung gibt, die möglicherweise mit einer alternativen Terminologie ("Community-Struktur", Schnittgrößen usw.) getarnt sind.

Adam Smith
quelle
1

Potenzgesetzgraphen sind wohl gute Modelle für Graphen sozialer Netzwerke. Dieses Papier von Gkantsidis, Mihail und Saberi zeigt, dass Potenzgesetzgraphen Expander sind.

Thatchaphol
quelle
Die Idee, dass soziale Netzwerke wie Machtgesetze verteilt werden, wurde kürzlich durch eine äußerst strenge Datenanalyse bestritten: nature.com/articles/s41467-019-08746-5
Stella Biderman