Modelos de gráficos aleatórios, para redes de computadores reais

19

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 é?).G(n,p)np

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.)G(n,p)

Kaveh
fonte
2
Onde você precisa desses modelos - é apenas para gerar algumas entradas de teste para algoritmos ou deseja analisar os modelos para aprender algo sobre redes de computadores? Em que tipo de redes de computadores você está interessado; qual é a sua escala (LAN x Internet)? Por que você supõe que as redes de computadores reais são geradas por um processo aleatório - surpreendentemente, as redes do mundo real são realmente projetadas por um engenheiro, com pouco lançamento de moedas?
Jukka Suomela
@Jukka, estou tentando ver se posso aplicar as técnicas desenvolvidas para a esses modelos aleatórios para obter informações sobre as redes reais, não gosto de ser mais específico agora, porque isso pode dar longe o problema que estou pensando :). Estou interessado principalmente na camada IP da Internet. Eu já vi pessoas usarem gráficos aleatórios para analisar os gráficos resultantes das redes sociais. Não sei por que essas redes reais compartilham propriedades com gráficos aleatórios; pode haver um processo aleatório oculto atrás da superfície no trabalho (parece uma pergunta interessante a ser feita :). G(n,p)
Kaveh
Acho que parte do interesse em usar os modelos aleatórios é que analisá-los é mais fácil do que analisar redes reais; portanto, é razoável considerá-los se eles são suficientemente bons para aproximar o real.
Kaveh
Obrigado a todos por boas respostas. (Agora eu tenho que passou algum tempo lendo esses papéis :).
Kaveh

Respostas:

10

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.nn

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:

  • Sobre a distribuição de graus de gráficos planares aleatórios . Konstantinos Panagiotou e Angelika Steger . Aparecer nos Anais do 22º Simpósio Anual da ACM-SIAM sobre Algoritmos Discretos (SODA '11).
  • Sobre propriedades de dissecções aleatórias e triangulações . Nicla Bernasconi, Konstantinos Panagiotou e Angelika Steger . Em Anais do 19º Simpósio Anual da ACM-SIAM sobre Algoritmos Discretos (SODA '08), p. 132-141. [http://www.mpi-inf.mpg.de/~kpanagio/Dissections.pdf]
  • Nas seqüências de graus dos gráficos externo-planar e paralelo em série . Nicla Bernasconi, Konstantinos Panagiotou e Angelika Steger . Em Anais do 12º Workshop Internacional de Técnicas Aleatórias em Computação (RANDOM'08), p. 303-316. [http://www.mpi-inf.mpg.de/~kpanagio/OPSP.pdf]
Máx.
fonte
11
Um comentário adicional: essa linha de pesquisa remonta a cerca de 15 anos, pelo menos a um artigo de Denise, Vasconcellos e Welsh (1996), e uma das razões pelas quais ela "ganhou força" agora é o grande sucesso da aplicação de combinatória analítica e enumeração assintótica aqui, por exemplo, por Gimenez e Noy (2009).
RJK 29/04
10

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)

Mohammad Al-Turkistany
fonte
11
apenas curioso: isso é para redes "sociais" versus a internet?
Suresh Venkat
Em segundo lugar: as abordagens às redes sociais devem ser altamente úteis, uma vez que grande parte do estudo dessas redes era originalmente focada em propriedades "universais" das redes e incluía topologia neural, rede elétrica e redes rodoviárias. Além disso, as redes Barabasi-Albert e Watts-Strogatz, cada uma com propriedades que as redes reais têm e as negligências de Erdos-renyi, são muito, muito, muito bem estudadas.
Elliot JJ -
11
@Suresh, essas redes complexas abordadas em ambas as referências incluem redes de computadores como a Internet e redes sociais.
Mohammad Al-Turkistany
8

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

Peter Boothe
fonte
Estou interessado principalmente em redes físicas (por exemplo, camada IP). Obrigado pelo link, vou verificar.
Kaveh
2
A camada IP não é a camada física. O MPLS e outras tecnologias de comutação de circuitos quebram essa suposição. A camada física são os fios. Temos até links multi-wire que parecem ser únicos saltos ethernet! Essa questão de "qual camada" é mais profunda do que a primeira inspeção pode sugerir e requer uma reflexão cuidadosa. Sugiro que você pense nas propriedades que deseja que uma rede tenha, encontre a camada em que a análise de topologia o ajudará melhor a analisar essa propriedade e espero que os dados estejam disponíveis.
precisa
5

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).

Suresh Venkat
fonte
5

Você pode conferir o livro de Durrett . Eu acredito que você tem muita leitura para fazer.

RJK
fonte
5

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).

Sp1:(S)Sp2:εp1,p2

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) ).

Rafael
fonte
11
isso é legal, mas a natureza livre de contexto do SCFG força o aluno a negligenciar certa estrutura global que as redes em seu conjunto de treinamento podem ter?
Artem Kaznatcheev
Bem, sim, recursos que não são livres de contexto são perdidos. Mas observe que propriedades como graus (médios) de nós podem ser capturadas. Para mais, veja minha edição.
Raphael
Obrigado! Vou dar uma olhada mais de perto. Os MDPs ocultos não podem capturar propriedades como o grau médio? Parece que algo que uma linguagem comum deve ser capaz de capturar, ou estou confuso? (Além disso, um ponto secundário: o link Weinberg, Nebel possui um caractere final que o mata, é óbvio o link que você pretendia, mas se você fizer mais edições, poderá valer a pena corrigi-lo).
Artem Kaznatcheev
Claro, eu só queria ressaltar que você pode cobrir algumas características globais usando esse modelo. O REG também pode cobrir alguns, mas falhará ao modelar estruturas inerentemente não regulares. (obrigado, corrigido)
Raphael
3

G(n,p)G(n,m)

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.

G(n,p)G(n,m)) não funcionam precisamente porque o diploma de lei de potência ou sem escala distribuiu gráficos aleatórios divergindo o segundo momento na distribuição de graus. Não pretendo saber o suficiente sobre o assunto para reivindicar categoricamente a "maioria" de provas, mas pelo que vi, uma das primeiras linhas de provas de propriedades nos gráficos aleatórios Erdos-Renyi assume explicitamente uma definição finita. segundo momento na distribuição de graus. Do meu ponto de vista, isso faz sentido, pois um segundo momento finito torna os gráficos de Erdos-Renyi muito mais parecidos com árvores localmente (consulte Informações, física e computação de Mertens e Montanari.) que efetivamente concede independência às propriedades / caminhos / estruturas. Como os gráficos aleatórios distribuídos pelo grau de direito do poder têm um segundo momento divergente, essa estrutura local em forma de árvore é destruída (e, portanto, requer diferentes técnicas de prova?). Eu ficaria feliz em ter essa intuição invalidada se alguém com mais conhecimento ou discernimento demonstrasse por que não é assim.

Espero que ajude.

user834
fonte
3

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

Vasilis
fonte
2

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.

dpufrj
fonte