Análise de rede

A análise de redes é a área de tecnologia da informação e das ciências sociais que trata do processo de analisar qualquer tipo de rede por meio da teoria das redes. As redes podem ser social, de transporte ou tecnológicas, como a internet.

A análise inclui descrições da estrutura, como redes de pequeno mundo, círculos sociais ou redes sem escala, otimização, como a Análise de Caminho Crítico e PERT (Program Evaluation & Review Technique), e propriedades como atribuição de fluxo.

A teoria de redes preocupa-se com o estudo dos grafos como uma representação de relações simétricas ou, mais geralmente, de relações assimétricas entre objetos discretos. Aplicações da teoria de redes incluem redes logísticas, a World Wide Web, Internet, redes reguladoras de genes, redes metabólicas, redes sociais, redes epistemológicas, etc.

Optimização de redes

Problemas de redes que envolvem encontrar uma forma ideal para fazer algo são estudados sob o nome de otimização combinatória. Os exemplos incluem fluxo de redes, problemas de caminho crítico, problema de transporte, problema de alteração, problema de localização, problema de correspondência, problema de atribuição, de roteamento, análise do caminho crítico e PERT.

Análise de redes

A análise de rede - assim como sua prima próxima, análise de tráfego -, tem uso significativo em atividades de inteligência. Ao monitorizar os padrões de comunicação entre os nós de uma rede, pode-se estabelecer sua estrutura. Isto pode ser usado para rastrear redes insurgentes de natureza tanto hierárquica quando descentralizada.

Análise de redes sociais

A análise de redes sociais mapeia relacionamentos entre indivíduos numa rede social. Examina a estrutura das relações entre entidades sociais.^[1] Essas entidades são, muitas vezes pessoas, mas também podem ser grupos, organizações, nações, websites, publicações académicas.

Desde os anos 70, o estudo empírico das redes tem desempenhado um papel central na ciência social, e muitas das ferramentas Matemática e estatísticas usadas para estudar as redes foram primeiro desenvolvidas na Sociologia.^[2] Entre muitas outras aplicações, a análise de redes sociais tem sido usada para entender a difusão das inovações, notícias e rumores. Similarmente, tem sido usada para examinar a propagação das doenças e comportamentos relacionados com saúde. Também tem sido aplicada no estudo dos mercados, onde tem sido usada para examinar o papel da confiança nas relações de troca e de mecanismos sociais na fixação de preços. Do mesmo modo, tem sido utilizada para estudar o recrutamento dentro dos movimentos políticos e organizações sociais. Também tem sido usada para conceptualizar divergências científicas bem como prestígio académico.

Análise de redes biológicas

O tipo de análise neste contexto está intimamente relacionado com a análise de rede social, mas foca-se frequentemente em padrões locais na rede. Por exemplo motivos de rede são pequenos subgrafos pequenos que estão sobre-representados na rede. Da mesma forma, motivos de atividade são padrões nos atributos de nós e arestas na rede que estão sobre-representadas dada a estrutura da rede.

Análise de ligações

A análise de ligações (ou de links) é um subsetor da análise de rede que explora associações entre objetos. Um exemplo pode ser quando a polícia examina os endereços de suspeitos e vítimas, os números de telefone que discaram e as transações financeiras que realizaram num determinado período de tempo, e as relações familiares entre estas pessoas. A análise de link (ou ligação) neste caso fornece as relações e associações cruciais entre vários objetos de diferentes tipos que não estão aparentes de pedaços isolados de informação. A análise de links assistida por computador ou totalmente automatizada é cada vez mais empregada por bancos e empresas de segurança de dados para detecção de fraudes, por operadoras de telecomunicação em análise de redes de comunicação, pelo setor médico em estudos de epidemiologia e farmacologia, na segurança pública e em investigações policiais, por mecanismos de busca para taxa de relevância (e, no sentido oposto, por spammers para spamdexação) e por empresários para otimização em retornos de sites de busca, além de todo lugar onde relacionamentos entre pessoas e objetos possam ser analisados.

