dc.contributor.author | Pereira, Vicenzo Bonasorte Reis | |
dc.date.accessioned | 2024-07-11T11:44:02Z | |
dc.date.available | 2024-07-11T11:44:02Z | |
dc.date.issued | 2024-02-19 | |
dc.identifier.citation | PEREIRA, Vicenzo Bonasorte Reis. Rumour spreading in dynamic random graphs. 2024. Dissertação (Mestrado em Estatística) – Universidade Federal de São Carlos, São Carlos, 2024. Disponível em: https://repositorio.ufscar.br/handle/ufscar/19880. | * |
dc.identifier.uri | https://repositorio.ufscar.br/handle/ufscar/19880 | |
dc.description.abstract | We study rumour spreading in dynamic random graphs. Starting with a single informed vertex, the information flows until it reaches all the vertices of the graph (completion), according to the following process. At each step $k$, the information is propagated to neighbours, in the $k$-th generated random graph, of the informed vertices. The way this information propagates from vertex to vertex at each step will depend of the "protocol".
First we consider a sequence of graphs in which the presence or absence of an edge follows the dynamic of a Markov chain. We provide a method based on strong stationary times allowing to bound the completion time for the Markov dynamic using bounds on the completion time in the i.i.d. dynamic.
We also consider the rumour spreading according to the Push Protocol (at every round, informed nodes send the rumour to one of their neighbours, chosen uniformly at random) in a sequence of independent stochastic block model random graphs. We are able to bound the completion time in this setting using comparisons with rumour spreading in dynamic random graphs with skeptical nodes (nodes that cannot become informed) and stifler nodes (nodes that, after being informed, do not spread the information further). | eng |
dc.description.sponsorship | Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) | por |
dc.language.iso | eng | por |
dc.publisher | Universidade Federal de São Carlos | por |
dc.rights | Attribution-NonCommercial-NoDerivs 3.0 Brazil | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/br/ | * |
dc.subject | Strong stationary times | eng |
dc.subject | Propagação de rumor | por |
dc.subject | Rumour spreading | eng |
dc.subject | Tempos estacionários fortes | por |
dc.subject | Modelo estocástico de blocos | por |
dc.subject | Dynamic random graphs | eng |
dc.subject | Stochastic block model | eng |
dc.title | Rumour spreading in dynamic random graphs | eng |
dc.title.alternative | Propagação de informação em grafos aleatórios dinâmicos | por |
dc.type | Dissertação | por |
dc.contributor.advisor1 | Gallo, Alexsandro Giacomo Grimbert | |
dc.contributor.advisor1Lattes | http://lattes.cnpq.br/4037274656833325 | por |
dc.description.resumo | 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 segue 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 (vértices, que após serem informados, não passam a informação adiante). | por |
dc.publisher.initials | UFSCar | por |
dc.publisher.program | Programa Interinstitucional de Pós-Graduação em Estatística - PIPGEs | por |
dc.subject.cnpq | CIENCIAS EXATAS E DA TERRA::PROBABILIDADE E ESTATISTICA::PROBABILIDADE::PROCESSOS ESTOCASTICOS ESPECIAIS | por |
dc.publisher.address | Câmpus São Carlos | por |
dc.contributor.authorlattes | http://lattes.cnpq.br/9468034476394021 | por |