Como testar estatisticamente se minha rede (gráfico) é uma rede de “mundo pequeno” ou não?

10

Uma rede de mundo pequeno é um tipo de gráfico matemático no qual a maioria dos nós não é vizinhos um do outro, mas a maioria dos nós pode ser alcançada entre si por um pequeno número de saltos ou etapas. Especificamente, uma rede de mundo pequeno é definida como uma rede em que a distância típica L entre dois nós escolhidos aleatoriamente (o número de etapas necessárias) cresce proporcionalmente ao logaritmo do número de nós N na rede, ou seja,

Llog(N)

Essa relação entre L e N é uma "regra geral". Estou procurando uma determinação mais profissional de gráficos do mundo pequeno para minha pesquisa. Como posso testar se meu gráfico é um mundo pequeno ou não?

O experimento no mundo pequeno compreendeu vários experimentos realizados por Stanley Milgram e outros pesquisadores que examinam o comprimento médio do caminho para redes sociais de pessoas nos Estados Unidos. A pesquisa foi inovadora na medida em que sugeria que a sociedade humana é uma rede do tipo mundo pequeno, caracterizada por trechos curtos. Os experimentos são frequentemente associados à frase "seis graus de separação", embora Milgram não tenha usado esse termo.

Agradeço antecipadamente.

Übel Yildmar
fonte
2
Não sei qual é o propósito do seu papar ou seu histórico. Você tem um gráfico real que deseja testar? Você poderia tomar medidas descritivas básicas do seu gráfico, qualquer biblioteca de gráficos faria (por exemplo, networkx em python ou igraph em R). Basta verificar se sua rede está conectada, qual é o diâmetro, o caminho mais curto médio etc. Se você estiver gerando o gráfico ou se o seu contexto for diferente, eu diria que são necessárias mais informações para responder à sua pergunta.
Lrnzcig # 5/15
2
Para avaliar a presença desse relacionamento logarítmico, acho que você precisaria de uma série de valores. Por exemplo, uma sequência de instantâneos do seu gráfico evoluindo ao longo do tempo. Ou uma coleção de gráficos diferentes correspondentes a sistemas similares (comparáveis) (por exemplo, redes de computadores de várias empresas de vários tamanhos).
Vincent Labatut

Respostas:

7

TL; DR:

Você não pode.

O que normalmente é feito

O atual "estado da arte" para determinar se uma rede é um mundo pequeno usa a seguinte abordagem:

  1. Calcule o comprimento médio do caminho mais curto  e o coeficiente de cluster  da sua rede.LC

  2. Gere um conjunto apropriado de redes de modelo nulo, como gráficos aleatórios Erdős – Rényi ou gráficos aleatórios Maslov-Sneppen .

  3. Calcule a média do comprimento médio do caminho mais curto neste conjunto de redes de modelo nulo; calcule analogamente.LrCr

  4. Calcule o caminho mais curto normalizado . e .λ:=L/Lrγ:=C/Cr

  5. Se e certos critérios (por exemplo, e ), chame a rede de rede do mundo pequeno.λγλ1γ>1

A idéia por trás disso é que:

  • As redes de pequenos países devem ter alguma estrutura espacial, refletida por um alto coeficiente de agrupamento. Por outro lado, as redes aleatórias não possuem essa estrutura e um baixo coeficiente de agrupamento.

  • As redes de mundo pequeno são eficientes na comunicação e similares e, portanto, têm um pequeno comprimento de caminho mais curto, comparável ao das redes aleatórias. Por outro lado, redes puramente espaciais têm um comprimento de caminho mais curto alto.

Onde estão os problemas

  • Isso não diz nada sobre como o caminho mais curto médio é dimensionado com o tamanho da rede. De fato, para redes reais, toda a definição que você citou não pode ser aplicada, pois não existe a mesma rede com um número diferente de nós.

  • Suponhamos que tomemos outra definição de um mundo pequeno que não seja diretamente baseado nos valores de e , por exemplo:λγ

    Uma rede de mundo pequeno é uma rede espacial com conexões de longo alcance adicionadas.

    Então, ainda não podemos ter implicações robustas sobre se essa definição é cumprida apenas usando e (ou de fato outras medidas de rede). A interpretação de muitos estudos pressupõe que todas as redes são uma realização do modelo Watts-Strogatz para alguma probabilidade de religação, o que não se justifica: conhecemos muitos outros modelos de rede cujas realizações são inteiramente diferentes do modelo Watts-Strogatz.λγ

  • O método acima não é robusto para erros de medição. Pequenos erros ao estabelecer uma rede a partir de medições são suficientes para fazer, por exemplo, uma rede parecer uma rede de mundo pequeno; veja, por exemplo, Bialonski et al., Chaos (2010) e Papo et al., Front. Cantarolar. Neurosci. (2016) . De fato, não conheço um único estudo que afirme que alguma rede empírica não seja uma rede de mundo pequeno.

Sidenote: O que você ganharia?

Não conheço nenhum insight útil que possa ser derivado de alguma rede ser um mundo pequeno. A afirmação de que algum tipo de rede é bem descrita por um determinado modelo de rede (por exemplo, o modelo Watts-Strogatz) pode ser útil para estudos de modelagem, mas isso vai muito além do que alegar um mundo pequeno.

Isenção de responsabilidade completa: Um dos artigos acima é da minha vizinhança acadêmica direta.

Wrzlprmft
fonte
Além disso, você conhece algum artigo em que a metodologia mencionada nesta resposta esteja listada. Criando um conjunto de redes, o cálculo da sua média etc
A Última Palavra
@ TheLastWord: Além disso, você conhece algum artigo em que a metodologia mencionada nesta resposta esteja listada. - O artigo de Bialonski et al resume essa abordagem e deve conter referências relevantes. Veja também este meu papel .
Wrzlprmft