Detecção de comunidades em redes complexas

Adilton C. Santos Universidade Federal do ABC Comunicação e Redes – BC0506 – Atividade 1 Prof. Raphael Yokoingawa de Camargo – 1T2010 ____________________________________________________________

________________________ DETECÇÃO DE COMUNIDADES EM REDES COMPLEXAS: UM MODELO DE CORRELAÇÃO OSCILATÓRIA Uma característica notável observada nas redes complexas é a presença de comunidades, também definidas como grupos de vértices da rede densamente conectados. Essas comunidades representam padrões de interação entre os vértices da rede. A identificação e a similaridade das características dos vértices que as compõem são fatores importantes para a formação e o entendimento dos mecanismos de crescimento de uma comunidade. Desta forma, por meio da identificação e do estudo das comunidades é possível obter informações pertinentes ao domínio da rede. O processo de detecção de comunidades em uma rede não é computacionalmente trivial. Dada a grande quantidade de modelos propostos e seus distintos mecanismos computacionais, uma maneira usual de compará-los é utilizando redes randômicas clusterizadas. Tais redes são compostas por N vértices divididos em M grupos. A rede é formada com base em duas probabilidades definidas: a probabilidade de ligação entre vértices de uma mesma comunidade e a probailidade de ligação entre vértices de comunidades distintas. Considerando o dilema precisão-eficiência observado em um estudo comparativo de diversas técnicas, uma nova técnica para a detecção de comunidades é proposta, baseada na teoria da correlação temporal. A teoria da correlação temporal define que um objeto é representado pela correlação temporal dos disparos de células neurais espacialmente distribuídas que representam diferentes características de um mesmo objeto, enquanto que neurônios codificando características de objetos distintos não possuem suas atividades correlacionadas. Uma maneira natural de realizar a correlação temporal é feita através de osciladores: cada objeto é