Grafos são utilizados para modelar redes em diversos campos cientíticos. Ao longo dos anos, o interesse em modelar redes do mundo real vem crescendo, com aplicações em diferentes áreas, como biologia molecular (redes genéticas regulatórias, redes de interação proteína- proteína), neurociência (rede funcional cerebral)e ciências sociais (redes sociais como facebook, instagram, foursquare). As redes do mundo real não podem ser modeladas por grafos determinístico adequadamente, pois tais grafos não apresentam componente aleatório dese- jável nestas situações. Além disso, algoritmos tradicionais e abordagem clássicas para grafos apresentam dificuldades e limitações que prejudicam tais análises. Com isso, grafos aleatórios são mais indicados para modelar as redes do mundo real e procedimentos estatísticos precisam ser formalizados com o intuito de facilitar a análise de dados destes grafos, como por exemplo: como comparar dois grafos reais? Uma abordagem tradicional seria verificar o isomorfismo entre gráficos, no entanto, tal abordagem apresenta alguns problemas, como, por exemplo, o custo computacional é alto (não existe algoritmo polinomial) e não considera a flutuação intrínseca presente em processos que modelam eventos do mundo real. Portanto, uma solução é considerar que os grafos reais são gerados por por processos probabilísti- cos (modelo de grafo aleatório) e testar se os grafos foram gerados pelo mesmo modelo e conjunto de parâmetros. Neste trabalho revisaremos os modelos de grafos aleatórios e suas aplicações na modelagem de redes do mundo real, bem como a teoria espectral para grafos e diversos resultados, medidas derivadas do seu estudo e trabalhos recentes que utilizam métodos baseados em medidas espectrais para seleção do modelo em conjuntos de grafos. Finalmente, introduzimos abordagens paramétricas para testar a igualdade entre dois ou mais grafos aleatórios desde que sejam grandes o suficiente. Primeiro é proposto uma generalização de teste de razão de verossimilhança (likelihood ratio test - LRT), a seguir o teste t (t student) é generalizado para grafos e finalmente, a análise de variância (ANOVA) é desenvolvida para testar a igualdade de dois ou mais grafos. Os testes desenvolvidos utilizam medidas baseadas no espectro do grafo, como a entropia espectral e a divergência de Kullback-Leibler no estimador dos parâmetros do modelo. Para estimar a variância, é usado um bootstrap paramétrico. O poder do teste é ilustrado com uso de curvas ROC e a i ii utilidade do método é demonstrada através de sua aplicação na comparação de redes reais de interação proteína-proteína em seis espécies.

Graphs are used to model networks in various scientific fields. The interest to model real world data as graphs (networks) is increasing over the years. Several examples can be found with applications in different areas such as molecular biology (gene regulatory networks, protein-protein interaction networks), neuroscience (functional brain networks), and social science (social networks like facebook, instagram, foursquare). Different of deterministic graphs, real world graphs present a random component, which makes their analysis difficult by traditional computer science algorithms. In addition, traditional algorithms and classical approach to graphs present difficulties and limitations that undermine such analysis. Clas- sical approaches do not handle intrinsic randomness. Thus, formal statistical procedures for graphs become necessary. Therefore, random graphs are better suited to model real world networks. In this context, one simple question is: how to compare two (or more) real graphs? A traditional solution would be to verify the isomorphism. However, this approach presents at least two problems: (i) there is no polynomial algorithm to verify isomorphism between graphs|and (ii) it does not take into account the intrinsic fluctuation present in real world graphs. Therefore, one solution is to imagine that these natural graphs are generated by random processes (models) and test if the graphs are generated by the same model and set of parameters. We present a solution for this problem by proposing generalizations of a likelihood ratio test, a t-test, and an analysis of variance for graphs. We demonstrate their performance in Monte Carlo simulations and illustrate their application in protein-protein interaction networks.