Robustez de redes

A robustez estrutural das redes^[3] é estuda usando a teoria de percolação. Quando uma fração crítica de nós (ou ligações) é removida, a rede fica fragmentada em pequenos grupos desconexos. Este fenómeno é chamado de percolação^[4] e representa um tipo de fase de transição ordem-desordem com expoentes críticos.

Análise de ligação web

Vários algoritmos de ranking de pesquisa na web usam ligações baseadas em métricas de centralidade, incluindo o PageRank do Google, o algoritmo HITS da Kleinberg, o CheiRank e algoritmos TrustRank. A análise de ligação também é realizada na ciência da informação e ciência da comunicação a fim de entender e extrair informações a partir da estrutura de coleções de páginas da web. Por exemplo, a análise pode ser da interligação entre os sites políticos ou blogs. Outra utilização é para a classificação de páginas de acordo com a sua menção em outras páginas.^[5]

Medições de centralidade

A informação sobre a relativa importância dos nós e arestas num gráfico pode ser obtida por meio de medições de centralidade. Por exemplo, centralidade eigenvetorial usa os eigenvetores da matriz de adjacência para determinar nós que tendem a ser freqüentemente visitados. Um exemplo é o algoritmo de ranking de páginas usados pelo Google. O principal eigenvetor da matriz de adjacência modificada pela representação gráfica da WWW dá o ranking de páginas como seus componentes.A finalidade ou objectivo da análise determina geralmente o tipo de medida de centralidade a ser usado. Por exemplo, se alguém está interessado em dinâmica nas redes ou na robustez de uma rede para remoção do nó/ligação, muitas vezes a importância da dinâmica^[6] de um nó é a medida de centralidade mais relevante.

Mistura associativa e dissociativa

Estes conceitos foram feitos por causa da natureza de hubs numa rede. Geralmente chamam-se Hubs aos nós que têm muitas ligações. Se virmos uma ligação no hub, não há diferença entre os hubs, no entanto, algumas diferenças estão encerradas entre esses nós. Alguns hubs tendem a ligar a outros nós e outros hubs evitando ligar a outros nós. Dizemos que um hub é associativo quando tende para outros hubs. O oposto é o hub dissociativo, que evita ligar-se a outros hubs. Se alguns nós têm algumas ligações com as probabilidade aleatórias esperadas, os hubs são neutros. Existem três métodos para quantificar as correlações de grau.

Processos de propagação

O conteúdo numa rede complexa pode-se propagar através de dois métodos principais: propagação conservada e propagação não conservada.^[7] Na propagação conservada, a totalidade de conteúdo que entra numa rede complexa permanece constante enquanto passa por ela. O modelo de propagação conservada pode ser melhor representado por um jarro contendo uma quantidade fixa de água sendo derramada numa série de funis ligados por tubos. Aqui, o jarro representa a fonte original e a água é o conteúdo sendo propagado. Os funis e os tubos de ligação representam os nós e as conexões entre eles, respetivamente. Enquanto a água passa de um funil para outro, desaparece instantaneamente do funil que foi anteriormente exposto à água. Na propagação não conservada, a quantidade de conteúdo altera-se à medida que entra e passa através da rede complexa. O modelo de propagação não conservada pode ser melhor representado por uma torneira a correr continuamente através de uma série de funis ligados por tubos. Aqui, a quantidade de água da fonte original é infinita. Também, quaisquer funis que tenham sido expostos à água, continuam a sentir a água, mesmo quando passa por funis sucessivos. O modelo não conservado é o mais adequado para explicar a transmissão das doenças mais infeciosas, excitação neural, informações e rumores, etc.

Redes interdependentes

Redes interdependentes são um sistema de redes acopladas onde os nós de uma ou mais redes dependem de nós de outras redes. Essas dependências são reforçadas pelos desenvolvimentos da tecnologia moderna. Dependências podem conduzir a falhas em cascata entre redes e uma falha relativamente pequena pode conduzir a um colapso catastrófico do sistema. Apagões são uma demostração fascinante papel importante desempenhado pelas dependências entre as redes. Um estudo recente desenvolveu uma estrutura para estudar as falhas em cascata num sistema de redes interdependente.^[8][9]

