Relações da estrutura de redes complexas com as dinâmicas do passeio aleatório, de transporte e de.. por Lucas Antiqueira - Versão HTML

ATENÇÃO: Esta é apenas uma visualização em HTML e alguns elementos como links e números de página podem estar incorretos.
Faça o download do livro em PDF, ePub, Kindle para obter uma versão completa.

UNIVERSIDADE DE SÃO PAULO

INSTITUTO DE FÍSICA DE SÃO CARLOS

LUCAS ANTIQUEIRA

Relações da estrutura de redes complexas com

as dinâmicas do passeio aleatório, de

transporte e de sincronização

São Carlos

2011

LUCAS ANTIQUEIRA

Relações da estrutura de redes complexas com

as dinâmicas do passeio aleatório, de

transporte e de sincronização

Tese apresentada ao Programa de Pós-graduação em

Física do Instituto de Física de São Carlos da Universi-

dade de São Paulo, para obtenção do título de Doutor

em Ciências.

Área de Concentração: Física Aplicada

Opção: Física Computacional

Orientador: Prof. Dr. Luciano da Fontoura Costa

VERSÃO CORRIGIDA

(versão original disponível na unidade que aloja o programa)

São Carlos

2011

AUTORIZO A REPRODUÇÃO E DIVULGAÇÃO TOTAL OU PARCIAL DESTE TRA-

BALHO, POR QUALQUER MEIO CONVENCIONAL OU ELETRÔNICO, PARA FINS

DE ESTUDO E PESQUISA, DESDE QUE CITADA A FONTE.

Ficha catalográfica elaborada pelo Serviço de Biblioteca e Informação do IFSC,

com os dados informados pelo(a) autor(a)

Antiqueira, Lucas

Relações da estrutura de redes complexas com as dinâmicas

do passeio aleatório, de transporte e de sincronização /

Lucas Antiqueira; orientador Luciano da Fontoura Costa -

versão corrigida –- São Carlos, 2011.

169 p.

Tese (Doutorado - Programa de Pós-Graduação em Física

Aplicada Computacional) –- Instituto de Física de São Carlos,

Universidade de São Paulo, 2011.

1.

Redes complexas.

2.

Grafos.

3.

Estrutura.

4.

Dinâmica.

5.

Sistemas complexos.

I. da Fontoura Costa,

Luciano, orient.

II. Título.

Página reservada à folha de aprovação.

À minha querida e encantadora mãe,

Valquíria (1962-2009).

Agradecimentos

Neste espaço, ofereço uma homenagem:

- Aos meus pais, Gilberto e Valquíria;

- Ao meu irmão, Moisés;

- À luz de todos os meus dias, Lia;

- Aos meus avôs, João e Amélia;

- Aos “cãopanheiros” Bob e Dig;

- Ao meu orientador, Prof. Luciano.

Faltam-me palavras para expressar completa e exatamente minha gratitude. Podem ter cer-

teza disto: lembro-me exatamente da importância de cada um em minha vida e, consequente-

mente, no desenvolvimento desta tese. Tenho esperança de que minhas atitudes em nosso dia a

dia tenham refletido meu apreço por vocês.

Ofereço também agradecimentos:

- Aos amigos do IFSC que ajudaram-me neste trabalho. Mais especificamente: João,

pelo suporte em sincronização de redes; Francisco, pelo suporte em análise canônica;

e Matheus, pelo cálculo da acessibilidade em redes grandes;

- Aos demais amigos do IFSC com quem tive a oportunidade de conviver durante esses

quatro anos: Mauro, Bruno, Alexandre, Marquinhos, Débora, Mônica, Krissia, Renato F.,

Renato P., Diego, Paulino, César, Osvaldo, André e Thomas.

Que Deus abençoe todos.

