Ciência da rede - Network science

Ciência de redes é um campo acadêmico que estuda redes complexas como redes de telecomunicações , redes de computadores , redes biológicas , redes cognitivas e semânticas e redes sociais , considerando elementos ou atores distintos representados por nós (ou vértices ) e as conexões entre os elementos ou atores como links (ou arestas ). O campo baseia-se em teorias e métodos, incluindo a teoria dos gráficos da matemática, mecânica estatística da física, mineração de dados e visualização de informações da ciência da computação, modelagem inferencial da estatística e estrutura social da sociologia. O Conselho de Pesquisa Nacional dos Estados Unidos define ciência de rede como "o estudo das representações de rede de fenômenos físicos, biológicos e sociais que levam a modelos preditivos desses fenômenos".

Antecedentes e história

O estudo de redes surgiu em diversas disciplinas como um meio de analisar dados relacionais complexos. O primeiro artigo conhecido neste campo são as famosas Sete Pontes de Königsberg, escritas por Leonhard Euler em 1736. A descrição matemática de Euler dos vértices e arestas foi a base da teoria dos grafos , um ramo da matemática que estuda as propriedades das relações entre pares em uma estrutura de rede . O campo da teoria dos grafos continuou a se desenvolver e encontrar aplicações na química (Sylvester, 1878).

Dénes Kőnig , matemático e professor húngaro, escreveu o primeiro livro de Teoria dos Grafos, intitulado "Teoria dos gráficos finitos e infinitos", em 1936.

Sociograma de Moreno de uma turma de 1ª série.

Na década de 1930, Jacob Moreno , psicólogo da tradição da Gestalt , chegou aos Estados Unidos. Ele desenvolveu o sociograma e o apresentou ao público em abril de 1933 em uma convenção de acadêmicos médicos. Moreno afirmava que "antes do advento da sociometria, ninguém sabia como era a estrutura interpessoal de um grupo 'precisamente'" (Moreno, 1953). O sociograma era uma representação da estrutura social de um grupo de alunos do ensino fundamental. Os meninos eram amigos de meninos e as meninas eram amigos de meninas, com exceção de um menino que disse gostar de uma única menina. O sentimento não foi correspondido. Essa representação em rede da estrutura social foi considerada tão intrigante que foi impressa no The New York Times (3 de abril de 1933, página 17). O sociograma encontrou muitas aplicações e cresceu no campo da análise de redes sociais .

A teoria probabilística na ciência de redes desenvolvida como um desdobramento da teoria dos grafos com os oito artigos famosos de Paul Erdős e Alfréd Rényi sobre gráficos aleatórios . Para redes sociais, o modelo de gráfico aleatório exponencial ou p * é uma estrutura notacional usada para representar o espaço de probabilidade de um empate ocorrer em uma rede social . Uma abordagem alternativa para as estruturas de probabilidade da rede é a matriz de probabilidade da rede , que modela a probabilidade de ocorrência de arestas em uma rede, com base na presença ou ausência histórica da aresta em uma amostra de redes.

Em 1998, David Krackhardt e Kathleen Carley introduziram a ideia de uma meta-rede com o modelo PCANS. Eles sugerem que "todas as organizações são estruturadas ao longo desses três domínios, indivíduos, tarefas e recursos". Seu artigo introduziu o conceito de que as redes ocorrem em vários domínios e que estão inter-relacionadas. Este campo cresceu em outra subdisciplina da ciência de redes, chamada análise dinâmica de redes .

Mais recentemente, outros esforços de ciência de rede se concentraram em descrever matematicamente diferentes topologias de rede. Duncan Watts e Steven Strogatz reconciliaram dados empíricos em redes com representação matemática, descrevendo a rede de pequeno mundo . Albert-László Barabási e Reka Albert desenvolveram a rede sem escala, que é uma topologia de rede vagamente definida que contém vértices de hub com muitas conexões, que crescem de forma a manter uma proporção constante no número de conexões versus todos os outros nós. No contexto das redes de citações, o modelo de rede sem escala é uma versão não direcionada do modelo anterior de Price direcionado . Há um desacordo significativo dentro da comunidade científica sobre se as redes do mundo real são livres de escala ou não, com alguns argumentando que são onipresentes e outros argumentando que são raras. Muitos na comunidade científica de rede argumentam que saber se a distribuição de graus é limitada ou não é mais importante do que saber se a distribuição se encaixa nos critérios mais rígidos de ser sem escala.

Iniciativas do Departamento de Defesa

Os militares dos EUA começaram a se interessar pela guerra centrada em rede como um conceito operacional baseado na ciência de redes em 1996. John A. Parmentola, Diretor de Pesquisa e Gerenciamento de Laboratório do Exército dos EUA, propôs ao Conselho de Ciência e Tecnologia do Exército (BAST) em 1º de dezembro de 2003 que a Network Science se tornou uma nova área de pesquisa do Exército. O BAST, a Divisão de Engenharia e Ciências Físicas do Conselho Nacional de Pesquisa (NRC) das Academias Nacionais, atua como uma autoridade convocatória para a discussão de questões científicas e tecnológicas importantes para o Exército e supervisiona estudos independentes relacionados ao Exército conduzidos por as Academias Nacionais. A BAST conduziu um estudo para descobrir se a identificação e o financiamento de um novo campo de investigação em pesquisa básica, a Ciência de Redes, poderia ajudar a fechar a lacuna entre o que é necessário para realizar Operações Centradas em Rede e o estado primitivo atual do conhecimento fundamental de redes.

Como resultado, o BAST publicou o estudo do NRC em 2005 intitulado Network Science (referenciado acima) que definiu um novo campo de pesquisa básica em Network Science for the Army. Com base nas conclusões e recomendações desse estudo e do relatório subsequente do NRC de 2007 intitulado Estratégia para um Centro do Exército para Ciência, Tecnologia e Experimentação de Rede, os recursos de pesquisa básica do Exército foram redirecionados para iniciar um novo programa de pesquisa básica em Ciência de Rede. Para construir uma nova base teórica para redes complexas, alguns dos principais esforços de pesquisa em Ciências de Rede agora em andamento nos laboratórios do Exército abordam:

Modelos matemáticos do comportamento da rede para prever o desempenho com o tamanho, complexidade e ambiente da rede
Desempenho humano otimizado necessário para guerra habilitada em rede
Trabalho em rede dentro dos ecossistemas e no nível molecular das células.

Iniciado em 2004 por Frederick I. Moxley com o apoio que solicitou de David S. Alberts, o Departamento de Defesa ajudou a estabelecer o primeiro Network Science Center em conjunto com o Exército dos EUA na Academia Militar dos Estados Unidos (USMA). Sob a tutela do Dr. Moxley e do corpo docente da USMA, os primeiros cursos interdisciplinares de graduação em Ciência de Redes foram ministrados a cadetes em West Point. A fim de melhor incutir os princípios da ciência em rede entre seu quadro de futuros líderes, o USMA também instituiu um curso de graduação de cinco cursos em Ciências de Rede.