Redes Complexas

Nas últimas décadas, surgiu um novo campo de estudo focado nas redes complexas. Essas redes são caracterizadas por estruturas irregulares e dinâmicas que mudam com o tempo. Ao contrário de grafos simples e aleatórios, redes complexas possuem propriedades únicas e padrões de conexão mais sofisticados. Embora apresentem características irregulares, elas não são totalmente aleatórias, pois seguem certos padrões de conexão entre seus componentes. Essas características são comuns em redes reais, como redes sociais e sistemas biológicos.

Estruturas complexas

descrevem uma enorme quantidade de sistemas que recentemente tem instigado os cientistas a investigarem mecanismos que determinem a sua topologia. Podemos citar alguns exemplos como:

1. Redes Sociais: Conexões entre usuários em plataformas online.
2. Redes de Transporte: Infraestruturas de transporte urbano e suas rotas.
3. Redes de Comunicação: A arquitetura da internet e a transmissão de dados.
4. Redes Biológicas: Interações entre proteínas e genes em organismos.
5. Redes de Coautoria Científica: Colaborações entre pesquisadores em publicações acadêmicas.

Esses sistemas revelam padrões e características que não são evidentes em redes simples ou aleatórias.

(a) Cadeia Alimentar do lago Little Rock, Wisconsin (Figura fornecida por Neo D. Martinez)

(b) Rede social mostrando a comunicação de email entre 436 funcionários do Laboratorio de Pesquisa da Hewlett Packard

Redes reais possuem estruturas complexas, com partes variando em densidade de conexões. Algumas redes têm um núcleo central com muitas conexões, enquanto outras são divididas em regiões fortemente conectadas. A compreensão da estrutura de uma rede é crucial para entender seu funcionamento, como a dispersão de informações em redes sociais ou a estabilidade de redes de energia. O próximo passo é explorar os principais modelos de redes complexas estudados para analisar essas características.

Redes Aleatórias

Em 1959, Paul Erdős e Alfred Rényi criaram o modelo Erdős-Rényi para redes complexas. Nesse modelo, uma rede é formada com ${\displaystyle n}$ vértices e cada par de vértices tem uma probabilidade ${\displaystyle p}$ de ser conectado por uma aresta. A estrutura da rede é determinada aleatoriamente com base nessa probabilidade. A relação entre o número total de vértices ${\displaystyle n}$ e o número de arestas ${\displaystyle m}$ é dada por ${\displaystyle m=p.{\frac {n(n-1)}{2}}}$

${\displaystyle {\frac {n(n-1)}{2}}}$ indica o número máximo de ligações.

Embora Erdős e Rényi tenham se concentrado principalmente nos aspectos matemáticos do problema, e não em suas aplicações práticas em sistemas reais, o modelo que desenvolveram consegue ilustrar diversas redes existentes no mundo, como rodovias e ferrovias.

Modelo Watts-Strogatz

Em 1967, o psicólogo Stanley Milgram realizou um experimento para descobrir quantos conhecidos separam duas pessoas escolhidas aleatoriamente. Ele recrutou 160 voluntários que deveriam enviar uma carta a uma pessoa alvo. Se não conhecessem a pessoa, deveriam repassar a carta a um conhecido. No final, 42 cartas chegaram ao destino, indicando que o grau médio de separação é de seis pessoas. Essa propriedade ficou conhecida como “mundo pequeno”.

Observando que muitas redes reais estão entre a regularidade e a aleatoriedade, os pesquisadores Duncan Watts e Steven Strogatz criaram um modelo mais sofisticado para representar esse padrão e incluir a propriedade de “mundo pequeno”. Como funciona:

Rede Inicial: Começa-se com uma rede regular, onde cada nó (ou vértice) está conectado a seus vizinhos mais próximos de forma ordenada.

