INTRODUC¸AO˜ AS REDES COMPLEXAS-Tiago sousa alves RA:13566

INTRODUC¸AO˜ AS REDES COMPLEXAS ` Por Aline D. Bessa, Leonardo B. L. Santos∗ , Lorena P. N. R. Martinez, Mariana C. Costa e Pedro G. S. Cardoso Alunos do grupo de F´ısica Estat´ıstica e Sistemas Complexos (FESC) da Universidade Federal da Bahia 23 de Dezembro de 2010 1 Apresenta¸c˜ao Ao se conhecer a Teoria de Redes Complexas (TRC) passamos a notar sua extensa aplicabilidade. As estradas que conectam cidades, as rela¸c˜oes de amizade entre pessoas, as interliga¸c˜oes entre p´aginas da internet, esses e muitos outros s˜ao exemplos do cotidiano em que podemos enxergar a id´eia b´asica que norteia a constru¸c˜ao de uma rede complexa. O conjunto de ´areas do conhecimento que se utilizam da Teoria de Redes Complexas ´e grande e heterogˆeneo. H´a pesquisas envolvendo redes complexas em um leque de campos que vai de Artes a Zoologia, passando por Ling¨u´ıstica e Psicologia. Al´em de ser particularmente interessante como ciˆencia pura, o conhecimento sobre Redes Complexas proporciona uma excelente metodologia `as quest˜oes aplicadas. O curioso ´e que, apesar de haver uma enorme contribui¸c˜ao dos pesquisadores brasileiros em aplica¸c˜oes de redes complexas, pouca aten¸c˜ao ´e destinada `a teoria, gerando uma lacuna de publica¸c˜oes neste sentido. Diante deste panorama, o presente trabalho se prop˜oe a apresentar a TRC n˜ao apenas em n´ıvel de divulga¸c˜ao mas tamb´em como uma introdu¸c˜ao aos leitores interessados em geral. Este conteudo sob este formato ser´a disponibilizado apenas pela Internet, para download livre (do arquivo no formato pdf e LaTeX)1 . Com votos de proveitosa leitura; Os autores. ∗e-mail: santoslbl@gmail.com 1Dispon´ıvel no reposit´orio 4Shared. 1 2 Conceitos Preliminares Nesta se¸c˜ao, apresentaremos alguns fundamentos das Teorias de Grafos, F´ısica Estat´ıstica e Sistemas Complexos. 2.1 Introdu¸c˜ao `a Teoria dos Grafos Um grafo ´e um par G = (V, E) de conjuntos tal que os elementos de V s˜ao seus v´ertices e os elementos de E, suas arestas. Neste livro, consideraremos apenas grafos para os quais a cardinalidade de V e a de E s˜ao finitas. Grafos costumam ser representados visualmente da seguinte forma: cada v´ertice ´e indicado por um ponto e cada aresta ´e indicada por uma linha conectando dois pontos. Figura 1: Exemplo de um grafo Um v´ertice v ´e incidente a uma aresta e se v ∈ e. Dois v´ertices s˜ao ditos adjacentes se eles s˜ao incidentes a uma mesma aresta. Para cada v´ertice i ∈ V ´e poss´ıvel, portanto, determinar o conjunto Ai ⊆ V de seus v´ertices adjacentes de acordo com a seguinte equa¸c˜ao: Ai = {j ∈ V |{i, j} ∈ E} (1) Existem algumas defini¸c˜oes simples que s˜ao muito importantes para a Teoria dos Grafos. Enumeraremos algumas delas: • Um grafo ´e dito ponderado quando se associa um valor (normalmente, um n´umero real) a cada uma de suas arestas. Este valor ´e denominado comumente de peso da aresta. O grafo representado na Figura 1, por exemplo, n˜ao ´e ponderado: n˜ao h´a nenhum valor associado a suas arestas2 . • Um la¸co ´e uma aresta que conecta um v´ertice a si mesmo. Na figura acima, h´a um la¸co envolvendo o v´ertice 11. 2Em determinados casos, ´e conveniente assumir que todas as arestas possuem peso igual a um ou zero. 2 • Um grafo possui arestas m´ultiplas quando h´a pelo menos duas arestas incidentes a um mesmo par de v´ertices. Neste caso, o grafo ´e considerado um multigrafo. As trˆes arestas que incidem nos v´ertices 6 e 8 da Figura 1 indicam que o grafo em quest˜ao ´e um multigrafo. • Um grafo ´e dito ser desconexo se h´a pelo menos um par de v´ertices para o qual, partindo de um deles e atravessando qualquer sequˆencia finita de arestas, n˜ao ´e poss´ıvel atingir o outro. Caso esta propriedade n˜ao valha para nenhum par de v´ertices no grafo, ele ´e conexo. Cada subgrafo conexo de um grafo ´e dito ser uma componente. O grafo representado na Figura 1 ´e desconexo e possui trˆes componentes. Um grafo ´e simples quando n˜ao ´e um multigrafo, n˜ao ´e ponderado e n˜ao possui la¸cos. O grafo representado acima, por exemplo, n˜ao ´e simples. No decorrer deste artigo, por uma quest˜ao de simplicidade, manteremos o enfoque apenas em grafos simples. Por fim, introduziremos o conceito de isomorfismo entre grafos; dois grafos G(V, E) e G0 (V 0 , E0 ) s˜ao isomorfos se e somente for poss´ıvel obter um a partir do outro apenas via renumera¸c˜ao de seus v´ertices. Mais formalmente, G(V, E) e G0 (V 0 , E0 ) s˜ao isomorfos se e somente se existir uma fun¸c˜ao bijetora (isomorfismo) entre V e V 0 que preserve as rela¸c˜oes de adjacˆencia de G e G0 . Uma rede ´e um grafo utilizado para a representa¸c˜ao de um sistema complexo, tipo de sistema que ser´a definido ainda nesta se¸c˜ao. Por este motivo, no corpo deste artigo, todas as defini¸c˜oes que se aplicam a grafos ser˜ao, com igual naturalidade, aplicadas a redes. 2.2 Sobre F´ısica Estat´ıstica Em oposi¸c˜ao `a vis˜ao inerentemente macrosc´opica da termodinˆamica, a F´ısica Estat´ıstica trata seus sistemas sob uma perspectiva reducionista, procurando, por equa¸c˜oes matem´aticas capazes de descrever comportamentos microsc´opicos, e via operadores de m´edias (no dom´ınio do tempo, espa¸co ou freq¨uˆencia), recuperar a fenomenologia macrosc´opica. Como exemplo, temos o conceito de temperatura, tomado na F´ısica Estat´ıstica como mensura¸c˜ao do grau de agita¸c˜ao (energia cin´etica) dos constituintes (microsc´opicos) do sistema (macrosc´opico). A F´ısica Estat´ıstica est´a fortemente presente nos fundamentos da Teoria das Redes Complexas uma vez que, por exemplo, diversas caracter´ısticas dinˆamicas (macrosc´opicas) de uma rede podem ser descritas tomando como base grandezas b´asicas, como a sua distribui¸c˜ao de graus (microsc´opica). 2.3 Sobre Sistemas Complexos A Teoria de Sistemas Complexos surge no final do s´eculo XX se propondo a tratar de sistemas com algumas caracter´ısticas especiais: 3 • grande n´umero de constituintes que interagem muitas vezes de forma n˜aolinear e se relacionam com o meio - tanto influenciando quanto por ele sendo influenciado; • invariˆancia por escala, ou seja, a presen¸ca de padr˜oes auto-similares (geometria fractal) e/ou auto-afins, e distribui¸c˜oes (de freq¨uˆencia e/ou energia) obedecendo a leis de potˆencia (criticalidade auto-organizada); • exibi¸c˜ao de propriedades coletivas - logo, dividir o sistema em partes menores para tentar analis´a-lo melhor, em alguns casos, n˜ao ´e apropriado. A Teoria de Redes Complexas ´e, hoje, amplamente aplicada tanto `a caracteriza¸c˜ao quanto `a modelagem matem´atica de Sistemas Complexos. Modelagem, no contexto deste artigo, deve ser entendido como o processo de simplifica¸c˜ao de uma realidade f´ısica, marcado pelo equil´ıbrio entre confiabilidade e operacionalidade. Um modelo deve apresentar o m´aximo de caracter´ısticas do sistema original, mas n˜ao pode inviabilizar o estudo eficiente de suas propriedades - quer seja analiticamente, quer seja computacionalmente. Com o desenvolvimento das ferramentas computacionais e a vis´ıvel ruptura dos limites disciplinares, a Teoria dos Grafos passou a ser cada vez mais utilizada na modelagem de diversos Sistemas Complexos. Isto se deu no in´ıcio de uma ´epoca de s´ıntese do conhecimento cient´ıfico, ressaltando diversas interconex˜oes entre as mais distintas ´areas. A medida que a complexidade dos sistemas modelados ` crescia (n´umero muito grande de constituintes - v´ertices, e intera¸c˜oes - arestas), tornou-se usual utilizar ferramentas da F´ısica Estat´ıstica, como invariˆancia de escala e auto-similaridade, no estudo dos modelos.