Em 2006, o Exército dos EUA e o Reino Unido (RU) formaram a Network and Information Science International Technology Alliance , uma parceria colaborativa entre o Laboratório de Pesquisa do Exército, o Ministério da Defesa do RU e um consórcio de indústrias e universidades nos Estados Unidos e no RU. O objetivo da aliança é realizar pesquisa básica em apoio às Operações Centradas em Rede para as necessidades de ambas as nações.

Em 2009, o Exército dos EUA formou o Network Science CTA , uma aliança de pesquisa colaborativa entre o Laboratório de Pesquisa do Exército , CERDEC , e um consórcio de cerca de 30 laboratórios industriais de P&D e universidades nos Estados Unidos. O objetivo da aliança é desenvolver um entendimento profundo de as semelhanças subjacentes entre redes sociais / cognitivas, de informação e de comunicação interligadas e, como resultado, melhoram nossa capacidade de analisar, prever, projetar e influenciar sistemas complexos que entrelaçam muitos tipos de redes.

Posteriormente, como resultado desses esforços, o Departamento de Defesa dos Estados Unidos patrocinou vários projetos de pesquisa que apóiam a Network Science.

Propriedades de rede

Freqüentemente, as redes têm certos atributos que podem ser calculados para analisar as propriedades e características da rede. O comportamento dessas propriedades de rede geralmente define modelos de rede e pode ser usado para analisar como certos modelos contrastam entre si. Muitas das definições de outros termos usados na ciência de redes podem ser encontradas no Glossário da teoria dos grafos .

Tamanho

O tamanho de uma rede pode referir-se ao número de nós ou, menos comumente, ao número de arestas que (para grafos conectados sem múltiplas arestas) pode variar de (uma árvore) a (um grafo completo). No caso de um grafo simples (uma rede na qual existe no máximo uma aresta (não direcionada) entre cada par de vértices, e na qual nenhum vértice se conecta a si mesmo), temos ; para grafos direcionados (sem nós auto-conectados) ,; para gráficos direcionados com auto-conexões permitidas ,. Na circunstância de um gráfico dentro do qual várias arestas podem existir entre um par de vértices ,. ${\ displaystyle N}$ ${\ displaystyle E}$ ${\ displaystyle N-1}$ ${\ displaystyle E _ {\ max}}$ ${\ displaystyle E _ {\ max} = {\ tbinom {N} {2}} = N (N-1) / 2}$ ${\ displaystyle E _ {\ max} = N (N-1)}$ ${\ displaystyle E _ {\ max} = N ^ {2}}$ ${\ displaystyle E _ {\ max} = \ infty}$

Densidade

A densidade de uma rede é definida como uma razão entre o número de arestas e o número de arestas possíveis em uma rede com nós, dado (no caso de grafos simples) pelo coeficiente binomial , dando outra equação possível é que os laços são unidirecional (Wasserman & Faust 1994). Isso oferece uma visão geral melhor sobre a densidade da rede, porque os relacionamentos unidirecionais podem ser medidos. ${\ displaystyle D}$ ${\ displaystyle E}$ ${\ displaystyle N}$ ${\ displaystyle {\ tbinom {N} {2}}}$ ${\ displaystyle D = {\ frac {E- (N-1)} {E _ {\ mathrm {max}} - (N-1)}} = {\ frac {2 (E-N + 1)} {N (N-3) +2}}}$ ${\ displaystyle D = {\ frac {T-2N + 2} {N (N-3) +2}},}$ ${\ displaystyle T}$

Densidade de rede planar

A densidade de uma rede, onde não há interseção entre as arestas, é definida como a razão entre o número de arestas e o número de arestas possíveis em uma rede com nós, dada por um grafo sem arestas que se cruzam , dando ${\ displaystyle D}$ ${\ displaystyle E}$ ${\ displaystyle N}$ ${\ displaystyle (E _ {\ max} = 3N-6)}$ ${\ displaystyle D = {\ frac {E-N + 1} {2N-5}}.}$

Grau médio

O grau de um nó é o número de arestas conectadas a ele. Intimamente relacionado à densidade de uma rede está o grau médio, (ou, no caso de grafos direcionados , o primeiro fator de 2 surgindo de cada aresta em um grafo não direcionado contribuindo para o grau de dois vértices distintos). No modelo de gráfico aleatório ER ( ) podemos calcular o valor esperado de (igual ao valor esperado de de um vértice arbitrário): um vértice aleatório tem outros vértices na rede disponíveis e, com probabilidade , se conecta a cada um. Assim ,. ${\ displaystyle k}$ ${\ displaystyle \ langle k \ rangle = {\ tfrac {2E} {N}}}$ ${\ displaystyle \ langle k \ rangle = {\ tfrac {E} {N}}}$ ${\ displaystyle G (N, p)}$ ${\ displaystyle \ langle k \ rangle}$ ${\ displaystyle k}$ ${\ displaystyle N-1}$ ${\ displaystyle p}$ ${\ displaystyle \ mathbb {E} [\ langle k \ rangle] = \ mathbb {E} [k] = p (N-1)}$

Comprimento médio do caminho mais curto (ou comprimento do caminho característico)

O comprimento médio do caminho mais curto é calculado encontrando o caminho mais curto entre todos os pares de nós, e tomando a média de todos os caminhos do seu comprimento (o comprimento é o número de arestas intermediárias contidas no caminho, ou seja, a distância entre os dois vértices dentro do gráfico). Isso nos mostra, em média, o número de etapas necessárias para ir de um membro da rede a outro. O comportamento do comprimento do caminho mais curto médio esperado (ou seja, a média do conjunto do comprimento do caminho mais curto médio) como uma função do número de vértices de um modelo de rede aleatório define se esse modelo exibe o efeito de mundo pequeno; se for dimensionado como , o modelo gerará redes de pequenos mundos. Para um crescimento mais rápido do que logarítmico, o modelo não produz mundos pequenos. O caso especial de é conhecido como efeito de mundo ultrapequeno. ${\ displaystyle d_ {u, v}}$ ${\ displaystyle u, v}$ ${\ displaystyle N}$ ${\ displaystyle O (\ ln N)}$ ${\ displaystyle O (\ ln \ ln N)}$

Caminho ideal

Quando os links ou nós são ponderados, pode-se considerar o caminho ideal entre os nós.

Diâmetro de uma rede

Como outro meio de medir gráficos de rede, podemos definir o diâmetro de uma rede como o mais longo de todos os caminhos mais curtos calculados em uma rede. É a distância mais curta entre os dois nós mais distantes da rede. Em outras palavras, uma vez que o comprimento de caminho mais curto de cada nó para todos os outros nós é calculado, o diâmetro é o mais longo de todos os comprimentos de caminho calculados. O diâmetro é representativo do tamanho linear de uma rede. Se o nó ABCD estiver conectado, indo de A-> D, isso teria o diâmetro de 3 (3 saltos, 3 links).

Coeficiente de agrupamento

O coeficiente de agrupamento é uma medida de uma propriedade "todos os meus amigos se conhecem". Isso às vezes é descrito como os amigos dos meus amigos são meus amigos. Mais precisamente, o coeficiente de agrupamento de um nó é a proporção de links existentes que conectam os vizinhos de um nó entre si para o número máximo possível de tais links. O coeficiente de agrupamento para toda a rede é a média dos coeficientes de agrupamento de todos os nós. Um alto coeficiente de agrupamento para uma rede é outra indicação de um mundo pequeno .

