Na natureza e na ciência, dados e informações que desviam significativamente da média frequentemente possuem grande relevância. Esses dados são usualmente denominados na literatura como outliers. A identificação de outliers é importante em muitas aplicações reais, tais como detecção de fraudes, diagnóstico de falhas, e monitoramento de condições médicas. Nos últimos anos tem-se testemunhado um grande interesse na área de Redes Complexas. Redes complexas são grafos de grande escala que possuem padrões de conexão não trivial, mostrando-se uma poderosa maneira de representação e abstração de dados. Embora um grande montante de resultados tenham sido reportados nesta área de pesquisa, pouco tem sido explorado acerca de detecção de outliers em redes complexas. Considerando-se a dinâmica de uma caminhada aleatória, foram propostos neste trabalho uma medida de distância e um método de ranqueamento de outliers. Através desta técnica, é possível detectar como outlier não somente nós periféricos, mas também nós centrais (hubs), depedendo da estrutura da rede. Também foi identificado que existem características bem definidas entre os nós outliers, relacionadas a funcionalidade dos mesmos para a rede. Além disso, foi descoberto que nós outliers têm papel importante para a rotulação a priori na tarefa de detecção de comunidades semi-supervisionada. Isto porque os nós centrais são bons difusores de informação e os nós periféricos encontram-se em regiões de borda de comunidade. Baseado nessa observação, foi proposto um método de detecção de comunidades semi-supervisionado. Os resultados de simulações mostram que essa abordagem é promissora / In nature and science, information and data that deviate significantly from the average value often have great relevance. These data are often called in literature as outliers. Outlier identification is important in many real applications, such as fraud detection, fault diagnosis, monitoring of medical conditions. In recent years, it has been witnessed a great interest in the area of Complex Networks. Complex networks are large-scale graphs with non-trivial connection patterns, proving to be a powerful way of data representation and abstraction. Although a large amount of results have been reported in this research area, little has been explored about the outlier detection in complex networks. Considering the dynamics of a random walk, we proposed in this paper a distance measure and a outlier ranking method. By using this technique, we can detect not only peripheral nodes, but also central nodes (hubs) as outliers, depending on the network structure. We also identified that there are well defined relationship between the outlier nodes and the functionality of the same nodes for the network. Furthermore, we found that outliers play an important role to label a priori nodes in the task of semi-supervised community detection. This is because the hubs are good information disseminators and peripheral nodes are usually localized in the regions of community edges. Based on this observation, we proposed a method of semi-supervised community detection. The simulation results show that this approach is promising
| Identifer | oai:union.ndltd.org:IBICT/oai:teses.usp.br:tde-06102010-141931 |
| Date | 20 September 2010 |
| Creators | Bilzã Marques de Araújo |
| Contributors | Zhao Liang, Marcos Gonçalves Quiles, Francisco Aparecido Rodrigues |
| Publisher | Universidade de São Paulo, Ciências da Computação e Matemática Computacional, USP, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da USP, instname:Universidade de São Paulo, instacron:USP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0013 seconds