Estou interessado em modelos de gráficos aleatórios que são semelhantes aos gráficos de redes de computadores reais. Não tenho certeza se o modelo comum e bem estudado ( n vértices, cada aresta possível é selecionada com probabilidade p ) é bom para estudar redes de computadores reais (não é?).
Que modelos de gráficos aleatórios são úteis para entender as redes de computadores criadas na prática?
De maneira mais geral, que outros modelos de gráficos aleatórios finitos (que não sejam equivalentes ao modelo ) foram estudados na literatura? (Uma resposta ideal seria um ponteiro para uma pesquisa para modelos estudados de gráficos aleatórios finitos.)
Respostas:
Nos últimos anos, o estudo de gráficos aleatórios com restrições estruturais "naturais" ganhou força. Por exemplo, pode-se considerar um gráfico plano desenhado uar da classe de todos os gráficos planares com vértices e estudar como ele se comporta como n → ∞ . Diferentemente dos gráficos aleatórios Erdős-Rényi ou de outros modelos similares, as arestas nesses gráficos são altamente dependentes; portanto, uma das pseudo-motivações para o estudo de tais distribuições é analisar modelos de rede com independência muito limitada entre as arestas.n n → ∞
No entanto, talvez, atualmente, esse objetivo pareça muito distante, pois a independência limitada torna muito mais difícil analisar as propriedades desses gráficos. De fato, várias questões básicas que são facilmente respondidas para , como a distribuição da sequência de graus, foram resolvidas apenas recentemente para gráficos planares aleatórios.G ( n , p )
Para uma referência definitiva, consulte os artigos de Konstantinos Panagiotou e as citações nele contidas. Por conveniência, aqui está uma pequena amostra de alguns artigos relevantes:
fonte
Esta pesquisa, A estrutura e função de redes complexas de Newman, analisa técnicas e modelos para redes complexas reais, incluindo conceitos como efeito de mundo pequeno, distribuição de graus e modelos de gráficos aleatórios. Além disso, o mesmo autor tem um bom artigo, Gráficos aleatórios como modelos de redes , sobre adaptações de gráficos aleatórios para modelar redes reais.
Referências:
1) Gráficos aleatórios como modelos de redes, MEJ Newman, no Handbook of Graphs and Networks, S. Bornholdt e HG Schuster (eds.), Wiley-VCH, Berlin (2003).
2) A estrutura e função de redes complexas, MEJ Newman, SIAM Review 45, 167-256 (2003)
fonte
Redes de computadores reais em que camada? A Internet é, no nível AS (sem dúvida o nível mais alto), uma rede de mundo pequeno com alguns nós de grau extremamente alto. À medida que as camadas se aproximam dos fios reais, o gráfico se torna mais vinculado à geografia e menos vinculado à camada social (social é o tipo de palavra errada - é realmente uma rede social quando as entidades que são "amigas" são empresas multinacionais?) . No caso extremo, uma Ethernet local é uma árvore lógica que é (provavelmente) um subgrafo do padrão físico das conexões de fio, e esse padrão de conexões de fio provavelmente não possui muitos fios além de uma árvore.
"Redes de computadores reais" vêm em vários sabores e camadas. Alguns deles parecem redes sociais, outros não. Para mais informações, remeto-lhe indecentemente o capítulo 2 da minha dissertação - http://home.manhattan.edu/~peter.boothe/thesis.pdf
fonte
Waxman, Roteamento de conexões multiponto , IEEE J. Select. Áreas Commun. 6 (9), 1617-1622, 1988. Zegura, Calvert, Bhattacharjee, Como Modelar uma Internetwork , Proc. IEEE INFOCOM '96, 1996.
fonte
Walter Willinger construiu uma carreira no uso de gráficos sem escala para modelar redes. Há muito o que citar, por isso vou apontar para a entrada dele no DBLP . O ponto chave nesses modelos é que eles têm propriedades semelhantes às redes "reais" que não são capturadas por G (n, p).
fonte
Você pode conferir o livro de Durrett . Eu acredito que você tem muita leitura para fazer.
fonte
Em vez de encontrar laboriosamente, justificar e analisar um modelo específico, convém usar os dados da vida real que você possui (se houver). Isso significa definir um modelo probabilístico genérico e treinar seus parâmetros, considerando seus dados (por exemplo, por estimativa de probabilidade máxima).
Obviamente, a gramática específica pode (e deve!) Usar o conhecimento do domínio. Considere, por exemplo, gramáticas diferentes usadas para a previsão da estrutura secundária do RNA em Dowell, Eddy (2004) para um gosto.
Encontre alguns detalhes sobre essa técnica em Weinberg, Nebel (2010) . Não sei como (bem) isso pode ser aplicado a gráficos gerais.
Se você precisar de mais energia, poderá mudar para coisas como CFG multidimensional (S) (por exemplo , Seki, Kato (2008) ) ou SCFG dependente de comprimento / posição ( Weinberg, Nebel (2010) ).
fonte
Como você provavelmente sabe, parece haver uma diferença entre o gráfico de conectividade para a World Wide Web e se opôs ao gráfico de conectividade para a infraestrutura da Internet. Certamente não pretendo ser um especialista, mas vi o artigo de Li, Alderson, Tanaka, Doyle e Willinger "Para uma teoria de gráficos sem escala: definição, propriedades e implicações" que introduzem uma métrica 'medir a' liberdade de escala 'de um gráfico (com a definição de gráficos sem escala ainda em debate, tanto quanto eu sei) que afirmam ter um modelo de gráfico que cria gráficos que são semelhantes à conectividade da Internet em um roteador nível.
Aqui estão alguns modelos mais generativos que podem ser interessantes:
Artigo de Berger, Borgs, Chayes, D'Souza e Kleinberg "Acessório Preferencial Induzido pela Concorrência"
Tolerância altamente otimizada de Carlson e Doyle : um mecanismo para leis de energia em sistemas projetados
Um ponto crítico para gráficos aleatórios de Molloy e Reed com uma sequência de grau dado que introduz o "Modelo de configuração apagado"
Clustering de Newman e ligação preferencial em redes em crescimento (que já foi mencionado)
Também se pode gerar explicitamente uma distribuição de graus e criar um gráfico dessa maneira, mas não está claro para mim o quão próximo isso modela o gráfico da Internet no nível do roteador.
Obviamente, há muito mais literatura sobre o assunto e eu dei apenas alguns dos (o que considero) os destaques.
Espero que ajude.
fonte
Embora seja um tópico antigo, estou respondendo, pois muitas pessoas ainda visitam essas postagens. Estou motivado com um comentário em outra resposta.
O modelo Barabasi-Albert e outros modelos que produzem gráficos sem escala foram propostos para modelar a Internet no nível do roteador e no sistema autônomo. Embora inicialmente esses modelos fossem considerados precisos, descobrimos que não possuímos uma imagem completa da topologia da Internet devido a dificuldades em descobrir todos os links. Embora se acredite ser cauda pesada, é praticamente um trabalho em andamento.
Para sua referência, você pode ler: RG Clegg, C Di Cairano-Gilfedder, S Zhou, Um olhar crítico sobre a modelagem de leis de energia da Internet
fonte
Existem vários livros sobre gráficos aleatórios, como o Livro de Bollobás, e vários modelos de gráficos aleatórios, como o link da wikipedia do mundo pequeno ou o link preferencial da wikipedia , para modelar redes com pequenas distâncias entre computadores ou aqueles com distribuição de graus seguindo uma lei de energia. , respectivamente.
Acho que não há uma maneira fácil de modelar uma rede de computadores real, mas tenho certeza de que G (n, p) não a modelaria muito bem. A menos que você esteja trabalhando com uma rede organizada muito específica.
fonte
Minha recomendação é o trabalho de pesquisa escrito pelos inventores do gerador de gráficos aleatórios R-MAT. http://portal.acm.org/citation.cfm?id=1132954
O gerador de gráficos aleatórios R-MAT é muito simples e amplamente utilizado. Por exemplo, esse gerador é adotado no benchmark Graph500 ( http://www.graph500.org/ ).
fonte