O coeficiente de agrupamento do 'ésimo nó é ${\ displaystyle i}$

{\ displaystyle C_ {i} = {2e_ {i} \ over k_ {i} {(k_ {i} -1)}} \ ,,}

onde é o número de vizinhos do 'ésimo nó, e é o número de conexões entre esses vizinhos. O número máximo possível de conexões entre vizinhos é, então, ${\ displaystyle k_ {i}}$ ${\ displaystyle i}$ ${\ displaystyle e_ {i}}$

{\ displaystyle {\ binom {k} {2}} = {{k (k-1)} \ over 2} \ ,.}

Do ponto de vista probabilístico, o coeficiente de agrupamento local esperado é a probabilidade de um link existir entre dois vizinhos arbitrários do mesmo nó.

Conectividade

A maneira como uma rede é conectada desempenha um grande papel em como as redes são analisadas e interpretadas. As redes são classificadas em quatro categorias diferentes:

Clique / Gráfico completo : uma rede completamente conectada, onde todos os nós estão conectados a todos os outros nós. Essas redes são simétricas no sentido de que todos os nós têm links internos e externos de todos os outros.
Componente gigante : Um único componente conectado que contém a maioria dos nós da rede.
Componente Fracamente Conectado : Uma coleção de nós em que existe um caminho de qualquer nó para qualquer outro, ignorando a direcionalidade das arestas.
Componente fortemente conectado : uma coleção de nós em que existe um caminho direcionado de qualquer nó para qualquer outro.

Centralidade do nó

Os índices de centralidade produzem classificações que buscam identificar os nós mais importantes em um modelo de rede. Diferentes índices de centralidade codificam diferentes contextos para a palavra "importância". A centralidade de intermediação , por exemplo, considera um nó altamente importante se ele formar pontes entre muitos outros nós. A centralidade dos autovalores , em contraste, considera um nó altamente importante se muitos outros nós altamente importantes se vincularem a ele. Centenas dessas medidas foram propostas na literatura.

Os índices de centralidade são precisos apenas para identificar os nós mais centrais. As medidas raramente, ou nunca, são significativas para o restante dos nós da rede. Além disso, suas indicações são precisas apenas dentro de seu contexto assumido para importância e tendem a "errar" para outros contextos. Por exemplo, imagine duas comunidades separadas cujo único vínculo é uma ponta entre o membro mais jovem de cada comunidade. Uma vez que qualquer transferência de uma comunidade para outra deve passar por este link, os dois membros juniores terão alta centralidade de intermediação. Mas, como são juniores, (presumivelmente) eles têm poucas conexões com os nós "importantes" em sua comunidade, o que significa que sua centralidade de autovalor seria bastante baixa.

Influência do nó

As limitações às medidas de centralidade levaram ao desenvolvimento de medidas mais gerais. Dois exemplos são a acessibilidade , que usa a diversidade de passeios aleatórios para medir o quão acessível o resto da rede está a partir de um determinado nó inicial, e a força esperada , derivada do valor esperado da força de infecção gerada por um nó. Ambas as medidas podem ser calculadas de forma significativa apenas a partir da estrutura da rede.

Estrutura da comunidade

Fig. 1: Um esboço de uma pequena rede exibindo uma estrutura de comunidade , com três grupos de nós com conexões internas densas e conexões mais esparsas entre os grupos.

Os nós em uma rede podem ser divididos em grupos que representam comunidades. Dependendo do contexto, as comunidades podem ser distintas ou sobrepostas. Normalmente, os nós em tais comunidades serão fortemente conectados a outros nós na mesma comunidade, mas fracamente conectados a nós fora da comunidade. Na ausência de uma verdade fundamental que descreva a estrutura da comunidade de uma rede específica, vários algoritmos foram desenvolvidos para inferir possíveis estruturas da comunidade usando métodos de agrupamento supervisionados ou não supervisionados.

Modelos de rede

Os modelos de rede servem como base para a compreensão das interações em redes empíricas complexas. Vários modelos de geração de grafos aleatórios produzem estruturas de rede que podem ser usadas em comparação com redes complexas do mundo real.

Modelo de gráfico aleatório Erdős – Rényi

Este modelo Erdős – Rényi é gerado com

N = 4

nós. Para cada aresta no gráfico completo formado por todos os

N

nós, um número aleatório é gerado e comparado a uma determinada probabilidade. Se o número aleatório for menor que

p

, uma aresta é formada no modelo.

O modelo Erdős – Rényi , nomeado em homenagem a Paul Erdős e Alfréd Rényi , é usado para gerar gráficos aleatórios nos quais as arestas são definidas entre nós com probabilidades iguais. Pode ser usado no método probabilístico para provar a existência de gráficos que satisfazem várias propriedades ou para fornecer uma definição rigorosa do que significa uma propriedade ser válida para quase todos os gráficos.

Para gerar um modelo Erdős – Rényi, dois parâmetros devem ser especificados: o número total de nós $n$ e a probabilidade $p de$ um par aleatório de nós ter uma aresta. ${\ displaystyle G (n, p)}$

Como o modelo é gerado sem polarização para nós específicos, a distribuição de graus é binomial: para um vértice escolhido aleatoriamente , ${\ displaystyle v}$

{\ displaystyle P (\ deg (v) = k) = {n-1 \ escolha k} p ^ {k} (1-p) ^ {n-1-k}.}

Neste modelo, o coeficiente de agrupamento é $0$ A.Ş . O comportamento de pode ser dividido em três regiões. ${\ displaystyle G (n, p)}$

Subcrítico : Todos os componentes são simples e muito pequenos, o maior componente tem tamanho ; ${\ displaystyle np <1}$ ${\ displaystyle | C_ {1} | = O (\ log n)}$

Critical : ; ${\ displaystyle np = 1}$ ${\ displaystyle | C_ {1} | = O (n ^ {\ frac {2} {3}})}$

Supercrítico : onde está a solução positiva da equação . ${\ displaystyle np> 1}$ ${\ displaystyle | C_ {1} | \ aprox yn}$ ${\ displaystyle y = y (np)}$ ${\ displaystyle e ^ {- pny} = 1-y}$

O maior componente conectado possui alta complexidade. Todos os outros componentes são simples e pequenos . ${\ displaystyle | C_ {2} | = O (\ log n)}$

Modelo de configuração

O modelo de configuração usa uma sequência de graus ou distribuição de graus (que subsequentemente é usada para gerar uma sequência de graus) como entrada e produz gráficos conectados aleatoriamente em todos os aspectos, exceto a sequência de graus. Isso significa que, para uma determinada escolha de sequência de graus, o gráfico é escolhido de maneira uniforme e aleatória do conjunto de todos os gráficos que obedecem a essa sequência de graus. O grau de um vértice escolhido aleatoriamente é uma variável aleatória independente e distribuída de forma idêntica com valores inteiros. Quando , o gráfico de configuração contém o componente gigante conectado , que tem tamanho infinito. Os demais componentes possuem tamanhos finitos, que podem ser quantificados com a noção de distribuição de tamanhos. A probabilidade de que um nó amostrado aleatoriamente esteja conectado a um componente de tamanho é dada por potências de convolução da distribuição de graus: ${\ displaystyle k}$ ${\ textstyle \ mathbb {E} [k ^ {2}] - 2 \ mathbb {E} [k]> 0}$ ${\ displaystyle w (n)}$ ${\ displaystyle n}$