Reconexão Aleatória: Em seguida, algumas conexões são aleatoriamente reconectadas. Isso significa que alguns nós que estavam conectados a vizinhos próximos agora se conectam a nós distantes.

Propriedade de Mundo Pequeno: Esse processo cria uma rede que ainda mantém a estrutura local (regularidade), mas também possui algumas conexões de longa distância (aleatoriedade). Isso resulta em um pequeno número de passos necessários para conectar qualquer dois nós na rede, refletindo a ideia de “seis graus de separação”.

Aplicações: Esse modelo ajuda a entender como informações, doenças ou tendências podem se espalhar rapidamente em redes sociais, sistemas biológicos e até mesmo na internet.

Figura 2: O modelo Watts-Strogatz interpola entre uma rede regular e aleatória, sem alterar o número de nós ou arestas. O exemplo acima ilustra um grafo com n=20 vértices, cada um deles ligado aos k=4 vizinhos mais próximos.

Estrutura Regular: Começamos com um grafo onde cada um dos ${\displaystyle n}$ vértices está conectado a ${\displaystyle k}$ vizinhos. Para garantir que a rede seja esparsa e conectada, consideramos ${\displaystyle (n>k>ln(n)>1)}$.

Aleatorização: Com uma probabilidade ${\displaystyle p}$, cada aresta é reconectada (evitando conexões de um vértice a si mesmo e arestas duplicadas). Se ${\displaystyle p=1}$, todas as arestas são reconectadas, resultando em um comportamento semelhante ao de redes aleatórias. Se ${\displaystyle p=0}$, mantemos um grafo regular com caminhos mais longos.

Modelo Barabási-Albert

O modelo de redes de livre escala de Barabási-Albert explica como surgem os hubs, ou nós altamente conectados, em redes como a World Wide Web. Ele se baseia em duas ideias principais:

Crescimento: A rede aumenta com o tempo, com novos nós se conectando aos já existentes.

Ligação Preferencial: Nós com mais conexões têm maior probabilidade de receber novas conexões, o que significa que os “populares” ficam ainda mais conectados.

Esses princípios ajudam a entender por que algumas redes têm uma distribuição de conexões que segue uma lei de potência, com poucos nós muito conectados e muitos nós com poucas conexões.

Figura 3: Exemplo de power-law, onde uma quantidade varia como potência da outra quantidade.

O modelo Barabási-Albert é construído a partir de ${\displaystyle n_{\circ }}$ vértices inicialmente conectados por ${\displaystyle m_{\circ }}$ arestas. O algoritmo segue duas premissas principais:

Crescimento: A cada instante de tempo, um novo vértice é adicionado ao grafo que se conecta a outros ${\displaystyle m(m<n_{0})}$ vértices já existentes.

Ligação Preferencial: A probabilidade de um novo vértice escolher um determinado nó para conexão é proporcional ao número de arestas que esse nó possui. Assim, os novos nós tendem a se ligar aos nós com mais conexões. A probabilidade ( P ) de um novo vértice se conectar a um nó ${\displaystyle i}$ depende do seu grau ${\displaystyle k_{i}}$, conforme a equação: ${\displaystyle p(i)={\frac {ki}{\textstyle \sum _{j}kj\displaystyle }}}$

Após ${\displaystyle t}$ instantes de tempo, a rede resultante terá ${\displaystyle N=n_{0}+t}$ vértices e ${\displaystyle M=m_{0}+(m\cdot t)}$ arestas. A figura 4 ilustra um exemplo de rede inicialmente com ${\displaystyle n_{0}=3}$ vértices e ${\displaystyle m_{0}=3}$ arestas, onde cada novo vértice se liga a ${\displaystyle m=2}$ vértices. Nota-se claramente a preferência de conexão com os nós mais antigos e de maior grau, permitindo o surgimento de hubs.

Figura 4: Construção do modelo Barabasi-Albert.Se ligar aos nós mais conectados. Os novos vértices preferem devido as propriedades de crescimento e ligação preferencial podemos perceber o surgimento de hubs.

