Published January 23, 2013 | Version v1
Journal article

Vertex pursuit in random directed acyclic graphs

Description

We examine a dynamic model for the disruption of information flow in hierarchical social networks by considering the vertex-pursuit game Seepage played in directed acyclic graphs (DAGs). In Seepage, agents attempt to block the movement of an intruder who moves downward from the source node to a sink. The minimum number of such agents required to block the intruder is called the green number. We propose a generalized stochastic model for DAGs with given expected total degree sequence. Seepage and the green number is analyzed in stochastic DAGs in both the cases of a regular and power law degree sequence. For each such sequence, we give asymptotic bounds (and in certain instances, precise values) for the green number.

Abstract

International audience

Additional details

Identifiers

URL
https://hal.science/hal-00923080
URN
urn:oai:HAL:hal-00923080v1