{\ displaystyle w (n) = {\ begin {cases} {\ frac {\ mathbb {E} [k]} {n-1}} u_ {1} ^ {* n} (n-2), & n> 1, \\ u (0) & n = 1, \ end {casos}}}

onde denota a distribuição de graus e . O componente gigante pode ser destruído removendo aleatoriamente a fração crítica de todas as arestas. Este processo é denominado percolação em redes aleatórias . Quando o segundo momento da distribuição de graus é finito,, esta fração crítica da aresta é dada por , e a distância vértice-vértice média no componente gigante escala logaritmicamente com o tamanho total da rede ,.

{\ displaystyle u (k)}

{\ displaystyle u_ {1} (k) = {\ frac {(k + 1) u (k + 1)} {\ mathbb {E} [k]}}}

{\ displaystyle p_ {c}}

{\ textstyle \ mathbb {E} [k ^ {2}] <\ infty}

{\ displaystyle p_ {c} = 1 - {\ frac {\ mathbb {E} [k]} {\ mathbb {E} [k ^ {2}] - \ mathbb {E} [k]}}}

{\ displaystyle l}

{\ displaystyle l = O (\ log N)}

No modelo de configuração direcionada, o grau de um nó é dado por dois números, em grau e em grau externo e, conseqüentemente, a distribuição de graus é duas variáveis. O número esperado de bordas internas e externas coincide, de modo que . O modelo de configuração direcionada contém o

componente gigante iff

{\ displaystyle k _ {\ text {in}}}

{\ displaystyle k _ {\ text {out}}}

{\ textstyle \ mathbb {E} [k _ {\ text {in}}] = \ mathbb {E} [k _ {\ text {out}}]}

{\ displaystyle 2 \ mathbb {E} [k _ {\ text {in}}] \ mathbb {E} [k _ {\ text {in}} k _ {\ text {out}}] - \ mathbb {E} [k_ {\ text {in}}] \ mathbb {E} [k _ {\ text {out}} ^ {2}] - \ mathbb {E} [k _ {\ text {in}}] \ mathbb {E} [k_ {\ text {in}} ^ {2}] + \ mathbb {E} [k _ {\ text {in}} ^ {2}] \ mathbb {E} [k _ {\ text {out}} ^ {2} ] - \ mathbb {E} [k _ {\ text {in}} k _ {\ text {out}}] ^ {2}> 0.}

Observe que e são iguais e, portanto, intercambiáveis na última desigualdade. A probabilidade de um vértice escolhido aleatoriamente pertencer a um componente de tamanho é dada por:

{\ textstyle \ mathbb {E} [k _ {\ text {in}}]}

{\ textstyle \ mathbb {E} [k _ {\ text {out}}]}

{\ displaystyle n}

{\ displaystyle h _ {\ text {in}} (n) = {\ frac {\ mathbb {E} [k_ {in}]} {n-1}} {\ tilde {u}} _ {\ text {in }} ^ {* n} (n-2), \; n> 1, \; {\ tilde {u}} _ {\ text {in}} = {\ frac {k _ {\ text {in}} + 1} {\ mathbb {E} [k _ {\ text {in}}]}} \ sum \ limits _ {k _ {\ text {out}} \ geq 0} u (k _ {\ text {in}} + 1 , k _ {\ text {out}}),}

para componentes internos, e

${\ displaystyle h _ {\ text {out}} (n) = {\ frac {\ mathbb {E} [k _ {\ text {out}}]} {n-1}} {\ tilde {u}} _ { \ text {out}} ^ {* n} (n-2), \; n> 1, \; {\ tilde {u}} _ {\ text {out}} = {\ frac {k _ {\ text { out}} + 1} {\ mathbb {E} [k _ {\ text {out}}]}} \ sum \ limits _ {k _ {\ text {in}} \ geq 0} u (k _ {\ text {in }}, k _ {\ text {out}} + 1),}$

para componentes externos.

Modelo de mundo pequeno Watts-Strogatz

O modelo Watts e Strogatz usa o conceito de religação para obter sua estrutura. O gerador de modelo irá iterar através de cada aresta na estrutura de rede original. Uma aresta pode mudar seus vértices conectados de acordo com uma dada probabilidade de religação. neste exemplo.

{\ displaystyle \ langle k \ rangle = 4}

O modelo de Watts e Strogatz é um modelo de geração de gráfico aleatório que produz gráficos com propriedades de mundo pequeno .

Uma estrutura de rede inicial é usada para gerar um modelo Watts-Strogatz. Cada nó da rede está inicialmente vinculado a seus vizinhos mais próximos. Outro parâmetro é especificado como a probabilidade de religação. Cada aresta tem uma probabilidade de ser reconectada ao gráfico como uma aresta aleatória. O número esperado de links reconectados no modelo é . ${\ displaystyle \ langle k \ rangle}$ ${\ displaystyle p}$ ${\ displaystyle pE = pN \ langle k \ rangle / 2}$

Como o modelo Watts-Strogatz começa como uma estrutura de rede não aleatória, ele tem um coeficiente de agrupamento muito alto junto com um comprimento de caminho médio alto. Cada reconfiguração provavelmente criará um atalho entre clusters altamente conectados. Conforme a probabilidade de religação aumenta, o coeficiente de agrupamento diminui mais lentamente do que o comprimento médio do caminho. Na verdade, isso permite que o comprimento médio do caminho da rede diminua significativamente, com apenas pequenas diminuições no coeficiente de agrupamento. Valores mais altos de p forçam bordas mais religadas, o que de fato torna o modelo de 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 apego preferencial ou um efeito de "enriquecimento e enriquecimento". Neste modelo, é mais provável que uma aresta se fixe em nós com graus mais altos. A rede começa com uma rede inicial de m ₀ nós. m ₀ ≥ 2 e o grau de cada nó na rede inicial deve ser de pelo menos 1, caso contrário permanecerá sempre desconectado do resto da rede.

No modelo BA, novos nós são adicionados à rede, um de cada vez. Cada novo nó é conectado a nós existentes com uma probabilidade que é proporcional ao número de links que os nós existentes já possuem. Formalmente, a probabilidade

p _{i de} que o novo nó está conectado ao nó i é

{\ displaystyle m}

{\ displaystyle p_ {i} = {\ frac {k_ {i}} {\ sum _ {j} k_ {j}}},}

onde k _i é o grau do nó i . Os nós fortemente vinculados ("hubs") tendem a acumular rapidamente ainda mais links, enquanto os nós com apenas alguns links provavelmente não serão escolhidos como o destino de um novo link. Os novos nós têm uma "preferência" para se anexar aos nós já fortemente vinculados.

