O estudo de redes complexas tem alavancado um tremendo interesse em anos recentes. Uma das características salientes de redes complexas é a presença de comunidades, ou grupos de nós densamente conectados. A detecção de comunidades pode não apenas ajudar a entender as estruturas topológicas de redes complexas, mas também pode fornecer novas técnicas para aplicações reais, como mineração de dados. Neste trabalho, propomos um novo modelo para detecção de comunidades em redes complexas, no qual várias partículas caminham na rede e competem umas com as outras para marcar seu próprio território e rejeitar partículas intrusas. O processo atinge o equilíbrio dinâmico quando cada comunidade tem apenas uma partícula. Nossa abordagem não apenas pode obter bons resultados na detecção de comunidades, como também apresenta diversas características interessantes: 1) O processo de competição de partículas é similar a muitos processos naturais e sociais, tais como competição de animais por recursos, exploração territorial por humanos (animais), campanhas eleitorais, etc.. Portanto, o modelo proposto neste trabalho pode ser útil para simular a dinâmica evolutiva de tais processos. 2) Neste modelo, nós introduzimos uma regra para controlar o nível de aleatoriedade do passeio da partícula. Descobrimos que uma pequena porção de aleatoriedade pode aumentar bastante a taxa de detecção de comunidades. Nossa descoberta é análoga ao notável fenômeno chamado ressonância estocástica onde o desempenho de um sistema determinístico não-linear pode ser bastante melhorado através da introdução de um certo nível de ruído. É interessante notar que tal fenômeno é observado em uma situação diferente aos sistemas clássicos de ressonância estocástica. 3) Nossa descoberta indica que a aleatoriedade tem um papel importante em sistemas evolutivos. Ela serve para automaticamente escapar de armadilhas não desejáveis e explorar novos espaços, isto é, ela é um descobridor de novidades. 4) Uma análise quantitativa para processo de competição entre duas particulas e duas comunidades foi conduzida, a qual é um passo de avanço para desenvolvimento de teoria fundamental de aprendizado competitivo / Study of complex networks has triggered tremendous interests in recent years. One of the salient features of complex networks is the presence of communities, or groups of densely connected nodes. Community detection can not only help to understand the topological structure of complex networks, but also provide new techniques for real applications, such as data mining. In this work, a new model for complex network community detection is proposed, in which several particles walk in the network and compete with each other to mark their own territory and reject particle intruders. The process reaches dynamics equilibrium when each community has only one particle. This approach not only can get good community detection results, but also presents several interesting features: 1) The particle competition process is rather similar to many natural and social processes, such as resource competition by animals, territory exploration by humans (animal), election campaigns, etc.. Thus, the model proposed in this work may be useful to simulate dynamical evolution of such processes. 2) In this model, a rule to control the level of randomness of particle walking is introduced. We found a small portion of randomness can largely improve the community detection rate. Such a finding is analogous to a remarkable phenomenon called stochastic resonance (SR) where the performance of a nonlinear deterministic system can be largely enhanced by introducing a certain level of noise. Interestingly, such a SR-type phenomenon is observed in quite a different situation from classical SR systems. 3) Our finding indicates that randomness has an important role in evolutionary systems and in machine learning. It serves to automatically escape some undesirable traps and explore new spaces, i.e., it is a novelty finder. 4) A quantitative analysis for two particle competition in two communities is provided. This is a step toward the development of fundamental theory of competitive learning
| Identifer | oai:union.ndltd.org:usp.br/oai:teses.usp.br:tde-01072008-141436 |
| Date | 19 May 2008 |
| Creators | Alonso, Ronaldo Luiz |
| Contributors | Liang, Zhao |
| Publisher | Biblioteca Digitais de Teses e Dissertações da USP |
| Source Sets | Universidade de São Paulo |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | Tese de Doutorado |
| Format | application/pdf |
| Rights | Liberar o conteúdo para acesso público. |
Page generated in 0.0024 seconds