Two Problems On The Structure-Identity Relationship On Networks
Autores
|
6058 |
2341,753
|
|
|
6059 |
2341,753
|
Informações:
Publicações do PESC
Diversos fenômenos do mundo real podem ser modelados através de redes (grafos) - conjuntos de objetos (vértices) entre os quais codificamos relacionamentos (arestas) de alguma natureza. Redes como a rede neuronal humana ou a rede de amizades do Facebook possuem um papel fundamental no desenrolar de diversos processos. Tendo em vista a quantidade cada vez maior de dados disponíveis sobre suas estruturas, e um dos grandes desa os da atualidade compreender a relação entre identidades de objetos nestas redes e as estruturas que os conectam, seja visando realizar sua identificação precisa ou garantir seu anonimato.
Esta tese aborda dois problemas situados neste contexto. O primeiro problema trata do conceito de simetria como fonte de identidade estrutural para vértices em uma rede e sua relação com estruturas locais em torno destes vértices. Para estudar esta relação, propomos o conceito de simetria local utilizando uma modelagem hierárquica baseada em vizinhanças em torno de vértices. Aplicamos esta abordagem ao modelo Erdös-Rényi de grafos aleatórios e provamos a existência de regimes assintóticos de simetria local e de assimetria local, com a transição entre estes regimes ocorrendo em graus médios muito superiores a simetria tradicional.
O segundo problema é conhecido como casamento de múltiplas redes e trata da recuperação de um emparelhamento oculto entre vértices de múltiplas redes distintas utilizando informação contida na correlação estrutural entre estas redes. Propomos uma representação matemática deste problema baseada no conceito de hiperpermutação, e apresentamos um modelo para múltiplos grafos de Erdös-Rényi com estruturas correlacionadas. Introduzimos três métricas distintas de descasamento estrutural de hiperpermutações e derivamos diversos resultados sobre o comportamento estatístico destas métricas para o modelo proposto.
Several real-world phenomena can be modeled using networks (graphs) - sets of objects (vertices) between which we encode relationships (edges) of some nature. Networks such as the human neural network or the Facebook friendship network have a fundamental role in the development of several processes. Due to the ever increasing amount of data available on their structures, one of the great current challenges is to understand the relationship between identities of objects in these networks and the structures that connect them, whether we aim to precisely perform their identification or assure their anonymity.
This thesis addresses two problems within this context. The first problem deals with the concept of symmetry as source of structural identity for vertices in a network and its relationship with local structures around these vertices. To study this relationship, we propose the concept of local symmetry using a hierarchical model based on neighborhoods around vertices. We apply this approach to the Erdös-Rényi model of random graphs and we prove the existence of asymptotic regimes of local symmetry and of local asymmetry, with the transition between these regimes taking place in much higher average degrees than for traditional symmetry.
The second problem is known as multiple network matching and deals with the recovery of a hidden matching between vertices of multiple distinct networks using information obtained from the structural correlation between these networks. We propose a mathematical representation of this problem based on the concept of hyperpermutation, and present a model for multiple Erdös-Rényi graphs with correlated structures. We introduce three distinct statistics for structural mismatch of hyperpermutations and we derive several results about their statistical behavior for the proposed model.