Título: Local Symmetry in Erdős–Rényi Graphs

Palestrante: Jefferson Elbert Simões (DIA/UNIRIO)
Data: 16/08/2021
Horário: 15:00h
Local: Transmissão online.

Resumo: Real-world networks are often understood as being symmetrical, meaning that vertices can be found which perform similar or equivalent structural roles (such as hubs from different communities in social networks, or functional regions in neuronal networks). These roles are usually associated with their topological placement relative to its surroundings; however, traditional mathematical formulations of graph symmetry are based on automorphism groups, which depend fundamentally on global structure and do not account for similarities in local structures. In this work, we introduce the concept of local symmetry, which reflects the structural equivalence of vertices' egonets while generalizing classical conceptualizations of symmetry such as automorphism and isomorphism. We also study the emergence of local asymmetry in Erdős–Rényi graphs, identifying regimes of both asymptotic local symmetry and asymptotic local asymmetry. We find that local symmetry persists at least to an average degree of n^{1/3} and local asymmetry emerges at an average degree not greater than n^{1/2}, which are regimes of much larger average degree than for traditional, global asymmetry.
Joint work with Daniel Figueiredo (COPPE/UFRJ) and Valmir Barbosa (COPPE/UFRJ).
All the talks are held in English.

The videos of the online seminars are available:
2020 
2021-1

For the second semester, a few days after each meeting the video should be available at HERE.