Dados do Trabalhos de Conclusão

INSTITUTO MILITAR DE ENGENHARIA
ENGENHARIA DE DEFESA (31007015011P8)
UMA ABORDAGEM PARA DETECÇÃO DE COMUNIDADES EM REDES COMPLEXAS BASEADA EM INFORMAÇÕES DE DOMÍNIO
MARCIO VINICIUS DIAS
DISSERTAÇÃO
08/12/2016

Os constantes avanços tecnológicos ocorridos sobretudo nos últimos anos têm levado a um expressivo aumento no volume de dados armazenados pelo mundo. Nesse cenário, surgiram as chamadas redes complexas, que são grafos que se caracterizam pela presença de grandes quantidades de vértices interconectados por um grande número de arestas. Entre os clássicos exemplos de redes complexas estão as redes sociais tais como Facebook, Google+, Twitter, Wikipedia, e Flickr. Um dos principais problemas investigados no contexto dessas redes é a detecção de comunidades. Tal problema consiste em identificar grupos de vértices que contêm alta densidade de arestas dentro de cada grupo e baixa densidade de arestas que interligam vértices de grupos distintos. O tratamento deste tipo de problema possui aplicações em diversas áreas, em especial na área da segurança. Pode permitir, por exemplo, o combate ao terrorismo, tráfico de drogas, pedofilia, racismo, dentre outros crimes cada vez mais frequentes nas redes sociais. Por limitarem seu processamento apenas à consideração de aspectos topológicos dos grafos, a maioria dos algoritmos clássicos da área de detecção de comunidades deixa de utilizar informações do domínio da aplicação, importantes na efetiva identificação de grupos sociais. Os poucos algoritmos que utilizam informação de domínio para detectar comunidades têm sua aplicação restrita a redes homogêneas, ou seja, redes que contêm apenas um tipo de vértice e um tipo de aresta. No entanto, grande parte das redes complexas da atualidade são heterogêneas (vários tipos de vértices e de arestas) e, como tal, não podem ser amplamente exploradas pelos algoritmos clássicos de detecção de comunidades. Assim sendo, diante desse contexto, o presente trabalho tem como objetivo geral demonstrar que a utilização de informações de domínio existentes em redes complexas heterogêneas pode contribuir para tornar mais precisa a tarefa de detecção de comunidades. Para tanto, foi concebida, implementada e avaliada uma abordagem que realiza clusterização de dados de domínio como uma etapa prévia ao processo de detecção de comunidades. Desta forma, a clusterização de dados assegura o agrupamento de vértices e arestas em função da semântica dos dados de domínio existentes. Em seguida, a abordagem proposta permite detectar comunidades estruturalmente densas a partir de cada grupo identificado, assegurando, assim, a coesão semântica e topológica entre os vértices de cada comunidade detectada. Os experimentos realizados em conjuntos de dados provenientes dos contextos militar e civil mostraram que o uso de informações de domínio pode, de fato, levar a interessantes partições contendo comunidades semântica e topologicamente coesas.

DETEÇÃO;COMUNIDADE;REDE;COMPLEXA;CAMINHO;SEMÂNTICO;DOMÍNIO;ATRIBUTO
The constant technological advances occurred over the last few years have led to an expressive increase in the volume of data stored around the world. In this scenario, complex networks emerged. They are graphs characterized by the presence of large number of nodes interconnected by a large number of edges. Social networks such as Facebook, Google+, Twitter, Wikipedia, and Flickr are classical examples of complex networks. Community detection is one of the main problems investigated in the context of those networks. Such problem tries to identify groups of vertices that contain high density of edges within each group and low density of edges that interconnect vertices of different groups. The treatment of this type of problem has applications in several areas, especially in security. It may allow, for example, the fight against terrorism, drug trafficking, pedophilia, racism, among other crimes increasingly frequent in social networks. Classic community detection algorithms only consider topological aspects of the graph. Although important in social group characterization, few algorithms take contextual information into consideration in order to detect communities. Moreover, those algorithms are restricted to homogeneous graphs (graphs that contain only one type of node and only one type of edge). However, most complex networks are heterogeneous (various types of vertices and edges). Hence, those networks cannot be widely submeted to the existing community detection algorithms that consider contextual information. Thus, the present work aims to demonstrate that the use of existing contextual information in heterogeneous complex networks can contribute to make the task of detecting communities more precise. In order to accomplish this goal, a community detection approach that takes both topological and contextual information into consideration was formulated, implemented and evaluated. This approach introduces data clustering as a pre-processing step for the community detection procedure. Data clustering ensures the grouping of nodes and edges according to the semantics of the existing contextual data. Then, the proposed approach allows the detection of structurally dense communities from each identified cluster. This providence ensures semantic and topological cohesion among the nodes of each detected community. Experiments with military and civil datasets have shown that the use of contextual information may, in fact, lead to interesting partitions containing semantically and topologically cohesive communities.
DETECTION;COMUNITY;NETWORK;COMPLEX;PATH;SEMANTICS;DOMAIN;ATTRIBUTE
1
115
PORTUGUES
INSTITUTO MILITAR DE ENGENHARIA
O trabalho não possui divulgação autorizada

Contexto

ENGENHARIA DE DEFESA
COMUNICAÇÕES E INTELIGÊNCIA EM SISTEMAS DE DEFESA
-

Banca Examinadora

RONALDO MOREIRA SALLES
DOCENTE - PERMANENTE
Sim
Nome Categoria
RONALDO RIBEIRO GOLDSCHMIDT Participante Externo
EDUARDO BEZERRA DA SILVA Participante Externo
MARIA CLAUDIA REIS CAVALCANTI Participante Externo
PAULO FERNANDO FERREIRA ROSA Docente - PERMANENTE

Vínculo

CLT
Empresa Privada
Pesquisa
Sim