A distribuição de graus do Modelo BA, que segue uma lei de potência. Na escala loglog, a função da lei de potência é uma linha reta.

A distribuição de graus resultante do modelo BA é livre de escala, em particular, é uma lei de potência da forma:

{\ displaystyle P (k) \ sim k ^ {- 3} \,}

Os hubs exibem alta centralidade de intermediação, o que permite que caminhos curtos existam entre os nós. Como resultado, o modelo BA tende a ter comprimentos de caminho médios muito curtos. O coeficiente de agrupamento desse modelo também tende a 0. Enquanto o diâmetro, D, de muitos modelos, incluindo o modelo de gráfico aleatório Erdős Rényi e várias redes de pequenos mundos é proporcional a log N, o modelo BA exibe D ~ loglogN (mundo ultrasmall). Observe que o comprimento médio do caminho é dimensionado com N como o diâmetro.

Fixação preferencial não linear

Na fixação preferencial não linear (NLPA), os nós existentes na rede ganham novas arestas proporcionalmente ao grau do nó elevado a uma potência positiva constante ,. Formalmente, isso significa que a probabilidade de que o nó ganhe uma nova aresta é dada por ${\ displaystyle \ alpha}$ ${\ displaystyle i}$

{\ displaystyle p_ {i} = {\ frac {k_ {i} ^ {\ alpha}} {\ sum _ {j} k_ {j} ^ {\ alpha}}}.}

Se , o NLPA se reduz ao modelo BA e é referido como "linear". Se , NLPA é referido como "sublinear" e o grau de distribuição da rede tende a uma

distribuição exponencial esticada . Se , o NLPA é referido como "superlinear" e um pequeno número de nós se conecta a quase todos os outros nós da rede. Para ambos e , a propriedade de escala livre da rede é quebrada no limite do tamanho infinito do sistema. No entanto, se for apenas ligeiramente maior do que , o NLPA pode resultar em distribuições de graus que parecem ser transitoriamente sem escala.

{\ displaystyle \ alpha = 1}

{\ displaystyle 0 <\ alpha <1}

{\ displaystyle \ alpha> 1}

{\ displaystyle \ alpha <1}

{\ displaystyle \ alpha> 1}

{\ displaystyle \ alpha}

{\ displaystyle 1}

Modelo de anexo orientado por mediação (MDA)

No modelo de anexo dirigido por mediação (MDA) em que um novo nó que vem com arestas escolhe um nó existente conectado aleatoriamente e então se conecta não com aquele, mas com seus vizinhos escolhidos também aleatoriamente. A probabilidade de que o nó do nó existente escolhido é ${\ displaystyle m}$ ${\ displaystyle m}$ ${\ displaystyle \ Pi (i)}$ ${\ displaystyle i}$

{\ displaystyle \ Pi (i) = {\ frac {k_ {i}} {N}} {\ frac {\ sum _ {j = 1} ^ {k_ {i}} {\ frac {1} {k_ { j}}}} {k_ {i}}}.}

O fator é o inverso da média harmônica (IHM) dos graus dos vizinhos de um nó . A investigação numérica extensiva sugere que para um valor IHM aproximadamente médio no limite grande se torna uma constante, o que significa . Isso implica que quanto mais altos os links (grau) de um nó, maior sua chance de ganhar mais links, uma vez que eles podem ser alcançados em um número maior de maneiras através de mediadores que essencialmente incorporam a ideia intuitiva de mecanismo de enriquecimento rico (ou o mecanismo preferencial regra de fixação do modelo Barabasi-Albert). Portanto, a rede MDA pode ser vista seguindo a regra PA, mas disfarçada. ${\ displaystyle {\ frac {\ sum _ {j = 1} ^ {k_ {i}} {\ frac {1} {k_ {j}}}} {k_ {i}}}}$ ${\ displaystyle k_ {i}}$ ${\ displaystyle i}$ ${\ displaystyle m> 14}$ ${\ displaystyle N}$ ${\ displaystyle \ Pi (i) \ propto k_ {i}}$

No entanto, para descrever o vencedor leva todo o mecanismo, pois descobrimos que quase do total de nós têm grau um e um é super rico em grau. À medida que o valor aumenta, a disparidade entre os super-ricos e os pobres diminui e à medida que encontramos um mecanismo de transição do rico para o super rico para o rico. ${\ displaystyle m = 1}$ ${\ displaystyle 99 \%}$ ${\ displaystyle m}$ ${\ displaystyle m> 14}$

Modelo de fitness

Outro modelo onde o ingrediente chave é a natureza do vértice foi introduzido por Caldarelli et al. Aqui, uma ligação é criada entre dois vértices com uma probabilidade dada por uma função de ligação das

aptidões dos vértices envolvidos. O grau de um vértice i é dado por

{\ displaystyle i, j}

{\ displaystyle f (\ eta _ {i}, \ eta _ {j})}

{\ displaystyle k (\ eta _ {i}) = N \ int _ {0} ^ {\ infty} f (\ eta _ {i}, \ eta _ {j}) \ rho (\ eta _ {j} ) \, d \ eta _ {j}}

Se for uma função invertível e crescente de , então a distribuição de probabilidade é dada por ${\ displaystyle k (\ eta _ {i})}$ ${\ displaystyle \ eta _ {i}}$ ${\ displaystyle P (k)}$

