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.
graph-theory
application-of-theory
expanders
Zur Luria
quelle
quelle
Antworten:
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.
quelle
Potenzgesetzgraphen sind wohl gute Modelle für Graphen sozialer Netzwerke. Dieses Papier von Gkantsidis, Mihail und Saberi zeigt, dass Potenzgesetzgraphen Expander sind.
quelle