As redes sociais geralmente são boas expansoras?

11

Estou interessado nas propriedades combinatórias das redes sociais como gráficos. As pessoas analisaram coisas como a distribuição dos graus, o coeficiente de agrupamento e a compressibilidade desses gráficos. Uma pergunta básica é: esses gráficos geralmente são bons gráficos de expansão?

Alguém verificou, digamos, a lacuna espectral do gráfico do facebook? Ou a lacuna espectral de outras grandes redes do mundo real? Espero que alguém possa me indicar a direção certa para aprender sobre este tópico.

graph-theory application-of-theory expanders Zur Luria
fonte
Uma vez que cada passo de um iterativo valor próprio algoritmo para por n matrizes normalmente requer c n 2 passos, os gráficos para o qual podemos facilmente decidir se eles são expansores são muito menores do que os gráficos de escala da web que você perguntar. Mesmo n = 10 5 é um desafio. No entanto, as redes sociais são bastante especiais. Essencialmente, você está perguntando se é possível aproximar um valor próprio em algo como tempo quaseilinear e espaço quaseilinear em n , se o gráfico de entrada é esparso e seus graus de vértice seguem uma lei de potência. nncn2n=105n
András Salamon
Estou focado na teoria há muito tempo. Nunca me ocorreu que o gráfico do facebook fosse tão grande que seria inviável calcular sua lacuna espectral.
Zur Luria

Respostas:

8

As redes sociais geralmente têm muitos vértices com apenas uma ou duas conexões com o restante do gráfico. Tais vértices normalmente levam a uma lacuna espectral ruim.

O que você poderia esperar é uma boa expansão de vértice / borda para conjuntos suficientemente grandes. No entanto, se você tiver comunidades muito unidas na rede, novamente esperaria uma baixa expansão.

Não tenho certeza se isso responde à sua pergunta, mas o artigo empírico a seguir analisa exatamente as propriedades semelhantes às de expansão nas redes sociais. A resposta parece variar de rede para rede. http://fragkiskos.me/papers/expansion_SNSMW11.pdf

Tenho certeza de que existem outros trabalhos nesse sentido, possivelmente disfarçados usando terminologia alternativa ("estrutura da comunidade", tamanhos de corte, etc.).

Adam Smith
fonte
1

Os gráficos de direito do poder são indiscutivelmente bons modelos para gráficos de redes sociais. Este artigo de Gkantsidis, Mihail e Saberi mostra que os gráficos de leis de potência são expansores.

Thatchaphol
fonte
A ideia de que as redes sociais são distribuídas como leis de poder foi recentemente contestada por uma análise altamente rigorosa dos dados: nature.com/articles/s41467-019-08746-5
Stella Biderman