Análise de percolação em redes complexas

Dando continuidade a um projeto iniciado na UFF, propomos estudar a rede de compartilhamento de artigos CiteULike. Retomaremos o estudo das prepriedades geométricas e de transições para o comportamento da evolução de um grafo complexo obtido a partir de dados reais.  O objetivo do inicial do estudo, foi criar uma rede baseado em dados de conexões reais, fornecido de forma codificada pelo próprio site. A rede foi montada pelo agrupamento de perfis (usuário) que distribuem e compartilham entre um conjunto de artigos, artigos estes, vinculados aos perfis. Esses artigos são caracterizados por tags, palavras chaves que indicam o assunto a qual o artigo está relacionado. A significância das tags foram mantidas intactas, sendo codificados apenas outros dados dos perfis.  Uma base de dados é disponibilizada pelo próprio site, que fornece informações de um período desde 2004 até os dias de hoje, contendo todas as informações das evolução e conexão dos perfis tais como: artigos, tags e evolução temporal do crescimento de cada perfil. Várias perguntas podem ser feitas acerca dessas estruturas, perguntas que nos remetem a um estudo que se relacionam as redes complexas bem como um estudo sobre a correlação de grupos de interesses ou comunidades de assuntos  a partir da análise dessas tags. Inicialmente, foi varrida toda a rede até a data de 2008, época em que fiz os estudos preliminares. Desta varredura, foram selecionados os 1000 artigos mais citadas para se trabalhar de maneira mais objetiva e rápida em um estudo prévio.  

Descrição do Banco de Dados.

A base de dados fornecida pelo CiteULike é estruturada da seguinte forma: Coluna 1- (identificação dos usuários)

Coluna 2 – (identificação dos artigos) Coluna 3- (Evolução temporal) Coluna 4 – (tags dos artigos)

A estrutura é construída considerando-se que o usuário se repete para cada nova tag adicionada a um artigo, de maneira que que se um artigo tem 10 tags, o usuário se repetirá 10 vezes juntamente com o artigo.

UsuáriosArtigosEvoluçãoTags
usuário1 artigo_a (####) tag_a1
usuário1 artigo_a (####) tag_a2
usuário1 artigo_a (####) tag_a3
usuário1 artigo_a (####) tag_a4
usuário1 artigo_a (####) tag_a5
usuário1 artigo_b (####) tag_b1
usuário1 artigo_b (####) tag_b2
usuário1 artigo_b (####) tag_b3

Na tabela acima, o usuário 1 possui 2 artigos e 8 tags em seu perfil. Nossa proposta inicial foi filtrar toda a base de dados (2004 a 2008), que compreende um período de evolução do CiteULike  com aproximadamente 10.000.000 linhas para serem filtradas. Serão filtrados os 1000 artigos mais citados. Iremos considerar em nossa análise apenas a segunda e quarta coluna, uma vez que é nosso interesse montar uma rede entre os artigos conectada por tags comuns.

Click aqui e veja o código

O código acima retorna um arquivo “ordem.dat” que organiza em ordem decrescente os nmax artigos mais citado. Varremos toda a base de dados (11.000.000 de linhas) e retornamos em “ordem.dat” os 1.000 artigos mais citados. O arquivo segue a mesma etrutura da tabela citada anteriormente, no entanto são armazenados apenas os artigos e suas respectivas tags. Click aqui (ordem.dat.tar.gz)para fazer o download do arquivo.

Uma primeira tentativa de modelagem matemática

Iremos propor uma abordagem matemática inspirada na modelagem para a rede citeulike, para tanto, as definições apresentadas aqui, serão adiantes comparadas com as simulações obtidas de dados reais da rede.

Considere um grafo \(\mathcal{G}^n_{k\,p}\) formado por \(k\) sítios e \(p\) ligações, sendo que cada sítio pode conter até \(n\) tag´s. As tags são distribuídas nos sítios, imaginando-se que cada sítio pode ser representado por um vetor. De maneira geral representaremos o k-ésimo sítio que contêm \(m\) das \(n\) tag´s da forma

\[\begin{eqnarray} {\bf S}_i^m={\bf t}_i^1+{\bf t}_i^2+{\bf t}_i^3+...+{\bf t}_i^m\end{eqnarray}\]

sendo (\(m<n\)) e \(m\), \(n\) e \(k\) números  inteiros. Os t-ésimos representam a ordem, número inteiro representando a ordem da tag, na lista de tag´s. Por exemplo, considere a lista de tag´s:

Ordem Tag
1 arroz
2 feijão
3 trigo
...  
k ésima tag xxx

o sítio \({\bf S}_5^2={\bf t}_5^1+{\bf t}_5^3\) tem as tag´s arroz e trigo e de maneira geral, também pode ser representado da forma

\[\begin{eqnarray}{\bf S}_5^2={\bf t}_5^1+0\dot{}{\bf t}_5^2+{\bf t}_5^3+0\dot{}{\bf t}_5^4+0\dot{}{\bf t}_5^5+...+0\dot{}{\bf t}_5^m \end{eqnarray}\]

Para o exemplo da rede citeulike que adotamos, o grafo é formado por sítios que representam os artigos, sendo que cada artigo tem um conjunto de \(m\) tag´s distintas. Para o caso em questão, dois sítios \(i\) e \(j\) se conectam se existe um número de tag´s em comum maior que um parâmetro de corte \(w\). Para nossa abordagem, o número de tag´s em comum para dois sítios quaisquer \({\bf S}_i^m\) e \({\bf S}_j^{m´}\)  do grafo \(\mathcal{G}_{k\,p}^n\) com \(m\) e \(m´\) tag,s respectivamente, é definido como

\[\begin{eqnarray} N={\bf S}_i^m\dot{}{\bf S}_j^{m´}\end{eqnarray}\].

Podemos mensurar de maneira mais objetiva, se definirmos um peso que envolva o parâmetro de corte \(w\), dessa forma, definiremos um peso dado por

\[\begin{eqnarray}\label{peso} P&=&\frac{N}{w}\nonumber\\&=&\frac{{\bf S}_i^m\dot{}{\bf S}_j^{m´}}{w}\end{eqnarray}\].

Para \(P>1\), a conexão é aceita, caso contrário, rejeitada.

Para um conjunto dos mil artigos mais citados dos dados analisados do citeulike, aplicamos a Eq.(\ref{peso}) para diferentes valores de \(w\) e para cada valor de \(w\) calculamos o tamanho do maior cluster que se formou. Obtemos o gráfico a seguir

Figura 1 - Relação entre o maior cluster e o parâmetro de corte \(w\)

Foram utilizados scriptes em Perl na seguinte sequencia:

  • Criar a rede principal a partir dos mil artigos mais citados, obtendo para cada um deles um conjunto de tags;
  • Propor um valor de corte para \(w\) e calcular o maior cluster restante.

a seguir os códigos utilizados

Click aqui: Criando rede a partir dos artigos mais citados

Clique aqui: Calculando o maior cluster

Percebe-se claramente que a figura 1 tem um comportamento de uma transição entre um estado em que todos os sítios estão conectados (cluster único) a um estado de fragmentação, passando por um possível valor de corte bem definido w. Estamos repetindo as analises para um número muito elevado de dados, uma vez que a rede está ativa desde 2004. Após a repetição, elaboraremos um modelo físico matemático baseado no estudo de percolação em redes complexas. 

 

Trabalhos no Bloco