Agradeço também a FAPESP pelo apoio financeiro (processo #06/61743-7).

“Não há escola que se iguale a um lar decente,

nem professores que se igualem a pais honestos e virtuosos.”

— MAHATMA GANDHI (1869-1948)

“Fly, on your way, like an eagle.

Fly as high as the sun.”

— BRUCE DICKINSON (1958-...)

Resumo

ANTIQUEIRA, Lucas. Relações da estrutura de redes complexas com as dinâmicas do

passeio aleatório, de transporte e de sincronização. 2011. 169 p. Tese (Doutorado em

Ciências) - Instituto de Física de São Carlos, Universidade de São Paulo, São Carlos, 2011.

O relacionamento entre estrutura e dinâmica em redes complexas foi considerado utilizando-se

uma ampla gama de diferentes técnicas. Diversas redes reais foram estudadas em termos das

correlações entre grau e atividade. A medida de atividade é definida como a proporção de vi-

sitas por vértice no regime estacionário do passeio aleatório simples. O estudo desse tipo de

correlação é importante pois pode fornecer subsídios para que uma propriedade dinâmica de

um vértice possa ser obtida somente analisando-se seu(s) grau(s). O conceito de acessibilidade

foi abordado nesse contexto, permitindo que fossem evidenciadas diferentes correlações, em

redes como a WWW, de acordo com a intensidade de acessibilidade dos vértices. Propôs-se

também um novo modelo de rede baseado no crescimento do número de vértices em que novas

conexões são criadas com probabilidade proporcional à atividade de cada vértice. Esse modelo

pode ser entendido como uma generalização do modelo de Barabási e Albert para redes com

arestas direcionadas. Utilizando-se um conjunto de diversas medidas estruturais, mostrou-se

que o novo modelo apresenta, entre outros modelos tradicionais de redes, a maior compatibi-

lidade com três redes corticais. Foi também desenvolvido um método para caracterização da

distribuição de subgrafos e seus inter-relacionamentos. O principal aspecto dessa metodolo-

gia é a expansão gradual dos subgrafos, desenvolvida para que os vértices que encontram-se

fora de subgrafos possam ter suas relevâncias quantificadas em termos da importância no es-

tabelecimento das conexões entre subgrafos. Experimentos para ilustração do método foram

realizados utilizando-se quatro modelos de redes e cinco redes reais, e os resultados obtidos fo-

ram relacionados aos processos dinâmicos de transporte e de espalhamento. Outro tópico aqui

considerado é o dos efeitos da amostragem de redes corticais, quantificados por meio de análise

multivariada e classificação, fazendo uso de um conjunto de medidas estruturais de redes. Esses

efeitos também foram mensurados em termos do comportamento dinâmico das redes (sincro-

nização e acessibilidade). Simulações dos métodos de encefalografia MEG e EEG mostraram

que as redes amostradas podem apresentar características bem diferentes das da rede original,

principalmente no caso de amostras pequenas. Adicionalmente, a rede integrada da bactéria

Escherichia coli foi analisada, a qual incorpora (i) regulação de transcrição gênica, (ii) vias

metabólicas e de sinalização e (iii) interações entre proteínas. Outliers foram identificados no

relacionamento entre grau e atividade, os quais representam reguladores globais de transcrição.

Além disso, verificou-se que esses outliers são genes altamente expressos em diferentes con-

dições, apresentando, portanto, uma natureza global no controle de diversos outros genes da

célula.

Palavras-chave: Redes complexas. Grafos. Estrutura. Dinâmica. Sistemas complexos.

Abstract

ANTIQUEIRA, Lucas. Relationships between the structure of complex networks and the

random walk, transport and synchronization dynamics. 2011. 169 p. Tese (Doutorado em

Ciências) - Instituto de Física de São Carlos, Universidade de São Paulo, São Carlos, 2011.

The relationship between structure and dynamics was addressed by employing a wide range of

different approaches. First, the correlations between degree and activity were studied in vari-

ous real-world networks. The activity is defined as the proportion of visits to each node in the

steady-state regime of the simple random walk. This type of correlation can provide means

to assess node activity only in terms of the degree. The concept of accessibility was included

in this analysis, showing an intimate relationship (in networks such as the WWW) between

the type of correlation and the level of accessibility observed on nodes. A new complex net-

work model founded on growth was also proposed, with new connections being established

proportionally to the current activity of each node. This model can be understood as a gen-

eralization of the Barabási-Albert model for directed networks. By using several topological

measurements we showed that this new model provides, among several other traditional the-

oretical types of networks, the greatest compatibility with three real-world cortical networks.

Additionally, we developed a novel approach considering non-overlapping subgraphs and their

interrelationships and distribution through a given network. The main aspect of the method-

ology is a novel merging procedure developed to assess the relevance of nodes (in relation to

the overall subgraph interconnectivity) lying outside subgraphs. Experiments were carried out

on four types of network models and five instances of real-world networks, in order to illus-

trate the application of the method. Furthermore, these results were related to the properties

of the transport and spreading processes. Other topic here addressed is the sampling problem

in cortical networks. Effects of sampling were quantified using multivariate analysis and clas-

sifiers based on structural network measurements. Samples were also evaluated in terms of

their dynamical behavior using a synchronization model and the measure of accessibility. By

simulating MEG/EEG recordings it was found that sampled networks may substantially devi-

ate from the respective original networks, mainly for small sample sizes. We also report an

analysis of the integrated network of Escherichia coli, which incorporates (i) transcriptional

regulatory interactions, (ii) metabolic/signaling feedback and (iii) protein-protein interactions.

Network outliers, which represent global transcriptional regulators, were identified in the rela-

tionship between out-degree and activity. These outliers are highly and widely expressed across

conditions, therefore supporting their global nature in controlling many genes in the cell.

Keywords: Complex networks. Graphs. Structure. Dynamics. Complex systems.

Lista de Figuras

Figura 1.1 - Resumo das investigações realizadas neste projeto.

. . . . . . . . . . .

29

Figura 1.2 - Principais conceitos trabalhados na tese e suas inter-relações. . . . . . .

37

Figura 2.1 - Exemplo de cálculo da acessibilidade. . . . . . . . . . . . . . . . . . .

53

Figura 2.2 - Número de pacotes de dados durante a dinâmica de transporte. . . . . .

56

Figura 2.3 - Classificação de máximo a posteriori unidimensional. . . . . . . . . . .

71

Figura 2.4 - Classificação de máximo a posteriori bidimensional. . . . . . . . . . . .

71

Figura 2.5 - Visão geral do método de classificação de redes. . . . . . . . . . . . . .

72

Figura 3.1 - Exemplos de correlações grau-atividade em um grafo não direcionado e

em um direcionado. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

74

Figura 3.2 - Intensidades das correlações do tipo B como função da reciprocidade. .

75

Figura 3.3 - Intensidades das correlações do tipo A como função da reciprocidade. .

76

Figura 3.4 - Ilustração do tipo de análise realizada nas correlações do tipo A. . . . .

77

Figura 3.5 - Correlações grau de entrada vs. atividade na rede Macaco’85. . . . . . .

78

Figura 3.6 - Correlações grau de entrada vs. atividade na rede C. elegans. . . . . . .

80

Figura 3.7 - Correlações grau de entrada vs. atividade na rede Roget.

. . . . . . . .

80

Figura 3.8 - Correlações grau de entrada vs. atividade na rede Massey. . . . . . . . .

81

Figura 3.9 - Correlações grau de entrada vs. atividade na rede Flinders. . . . . . . .

82

Figura 3.10 - Correlações grau de entrada vs. atividade na rede Nottingham. . . . . .

82

Figura 3.11 - Correlações entre grau de entrada e atividade (visualização parcial) nas

redes WWW.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

82

Figura 3.12 - Intensidades das correlações do tipo A como função da reciprocidade

após a análise borda/núcleo.

. . . . . . . . . . . . . . . . . . . . . . .

83

Figura 4.1 - Passo T ao longo do crescimento de uma rede APA com m = 2. . . . . .

86

Figura 4.2 - Distribuições de grau e atividade nos modelos APA, APA’ e BA. . . . .

87

Figura 4.3 - Histogramas dos coeficientes de correlação grau-atividade nos modelos

APA e APA’. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

89

Figura 4.4 - Correlações grau-atividade em três redes APA. . . . . . . . . . . . . . .

90

Figura 4.5 - Correlações grau-atividade em três redes APA’. . . . . . . . . . . . . .

91

Figura 4.6 - Comparação de redes reais com os modelos APA e APA’. . . . . . . . .

92

Figura 4.7 - Correlações grau-atividade nas redes corticais. . . . . . . . . . . . . . .

93

Figura 5.1 - Exemplo de um grafo e seus subgrafos. . . . . . . . . . . . . . . . . . .

95

Figura 5.2 - Grafo utilizado como exemplo de aplicação do método de análise de

subgrafos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

98

Figura 5.3 - Operação de dilatação de um subgrafo. . . . . . . . . . . . . . . . . . . 100

Figura 5.4 - Valores de relevância r(v) para os vértices do grafo da Figura 5.2.

. . . 103

Figura 5.5 - Expansão dos subgrafos da Figura 5.2. . . . . . . . . . . . . . . . . . . 104

Figura 5.6 - Tamanhos de (e distâncias entre) subgrafos nos modelos de rede. . . . . 108

Figura 5.7 - Número de subgrafos e de vértices na expansão gradual realizada nos

modelos de rede.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

Figura 5.8 - Taxas críticas de geração de pacotes na dinâmica de transporte. . . . . . 111

Figura 5.9 - Tempo de cobertura do passeio aleatório simples. . . . . . . . . . . . . 112

Figura 5.10 - Tamanhos de (e distâncias entre) subgrafos nas redes reais. . . . . . . . 113

Figura 5.11 - Número de subgrafos e de vértices na expansão gradual realizada nas

redes reais. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

Figura 6.1 - Ilustração do processo de amostragem de redes. . . . . . . . . . . . . . 118

Figura 6.2 - Ilustrações do modelo neuronal e do método de amostragem. . . . . . . 120

Figura 6.3 - Classificação das redes neuronais.

. . . . . . . . . . . . . . . . . . . . 124

Figura 6.4 - Classificação das redes amostradas com decaimento linear de sinal. . . . 125

Figura 6.5 - Classificação das redes amostradas com decaimento quadrático de sinal. 126

Figura 6.6 - Distribuição de subgrafos nas redes neuronais e nas respectivas amostras. 128

Figura 6.7 - Níveis de sincronia ao longo do tempo nas redes neuronais e nas respec-

tivas amostras. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

Figura 6.8 - Histogramas de acessibilidade para h = 2 nas redes neuronais e nas res-

pectivas amostras. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

Figura 6.9 - Histogramas de acessibilidade para h = 3 nas redes neuronais e nas res-

pectivas amostras. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

Figura 7.1 - Identificação dos outliers de dinâmica na rede integrada E. coli. . . . . . 139

Figura 7.2 - Identificação dos outliers de estrutura na rede integrada E. coli. . . . . . 140

Figura 7.3 - Diagramas em caixa para a acessibilidade na rede integrada E. coli. . . . 141

Figura 7.4 - Motivos identificados na rede integrada E. coli. . . . . . . . . . . . . . 142

Figura 7.5 - Diagramas em caixa para a expressão gênica na E. coli. . . . . . . . . . 146

Lista de Tabelas

Tabela 2.1 - Informações básicas a respeito das redes reais utilizadas neste projeto. .

59

Tabela 2.2 - Disponibilidade das redes reais utilizadas neste projeto. . . . . . . . . .

60

Tabela 4.1 - Medidas calculadas para os modelos APA, APA’ e BA. . . . . . . . . .

88

Tabela 6.1 - Medidas calculadas para o modelo neuronal e para os modelos ER, WS,

BA e GG. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

Tabela 7.1 - Medidas computadas para as redes TRN, MSFN e PPIN. . . . . . . . . 137

Tabela 7.2 - Medidas obtidas para a rede integrada E. coli e seu maior componente

conexo.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138

Tabela 7.3 - Genes da E. coli mais frequentes nos motivos de tamanho 3.

. . . . . . 143

Tabela 7.4 - Genes da E. coli mais frequentes nos motivos de tamanho 4.

. . . . . . 144

Lista de Abreviaturas

APA

Activity-based Preferential Attachment

BA

Barabási-Albert

BGP

Border Gateway Protocol

CPD

Central Point Dominance

EAT

Edinburgh Associative Thesaurus

EEG

Electroencephalography

ER

Erd˝os-Rényi

FFL

Feed-Forward Loop

FOLDOC

Free On-line Dictionary of Computing

(f)MRI

(functional) Magnetic Resonance Imaging

GG

Modelo Geográfico

MEG

Magnetoencephalography

MSFN

Metabolic and Signaling Feedback Network

ODLIS

Online Dictionary for Library and Information Science

P2P

Peer-to-Peer

PCA

Principal Components Analysis

PPIN

Protein-Protein Interaction Network

TF

Transcription Factor

TG

Target Gene

TRN

Transcriptional Regulatory Network

USFFAN

University of South Florida Free Association Norms

WS

Watts-Strogatz

WWW

World Wide Web

Lista de Símbolos

G(V,E)

Grafo definido pelo conjunto de vértices V interconectados pelas arestas

especificadas no conjunto E

A

Matriz de adjacências de um grafo

N

Número de vértices em um grafo

E

Número de arestas em um grafo

P

Matriz de transições do passeio aleatório simples

ki

Grau de um vértice i

kin

Grau de entrada de um vértice i

i

kout

Grau de saída de um vértice i

i

(d)

k

Grau hierárquico no nível d de um vértice i

i

(d|in)

k

Grau hierárquico de entrada no nível d de um vértice i

i

(d|out)

k

Grau hierárquico de saída no nível d de um vértice i

i

(nn)

k

Grau médio da vizinhança de um vértice i

i

(d)

er

Grau inter-anel no nível hierárquico d de um vértice i

i

(d)

ar

Grau intra-anel no nível hierárquico d de um vértice i

i

cci

Coeficiente de agrupamento de um vértice i

ccin

Coeficiente de agrupamento de entrada de um vértice i

i

ccout

Coeficiente de agrupamento de saída de um vértice i

i

(d)

cc

Coeficiente de agrupamento hierárquico no nível d de um vértice i

i

(d|in)

cc

Coeficiente de agrupamento hierárquico de entrada no nível d de um vér-

i

tice i

(d|out)

cc

Coeficiente de agrupamento hierárquico de saída no nível d de um vértice i

i

i

Comprimento médio dos caminhos mínimos que partem de um vértice i

Comprimento médio dos caminhos mínimos em um grafo

r

Assortatividade de um grafo

rii

Assortatividade de entrada de um grafo

roo

Assortatividade de saída de um grafo

(n)

B

Centralidade de um vértice i

i

(e)

B

Centralidade de uma aresta i

i

Eglobal

Eficiência global de um grafo

Elocal

Eficiência local de um grafo

CPD

Dominância do ponto central em um grafo

ρ

Reciprocidade das arestas direcionadas de um grafo

ρmin

Reciprocidade mínima possível em um grafo

ρcorr

Coeficiente de correlação linear de Pearson

(d)

cv

Taxa de convergência no nível hierárquico d de um vértice i

i

(d)

dv

Taxa de divergência no nível hierárquico d de um vértice i

i

πi

Atividade de um vértice i

(h)

Ac

Acessibilidade do vértice i a h passos

i

λc

Taxa crítica de criação de pacotes na dinâmica de transporte

rsync

Nível global de sincronia em uma rede

Sumário

1

Introdução

27

2

Material e Métodos

39

2.1

Representação e Caracterização Estrutural de Redes . . . . . . . . . . . . . . .

39

2.2

Dinâmica do Passeio Aleatório Simples

. . . . . . . . . . . . . . . . . . . . .

49

2.3

Dinâmica de Acessibilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51

2.4

Dinâmica de Transporte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

54

2.5

Dinâmica de Sincronização . . . . . . . . . . . . . . . . . . . . . . . . . . . .

55

2.6

Modelos de Redes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

2.7

Redes Reais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

58

2.8

Análise de Componentes Principais . . . . . . . . . . . . . . . . . . . . . . . .

66

2.9

Análise de Variável Canônica e Classificação

. . . . . . . . . . . . . . . . . .

68

3

Correlações entre Grau e Atividade

73

3.1

Tipos de Correlação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

73

3.2

Reciprocidade e Correlações Tipo B . . . . . . . . . . . . . . . . . . . . . . .

75

3.3

Acessibilidade e Correlações Tipo A . . . . . . . . . . . . . . . . . . . . . . .

76

4

Conectividade Guiada pela Atividade

85

4.1

Modelo Proposto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

85

4.2

Propriedades do Modelo

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

87

4.3

Comparação com Redes Reais . . . . . . . . . . . . . . . . . . . . . . . . . .

90

5

Caracterização da Distribuição de Subgrafos

95

5.1

Método Proposto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

96

5.2

Subgrafos com Alto Agrupamento e Processos Dinâmicos . . . . . . . . . . . . 105

6

Efeitos da Amostragem de Redes Corticais

117

6.1

Modelo de Rede Neuronal

. . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

6.2

Amostragem da Rede Neuronal . . . . . . . . . . . . . . . . . . . . . . . . . . 119

6.3

Efeitos Estruturais e Dinâmicos da Amostragem . . . . . . . . . . . . . . . . . 121

7

Rede Escherichia coli: Uma Abordagem Integrada

135

7.1

Integração dos Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

7.2

Relacionamento Estrutura-Dinâmica: Outliers . . . . . . . . . . . . . . . . . . 138

7.3

Funções Biológicas dos Outliers . . . . . . . . . . . . . . . . . . . . . . . . . 145

8

Conclusões

149

Referências

155

27

1

Introdução

A origem dos estudos em redes complexas pode ser traçada até as primeiras investigações em

grafos realizadas por Leonhard Euler no século XVIII, quando o problema das pontes de Kö-

nigsberg foi solucionado utilizando-se uma representação formada por um conjunto de vértices

conectados por arestas (1), ou seja, empregando-se o conceito de grafo. Euler desejava saber se existia um caminho em Königsberg (hoje Kaliningrado, Rússia) pelo qual cada uma das sete

pontes da cidade seria cruzada uma única vez – ele provou que tal caminho não existia. Desde

então, a teoria dos grafos evoluiu a ponto de se tornar um importante ramo da matemática (2),

tendo como exemplo fundamental de investigação a teoria dos grafos aleatórios desenvolvida

por Erd˝os e Rényi (3). Redes, que são estruturas naturalmente representadas por grafos, surgem em uma ampla gama de circunstâncias, o que faz do ramo das redes complexas um campo de

pesquisa excepcionalmente interdisciplinar (4–6). Exemplos envolvem, entre muitos outros, (i) cientistas da computação, que, por exemplo, desenvolvem estruturas de dados e algoritmos para

grafos (7), (ii) sociologistas, os quais investigam a estrutura e a dinâmica das relações sociais (tome como exemplo o famoso experimento de Milgram que deu origem ao termo seis graus de

separação (8)), (iii) biólogos, que frequentemente representam e estudam interações entre proteínas (9), genes (10) e metabólitos (11) utilizando o conceito de grafo, e (iv) físicos, que fazem uso recorrente da mecânica estatística a fim de solucionar problemas importantes em redes (4).

O interesse em redes cresceu vertiginosamente há aproximadamente uma década, quando

grandes estruturas do mundo real foram analisadas e descobriu-se importantes diferenças entre

essas estruturas e o grafo aleatório clássico. A partir desse momento, o termo redes comple-

xas passou a ser largamente utilizado para denominar estruturas com propriedades não triviais.

Primeiramente, descobriu-se que muitas redes do mundo real apresentam o chamado efeito pe-

queno mundo: as distâncias entre seus vértices são curtas (como em uma rede aleatória) e apre-

28

1 Introdução

sentam alto agrupamento local (diferentemente de uma rede aleatória) (12). Exemplo de rede pequeno mundo é a rede elétrica. Outra propriedade importante está relacionada à distribuição

do número de conexões de cada vértice – o chamado grau. Nesse caso, a distribuição segue

uma lei de potência (da forma P(k) ∼ k−γ , onde k representa o grau e o expoente γ depende

da rede analisada), revelando um padrão de conexões bem diferente do das redes aleatórias:

alguns poucos vértices, os chamados hubs, possuem um alto número de conexões, enquanto a

maior parte dos vértices apresenta poucas ligações (13, 14). Redes desse tipo, como a Internet e a World Wide Web (WWW), são frequentemente chamadas de redes sem escala (no sentido de

invariância de escala). Os hubs têm papel importante na resistência a ataques (15), propagação de doenças (16) e navigabilidade (17).

Redes complexas são frequentemente estudadas por meio da análise de suas proprieda-

des estruturais ou dinâmicas (5, 6). A estrutura está relacionada à maneira como as conexões organizam-se entre os vértices da rede. Por exemplo, propriedades estruturais bem conhecidas

são o efeito pequeno mundo e a distribuição de graus seguindo uma lei de potência. Por ou-

tro lado, a dinâmica é baseada em um processo dependente do tempo que faz uso da estrutura

da rede – por exemplo, transporte (18) e sincronização (19). Diversas investigações acerca da dinâmica já foram realizadas em redes regulares utilizadas como modelos de matéria conden-sada (20), onde a estrutura é ditada pelas propriedades físicas do material e é frequentemente conhecida de maneira completa. Desenvolvimentos mais recentes passaram a considerar processos dinâmicos em estruturas mais complexas. Exemplos são os processos de contágio em

redes sociais e de sincronização em redes neuronais (5, 6, 20). Além disso, entender o relacionamento entre estrutura e dinâmica é de grande importância no avanço do conhecimento sobre

os princípios que norteiam a organização das redes complexas (21). Diversos trabalhos na literatura demonstram uma preocupação nesse sentido (5), como o estudo da relação do fluxo do passeio aleatório com a estrutura de comunidades (22) e o uso de medidas de compressão de dados como indicadores do relacionamento estrutura-dinâmica (23). Nesta tese, o relacionamento estrutura-dinâmica é investigado utilizando-se diferentes técnicas em diferentes contextos (vide

esquema na Figura 1.1), conforme detalhado ao longo desta introdução.

1 Introdução

29

Correlações grau-atividade

xas

,

(Capítulo 3)

tório

ão

omple

aç Conectividade guiada pela atividade

(Capítulo 4)

oniz

edes c

Distribuição de subgrafos e

dinâmicas de transporte/espalhamento

a de r

(Capítulo 5)

as do passeio alea

e e de sincr

trutur

Aplicação: Efeitos estruturais e dinâmicos

na amostragem de redes corticais

(Capítulo 6)

ansport

ões da es

de tr Aplicação: Outliers de correlação grau-atividade

na rede integrada E. coli

elaç

com as dinâmic

R

(Capítulo 7)

Figura 1.1 – Resumo das investigações realizadas neste projeto, inseridas no contexto do estudo do rela-

cionamento da estrutura de redes complexas com diferentes tipos de processos dinâmicos.

A estrutura de cada vértice pode ser representada pelo grau, o mais simples indicador de

conectividade, enquanto a dinâmica pode ser representada pelo conceito aqui identificado por

atividade, que é a frequência estacionária de visitas a cada vértice em um passeio aleatório sim-

ples. O passeio aleatório é um modelo bastante conhecido de dinâmica em redes (20, 24–27),

cujas variantes incluem o passeio preferencial e o passeio com reforço. Escolheu-se o pas-

seio aleatório por ser um modelo geral e um dos mais importantes modelos de dinâmica em

diversas disciplinas, inclusive redes complexas (20). Exemplos de investigações nessa direção incluem o estudo das propriedades do passeio aleatório em redes sem escala (28–30), pequeno-mundo (31, 32) e aleatórias (33). No passeio aleatório do tipo simples, em que é permitido visitar apenas vértices vizinhos do vértice atual com probabilidade independente do histórico

do passeio, o grau é perfeitamente correlacionado com a atividade em redes não direciona-

das (24, 25). No caso de redes com arestas direcionadas as correlações tendem a ser bastante intrincadas, como na WWW (34). Portanto, foi empregada nesta tese uma nova abordagem para o estudo das correlações grau-atividade em redes direcionadas, as quais são pouco trabalhadas

na literatura (34). Primeiramente, o nível de reciprocidade das arestas de uma rede (35) foi utilizado como indicador da intensidade da correlação entre o grau de saída e a atividade em diversas redes reais. A reciprocidade funciona da seguinte maneira: seu nível máximo ocorre em

30

1 Introdução

redes não direcionadas, enquanto menores valores de reciprocidade são encontrados em redes

onde as arestas direcionadas não apresentam total simetria (ou seja, para um conjunto de arestas

i → j não existe a aresta recíproca j → i). Adicionalmente, o conceito de acessibilidade (36) foi empregado na análise das correlações entre grau de entrada e atividade. A acessibilidade está

relacionada ao número (e respectivas probabilidades) de diferentes caminhos que conectam um

vértice específico ao restante dos vértices da rede. Vértices com baixa acessibilidade tendem a

se posicionar na periferia (borda) da rede, enquanto vértices com alta acessibilidade tendem a

se posicionar no núcleo da rede (36). As correlações entre grau de entrada e atividade foram então analisadas separadamente na borda e no núcleo em várias redes reais, o que evidenciou

a existência de dois regimes separados de correlação (exemplos dessas redes são as corticais e

a WWW). Esses resultados fornecem subsídios importantes para uma melhor compreensão das

intrincadas correlações que podem existir em redes direcionadas (vide Capítulo 3)∗.

Outro aspecto relevante na área de redes complexas é a criação e análise de modelos de

rede, que são desenvolvidos para que a estrutura e a evolução de importantes classes de redes

sejam melhor compreendidas. Exemplos são o modelo de grafos aleatórios de Erd˝os e Rényi

(ER) (3) e o modelo pequeno mundo de Watts e Strogatz (WS) (12) (mais detalhes a respeito desses modelos são fornecidos na Seção 2.6, p. 57). Outro modelo bastante conhecido é o de Barabási-Albert (BA) (13), o qual reproduz a distribuição de graus observada nas redes sem escala. O modelo BA é baseado nos mecanismos de crescimento e ligação preferencial: vértices

são sequencialmente adicionados à rede, e suas conexões são criadas com outros vértices já

presentes na rede dando-se preferência aos vértices que já são bem conectados – ou seja, a

probabilidade de conexão é proporcional ao grau (13). Nesta pesquisa, procurou-se generalizar o modelo BA de modo que passasse a considerar (i) redes com arestas direcionadas, pois são

casos extremamente comuns e pouco estudados, e (ii) um processo dinâmico que porventura

ocorra na rede, ao invés de se utilizar somente uma propriedade estrutural, como o grau. Uma

motivação para essa investigação reside no fato de que, em muitos casos, uma propriedade

relacionada a um processo dinâmico está mais intimamente relacionada à importância de um

∗ Parte desse trabalho foi publicada nos anais do 2nd Workshop on Complex Networks (CompleNet’2010) (37).

1 Introdução

31

vértice do que o grau ou outra medida puramente estrutural. Por exemplo, a frequência de

visitas às páginas da WWW é um indicador particularmente eficiente da relevância de cada

página (por exemplo, o índice PageRank do Google (38)). Outra motivação é a de que o estudo de modelos como o proposto fornecem base para que o relacionamento estrutura-dinâmica seja

estudado em maior profundidade.

Alguns modelos de rede complexa foram propostos como modificações ou generalizações

do modelo BA (39). Entretanto, esses modelos baseiam-se apenas em propriedades estruturais das redes em crescimento. Outros modelos consideram de fato alguma propriedade dinâmica

do sistema na formação da rede. Por exemplo, a ligação preferencial já foi combinada com

a dinâmica evolucionária de jogos (dilema do prisioneiro) (40). Nesse caso, os vértices são considerados indivíduos de um grupo social, e novos indivíduos são conectados preferenci-almente aos vértices que apresentam maior aptidão na dinâmica evolucionária. Dependendo

dos parâmetros escolhidos, o modelo pode gerar redes homogêneas ou sem escala. Em outro

trabalho, redes com grau de sincronização ótimo foram construídas por meio de simulated an-

nealing (41). O grau de sincronização é alto em redes propensas a manter um estado global de sincronia entre osciladores definidos em cada um dos seus vértices. A criação de conexões

nesse caso é, portanto, guiada por um parâmetro de um processo dinâmico que ocorre na rede

(vide outros exemplos em (42–45)). Um modelo para a Internet baseado em agentes foi criado considerando-se o fluxo de tráfego de dados, além de outras características, como a geografia

(46). Sub-redes espacialmente posicionadas, os sistemas autônomos, têm um interesse econô-

mico em aumentar seu tráfego e assim incrementar sua receita. Um aumento na receita gera

uma melhoria na infraestrutura (incremento no número de conexões), a qual leva a um aumento

no tráfego. A dinâmica de interações entre os agentes leva a uma rede que reproduz diversas

características da Internet (46). Outra abordagem considera a teoria Hebbiana (47), em que dois neurônios conectam-se se um neurônio repetidamente ou persistentemente participa do disparo

de outro neurônio. Essa teoria já foi considerada no estudo de redes complexas (48). Contudo, modelo similar que incorpore o mecanismo de crescimento da rede não foi encontrado. Além

disso, a existência de um modelo de rede direcionada com crescimento e ligação preferencial

32

1 Introdução

baseada em uma propriedade de um processo dinâmico é desconhecida.

Foi portanto proposto neste projeto um novo modelo de ligação preferencial em que vértices

com alta atividade (definida na Seção 2.2, p. 49) têm maior chance de receber novas conexões.

Foi provado que o novo modelo é uma generalização do modelo BA para o caso de redes com

arestas direcionadas. Ou seja, quando a direção das arestas é desconsiderada, o novo modelo

reproduz exatamente o modelo BA. Foi mostrado também que o modelo proposto, ao integrar

propriedades estruturais e dinâmicas em seu crescimento, aproxima as características das redes

corticais do gato e do macaco (49, 50), estruturas que são base da atividade cerebral nesses animais. A metodologia empregada envolve a comparação dessas redes corticais com diversos

outros modelos, inclusive o aqui proposto, obtendo-se de cada rede um conjunto de métricas

(vetor de atributos) comumente utilizadas na caracterização de redes complexas. A partir disso,

o modelo que melhor se aproxima da rede real é escolhido por meio da análise de variável

canônica e da classificação por máxima probabilidade a posteriori (vide Capítulo 4)∗.

Redes complexas são frequentemente analisadas na mesoescala, ou seja, em uma escala

intermediária entre a dos vértices isolados e a de toda a rede. Diversos trabalhos levam em

consideração a estrutura de comunidades† ou dos caminhos existentes entre diferentes porções da rede (53, 54). Subgrafos são grupos de vértices, em princípio, genéricos; contudo, podem representar vértices importantes em uma rede, tais como os hubs. Subgrafos podem também

ser formados por motivos‡ e, portanto, podem ser analisados de acordo com sua distribuição na rede. Outra possibilidade refere-se à característica de algumas redes possuírem alguma informação associada aos seus vértices como, por exemplo, tópicos na WWW ou categorias morfos-

sintáticas em uma rede de palavras. De maneira geral, vértices que compartilham um atributo

de interesse podem formar subgrafos.

Poucos trabalhos foram realizados com relação ao estudo da distribuição de subgrafos.

Muitos trabalhos existem, de fato, com relação à detecção de subgrafos (de motivos e co-

∗ Esse trabalho foi publicado no periódico Journal of Statistical Mechanics (51).

† Comunidades, ou agrupamentos em grafos, são conjuntos de vértices densamente conectados entre si, enquanto

as conexões entre comunidades são relativamente mais esparsas (52).

‡ Motivos (do inglês, motifs) são grupos de vértices, geralmente pequenos, com estrutura (e por vezes função) bem

definidas (55).

1 Introdução

33

munidades, e também de subgrafos cujos vértices apresentam características similares (56)).

Contudo, o enfoque aqui é caracterizar as relações entre subgrafos previamente conhecidos. A

posição de subgrafos em grafos moleculares já foi estimada anteriormente, inclusive em termos

da distância entre subgrafos (57). Contudo, pretende-se aqui investigar (i) a proximidade entre os subgrafos e (ii) o papel dos demais vértices da rede no estabelecimento da conexão entre

subgrafos. Tais informações são importantes para uma maior compreensão da organização e

da dinâmica de uma rede. Por exemplo, se subgrafos formados por hubs estão muito próxi-

mos uns dos outros, a porção da rede contendo tais subgrafos pode ser entendida como crítica

para a integridade da rede e comunicação entre seus vértices. Outras situações similares podem

surgir ao se considerar outra medida na seleção de subgrafos. A motivação para esse estudo

surgiu a partir da observação de que regiões distintas de diversas redes direcionadas apresentam

diferentes comportamentos com relação às correlações grau-atividade (vide parágrafos prévios

desta Introdução). As propriedades dessas regiões (subgrafos) podem fornecer indícios que aju-

dem a explicar o comportamento da relação estrutura-dinâmica. Portanto, foi desenvolvida uma

nova metodologia para a caracterização da distribuição de subgrafos. Embora essa metodologia

possa apenas ser aplicada a redes não direcionadas, seu potencial foi mostrado por meio do

estudo de redes artificiais (por exemplo, modelo pequeno mundo) e reais (como a rede elétrica

dos EUA). Exemplos de subgrafos de interesse, formados por vértices com alto coeficiente de

agrupamento, foram selecionados. Adicionalmente, a análise das propriedades desses subgrafos

permitiu uma caracterização do seu relacionamento com os processos dinâmicos de transporte

e de espalhamento (vide Capítulo 5)∗.

Diversas questões em redes complexas continuam em aberto. Um exemplo é o problema

da amostragem: a rede existe, mas é difícil coletá-la de maneira precisa e completa. Dado

que utilizamos dados incompletos em diversos casos, é importante saber se nossas conclusões

podem ser extrapoladas para a rede completa (e inacessível). Em alguns casos, a grande mai-

oria dos vértices ou arestas pode estar oculta. Por exemplo, a WWW é uma rede enorme que

evolui rapidamente, sendo virtualmente impossível dela obter uma amostra exata em determi-

∗ Esse trabalho foi publicado no periódico New Journal of Physics (58).

34

1 Introdução

nado momento, pois até o fim da coleta de dados, a rede já teria sido alterada. Muitas redes

sociais são, por razões práticas, apenas esparsamente amostradas, já que em alguns casos é

necessário utilizar questionários ou realizar algum tipo de consulta pessoal. É interessante tam-

bém observar como o procedimento de amostragem influencia a natureza do relacionamento

estrutura-dinâmica, ou seja, de que maneira esse relacionamento é afetado como resultado do

processo de amostragem.

A questão da amostragem de redes complexas é de extrema importância para a área, e al-

guns estudos evidenciam os problemas que podem surgir ao se analisar redes amostradas. Por

exemplo, distribuições de graus foram avaliadas em redes aleatórias e sem escala utilizando

amostragem aleatória (59) ou inspirada na coleta de conexões da Internet (amostragem traceroute) (60). Inclusive, amostras do tipo traceroute implicam em uma probabilidade de detecção de vértices/arestas proporcional aos respectivos valores de centralidade (essa métrica é definida

na Seção 2.1.13, p. 47) (61). Outros trabalhos reportam análises de redes sem escala estimadas

(62, 63) e da precisão de amostras como uma função do tamanho da rede coletada (64). Em outro estudo (65), foi descrito como redes de interação de proteínas são afetadas pelo processo de amostragem. Os autores consideraram diversas estruturas diferentes como representantes da

rede original a ser amostrada, tais como a rede aleatória e a sem escala, entre outras. Dessas

redes, amostras aleatórias foram coletadas e tiveram suas distribuições de grau analisadas. In-

dependentemente da distribuição da rede original, todas as amostras apresentaram uma lei de

potência, demonstrando um problema sério que pode ocorrer na análise de redes de proteínas.

Neste projeto optou-se por estudar a amostragem cortical realizada por meio de sensores

posicionados na superfície do crânio. Investigou-se até que ponto as redes amostradas repro-

duzem características relevantes da rede original, ou seja, da estrutura fisiológica que forma a

base da atividade gravada pelos sensores. A rede original é a dos neurônios no sistema nervoso

central, que contém aproximadamente 1010–1012 neurônios com 103–104 conexões cada. A

conectividade funcional pode ser estimada por meio de técnicas como MEG/EEG (do inglês

magnetoencephalography/electroencephalography), as quais captam padrões de sincronização

em populações de neurônios com alta resolução temporal. O problema da amostragem nesse

1 Introdução

35

caso é um grande desafio, pois dispositivos disponíveis atualmente contêm tipicamente apenas

20–300 sensores MEG ou eletrodos EEG. Procurou-se aqui reproduzir, por meio de simulações,

esse tipo de amostragem, para então avaliar seus efeitos comparando-se métricas comumente

utilizadas na área de redes complexas. O processo começa com uma rede artificial criada para

representar a rede neuronal original. A partir disso, amostras de diversos tamanhos são obtidas e

suas características são comparadas às da rede completa. Por meio de análise de variável canô-

nica seguida de classificação, foi possível mensurar importantes imprecisões estruturais que

podem surgir como efeito desse tipo de amostragem. Propriedades dinâmicas também foram

analisadas, evidenciando que o nível de sincronização das redes originais pode ser bem reprodu-

zido nas amostras, ao contrário da dinâmica de acessibilidade (vide Capítulo 6)∗. Essa metodologia deve ainda ser generalizada para redes direcionadas, nas quais o processo de amostragem

pode ser investigado de acordo com a sua influência nas correlações grau-atividade, permitindo

assim verificar se (e quando) a amostragem é responsável pelo enfraquecimento das correlações

observadas em diversas redes (Capítulo 3).

De fato, tópicos em biologia têm sido frequentemente abordados utilizando-se o conceito

de rede (67, 68). No caso da célula, os processos guiados por vias metabólicas e de sinalização, as interações proteína-proteína e as regulações de transcrição gênica podem ser representados

por grafos (69–71). Entretanto, enquanto na maioria das investigações nessa área esses processos são estudados de uma maneira isolada, uma compreensão mais completa requer uma

integração entre os diferentes tipos de interações que ocorrem na célula (72). Embora desenvolvimentos tenham sido realizados nessa direção (interações proteína-proteína integradas com

dados de expressão e de localização subcelular na levedura Saccharomyces cerevisiae (73)), a maior parte dos estudos é limitada a subsistemas particulares. Um dos processos fundamentais,

mesmo em um sistema unicelular simples como o de bactérias, é o de regulação da transcri-

ção gênica. Ultimamente, uma grande quantidade de informação a respeito desse processo tem

sido gerada, o que possibilitou a representação, por meio de grafos, do conjunto completo de

interações em bactérias como Escherichia coli e Bacillus subtilis (74–76). Entretanto, as redes

∗ Esse trabalho foi publicado no periódico NeuroImage (66).

36

1 Introdução

de transcrição gênica já estudadas limitam-se a um conjunto de fatores de transcrição que con-

trolam um conjunto de genes-alvo (71, 77–80). Outra limitação é o emprego de um pequeno número de medidas de redes relativamente simples (como grau e coeficiente de agrupamento)

de maneira mutuamente exclusiva, a fim de se compreender as propriedades locais dos vértices

(81–83). Além disso, a associação entre estrutura e dinâmica é frequentemente deixada de lado no estudo dessas redes. Entender o relacionamento estrutura-dinâmica é de fato importante,

como demonstrado no caso da sincronização em redes corticais (84, 85). Por outro lado, um tó-

pico bastante explorado é a identificação de motivos em redes biológicas, dada a modularidade

inerente dos processos celulares (71, 86, 87).

Nesta tese, a regulação da transcrição gênica na bactéria Escherichia coli foi estudada por

meio da incorporação dos diferentes aspectos discutidos no parágrafo anterior: integração de

diferentes tipos de informação na rede, análise do relacionamento estrutura-dinâmica, utilização

de medidas mais complexas para caracterização de redes e detecção de motivos. Foi construída

uma rede que incorpora três diferentes processos celulares: (i) transcrição gênica (74), (ii) vias metabólicas e de sinalização (88) e (iii) interações proteína-proteína (83, 89). A rede de transcrição foi tomada como a rede “base” da rede integrada utilizada neste estudo, na qual foram

inseridas novas conexões que representam as vias metabólicas e de sinalização e também as

interações entre proteínas. O conceito de atividade foi incluído na análise, o qual simula, neste

caso, a dinâmica de interação gênica em termos da frequência relativa de ativação de cada vér-

tice. Foi possível observar que alguns genes outliers (ou seja, com propriedades discrepantes

ou não usuais) apresentam características particulares com relação ao relacionamento estrutura-

dinâmica: eles são fracamente ativados embora controlem muitos outros genes. Convencionou-

se aqui denominar esses genes como outliers de dinâmica. A seguir, as propriedades estruturais

desses outliers foram analisadas por meio do cálculo de diversas medidas e posterior análise de

componentes principais. As medidas selecionadas representam atributos em escala local (como

o grau e o coeficiente de agrupamento), global (como a centralidade) e intermediária (medidas

hierárquicas) (90). Verificou-se que os outliers de dinâmica coincidem com os de estrutura, apresentam alta acessibilidade e têm participação importante na formação de motivos. Além

1 Introdução

37

disso, foi constatado que os outliers são reguladores globais na rede de transcrição gênica e que

também representam genes intensamente expressos em diferentes condições. Esses resultados

sugerem que o método proposto para detecção de outliers na rede integrada pode ser utilizado

na identificação de reguladores globais em outros organismos (vide Capítulo 7)∗.

Transporte

Sincronização

Estrutura

Dinâmica

Capítulo 5

Capítulo 6

Subgrafos

Capítulo 6

Amostragem

Capítulo 5

Capítulo 6

Capítulo 5

Capítulo 6

Medidas

Capítulos 3, 4 e 7

Passeio aleatório

estruturais

Figura 1.2 – Principais conceitos trabalhados na tese e suas inter-relações. Para cada inter-relaciona-

mento, é especificado o respectivo capítulo em que ele é tratado.

A Figura 1.2 contém um diagrama que integra todos os conceitos estruturais e dinâmicos tratados nesta tese. A estrutura é representada por três itens: cálculo de medidas estruturais,

análise da distribuição de subgrafos e estudo dos efeitos da amostragem de redes corticais. Já

a dinâmica relaciona-se aos processos do passeio aleatório (o qual inclui as dinâmicas de ati-

vidade e de acessibilidade), de transporte e de sincronização. Grande parte das contribuições

desta tese está resumida na Figura 1.2, a qual mostra em quais capítulos são abordados os diversos relacionamentos existentes entre os conceitos estruturais e dinâmicos aqui considerados.

A seguir, no Capítulo 2, os métodos e recursos utilizados neste projeto são detalhados. Os capítulos posteriores referem-se ao estudo do relacionamento estrutura-dinâmica nos diversos

casos já comentados nesta introdução: análise das correlações grau-atividade em redes direcio-

nadas utilizando os conceitos de reciprocidade e acessibilidade (Capítulo 3); definição e análise de um modelo de crescimento de rede com ligação preferencial baseada na atividade (Capí-

∗ Esse trabalho foi submetido ao periódico Bioinformatics.

38

1 Introdução

tulo 4); desenvolvimento de uma metodologia para caracterização da distribuição de subgrafos e aplicação no estudo do relacionamento estrutura-dinâmica (Capítulo 5); estudo dos efeitos estruturais e dinâmicos da amostragem de redes corticais funcionais (Capítulo 6); e construção de uma rede integrada da bactéria Escherichia coli, com detecção de outliers no relacionamento

grau-atividade e análise da estrutura e função desses outliers com relação ao processo de regu-

lação gênica (Capítulo 7). Por fim, o Capítulo 8 contém as conclusões a respeito deste trabalho de doutorado∗ e indicações para trabalhos futuros.

∗ Durante o período de doutoramento também houve participação na elaboração de um artigo de revisão, publicado

no periódico Advances in Physics (91), o qual trata do uso de redes complexas em diversas áreas do conhecimento.

Além disso, encontra-se disponível um manuscrito (92) desenvolvido durante a participação na Complex Systems Summer School de 2010, um evento organizado pelo Santa Fe Institute.

39

2

Material e Métodos

2.1

Representação e Caracterização Estrutural de Re-

des

Uma rede é representada por um grafo G(V,E), onde V = {v1,v2, . . . ,vN} é o seu conjunto de

N vértices (ou nós) e E = {e1,e2, . . . ,eL} é o seu conjunto de L arestas (ou conexões). Uma

aresta ek é um par (vi,v j) que representa uma conexão entre os vértices vi ∈ V e v j ∈ V . Uma

rede pode ser codificada em uma matriz de adjacência A de ordem N × N, cuja posição A(i, j) é

igual a 1 se existe uma aresta direcionada do vértice i ao j. Caso contrário, A(i, j) é igual a 0.

Em uma rede não direcionada, uma conexão entre i e j implica A(i, j) = A( j,i) = 1, ou seja, a

matriz A é necessariamente simétrica. Note que aqui não consideramos autoconexões (loops),

de modo que A(i,i) = 0 para todo i. O grau∗ de entrada de um vértice i representa o número de conexões que terminam em i, e é dado por kin =

i

∑ j A( j,i). O grau de saída é o número de

ligações que partem de i: kout =

i

∑ j A(i, j). Em redes não direcionadas o grau ki de um vértice

i é dado por ki = kin = kout. Os valores máximos de grau são denotados por k

i

i

max, kin

max e kout

max.

A conectividade global de uma rede pode ser quantificada pelo grau médio k em redes não

direcionadas ou pelas médias kin ou kout no caso direcionado – note que a média do grau de

entrada é sempre igual à media do grau de saída.

Nas subseções seguintes, diversas métricas de redes complexas utilizadas neste projeto são

definidas (93), bem como outros conceitos relevantes. As implementações foram feitas nas linguagens C e Scilab, sendo que C foi utilizada nos casos com grandes demandas de eficiência

(como no cálculo da centralidade em redes grandes).

∗ Com frequência muito menor, grau é também chamado de conectividade por alguns autores (6). Grau é o termo derivado da teoria dos grafos.

40

2 Material e Métodos

2.1.1

Coeficiente de Agrupamento

Se dois vértices q e j estão ambos conectados a i, existe uma probabilidade de que q e j estejam

também conectados entre si. Essa probabilidade pode ser quantificada pelo coeficiente de agru-

pamento cci, o qual reflete a densidade de conexões existentes entre os vizinhos de um vértice

i. Considere o conjunto ηi dos vizinhos de i e o número de arestas εi que conectam os vizinhos

de i entre si em uma rede não direcionada:

ηi ={ j | A(i, j) = A( j,i) = 1, i = j} ,

(2.1)

εi =

A(u,v)/2 .

(2.2)

u,v∈ηi,u=v

O coeficiente de agrupamento de um vértice i é então definido como (12):

2εi

cci =

,

(2.3)

|ηi| (|ηi| − 1)

onde |ηi| é a cardinalidade de ηi, ou seja, é o número de vizinhos de i. No caso especial em que

o coeficiente médio da rede cc é zero, a rede é na verdade uma árvore, e se cci = 1 os vizinhos

de i formam um clique, ou seja, formam um subgrafo completo.

Em redes direcionadas é possível aplicar as medidas definidas para redes não direcionadas

desconsiderando-se as direções de suas arestas. Portanto, o coeficiente de agrupamento pode ser

calculado em redes direcionadas de acordo com as explicações dadas acima (essa abordagem foi

utilizada no Capítulo 4). Outra abordagem diferencia os vizinhos do vértice i entre os vizinhos de saída

out

in

η

e os de entrada

:

i

ηi

out

ηi

={ j | A(i, j) = 1, i = j} ,

(2.4)

in

ηi ={ j | A( j,i) = 1, i = j} .

(2.5)

O número de arestas entre esses vizinhos é dado, respectivamente, por:

out

εi

=

A(u,v) ,

(2.6)

u,v∈ out

η

,u=v

i

2.1 Representação e Caracterização Estrutural de Redes

41

in

εi =

A(u,v) .

(2.7)

u,v∈ in

η

,u=v

i

Portanto, os coeficientes de agrupamento de saída e de entrada são obtidos, respectivamente,

por:

out

ε

ccout

i

i

=

,

(2.8)

out

out

η

− 1

i

ηi

in

ε

ccin

i

i =

.

(2.9)

in

in

η

− 1

i

ηi

Esses coeficientes de agrupamento que diferenciam o sentido das arestas em redes direcionadas

foram utilizados no Capítulo 7.

2.1.2

Grau da Vizinhança

(nn)

O grau médio k

da vizinhança de um determinado vértice i pode ser calculada considerando-

i

se a média dos graus k j de todos os vizinhos j de i (16). Essa medida complementa o coeficiente de agrupamento ao considerar todas as conexões existentes na vizinhança de um vértice, e não

apenas as arestas que conectam os vizinhos entre si. O grau da vizinhança para a rede toda é

simplesmente tomado como a média entre todo os valores individuais, e é denotado por k(nn) .

2.1.3

Assortatividade

A assortatividade é outra medida relacionada à conectividade entre vizinhos, e mensura a cor-

relação entre os graus dos vértices que compartilham uma conexão. Em outras palavras, o

coeficiente de assortatividade indica se vértices de grau similar tendem a se conectar entre si

(rede assortativa), ou se vértices com alto grau tendem a se conectar com vértices de baixo grau

(rede não assortativa) (94). Esse coeficiente pode ser computado ao se aplicar o coeficiente de correlação de Pearson nos graus que aparacem nas extremidades de cada aresta:

1

1

2

(ki + k j)A(i, j)

r =

L ∑ j>i kik jA(i, j) −

1

L ∑ j>i 2

,

(2.10)

1

1

2

(k2 + k2)A(i, j) − 1

1 (k

L ∑ j>i 2

i

j

L ∑ j>i 2

i + k j)A(i, j)

42

2 Material e Métodos

onde L é o número total de arestas na rede. No caso r → 1, a rede é assortativa, e se r → −1, a

rede é não assortativa. Quando r → 0, não há correlação significante entre os graus dos vértices.

No caso de redes direcionadas, considerou-se aqui as correlações entre os graus de entrada (rii,

indegree-indegree) e entre os graus de saída (roo, outdegree-outdegree).

2.1.4

Grau Hierárquico

A estrutura de uma rede pode ser quantificada ao longo de progressivos níveis mesoscópicos.

Uma maneira de se realizar uma análise em escala intermediária é utilizando-se medidas hi-

erárquicas (ou concêntricas), as quais são calculadas levando-se em consideração vizinhanças

sucessivas em torno de cada vértice (95–97). Tais medidas hierárquicas são particularmente eficientes no fornecimento de informações adicionais a respeito da estrutura de uma rede, pois

elas consideram um número maior de vizinhanças do que as medidas tradicionais. Um conceito

(d)

essencial é o do anel R

, o qual é formado por todos os vértices distantes d − 1 arestas do

i

(d)

vértice de referência i. R

é também conhecido como nível hierárquico d do vértice i. O grau

i

(d)

hierárquico no nível d, denotado por k

, é então definido como o número de arestas que co-

i

(d)

(d+1)

nectam os anéis R

e R

– note que o grau tradicional k

i

i

i é equivalente ao grau hierárquico

(1)

k

. Considerando a rede toda, o grau hierárquico no nível d é apenas a média de todos os graus

i

hierárquicos da rede: k(d) .

No caso de redes direcionadas, pode-se considerar que as arestas não têm direção, e assim

obter os níveis e graus hierárquicos como explicado acima (essa abordagem foi utilizada no

Capítulo 4). Outra opção é considerar que os anéis sejam definidos pela direção das arestas: (d|out)

R

é então formado por todos os vértices j tal que o menor caminho que ligue i a j (agora

i

(d|in)

desconsiderando-se o sentido inverso) tenha comprimento d − 1; e, analogamente, R

con-

i

tém os vértices j tal que o menor caminho que ligue j a i tenha comprimento d − 1. O grau de

(d|out)

saída hierárquico k

no nível d é então definido como o número de conexões que partem do

i

(d|out)

(d+1|out)

(d|in)

nível R

para o nível R

; e o grau de entrada hierárquico k

no nível d é, portanto,

i

i

i

(d+1|in)

(d|in)

igual ao número de arestas que originam-se no nível R

e terminam no nível R

. Essa

i

i

2.1 Representação e Caracterização Estrutural de Redes

43

abordagem foi utilizada no Capítulo 7. Note que o grau de saída tradicional kout é equivalente a i

(1|out)

(1|in)

k

, e o grau de entrada tradicional kin é equivalente a k

.

i

i

i

2.1.5

Coeficiente de Agrupamento Hierárquico

Essa medida é uma generalização do coeficiente de agrupamento tradicional por meio do em-

(d)

prego de vizinhanças mais distantes. Esse coeficiente é dado pelo número de arestas ε

no

i

(d)

respectivo anel R

dividido pelo número total de possíveis arestas que podem existir entre os

i

vértices do referido anel (96). Formalmente, tem-se:

(d)

(d)

cc

=

i

,

(2.11)

i

| (d)

(d)

R

|(|R

| − 1)

i