Mostrar código-fonte de Ciência das redes

{{Ciência da Rede}}

'''Ciência das redes''' é um campo académico [[Interdisciplinaridade|interdisciplinar]] que estuda redes complexas tais como redes de telecomunicações, redes de computadores, redes biológicas, redes cognitivas, redes semânticas e [[Rede social|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."<ref name="NRC">{{citar livro|título=Network Science |autor =Committee on Network Science for Future Army Applications |publicado=National Research Council |isbn=0309653886 |ano=2006 |url=http://www.nap.edu/catalog/11516.html}}</ref>

== 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<ref>{{Citar periódico |url=https://www.nature.com/articles/017284a0 |título=Chemistry and Algebra |data=1878-02 |acessodata=2024-09-26 |periódico=Nature |número=432 |ultimo=Sylvester |primeiro=J. J. |paginas=284–284 |lingua=en |doi=10.1038/017284a0 |issn=0028-0836}}</ref>.

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 <ref>{{citar livro|url=https://archive.org/details/whoshallsurvivef00more/|título=Who shall survive? Foundations of sociometry, group psychotherapy and sociodrama|ultimo=Moreno|primeiro=Jacob Levy|editora=Beacon House|ano=1953|local=Beacon, New York}}</ref>. 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]] <ref>{{citar periódico |url=https://www.proquest.com/newspapers/emotions-mapped-new-geography/docview/100744844/se-2 |título=EMOTIONS MAPPED BY NEW GEOGRAPHY: CHARTS SEEK TO PORTRAY THE PSYCHOLOGICAL CURRENTS OF HUMAN RELATIONSHIPS. FIRST STUDIES EXHIBITED COLORED LINES SHOW LIKES AND DISLIKES OF INDIVIDUALS AND OF GROUPS. MANY MISFITS REVEALED DR. J.L. MORENO CALCULATES THERE ARE 10 TO 15 MILLION ISOLATED INDIVIDUALS IN NATION |data=1933-04-17 |acessodata=2024-09-26 |periódico=New York Times |publicado=New York Times |pagina=17}}</ref>. 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<ref>{{Citar web|ultimo=CONCER|primeiro=Ronald|url=https://www.ronaldconcer.com/desenvolvimento|titulo=Desenvolvimento da Ciência das Redes|acessodata=2023-03-13|website=Dr. Ronald Concer|lingua=pt}}</ref>.

A Teoria probabilística na ciência das redes que foi desenvolvida a partir da teoria dos grafos por [[Paul Erdős]] e [[Alfred Rényi|Alfréd Rényi]] nos [[Modelo Erdős–Rényi|oito famosos trabalhos sobre grafos aleatórios]]. Para redes sociais o modelo grafo aleatório exponencial ou <math>p*</math> é 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<ref>{{Citar periódico |url=https://www.heinz.cmu.edu/faculty-research/profiles/krackhardt-davidm/_files/1998-pcans-model-structure-in-organizations.pdf |título=A PCANS model of structure in organization |data=1988 |acessodata=2024-09-26 |periódico=Proceedings of the 1998 International Symposium on Command and Control Research  and Technology |número= |ultimo=Krackhardt |primeiro=David |ultimo2=Carley |primeiro2=Kathleen M. |paginas=113-119 |doi= |issn=}}</ref>. 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]] <ref>{{Citar periódico |url=https://www.nature.com/articles/30918 |título=Collective dynamics of ‘small-world’ networks |data=1998-06 |acessodata=2024-09-26 |periódico=Nature |número=6684 |ultimo=Watts |primeiro=Duncan J. |ultimo2=Strogatz |primeiro2=Steven H. |paginas=440–442 |lingua=en |doi=10.1038/30918 |issn=0028-0836}}</ref>. [[Albert-László Barabási]] e Reka Albert desenvolveram a rede livre de escala<ref>{{Citar periódico |url=https://www.science.org/doi/10.1126/science.286.5439.509 |título=Emergence of Scaling in Random Networks |data=1999-10-15 |acessodata=2024-09-26 |periódico=Science |número=5439 |ultimo=Barabási |primeiro=Albert-László |ultimo2=Albert |primeiro2=Réka |paginas=509–512 |lingua=en |doi=10.1126/science.286.5439.509 |issn=0036-8075}}</ref> 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 <math>D</math> de uma rede é definida como uma relação entre o número de arestas <math>E</math> para o número de arestas possíveis, dada pelo coeficiente binomial  <math>\tbinom N2</math>, dando <math>D = \frac{2E}{N(N-1)}.</math>

=== Tamanho ===
O tamanho de uma rede pode referir-se o número de nós <math>N</math> ou, menos comumente, o número de arestas <math>E</math> que pode variar de  <math>N-1</math> (uma árvore) para <math>E_{max}</math> (um grafo completo).

=== Grau médio  ===
O grau  <math>k</math> de um nó é o número de arestas conectadas a ele. Intimamente relacionado com a densidade de uma rede é o grau médio, <math><k> = \tfrac{2E}{N}</math>. INo modelo ER grafo aleatório, podemos calcular  <math><k> = pN(N-1)</math> onde <math>p</math> é 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  <math>i</math>nó é:
<math>C_i = {2e_i\over k_i{(k_i - 1)}}\,,</math>
Onde <math>k_i</math> é o número de vizinhos do  <math>i</math>nó, e  <math>e_i</math> ié o número de conexões entre esses vizinhos. O maior número possível de conexões entre vizinhos é, naturalmente,
:<math>{\binom {k}{2}} = {{k(k-1)}\over 2}\,.</math>

=== 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 ===
[[Imagem:ER model.svg|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  <math>N</math> e a probabilidade de que uma ligação deve ser formada entre quaisquer dois nós como <math>p</math>.
Uma constante  <math><k></math> que pode ser derivada destes dois componentes com a fórmula  <math><k> = 2E/N = p(N-1)</math>.

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: <math>P(\operatorname{deg}(v) = k) = {n-1\choose k}p^k(1-p)^{n-1-k}</math>. 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 <k> > 1 num processo chamado percolação. O comprimento do percurso médio é relativamente curto neste modelo e tende para  <math>log(N)</math>.

=== Modelo Watts-Strogatz pequeno mundo  ===
[[Imagem:Watts-Strogatz-rewire.png|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. <math><k> = 4</math>]]

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 <math><k></math> vizinhos mais próximos. Outro parâmetro é especificado como a probabilidade de religação. Cada aresta tem uma probabilidade. <math>p</math> que vai ser religado ao grafo como uma aresta aleatória. O número esperado de religações no modelo é <math>pE = pN<k>/2</math>.

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  ''m''<sub>0</sub> nós.  ''m''<sub>0</sub>&nbsp;≥&nbsp;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 ''p''<sub>''i''</sub> que o novo nó está conectado ao nó  ''i'' is<ref name=RMP>{{citar periódico
 | url =http://www.nd.edu/~networks/Publication%20Categories/03%20Journal%20Articles/Physics/StatisticalMechanics_Rev%20of%20Modern%20Physics%2074,%2047%20(2002).pdf
 |autor = Albert-László Barabási & Réka Albert
 |título= Statistical mechanics of complex networks
 |periódico= [[Reviews of Modern Physics]]
 | volume = 74
 |páginas= 47–97
 |ano= 2002
 | doi = 10.1103/RevModPhys.74.47
 | bibcode=2002RvMP...74...47A
 |arxiv = cond-mat/0106096 }}</ref>

: <math>p_i = \frac{k_i}{\sum_j k_j},</math>

onde ''k''<sub>''i''</sub> ié o grau do nó  ''i''. Nós fortemente vinculados ("hubs") tendem a acumular rapidamente ainda mais ligações, enquanto nós com apenas algumas ligações não são suscetíveis de ser escolhidos como destino para uma nova ligação. Os novos nós tem uma "preferência" para unir-se a nós já fortemente ligados.

[[File:Barabasi-albert model degree distribution.svg|thumb|O grau da distribuição do modelo BA, que segue uma lei de potência. Na escala Loglog a função lei de poder é uma linha reta.<ref name=Barabasi1999>{{citar periódico
 | url = http://www.nd.edu/~networks/Publication%20Categories/03%20Journal%20Articles/Physics/EmergenceRandom_Science%20286,%20509-512%20(1999).pdf
 |autor = Albert-László Barabási & Réka Albert
 |título= Emergence of scaling in random networks
 |periódico= [[Science (journal)|Science]]
 | volume = 286
 |páginas= 509–512
 |data=outubro de 1999
 | doi = 10.1126/science.286.5439.509
 |número=5439
 | pmid=10521342
|arxiv = cond-mat/9910332 |bibcode = 1999Sci...286..509B }}</ref>]]
A distribuição de grau resultantes do modelo BA escala livre, em particular, é uma lei de potência da forma:
: <math>P\left(k\right)\sim k^{-3} \, </math>

Hubs apresentam alto grau centralidade que permite a existência de caminhos curtos entre nós. Como resultado, o modelo BA tende a ter comprimentos de trajeto médio muito curto. O coeficiente de agregação desse modelo também tende a 0. Enquanto o diâmetro do grafo aleatório de Erdős Rényi D, é proporcional ao log N (pequeno mundo), para redes de escala livre devido à existência de Hubs D ~ loglogN (ultrapequeno mundo). Observe que a escala da média do comprimento do caminho tem N como o diâmetro.<ref>{{citar periódico|último =R. Cohen|primeiro =S. Havlin|título=Scale-free networks are ultrasmall|periódico=Phys. Rev. Lett|ano=2003|volume=90|páginas=058701|url=http://havlin.biu.ac.il/Publications.php?keyword=Scale-free+networks+are+ultrasmall&year=*&match=all}}</ref>
Note that the average opath length scale with N as the diameter.

==Análise de redes==
===Análise de redes sociais ===
A análise de Redes sociais examina a estrutura de relacionamentos entre entidades sociais.<ref>Wasserman, Stanley and Katherine Faust. 1994. ''Social Network Analysis: Methods and Applications.'' Cambridge: Cambridge University Press.
</ref> 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 .<ref name="Newman">Newman, M.E.J. ''Networks: An Introduction.'' Oxford University Press. 2010</ref>  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.<ref name=GT-33/><ref>{{Citar web |url=http://firstmonday.org/htbin/cgiwrap/bin/ojs/index.php/fm/article/view/941/863 |titulo=Network analysis of terrorist networks |acessodata=2013-02-24 |arquivourl=https://web.archive.org/web/20121123010939/http://firstmonday.org/htbin/cgiwrap/bin/ojs/index.php/fm/article/view/941/863 |arquivodata=2012-11-23 |urlmorta=yes }}</ref>

===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.

====Robustez da rede====
Robustez da rede <ref>{{citar livro|título= Complex Networks: Structure, Robustness and Function |autor =R. Cohen, S. Havlin|ano= 2010 |publicado= Cambridge University Press |url= http://havlin.biu.ac.il/Shlomo%20Havlin%20books_com_net.php}}</ref> é estudada usando a teoria de percolação . Quando uma fração crítica de nós é removida da rede torna-se fragmentado em pequenos grupos. Este fenômeno é chamado de percolação<ref>{{citar livro|título= Fractals and Disordered Systems |autor =A. Bunde, S. Havlin|ano= 1996 |publicado= Springer |url= http://havlin.biu.ac.il/Shlomo%20Havlin%20books_fds.php}}</ref> e representa um tipo de ordem-desordem de fase de transição com expoentes críticos.

====Análise de pandemia====
O Modelo SIR é um dos mais conhecidos algoritmos para prever a disseminação de pandemias globais dentro de uma população infecciosa.

=====Suscetíveis de ser infetados=====
<math>S = \beta(1/N)</math>

A fórmula acima descreve a "força" de infeção para cada unidade suscetível numa população infetada, onde
{{math|&beta;}} é equivalente a taxa de transmissão da referida doença.

Para acompanhar a mudança dos mais suscetíveis de contrair uma infeção numa população infetada:

<math>\Delta S = \beta \times S {1\over N} \Delta t</math>

=====Infetados a recuperados=====
<math>\Delta I = \mu I\Delta t</math>

Ao longo do tempo, o número de pessoas infetadas flutua pela: taxa especificada de recuperação, representada por <math>\mu</math> mas deduzida para um sobre o período de contágio médio  <math>{1\over \tau}</math>, o número de indivíduos infetados, <math>I</math>, e a mudança no tempo, <math>\Delta t</math>.

=====Período de contágio=====
Se uma população poderá ou não superar uma pandemia, com relação ao modelo SIR, é dependente do valor de <math>R_0</math> or the "ou às "média de pessoas infetadas por um indivíduo infetado."

<math>R_0 = \beta\tau = {\beta\over\mu}</math>

====Análise de Ligações Web====
Vários algoritmos de ranking de pesquisas na Web usam métricas de centralidade baseada nas ligações, incluindo (por ordem de aparição) hiper busca Marchiori, Google PageRank, o algoritmo de HITS da Kleinberg, os algoritmos CheiRank e TrustRank. Análise de ligações também é realizado em ciências da informação e ciências da comunicação para entender e extrair informações a partir da estrutura das coleções de páginas da web. Por exemplo, a análise pode ser a da interligação dos políticos com web sites ou blogs.

=====PageRank=====
PageRank trabalha escolhendo aleatoriamente sites ou "nós" e, em seguida, com uma certa probabilidade, "aleatoriamente saltar" para outros nós. Aleatoriamente saltando para esses outros nós, ajuda o PageRank a atravessar completamente a rede como algumas páginas da Web existem na periferia e não seriam tão prontamente avaliadas.

Cada nó, <math>x_i</math>, tem um PageRank conforme definido pelo somatório das páginas <math>j</math> que apontam para  <math>i</math> tempos um para as ligações para fora ou "grau de saida" de <math>j</math> vezes a "importância" ou PageRank de  <math>j</math>.

<math>x_i = \sum_{j\rightarrow i}{1\over N_j}x_j^{(k)}</math>

======Salto aleatório======
Como explicado acima, o PageRank inscreve saltos aleatórios na tentativa de atribuir o PageRank de cada site na internet. Estes saltos aleatórios encontram sites que não podem ser encontrados durante as metodologias de pesquisa normais como pesquisa de amplitude e profundidade-primeira busca.

Uma melhoria em relação à fórmula acima para determinar o PageRank inclui adicionar a estes saltos aleatórios componentes. Sem os saltos aleatórios, algumas páginas receberiam um PageRank de 0, o que não seria bom.

O primeiro é  <math>\alpha</math>, ou a probabilidade de que ocorra um salto aleatório. O Contraste é o "fator de amortecimento", ou  <math>1 - \alpha</math>.

<math>R{(p)} = {\alpha\over N} + (1 - \alpha) \sum_{j\rightarrow i}{1\over N_j}x_j^{(k)}</math>

Outra maneira de olhar para ele:

<math>R(A) = \sum {R_B\over B_{(outlinks)}} + ... + {R_n \over n_{(outlinks)}}</math>

===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.

*'''Grau de centralidade ''' de um nó numa rede é o número de ligações (vértices) no nó.
*'''Centralidade de proximidade ''' determina quão perto um nó de outros nós numa rede, medindo-se a soma das distâncias mais curtas (caminhos geodésicos) entre o nó e todos os outros nós na rede.
*'''Centralidade de Intermediação ''' determina a importância relativa de um nó, medindo a quantidade de tráfego fluindo através desse nó para outros nós na rede. Isso é feito medindo a fração de caminhos que ligam todos os pares de nós e que contém o nó de interesse.
*'''Centralidade do vetor próprio ''' é uma versão mais sofisticada do grau de centralidade onde a centralidade de um nó não depende só do número de incidentes de ligações sobre o nó, mas também a qualidade dessas relações. Este fator de qualidade é determinado pelos vetores próprios da matriz de adjacência da rede.
*'''Centralidade Katz Prestige ''' de um nó é medido somando-se os caminhos geodésicos entre nó e todos os nós (alcançáveis) na rede. Esses caminhos são ponderados, caminhos que ligam o nó com os seus vizinhos imediatos têm um peso mais elevado do que aqueles que se conectam com os nós mais distantes dos vizinhos imediatos.

==Propagação de conteúdo em redes==

Conteúdo numa rede complexa pode espalhar-se através de dois métodos principais: propagação conservada e propagação não conservada.<ref>Newman, M., Barabási, A.-L., Watts, D.J. [eds.] (2006) The Structure and Dynamics of Networks. Princeton, N.J.: Princeton University Press.</ref>  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 <math>S(t)</math>, infetados , <math>I(t)</math>, e recuperados , <math>R(t)</math>. Os compartimentos utilizados para esta consistem no modelo três classes:

* <math>S(t)</math> é usado para representar o número de indivíduos ainda não infetados com a doença no tempo t, ou aqueles sensíveis à doença.
* <math>I(t)</math> indica o número de indivíduos que foram infetados com a doença e são capazes de propagar a doença para aqueles na categoria suscetível.
* <math>R(t)</math> é o compartimento usado para aqueles indivíduos que foram infectados e, em seguida, recuperados da doença. Os que estão nesta categoria não são capazes de ser infectados novamente ou transmitir a infeção para outras pessoas.

O fluxo deste modelo pode ser considerado como se segue:

: <math>\color{blue}\mathcal{S} \rightarrow \mathcal{I} \rightarrow \mathcal{R}</math>

Utilizando uma população fixa,  <math>N = S(t) + I(t) + R(t)</math>, KKermack e McKendrick derivam as seguintes equações:<br />
: <math>\frac{dS}{dt} = - \beta S I </math>
: <math>\frac{dI}{dt} = \beta S I - \gamma I </math>
: <math>\frac{dR}{dt} = \gamma I </math>

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 <math>\beta</math>, 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  <math>\beta N</math> outros, por unidade de tempo e a fração dos contatos por um infetado com um suscetível é  <math>S/N</math>.  O número de novas infeções em unidade de tempo por infetado é  <math>\beta N (S/N)</math>, então, dando a taxa de novas infeções (ou aqueles que deixam a categoria suscetível) como  <math>\beta N (S/N)I = \beta SI</math> (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 (<math>\gamma</math> que representa a taxa de recuperação média ou <math>1/\gamma</math>  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.

==Redes interdependentes==
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 .<ref>{{citar periódico|autor = S. V. Buldyrev, R. Parshani, G. Paul, H. E. Stanley, S. Havlin |título= Catastrophic cascade of failures in interdependent networks|periódico= Nature |volume = 464 |páginas= 1025–28 |ano= 2010 | doi=10.1038/nature08932 |número=7291|url=http://havlin.biu.ac.il/Publications.php?keyword=Catastrophic+cascade+of+failures+in+interdependent+networks&year=*&match=all |bibcode=2010Natur.464.1025B|arxiv = 0907.1182 }}</ref><ref>{{citar periódico|último =Jianxi Gao|primeiro =Sergey V. Buldyrev3, Shlomo Havlin4, and H. Eugene Stanley|título=Robustness of a Network of Networks|periódico=Phys. Rev. Lett|ano=2011|volume=107|páginas=195701|url=http://havlin.biu.ac.il/Publications.php?keyword=Robustness+of+a+Tree-like+Network+of+Interdependent+Networks&year=*&match=all | doi = 10.1103/PhysRevLett.107.195701|bibcode=2011PhRvL.107s5701G|arxiv = 1010.5829 }}</ref>

==Otimização de rede==

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).

==Análise de rede e ferramentas de visualização==
*Ferramenta de grafo e NetworkX, gratuito e módulos eficientes Python para manipulação e análise estatística de redes. [http://graph-tool.skewed.de/] [http://networkx.lanl.gov/]
*igraph, uma biblioteca de código aberto C para a análise de redes complexas em grande escala, com interfaces para R, Python e Ruby.
[http://igraph.sourceforge.net],
*Orange, um software de mineração de dados, módulo orngNetwork [http://www.ailab.si/orange/doc/modules/orngNetwork.htm orngNetwork]
*Pajek, programa para visualização e análise de (grandes) redes [http://pajek.imfm.si/doku.php].
*Tulip, uma enciclopédia de mineração de dados e software de visualização dedicado à análise e visualização de dados relacionais. [http://tulip.labri.fr/]

== Ver também ==
* [[Rede complexa]]
* [[:en:Collaborative_innovation_network#cite_note-:1-3|Collaborative innovation network]]
* [[Dynamic network analysis]]
* [[Lista de termos técnicos relacionados à teoria dos grafos]]
* [[Higher category theory]]
* [[Immune network theory]]
* [[Irregular warfare]]
* [[Polytely]]
* [[Teoria de sistemas]]
* [[Modelo erdõs-rényi]]
* [[Random networks]]
*[[Constructal law]]<ref>[http://www.constructal.org/en/art/Phil.%20Trans.%20R.%20Soc.%20B%20%282010%29%20365,%201335%961347.pdf] Bejan A., Lorente S., The Constructal Law of Design and Evolution in Nature. ''Philosophical Transactions of the Royal Society B'', Biological Science, Vol. 365, 2010, pp. 1335-1347.</ref>
*[[Percolação]]
*[[Network Theory in Risk Assessment]]
*[[Topologia de rede]]
*[[Network analyzer]]
*[[Small-world networks]]
*[[Social-circles network model|Social circles]]
*[[Redes Livre de Escala]]
*[[Sequential dynamical system]]
*[[PageRank]]
*[[Teoria das redes complexas]]

==Referências==

* "Network Science Center," http://www.dodccrp.org/files/Network_Science_Center.asf
* "Connected: The Power of Six Degrees," http://ivl.slis.indiana.edu/km/movies/2008-talas-connected.mov
* R. Cohen, K. Erez, D. ben-Avraham, S. Havlin, "[http://havlin.biu.ac.il/Publications.php?keyword=Resilience+of+the+Internet+to+random+breakdown&year=*&match=all Resilience of the Internet to random breakdown]" Phys. Rev. Lett. 85, 4626 (2000).
* R. Cohen, K. Erez, D. ben-Avraham, S. Havlin, "[http://havlin.biu.ac.il/Publications.php?keyword=Breakdown+of+the+Internet+under+intentional+attack&year=*&match=all Breakdown of the Internet under intentional attack]" Phys. Rev. Lett. 86, 3682 (2001)
* R. Cohen, S. Havlin, "[http://havlin.biu.ac.il/Publications.php?keyword=Scale-free+networks+are+ultrasmall&year=*&match=all Scale-free networks are ultrasmall]" Phys. Rev. Lett. 90, 058701 (2003)

==Mais Leituras==
* "The Burgeoning Field of Network Science," http://themilitaryengineer.com/index.php?option=com_content&task=view&id=88
* S.N. Dorogovtsev and J.F.F. Mendes, ''Evolution of Networks: From biological networks to the Internet and WWW'', Oxford University Press, 2003, ISBN 0-19-851590-1
* ''Linked: The New Science of Networks'', A.-L. Barabási (Perseus Publishing, Cambridge
* ''[http://www.nap.edu/catalog.php?record_id=11516 Network Science]'', Committee on Network Science for Future Army Applications, National Research Council. 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
* ''Dynamical processes on complex networks'', 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, March 11, 2009) ISBN 0-470-33188-7
* ''Nexus: Small Worlds and the Groundbreaking Theory of Networks'', Mark Buchanan (W. W. Norton & Company, June 2003) ISBN 0-393-32442-7
* ''Six Degrees: The Science of a Connected Age'', Duncan J. Watts (W. W. Norton & Company, February 17, 2004) ISBN 0-393-32542-3
*[http://netwiki.amath.unc.edu/ netwiki] Scientific wiki dedicated to network theory
*[http://www.networkcultures.org/networktheory/ New Network Theory] International Conference on 'New Network Theory'
*[http://nwb.slis.indiana.edu/ Network Workbench]: A Large-Scale Network Analysis, Modeling and Visualization Toolkit
*[http://www.orgnet.com/SocialLifeOfRouters.pdf Network analysis of computer networks]
*[http://www.orgnet.com/OrgNetMap.pdf Network analysis of organizational networks]
*[https://web.archive.org/web/20121123010939/http://firstmonday.org/htbin/cgiwrap/bin/ojs/index.php/fm/article/view/941/863 Network analysis of terrorist networks]
*[https://web.archive.org/web/20080724193037/http://www.orgnet.com/AJPH2007.pdf Network analysis of a disease outbreak]
*[http://linkanalysis.wlv.ac.uk/ Link Analysis: An Information Science Approach] (book)
*[https://web.archive.org/web/20090307155011/http://gephi.org/2008/how-kevin-bacon-cured-cancer/ Connected: The Power of Six Degrees] (documentary)
*[http://havlin.biu.ac.il/Publications.php?keyword=Identification+of+influential+spreaders+in+complex+networks++&year=*&match=all Influential Spreaders in Networks], M. Kitsak, L. K. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H. E. Stanley, H.A. {{Not a typo|Makse}}, ''Nature Physics'' 6, 888 (2010)
*[http://havlin.biu.ac.il/course4.php A short course on complex networks]
*[https://web.archive.org/web/20160211200247/http://barabasilab.neu.edu/courses/phys5116/ A course on complex network analysis by Albert-László Barabási]

==Notas==
{{reflist|2|refs=
<ref name=GT-33>{{citar web|título=Toward a Complex Adaptive Intelligence Community The Wiki and the Blog|url=https://www.cia.gov/library/center-for-the-study-of-intelligence/csi-publications/csi-studies/studies/vol49no3/html_files/Wik_and_%20Blog_7.htm|obra=D. Calvin Andrus|publicado=cia.gov|acessodata=25 de agosto de 2012}}</ref>
}}

[[Categoria:Cibernética]]
[[Categoria:Redes]]