Tese

Rumour spreading in dynamic random graphs (2024)

• Authors:
  • Pereira, Vicenzo
  • Gallo, Alexsandro Giacomo Grimbert (Orientador)
• Autor USP: PEREIRA, VICENZO BONASORTE REIS - Interinstitucional de Pós-Graduação em Estatística
• Unidade: Interinstitucional de Pós-Graduação em Estatística
• Sigla do Departamento: SME
• DOI: 10.11606/D.104.2024.tde-15012026-172418
• Subjects: GRAFOS ALEATÓRIOS; CADEIAS DE MARKOV; PROCESSOS ESTOCÁSTICOS; PROCESSOS DE RAMIFICAÇÃO
• Keywords: Dynamic random graphs; Modelo estocástico de blocos; Propagação de rumor; Rumour spreading; Stochastic block model; Strong stationary times; Tempos estacionários fortes
• Language: Inglês
• Abstract: Nós estudamos propagação de rumor em grafos aleatórios dinâmicos. Começando com um único vértice informado, a informação se propaga até atingir todos os vértices do grafo (finalização), de acordo com o seguinte processo. A cada passo k, a informação é enviada, no k-ésimo grafo aleatório gerado, para os vizinhos de vértices informados. O modo como essa informação é propagada de vértice para vértice a cada passo depende do "protocolo". Primeiro consideramos uma sequência de grafos em que a presença e ausência de uma aresta seque a dinâmica de uma cadeia de Markov. Propomos um método baseado em tempos estacionários fortes que permite limitar o tempo até a finalização na dinâmica markoviana utilizando limitantes do tempo até a finalização no caso i.i.d.. Também consideramos o rumor se espalhando através do protocolo Push (a cada passo, vértices informados enviam o rumor para um de seus vizinhos, escolhido uniformemente ao acaso) em uma sequência de grafos independentes do modelo estocástico de blocos. Somos capazes de encontrar limitantes para o tempo até a finalização utilizando comparações com propagação de informação em grafos aleatórios dinâmicos com vértices céticos (vértices que não se tornam informados) e vértices contidos (nós, que após serem informados, não passam a informação adiante).
• Imprenta:
  • Publisher place: São Carlos
  • Date published: 2024
• Data da defesa: 19.02.2024


Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).

Status:

Artigo publicado em periódico de acesso aberto (Gold Open Access)

Versão do Documento:

Versão publicada (Published version)

Acessar versão aberta:

• PDF de acesso aberto

Por se tratar de integração com serviço externo, podem existir diferentes versões do trabalho (como preprints ou postprints), que podem diferir da versão publicada.

---

How to cite

A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

• ABNT

  PEREIRA, Vicenzo. Rumour spreading in dynamic random graphs. 2024. Dissertação (Mestrado) – Universidade de São Paulo, São Carlos, 2024. Disponível em: https://teses.usp.br/teses/disponiveis/104/104131/tde-15012026-172418/. Acesso em: 06 maio 2026.

• APA

  Pereira, V. (2024). Rumour spreading in dynamic random graphs (Dissertação (Mestrado). Universidade de São Paulo, São Carlos. Recuperado de https://teses.usp.br/teses/disponiveis/104/104131/tde-15012026-172418/

• NLM

  Pereira V. Rumour spreading in dynamic random graphs [Internet]. 2024 ;[citado 2026 maio 06 ] Available from: https://teses.usp.br/teses/disponiveis/104/104131/tde-15012026-172418/

• Vancouver

  Pereira V. Rumour spreading in dynamic random graphs [Internet]. 2024 ;[citado 2026 maio 06 ] Available from: https://teses.usp.br/teses/disponiveis/104/104131/tde-15012026-172418/

Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

• On random walks with geometric lifetimes