Entre as variações do modelo Barabási-Albert, destacam-se as redes onde novas conexões podem surgir durante o crescimento da rede, permitindo a formação de conexões internas entre nós antigos. Outra característica observada em sistemas reais, mas ausente nas redes de livre escala, é a possibilidade de alguns nós e arestas desaparecerem ao longo do tempo. Por exemplo, em redes sociais, um relacionamento pode não ser permanente.

Conexões internas, reconexões, remoção de nós e arestas, envelhecimento (“aging”), efeitos não-lineares, entre outras propriedades, são características que influenciam a evolução e o crescimento da rede, alterando a quantidade e o tamanho dos hubs. Diversos modelos são desenvolvidos com o objetivo de replicar as diferentes topologias observadas em redes reais.

Implementações

• Igraph Igraph, uma biblioteca de fonte aberta C para a análise de redes complexas de grande escala, com interfaces para R, Python e Ruby.
• Graph-tool e NetworkX, gratuitos e eficientes módulos Python para manipulação e análise estatística de redes.^[2]
• Orange, software gratuito de data mining, módulo orngNetwork.
• Pajek Pajek programa para (grande) análise de rede e visualização.
• Tulip, data mining gratuito e software de visualização dedicado à análise e visualização de dados relacionais.

Ver também

• Comunicação
• Teoria da informação
• Mineração de dados
• NTICs

Referências

1. Wasserman, Stanley and Katherine Faust. 1994. Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press.
2. Newman, M.E.J. Networks: An Introduction. Oxford University Press. 2010
3. R. Cohen, S. Havlin (2010). Complex Networks: Structure, Robustness and Function. [S.l.]: Cambridge University Press 
4. A. Bunde, S. Havlin (1996). Fractals and Disordered Systems. [S.l.]: Springer 
5. Attardi, G.; S. Di Marco, D. Salvi (1998). «Categorization by Context» (PDF). Journal of Universal Computer Science. 4 (9): 719–736  A referência emprega parâmetros obsoletos |coautor= (ajuda)
6. Restrepo, Juan, E. Ott, B. R. Hunt (2006). «Characterizing the Dynamical Importance of Network Nodes and Links». Phys. Rev. Lett. 97. 094102 páginas. doi:10.1103/PhysRevLett.97.094102 
7. Newman, M., Barabási, A.-L., Watts, D.J. [eds.] (2006) The Structure and Dynamics of Networks. Princeton, N.J.: Princeton University Press.
8. S. V. Buldyrev, R. Parshani, G. Paul, H. E. Stanley, S. Havlin (2010). «Catastrophic cascade of failures in interdependent networks». Nature. 464 (7291): 1025–28. doi:10.1038/nature08932  !CS1 manut: Nomes múltiplos: lista de autores (link)
9. Jianxi Gao, Sergey V. Buldyrev3, Shlomo Havlin4, and H. Eugene Stanley (2011). «Robustness of a Network of Networks». Phys. Rev. Lett. 107. 195701 páginas. doi:10.1103/PhysRevLett.107.195701 

Ligações externas

• netwiki Scientific wiki dedicated to network theory
• New Network Theory Conferência Internacional 'New Network Theory'
• Network Workbench: Análise de Redes de grande escala,ferramenta de modelação e visualização
• Network analysis of computer networks
• Network analysis of organizational networks
• Network analysis of terrorist networks
• Network analysis of a disease outbreak
• Link Analysis: An Information Science Approach (Livro)
• Connected: The Power of Six Degrees (Documento)
• Influential Spreaders in Networks, M. Kitsak, L. K. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H. E. Stanley, H.A. Makse, Nature Physics 6, 888 (2010)
• A short course on complex networks
• A course on complex network analysis by Albert-László Barabási
• Algoritmo Multinvel de Deteccao de Comunidades em Redes Complexas, Steven Koiti Tsukamoto

Livros

• E. Estrada, "The Structure of Complex Networks: Theory and Applications", Oxford University Press, 2011, ISBN 978-0-199-59175-6