Algoritmo para cálculo de distâncias mínimas em redes de escala livre

Elizabete Koehler, Reginaldo Aparecido Zara

Resumo

Muitos sistemas naturais e tecnológicos podem ser representados matematicamente por uma classe de grafos chamada de redes de escala livre. Exemplos destes sistemas são a Internet e a World-Wide Web.  Nestas redes, a distância média entre vértices é uma grandeza de fundamental importância em processos de transmissão de dados ou recuperação de informação. Neste trabalho aplicam-se métodos computacionais para estimar as distâncias entre vértices da rede de escala livre resultante do modelo de crescimento de Barabsi-Albert. Os resultados mostram que, independentemente da conectividade, as distâncias máximas são funções logarítmicas crescentes do número de vértices da rede.

Palavras-chave

Distribuições de conectividades; Grafos; Menores caminhos.

Texto completo:

PDF