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."
História
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.
A Teoria probabilística na ciência das redes que foi desenvolvida a partir da teoria dos grafos por Paul Erdős e Alfréd Rényi nos oito famosos trabalhos sobre grafos aleatórios. Para redes sociais o modelo grafo aleatório exponencial ou é um quadro de notação usado para representar o espaço de probabilidade de uma ocorrência de empate numa rede social. Uma abordagem alternativa para estruturas de probabilidade de rede é a matriz de probabilidade da rede, que modela a probabilidade das arestas que ocorrem numa rede, baseada na histórica presença ou ausência de aresta numa amostra de redes.
Em 1998, David Krackhardt e Kathleen Carley introduziram a ideia de uma meta-rede, com o modelo de PCANS. Eles sugerem que "todas as organizações são estruturadas ao longo destes três domínios, pessoas, tarefas e recursos". O seu estudo introduziu o conceito de que redes ocorrem em vários domínios e que são inter-relacionados. Este campo tem crescido em outro ramo da ciência das redes chamado análise de rede dinâmica .
Mais recentemente outros esforços da ciência das redes centraram-se em descrever matematicamente topologias de rede diferentes. Duncan Watts e Steven Strogatz reconciliaram dados empíricos em redes com representações matemática, descrevendo as redes de pequeno mundo . Albert-László Barabási e Reka Albert desenvolveram a rede livre de escala que é uma topologia de rede vagamente definida que contém os vértices do cubo com muitas conexões, que crescem de forma a manter uma relação constante no número de conexões contra todos os outros nós. Apesar de muitas redes, como a internet, parecem manter este aspecto, outras redes têm longa cauda de distribuições de nós que rácios livre escala apenas aproximado.
Propriedades de rede 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 .
Densidade A densidade de uma rede é definida como uma relação entre o número de arestas para o número de arestas possíveis, dada pelo coeficiente binomial , dando
Tamanho O tamanho de uma rede pode referir-se o número de nós ou, menos comumente, o número de arestas que pode variar de (uma árvore) para (um grafo completo).
Grau médio O grau de um nó é o número de arestas conectadas a ele. Intimamente relacionado com a densidade de uma rede é o grau médio, . INo modelo ER grafo aleatório, podemos calcular onde é 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 nó é:
Onde é o número de vizinhos do nó, e ié o número de conexões entre esses vizinhos. O maior número possível de conexões entre vizinhos é, naturalmente,
Ligação 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: Clique/Grafo completo: uma rede totalmente conectada, onde todos os nós estão conectados a todos os outros nós. Estas redes são simétricas, pois todos os nós têm ligações de entrada e saída entre eles. Componente gigante: Um único componente conectado que contém a maior parte dos nós na rede. Componente Fracamente ligado: Uma coleção de nós em que existe um caminho de qualquer nó para qualquer outro, ignorando a orientação das arestas. Componente Fortemente ligado: Uma coleção de nós em que existe um caminho orientado de um qualquer nó para outro.
Centralidade do nó 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. Proximidade : representa a distância média a que cada nó está, de todos os outros nós na rede Intermediação : representa o número dos caminhos mais curtos numa rede que passam por esse nó. Grau /Força: representa os quantidade ligações que um nó específico possui numa rede. Numa rede orientada, deve-se diferenciar entre ligações de entrada e ligações de saída calculando-se o grau de entrada e o grau de saída.
Modelos de rede 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 thumb|Este modelo Erdős–Rényi é gerado com N = 4 nós. Para cada aresta no grafo completo formado por todos os nós de N, um número aleatório é gerado e comparado com uma determinada probabilidade. Se o número aleatório é maior que p, uma aresta é formada no modelo.
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 e a probabilidade de que uma ligação deve ser formada entre quaisquer dois nós como . Uma constante que pode ser derivada destes dois componentes com a fórmula .
O modelo Erdős–Rényi tem várias características interessantes, em comparação com outros grafos. Porque o modelo é gerado sem viés para nós particulares, a distribuição de grau é binomial na natureza no que diz respeito à fórmula: . Também como consequência desta característica, o coeficiente de agregação tende para 0. O modelo tende a formar um componente gigante em situações onde num processo chamado percolação. O comprimento do percurso médio é relativamente curto neste modelo e tende para .
Modelo Watts-Strogatz pequeno mundo thumb|O Modelo de watts e Strogatz utiliza o conceito de religação para alcançar a sua estrutura. O gerador do modelo irá iterar através de cada aresta na estrutura em malha original. Neste exemplo uma aresta pode mudar os seus vértices conectados, de acordo com uma determinada probabilidade de religação.
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 vizinhos mais próximos. Outro parâmetro é especificado como a probabilidade de religação. Cada aresta tem uma probabilidade. que vai ser religado ao grafo como uma aresta aleatória. O número esperado de religações no modelo é .
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