Ciência das redes
Ciência das redes é um campo académico interdisciplinar que estuda redes complexas tais como redes de telecomunicações, redes de computadores, redes biológicas, redes cognitivas, redes semânticas e redes sociais. É baseado em um grupo de teorias e métodos, incluindo teoria dos grafos da matemática, mecânica estatística da física, mineração de dados, visualização de informação da ciência da computação, modelagem inferencial da estatística, e estrutura social da sociologia. O National Research Council define ciência das redes como "o estudo das representações de rede de fenômenos físicos, biológicos e sociais, levando a modelos preditivos desses fenómenos."
Imagem: Portuguese_eyes · BY-SA · Openverse
O estudo das redes surgiu em diversas disciplinas como um meio de análise de dados relacionais complexos. O livro mais antigo conhecido neste campo é o famoso Sete pontes de Königsberg escrito por Leonhard Euler em 1736. A descrição matemática de Euler de vértices e arestas foi o que fundou a teoria dos grafos, um ramo da matemática que estuda as propriedades das relações entre pares numa estrutura de rede. O campo da teoria dos grafos continuou a desenvolver-se encontrado aplicações em outras áreas, tal como a química. Na década de 1930, Jacob Levy Moreno, psicólogo da tradição Gestalt, chegou nos Estados Unidos. Ele desenvolveu o Sociograma e apresentou-o ao público em abril de 1933 em uma Convenção de médicos acadêmicos. Moreno afirmou que "antes do advento da sociometria ninguém sabia o que a estrutura interpessoal de um grupo 'precisamente' parecia . O Sociograma era uma representação da estrutura social de um grupo de alunos do ensino básico. Os meninos eram amigos dos meninos e as meninas eram amigas das meninas, com exceção de um menino que disse que ele gostava de uma única menina. O sentimento não foi retribuído. Esta representação da rede da estrutura social foi tão intrigante que foi impressa no The New York Times . O Sociograma encontrou muitas aplicações e cresceu no campo de análise de redes sociais. É atribuído a Jacob Levy Moreno a criação da sociometria, campo de estudos precursor da ciências das redes.
Imagem: Senado Federal · BY · Openverse
Muitas vezes, as redes têm certos atributos que podem ser calculados para analisar as propriedades e características da rede. Essas propriedades de rede muitas vezes definem Modelos de rede e podem ser usadas para analisar como alguns modelos contrastam entre si. Muitas das definições para outros termos usados na ciência de rede podem ser encontradas em Glossário de teoria dos grafos . A maneira de como uma rede está ligada desempenha um grande papel na forma como as redes são analisadas e interpretadas. As redes são classificadas em três categorias diferentes: Centralidade do nó pode ser vista como uma medida da influência ou importância num modelo de rede. Existem três principais medidas de centralidade que são estudadas nas ciências das redes.
Densidade
A densidade D {\displaystyle D} de uma rede é definida como uma relação entre o número de arestas E {\displaystyle E} para o número de arestas possíveis, dada pelo coeficiente binomial ( N 2 ) {\displaystyle {\tbinom {N}{2}}} , dando D = 2 E N ( N − 1 ) . {\displaystyle D={\frac {2E}{N(N-1)}}.}
Tamanho
O tamanho de uma rede pode referir-se o número de nós N {\displaystyle N} ou, menos comumente, o número de arestas E {\displaystyle E} que pode variar de N − 1 {\displaystyle N-1} (uma árvore) para E m a x {\displaystyle E_{max}} (um grafo completo).
Grau médio
O grau k {\displaystyle k} de um nó é o número de arestas conectadas a ele. Intimamente relacionado com a densidade de uma rede é o grau médio, ⟨ k ⟩ = 2 E N {\displaystyle \langle k\rangle ={\tfrac {2E}{N}}} . INo modelo ER grafo aleatório, podemos calcular ⟨ k ⟩ = p N ( N − 1 ) {\displaystyle \langle k\rangle =pN(N-1)} onde p {\displaystyle p} é a probabilidade de dois nós estarem ligados.
Comprimento médio do caminho
Comprimento médio do percurso é calculado encontrando o caminho mais curto entre todos os pares de nós, somando-os e dividindo-os pelo número total de pares. Isto mostra-nos, em média, o número de passos que leva para chegar de um membro da rede ao outro.
Diâmetro de uma rede
Como outro meio de medir grafos de rede, podemos definir o diâmetro de uma rede como o mais longo de todos os caminhos mais curtos calculados numa rede. Por outras palavras, uma vez que o menor comprimento do caminho de cada nó para todos os outros nós é calculado, o diâmetro é o mais longo de todos os comprimentos do caminho calculado. O diâmetro é representante do tamanho de uma rede linear.
Coeficiente de agrupamento local
O coeficiente de agregação é uma medida de propriedade "all-my-friends-know-each-other". Isso é algumas vezes descrito como os amigos dos meus amigos meus amigos são. Mais precisamente, o coeficiente de agregação de um nó é o rácio entre os ligações existentes conectando os vizinhos do nó uns aos outros para o maior número possível de tais ligações. O coeficiente de agregação para toda a rede é a média dos coeficientes de todos os nós de agregação. Um alto coeficiente de agregação de uma rede é outra indicação de um pequeno mundo. O coeficiente de agregação do i {\displaystyle i} nó é: C i = 2 e i k i ( k i − 1 ) , {\displaystyle C_{i}={2e_{i} \over k_{i}{(k_{i}-1)}}\,,} Onde k i {\displaystyle k_{i}} é o número de vizinhos do i {\displaystyle i} nó, e e i {\displaystyle e_{i}} ié o número de conexões entre esses vizinhos. O maior número possível de conexões entre vizinhos é, naturalmente,
Os modelos de redes servem como base para o entendimento das interações dentro das redes empíricas complexas. Vários modelos de geração de grafos aleatórios produzem estruturas de rede que podem ser usadas para efetuar comparações com redes complexas do mundo real.
Modelo de Grafo aleatório Erdős–Rényi
O modelo de Erdős–Rényi , cujo nome é este porque Paul Erdős e Alfréd Rényi foram quem desenvolveu esta teoria, é usado para gerar grafos aleatórios em que as arestas situam-se entre nós com probabilidade igual. Ele pode ser usado no método probabilístico para provar a existência de grafos satisfazendo várias propriedades, ou para fornecer uma definição rigorosa do que significa para uma propriedade armazenar para quase todos os grafos. Para gerar um modelo de Erdős–Rényi dois parâmetros devem ser especificados: o número de nós no grafo gerado como N {\displaystyle N} e a probabilidade de que uma ligação deve ser formada entre quaisquer dois nós como p {\displaystyle p} . Uma constante ⟨ k ⟩ {\displaystyle \langle k\rangle } que pode ser derivada destes dois componentes com a fórmula ⟨ k ⟩ = 2 E / N = p ( N − 1 ) {\displaystyle \langle k\rangle =2E/N=p(N-1)} .
Modelo Watts-Strogatz pequeno mundo
O Modelo de watts e Strogatz é um modelo de geração aleatória de grafo que produz grafos com Propriedades de pequeno mundo. Uma estrutura inicial em malha é utilizada para gerar um modelo de Watts-Strogatz. Cada nó da rede é inicialmente ligado aos seus ⟨ k ⟩ {\displaystyle \langle k\rangle } vizinhos mais próximos. Outro parâmetro é especificado como a probabilidade de religação. Cada aresta tem uma probabilidade. p {\displaystyle p} que vai ser religado ao grafo como uma aresta aleatória. O número esperado de religações no modelo é p E = p N ⟨ k ⟩ / 2 {\displaystyle pE=pN\langle k\rangle /2} . Como o modelo de Watts-Strogatz começa como estrutura não-aleatória em malha, tem um coeficiente de agregação muito alto em conjunto com uma media elevada do comprimento do caminho. Cada religação é suscetível de criar um atalho entre agrupamentos altamente conectados. À medida que aumenta a probabilidade de religação, o coeficiente de agregação diminui mais lentamente do que o comprimento médio do caminho. Com efeito, isso permite que o comprimento médio do caminho da rede diminua, significativamente, com apenas uma pequena diminuição no coeficiente de agregação. Valores mais elevados de p forçam mais arestas religadas, cujo efeito faz o modelo Watts-Strogatz uma rede aleatória.
Modelo de fixação preferencial de Barabási–Albert (BA)
O modelo Barabási–Albert é um modelo de rede aleatório usado para demonstrar um aglutinamento preferencial ou um efeito "os ricos ficam mais ricos". Neste modelo, é mais provável uma aresta anexar-se a nós com graus mais elevados A rede começa com uma rede inicial de m0 nós. m0 ≥ 2 e o grau de cada nó da rede inicial deve ser de pelo menos 1, caso contrário, ele permanecerá sempre desconectado do resto da rede. No modelo BA, são adicionados à rede novo nós, um cada vez. Cada novo nó está conectado a nós existentes com uma probabilidade proporcional ao número de ligações que os nós existentes já têm. Formalmente, a probabilidade pi que o novo nó está conectado ao nó i is
Imagem: Senado Federal · BY · Openverse
Análise de redes sociais
A análise de redes sociais examina a estrutura de relacionamentos entre entidades sociais. Estas entidades são muitas vezes pessoas, mas também podem ser grupos, organizações, Estados-nação, Web sites, publicações acadêmicas. Desde os anos 70, o estudo empírico das redes tem desempenhado um papel central nas ciências sociais e muitas das ferramentas matemáticas e estatísticas utilizadas para o estudo de redes foram desenvolvidas primeiramente na Sociologia . Entre muitas outras aplicações, a análise de redes sociais tem sido utilizada para compreender a difusão das inovações, notícias e rumores. Da mesma forma, tem sido utilizada para examinar a propagação de doenças e comportamentos de saúde. Também foi aplicado no estudo dos mercados, onde foi utilizado para examinar o papel da confiança em relações de troca e dos mecanismos sociais na definição dos preços. Da mesma forma, ela tem sido usada para estudar o recrutamento em movimentos políticos e organizações sociais. A análise de Redes sociais também tem sido usada para conceptualizar divergências científicas, bem como prestígio acadêmico. Mais recentemente, a análise de redes (e seu primo próximo análise de tráfego) ganhou um uso significativo na inteligência militar, para descobrir redes de natureza insurgentes quer de natureza hierárquica e sem liderança.
Análise de redes biológicas
Com a recente explosão, no que diz respeito à disponibilidade publica de dados biológicos, a análise de redes moleculares ganhou um interesse significativo. O tipo de análise deste conteúdo está intimamente relacionado com a análise de redes sociais, mas muitas vezes com foco em padrões locais na rede. Por exemplo motivos de rede são pequenos subgrafos que estão sobre-representados na rede. Motivos de atividade são semelhantes padrões sobre-representados nos atributos de nós e arestas na rede que são sobre representados dada a estrutura de rede-
Análise de ligação
Análise de ligação é um subconjunto da análise de rede, explorando as associações entre objetos. Um exemplo pode ser o exame efetuado aos suspeitos e vítimas com base nas moradas, números de telefone que discaram, as transações financeiras que tenham efetuado durante um determinado período de tempo e as relações familiares entre estes como parte do inquérito policial. A análise de ligações fornece as relações cruciais e associações entre muitos objetos de diferentes tipos que são aparentemente peças isoladas de informação. Análise de ligações assistida por computador ou totalmente automática baseada em computador é cada vez mais empregue por bancos e agências de seguros, em deteção de fraudes, pelos operadores de telecomunicações na análise de redes de telecomunicações, pelo setor médico em epidemiologia e farmacologia, na aplicação da lei nomeadamente em investigações, por motores de busca por classificação em termos de relevância (e, por outro lado por spammers para spamdexing e por empresários para optimização do motor de busca) e em todos os lugares onde os relacionamentos entre muitos objetos têm de ser analisados.
Medidas de centralidade
Informações sobre a importância relativa de nós e arestas num grafo podem ser obtidas através de medidas de centralidade, amplamente utilizadas em disciplinas como a sociologia. Medidas de centralidade são essenciais quando uma análise de rede tem de responder a perguntas como: "quais são os nós da rede que devem ser direcionados para garantir que uma mensagem ou informação se espalha a todos ou à maioria dos nós na rede?" ou, inversamente, "que nós devem ser direcionados para reduzir a propagação de uma doença?". Formalmente estabelecidas medidas de centralidade são o grau de centralidade, centralidade de proximidade, centralidade de Intermediação, centralidade do vetor próprio e centralidade de Katz Prestige. O objetivo da análise da rede geralmente determina o tipo de centralidades a ser usado.
Imagem: Senado Federal · BY · Openverse
Conteúdo numa rede complexa pode espalhar-se através de dois métodos principais: propagação conservada e propagação não conservada. Em propagação conservada, a quantidade total de conteúdo que entra numa rede complexa permanece constante quando ela a atravessa. O modelo de propagação conservada pode ser melhor representado por um jarro contendo uma quantidade fixa de água sendo esta derramada numa série de funis, conectados por tubos. Aqui, o arremessador representa a fonte original, e a água é o conteúdo que está a ser espalhado. Os tubos de ligação e funis representam os nós e as conexões entre os nós, respetivamente. Como a água passa de um funil para outro, a água desaparece instantaneamente do funil que anteriormente foi exposto à água. Na propagação não conservada, a quantidade de conteúdo altera conforme ele entra e passa através de uma rede complexa. O modelo de propagação não conservado pode ser melhor representado por uma torneira deitando água continuamente através de uma série de funis, conectados por tubos. Aqui, a quantidade de água da fonte original também é infinita, quaisquer funis que foram expostos à água continuam a experimentar a água, mesmo que ele passe em sucessivos funis. O modelo não conservado é o mais adequado para explicar a transmissão de doenças infeciosas.
O modelo de SIR
Em 1927, W. O. Kermack e A. G. McKendrick criaram um modelo em que consideravam uma população fixa com apenas três compartimentos, suscetíveis S ( t ) {\displaystyle S(t)} , infetados , I ( t ) {\displaystyle I(t)} , e recuperados , R ( t ) {\displaystyle R(t)} chamado modelo SIR (Susceptible-Infected-Recovered). Os compartimentos utilizados para esta consistem no modelo três classes: O fluxo deste modelo pode ser considerado como se segue: Utilizando uma população fixa, N = S ( t ) + I ( t ) + R ( t ) {\displaystyle N=S(t)+I(t)+R(t)} , Kermack e McKendrick derivam as seguintes equações: Várias hipóteses foram feitas na formulação destas equações: primeiro, um indivíduo da população deve ser considerado como tendo uma probabilidade igual como cada outro indivíduo de contrair a doença com uma taxa de β {\displaystyle \beta } , que é considerada a taxa de contato ou de infeção da doença. Portanto, um indivíduo infetado tem contato e é capaz de transmitir a doença com β N {\displaystyle \beta N} outros, por unidade de tempo e a fração dos contatos por um infetado com um suscetível é S / N {\displaystyle S/N} . O número de novas infeções em unidade de tempo por infetado é β N ( S / N ) {\displaystyle \beta N(S/N)} , então, dando a taxa de novas infeções (ou aqueles que deixam a categoria suscetível) como β N ( S / N ) I = β S I {\displaystyle \beta N(S/N)I=\beta SI} (Brauer & Castillo-Chavez, 2001). Para as segunda e terceira equações, considere a população deixando a classe sensível como igual ao número entrando na classe infetada. No entanto, um número igual à fração ( γ {\displaystyle \gamma } que representa a taxa de recuperação média ou 1 / γ {\displaystyle 1/\gamma } o período médio de infeção) de infetados estão a deixar essa classe por unidade de tempo para entrar a classe removida. Esses processos que ocorrem simultaneamente são referidos como a lei de ação de massa, uma ideia amplamente aceite de que a taxa de contato entre dois grupos numa população é proporcional ao tamanho de cada um dos grupos em questão (Daley & Gani, 2005). Por fim, presume-se que a taxa de infeção e a recuperação é muito mais rápida do que a escala de tempo de nascimentos e mortes, e portanto, esses fatores são ignorados neste modelo.
Imagem: Senado Federal · BY · Openverse
Uma rede interdependente é um sistema de redes acopladas, onde nós, de uma ou mais redes dependem de nós noutras redes. Essas dependências são reforçadas pelos desenvolvimentos na tecnologia moderna. Dependências podem levar a falhas em cascata entre as redes e uma falha relativamente pequena pode levar a um colapso catastrófico do sistema. Apagões são uma demonstração fascinante do importante papel desempenhado por dependências entre redes. Um estudo recente desenvolveu um quadro para estudar as falhas em cascata num sistema de redes interdependentes .
Imagem: Senado Federal · BY · Openverse
Problemas de rede que envolvem encontrar a maneira ideal de fazer algo são estudados sob o nome de otimização combinatória. Exemplos incluem fluxo de rede, problema de caminho mais curto, problema de transporte, problema de transbordo, problema de localização, problema de correspondencia, problema de atribuição, problema de embalagem, encaminhamento do problema, análise de caminho crítico e PERT (Program Evaluation & Review Technique).