{\ displaystyle P (k) = \ rho (\ eta (k)) \ cdot \ eta '(k)}

Como resultado, se as aptidões são distribuídas como uma lei de potência, o grau do nó também o faz. ${\ displaystyle \ eta}$

Menos intuitivamente, com uma distribuição de probabilidade de decadência rápida, juntamente com uma função de ligação do tipo ${\ displaystyle \ rho (\ eta) = e ^ {- \ eta}}$

{\ displaystyle f (\ eta _ {i}, \ eta _ {j}) = \ Theta (\ eta _ {i} + \ eta _ {j} -Z)}

com uma constante e a função Heavyside, também obtemos redes sem escala. ${\ displaystyle Z}$ ${\ displaystyle \ Theta}$

Esse modelo foi aplicado com sucesso para descrever o comércio entre as nações usando o PIB como adequação para os vários nós e uma função de ligação do tipo ${\ displaystyle i, j}$

{\ displaystyle {\ frac {\ delta \ eta _ {i} \ eta _ {j}} {1+ \ delta \ eta _ {i} \ eta _ {j}}}.}

Análise de rede

Análise de rede social

A análise de

redes sociais examina a estrutura das relações entre entidades sociais. Essas entidades geralmente são pessoas, mas também podem ser grupos , organizações , estados-nação , sites da Web , publicações acadêmicas .

Desde a década de 1970, o estudo empírico das redes tem desempenhado um papel central nas ciências sociais, e muitas das ferramentas matemáticas e estatísticas usadas para estudar as redes foram desenvolvidas pela primeira vez na sociologia . Entre muitas outras aplicações, a análise de redes sociais tem sido usada para entender a difusão de inovações , notícias e rumores. Da mesma forma, tem sido usado para examinar a propagação de doenças e comportamentos relacionados à saúde . Também foi aplicado ao estudo de mercados , onde foi usado para examinar o papel da confiança nas relações de troca e dos mecanismos sociais na fixação de preços. Da mesma forma, tem sido usado para estudar o recrutamento em movimentos políticos e organizações sociais. Também tem sido usado para conceituar divergências científicas, bem como prestígio acadêmico. Na literatura sobre aquisição de segunda língua, ele tem uma história estabelecida em pesquisas de estudo no exterior, revelando como as redes de interação entre colegas de aprendizagem influenciam o progresso da língua. Mais recentemente, a análise de rede (e sua prima próxima análise de tráfego ) ganhou um uso significativo na inteligência militar, para descobrir redes insurgentes de natureza hierárquica e sem liderança . Na criminologia , ele está sendo usado para identificar atores influentes em gangues criminosas, movimentos de criminosos, co-infratores, prever atividades criminosas e fazer políticas.

Análise de rede dinâmica

A análise de rede dinâmica examina a mudança da estrutura das relações entre diferentes classes de entidades em efeitos de sistemas sociotécnicos complexos e reflete a estabilidade social e as mudanças, como o surgimento de novos grupos, tópicos e líderes. A Análise de Rede Dinâmica se concentra em meta-redes compostas de vários tipos de nós (entidades) e vários tipos de links . Essas entidades podem ser muito variadas. Os exemplos incluem pessoas, organizações, tópicos, recursos, tarefas, eventos, locais e crenças.

As técnicas de rede dinâmica são particularmente úteis para avaliar tendências e mudanças nas redes ao longo do tempo, identificar líderes emergentes e examinar a coevolução de pessoas e ideias.

Análise de rede biológica

Com a recente explosão de dados biológicos de alto rendimento publicamente disponíveis, a análise de redes moleculares ganhou um interesse significativo. O tipo de análise neste conteúdo está intimamente relacionado à análise de rede social, mas geralmente se concentra em padrões locais na rede. Por exemplo, os motivos da rede são pequenos subgráficos que estão sobre-representados na rede. Motivos de atividade são padrões super-representados semelhantes nos atributos de nós e arestas na rede que são super-representados dada a estrutura da rede. A análise das redes biológicas levou ao desenvolvimento da medicina em rede , que analisa o efeito das doenças no interactome .

Análise de link

A análise de link é um subconjunto da análise de rede, explorando associações entre objetos. Um exemplo pode ser o exame dos endereços de suspeitos e vítimas, os números de telefone para os quais discaram e as transações financeiras das quais participaram durante um determinado período de tempo e as relações familiares entre esses sujeitos como parte da investigação policial. A análise de link aqui fornece os relacionamentos e associações cruciais entre muitos objetos de diferentes tipos que não são aparentes a partir de informações isoladas. A análise de link assistida por computador ou totalmente automática baseada em computador é cada vez mais empregada por bancos e agências de seguros na detecção de fraude , por operadoras de telecomunicações em análise de rede de telecomunicações, pelo setor médico em epidemiologia e farmacologia , em investigações de aplicação da lei , por motores de busca para classificação de relevância (e, inversamente, pelos spammers para spamdexing e pelos proprietários de negócios para otimização de mecanismo de pesquisa ) e em todos os outros lugares onde as relações entre muitos objetos devem ser analisadas.

Robustez da rede

A robustez estrutural das redes é estudada usando a teoria da percolação . Quando uma fração crítica de nós é removida, a rede se torna fragmentada em pequenos clusters. Este fenômeno é denominado percolação e representa um tipo de desordem de ordem de transição de fase com expoentes críticos .

Análise pandêmica

O modelo SIR é um dos algoritmos mais conhecidos para prever a propagação de pandemias globais em uma população infecciosa.

Susceptível a infectado

{\ displaystyle S = \ beta \ left ({\ frac {1} {N}} \ right)}

A fórmula acima descreve a "força" de infecção para cada unidade suscetível em uma população infecciosa, onde $β$ é equivalente à taxa de transmissão da referida doença.

Para rastrear a mudança daqueles suscetíveis em uma população infecciosa:

{\ displaystyle \ Delta S = \ beta \ times S {1 \ over N} \, \ Delta t}

Infectado para recuperado

{\ displaystyle \ Delta I = \ mu I \, \ Delta t}

Com o tempo, o número de infectados flutua por: a taxa especificada de recuperação, representada por, mas deduzida a um durante o período infeccioso médio , a numeração de indivíduos infecciosos e a mudança no tempo ,. ${\ displaystyle \ mu}$ ${\ displaystyle {1 \ over \ tau}}$ ${\ displaystyle I}$ ${\ displaystyle \ Delta t}$

Período infeccioso

Se uma população será superada por uma pandemia, no que diz respeito ao modelo SIR, depende do valor de ou da "média de pessoas infectadas por um indivíduo infectado". ${\ displaystyle R_ {0}}$

{\ displaystyle R_ {0} = \ beta \ tau = {\ beta \ over \ mu}}

Análise de link da web

Vários busca Web do ranking algoritmos utilizam métricas baseadas em links de centralidade, incluindo (em ordem de aparição) Marchiori 's Hiper busca , Google ' s PageRank , do Kleinberg HITS algoritmo , os CheiRank e TrustRank algoritmos. A análise de links também é realizada na ciência da informação e na ciência da comunicação, a fim de compreender e extrair informações da estrutura das coleções de páginas da web. Por exemplo, a análise pode ser da interligação entre sites ou blogs de políticos.

Ranking da página

O PageRank funciona escolhendo "nós" ou sites aleatoriamente e, em seguida, com uma certa probabilidade, "pulando aleatoriamente" para outros nós. Ao saltar aleatoriamente para esses outros nós, ele ajuda o PageRank a atravessar completamente a rede, pois algumas páginas da Web existem na periferia e não seriam avaliadas tão prontamente.

Cada nó ,, tem um PageRank conforme definido pela soma de páginas vinculadas a vezes um sobre os links externos ou "grau externo" de vezes a "importância" ou PageRank de . ${\ displaystyle x_ {i}}$ ${\ displaystyle j}$ ${\ displaystyle i}$ ${\ displaystyle j}$ ${\ displaystyle j}$

{\ displaystyle x_ {i} = \ sum _ {j \ rightarrow i} {1 \ over N_ {j}} x_ {j} ^ {(k)}}

Salto aleatório

Conforme explicado acima, o PageRank lista saltos aleatórios nas tentativas de atribuir o PageRank a todos os sites da Internet. Estes saltos aleatórios encontrar sites que não podem ser encontrados durante as metodologias de pesquisa normais, como em largura Pesquisa e Depth-Primeira Pesquisa .

Em uma melhoria sobre a fórmula acima mencionada para determinar o PageRank inclui a adição desses componentes de salto aleatório. Sem os saltos aleatórios, algumas páginas receberiam um PageRank de 0, o que não seria bom.

A primeira é , ou a probabilidade de ocorrer um salto aleatório. O contraste é o "fator de amortecimento", ou . ${\ displaystyle \ alpha}$ ${\ displaystyle 1- \ alpha}$

{\ displaystyle R {(p)} = {\ alpha \ over N} + (1- \ alpha) \ sum _ {j \ rightarrow i} {1 \ over N_ {j}} x_ {j} ^ {(k )}}

Outra maneira de ver isso:

{\ displaystyle R (A) = \ sum {R_ {B} \ over B _ {\ text {(outlinks)}}} + \ cdots + {R_ {n} \ over n _ {\ text {(outlinks)}}} }

Medidas de centralidade

Informações sobre a importância relativa de nós e arestas em um grafo podem ser obtidas por meio de medidas de centralidade , amplamente utilizadas em disciplinas como a sociologia . Medidas de centralidade são essenciais quando uma análise de rede precisa responder a perguntas como: "Quais nós da rede devem ser direcionados para garantir que uma mensagem ou informação se espalhe para todos ou a maioria dos nós da rede?" ou, inversamente, "Quais nódulos devem ser direcionados para reduzir a propagação de uma doença?". As medidas de centralidade formalmente estabelecidas são centralidade de grau , centralidade de proximidade , centralidade de intermediação , centralidade de autovetor e centralidade de katz . O objetivo da análise de rede geralmente determina o tipo de medida (s) de centralidade a ser usada.

O grau de centralidade de um nó em uma rede é o número de links (vértices) incidentes no nó.
A centralidade de proximidade determina o quão "perto" um nó está de outros nós em uma rede medindo a soma das distâncias mais curtas (caminhos geodésicos) entre aquele nó e todos os outros nós na rede.
A centralidade de intermediação determina a importância relativa de um nó medindo a quantidade de tráfego que flui através desse nó para outros nós na rede. Isso é feito medindo a fração de caminhos conectando todos os pares de nós e contendo o nó de interesse. A centralidade do grupo mede a quantidade de tráfego que flui através de um grupo de nós.
A centralidade de autovetor é uma versão mais sofisticada da centralidade de grau, em que a centralidade de um nó não depende apenas do número de links incidentes no nó, mas também da qualidade desses links. Este fator de qualidade é determinado pelos autovetores da matriz de adjacência da rede.
A centralidade Katz de um nó é medida somando os caminhos geodésicos entre aquele nó e todos os nós (alcançáveis) na rede. Esses caminhos são ponderados, os caminhos que conectam o nó com seus vizinhos imediatos carregam pesos maiores do que aqueles que se conectam com nós mais distantes dos vizinhos imediatos.

Disseminação de conteúdo nas redes

O conteúdo em uma rede complexa pode se espalhar por meio de dois métodos principais: disseminação conservada e disseminação não conservada. Na propagação conservada, a quantidade total de conteúdo que entra em uma rede complexa permanece constante à medida que ela passa. O modelo de propagação conservada pode ser melhor representado por um jarro contendo uma quantidade fixa de água sendo despejada em uma série de funis conectados por tubos. Aqui, o jarro representa a fonte original e a água é o conteúdo a ser espalhado. Os funis e os tubos de conexão representam os nós e as conexões entre os nós, respectivamente. Conforme a água passa de um funil para outro, a água desaparece instantaneamente do funil que foi previamente exposto à água. Na propagação não conservada, a quantidade de conteúdo muda à medida que entra e passa por uma rede complexa. O modelo de propagação não conservada pode ser mais bem representado por uma torneira em execução contínua, passando por uma série de funis conectados por tubos. Aqui, a quantidade de água da fonte original é infinita. Além disso, quaisquer funis que tenham sido expostos à água continuam a sentir a água mesmo quando ela passa em funis sucessivos. O modelo não conservado é o mais adequado para explicar a transmissão da maioria das doenças infecciosas .

O modelo SIR

Em 1927, WO Kermack e AG McKendrick criaram um modelo no qual consideraram uma população fixa com apenas três compartimentos, suscetível:, infectado , e recuperado ,. Os compartimentos usados para este modelo consistem em três classes: ${\ displaystyle S (t)}$ ${\ displaystyle I (t)}$ ${\ displaystyle R (t)}$

${\ displaystyle S (t)}$ é usado para representar o número de indivíduos ainda não infectados com a doença no tempo t, ou aqueles suscetíveis à doença
${\ displaystyle I (t)}$ denota o número de indivíduos que foram infectados com a doença e são capazes de propagar a doença para aqueles na categoria suscetível
${\ displaystyle R (t)}$ é o compartimento usado para aqueles indivíduos que foram infectados e depois se recuperaram da doença. Aqueles nesta categoria não podem ser infectados novamente ou transmitir a infecção a outras pessoas.

O fluxo deste modelo pode ser considerado da seguinte forma:

{\ displaystyle {\ mathcal {S}} \ rightarrow {\ mathcal {I}} \ rightarrow {\ mathcal {R}}}

Usando uma população fixa ,, Kermack e McKendrick derivaram as seguintes equações: ${\ displaystyle N = S (t) + I (t) + R (t)}$

{\ displaystyle {\ begin {align} {\ frac {dS} {dt}} & = - \ beta SI \\ [8pt] {\ frac {dI} {dt}} & = \ beta SI- \ gamma I \ \ [8pt] {\ frac {dR} {dt}} & = \ gamma I \ end {alinhado}}}

Várias suposições foram feitas na formulação dessas equações: Primeiro, um indivíduo na população deve ser considerado como tendo uma probabilidade igual a qualquer outro indivíduo de contrair a doença com uma taxa de , que é considerada a taxa de contato ou infecção da doença . Portanto, um indivíduo infectado faz contato e é capaz de transmitir a doença com outros por unidade de tempo e a fração de contatos de um infectado com um suscetível é . O número de novas infecções em unidade de tempo por infectante então é , dando a taxa de novas infecções (ou aquelas que saem da categoria suscetível) como (Brauer & Castillo-Chavez, 2001). Para a segunda e terceira equações, considere a população que sai da classe suscetível como igual ao número que entra na classe infectada. No entanto, os infectivos estão deixando essa classe por unidade de tempo para entrar na classe recuperada / removida a uma taxa por unidade de tempo (onde representa a taxa média de recuperação ou o período médio de infecção). Esses processos que ocorrem simultaneamente são chamados de Lei de Ação de Massa , uma ideia amplamente aceita de que a taxa de contato entre dois grupos em uma população é proporcional ao tamanho de cada um dos grupos envolvidos (Daley & Gani, 2005). Finalmente, presume-se que a taxa de infecção e recuperação é muito mais rápida do que a escala de tempo de nascimentos e óbitos e, portanto, esses fatores são ignorados neste modelo. ${\ displaystyle \ beta}$ ${\ displaystyle \ beta N}$ ${\ displaystyle S / N}$ ${\ displaystyle \ beta N (S / N)}$ ${\ displaystyle \ beta N (S / N) I = \ beta SI}$ ${\ displaystyle \ gamma}$ ${\ displaystyle \ gamma}$ ${\ displaystyle 1 / \ gamma}$

Mais pode ser lido sobre este modelo na página de modelo de Epidemia .

A abordagem da equação mestre

Uma equação mestre pode expressar o comportamento de uma rede em crescimento não direcionado onde, a cada passo de tempo, um novo nó é adicionado à rede, vinculado a um nó antigo (escolhido aleatoriamente e sem preferência). A rede inicial é formada por dois nós e dois links entre eles ao mesmo tempo , esta configuração é necessária apenas para simplificar os cálculos posteriores, para que no momento a rede possua nós e links. ${\ displaystyle t = 2}$ ${\ displaystyle t = n}$ ${\ displaystyle n}$ ${\ displaystyle n}$

A equação mestre para esta rede é:

{\ displaystyle p (k, s, t + 1) = {\ frac {1} {t}} p (k-1, s, t) + \ left (1 - {\ frac {1} {t}} \ right) p (k, s, t),}

onde é a probabilidade de ter o nó com grau no momento e é o intervalo de tempo em que esse nó foi adicionado à rede. Observe que existem apenas duas maneiras de um nó antigo ter links no momento : ${\ displaystyle p (k, s, t)}$ ${\ displaystyle s}$ ${\ displaystyle k}$ ${\ displaystyle t + 1}$ ${\ displaystyle s}$ ${\ displaystyle s}$ ${\ displaystyle k}$ ${\ displaystyle t + 1}$

O nó tem grau no tempo e será ligado pelo novo nó com probabilidade ${\ displaystyle s}$ ${\ displaystyle k-1}$ ${\ displaystyle t}$ ${\ displaystyle 1 / t}$
Já possui graduação no momento e não será vinculado pelo novo nó. ${\ displaystyle k}$ ${\ displaystyle t}$

Depois de simplificar este modelo, a distribuição de graus é ${\ displaystyle P (k) = 2 ^ {- k}.}$

Com base nesta rede crescente, um modelo de epidemia é desenvolvido seguindo uma regra simples: Cada vez que o novo nó é adicionado e após a escolha do nó antigo para vincular, é tomada uma decisão: se esse novo nó será infectado ou não. A equação mestre para este modelo epidêmico é:

{\ displaystyle p_ {r} (k, s, t) = r_ {t} {\ frac {1} {t}} p_ {r} (k-1, s, t) + \ left (1 - {\ frac {1} {t}} \ right) p_ {r} (k, s, t),}

onde representa a decisão de infectar ( ) ou não ( ). Resolvendo esta equação mestre, a seguinte solução é obtida: ${\ displaystyle r_ {t}}$ ${\ displaystyle r_ {t} = 1}$ ${\ displaystyle r_ {t} = 0}$ ${\ displaystyle {\ tilde {P}} _ {r} (k) = \ left ({\ frac {r} {2}} \ right) ^ {k}.}$

Redes interdependentes

Uma rede interdependente é um sistema de redes acopladas em que os nós de uma ou mais redes dependem dos nós de outras redes. Essas dependências são aprimoradas pelos desenvolvimentos em tecnologia moderna. As 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. Os apagões são uma demonstração fascinante do importante papel desempenhado pelas dependências entre as redes. Um estudo recente desenvolveu uma estrutura para estudar as falhas em cascata em um sistema de redes interdependentes usando a teoria da percolação.

Redes multicamadas

Redes multicamadas são redes com vários tipos de relações. As tentativas de modelar sistemas do mundo real como redes multidimensionais têm sido usadas em vários campos, como análise de redes sociais, economia, história, transporte urbano e internacional, ecologia, psicologia, medicina, biologia, comércio, climatologia, física, neurociência computacional, gerenciamento de operações e finanças.

Otimização de rede

Os problemas de rede que envolvem encontrar uma maneira ideal de fazer algo são estudados sob o nome de otimização combinatória . Exemplos incluem fluxo de rede , menor problema de caminho , problema de transporte , problema de transbordo , localização problema , problema de correspondência , problema de atribuição , problema de embalagem , problema de roteamento , Análise De Caminho Crítico e PERT (Programa de Avaliação e Revisão Técnica).

Veja também

Referências

Leitura adicional

A First Course in Network Science , F. Menczer , S. Fortunato, CA Davis. (Cambridge University Press, 2020). ISBN 9781108471138 . Site GitHub com tutoriais, conjuntos de dados e outros recursos
"Conectado: o poder dos seis graus," https://web.archive.org/web/20111006191031/http://ivl.slis.indiana.edu/km/movies/2008-talas-connected.mov
Cohen, R .; Erez, K. (2000). "Resiliência da Internet à repartição aleatória" . Phys. Rev. Lett . 85 (21): 4626–4628. arXiv : cond-mat / 0007048 . Bibcode : 2000PhRvL..85.4626C . CiteSeerX 10.1.1.242.6797 . doi : 10.1103 / physrevlett.85.4626 . PMID 11082612 . S2CID 15372152 .
Pu, Cun-Lai; Wen-; Pei, Jiang; Michaelson, Andrew (2012). "Análise de robustez de controlabilidade de rede" (PDF) . Physica A . 391 (18): 4420–4425. Bibcode : 2012PhyA..391.4420P . doi : 10.1016 / j.physa.2012.04.019 . Arquivado do original (PDF) em 13/10/2016 . Página visitada em 2013-09-18 .
"Perfil do líder: The Burgeoning Field of Network Science, The Military Engineer recentemente teve a oportunidade de falar com Frederick I. Moxley, Ph.D," https://web.archive.org/web/20190215025457/http://themilitaryengineer .com / index.php / item / 160-leader-profile-the-crescente-field-of-network-science
SN Dorogovtsev e JFF Mendes, Evolução das redes: das redes biológicas à Internet e WWW , Oxford University Press, 2003, ISBN 0-19-851590-1
Linked: The New Science of Networks , A.-L. Barabási (Perseus Publishing, Cambridge)
' Scale-Free Networks , G. Caldarelli (Oxford University Press, Oxford)
Network Science , Committee on Network Science for Future Army Applications, Conselho Nacional de Pesquisa. 2005. The National Academies Press (2005) ISBN 0-309-10026-7
Network Science Bulletin , USMA (2007) ISBN 978-1-934808-00-9
The Structure and Dynamics of Networks Mark Newman, Albert-László Barabási, & Duncan J. Watts (The Princeton Press, 2006) ISBN 0-691-11357-2
Processos dinâmicos em redes complexas , Alain Barrat, Marc Barthelemy, Alessandro Vespignani (Cambridge University Press, 2008) ISBN 978-0-521-87950-7
Network Science: Theory and Applications , Ted G. Lewis (Wiley, 11 de março de 2009) ISBN 0-470-33188-7
Nexus: Pequenos Mundos e a Teoria das Redes Inovadoras , Mark Buchanan (WW Norton & Company, junho de 2003) ISBN 0-393-32442-7
Six Degrees: The Science of a Connected Age , Duncan J. Watts (WW Norton & Company, 17 de fevereiro de 2004) ISBN 0-393-32542-3
Kitsak, M .; Gallos, LK; Havlin, S .; Liljeros, F .; Muchnik, L .; Stanley, HE; Makse, HA (2010). "Disseminadores influentes nas redes" . Nature Physics . 6 (11): 888–893. arXiv : 1001.5285 . Bibcode : 2010NatPh ... 6..888K . CiteSeerX 10.1.1.366.2543 . doi : 10.1038 / nphys1746 . S2CID 1294608 .

Languages

In other projects