In applications of group testing in networks, e.g. identifying individuals who are infected by a disease spread over a network, exploiting correlation among network nodes provides fundamental opportunities in reducing the number of tests needed. We model and analyze group testing on n correlated nodes whose interactions are specified by a graph G. We model correlation through an edge-faulty random graph formed from G in which each edge is dropped with probability$1-r$, and in the newly formed graph, all nodes in the same component have the same state. We consider three classes of graphs: cycles and trees, d-regular graphs and stochastic block models or SBM, and obtain lower and upper bounds on the number of tests needed to identify the defective nodes. Roughly speaking, we use correlation among the states of the nodes to transform the problem into that of a smaller graph with independent node states. This enhancement is quantified through the ratio of the diminished node count to the overall count of nodes, n; thus, a lower ratio signifies superior performance. The lower bounds are derived by illustrating a strong dependence of the number of tests needed on the expected number of components. In this regard, we establish a new approximation for the distribution of component sizes in “d-regular trees” which may be of independent interest and leads to a lower bound on the expected number of components in d-regular graphs. The upper bounds are found by forming dense subgraphs in which nodes are more likely to be in the same state. When G is a cycle or tree, we show an improvement by a factor of$\log (1/r)$. For grid, a graph with almost$2n$edges, the improvement is by a factor of$(1-r) \log (1/r)$, indicating drastic improvement compared to trees. When G has a larger number of edges, as in SBM, the improvement can scale in n.

Emerging V2X technology enables vehicles to exchange messages with each other (V2V) and with signaling infrastructure (I2V) on the roadways. Information propagation in transportation networks is highly influenced by both vehicle mobility and wireless communication. As for vehicle mobility, realistic traffic flow changes with time, exhibiting sharp time-triggered transitions, due to external factors such as traffic lights. Thus, mobility process is temporally heterogeneous and not smooth, which fundamentally alters the dynamics of V2X (V2V and I2V together) message propagation in a complex manner. As for wireless communication, communication heterogeneity is an integral component of V2X systems - different types of vehicles may have different communication capabilities, and V2V and I2V communications coexist. We propose a mathematical framework, based on a continuous-time Markov chain (CTMC), for characterizing the spatio-temporal spread of V2X information (1) when the traffic flow exhibits sharp time-triggered transitions and (2) when there exists communication heterogeneity comprising of different V2V commutation capabilities, different wireless communication conditions, and both V2V and I2V. We prove that the state evolutions under the CTMC model converge to a set of differential equations in the asymptotic limit of a large number of vehicles, enabling computations that gracefully scale with increase in network size and the number of vehicles. Our framework can accommodate arbitrary traffic synchronization patterns corresponding for example to incorporate the presence of an arbitrary number of traffic signals. Furthermore, numerical computations using this mathematical framework answer several questions that influence the practice of V2X network design and security.

In applications of group testing in networks, e.g. identifying individuals who are infected by a disease spread over a network, exploiting correlation among network nodes provides fundamental opportunities in reducing the number of tests needed. We model and analyze group testing on n correlated nodes whose interactions are specified by a graph G. We model correlation through an edge-faulty random graph formed from G in which each edge is dropped with probability 1−r, and all nodes in the same component have the same state.We consider three classes of graphs: cycles and trees, d-regular graphs, and stochastic block models or SBM, and obtain lower and upper bounds on the number of tests needed to identify the defective nodes. Our results are expressed in terms of the number of tests needed when the nodes are independent and they are in terms of n, r, and the target error. In particular, we quantify the fundamental improvements that exploiting correlation offers by the ratio between the total number of nodes n and the equivalent number of independent nodes in a classic group testing algorithm.The lower bounds are derived by illustrating a strong dependence of the number of tests needed on the expected number of components. In this regard, we establish a new approximation for the distribution of component sizes in "d-regular trees" which may be of independent interest and leads to a lower bound on the expected number of components in d-regular graphs.The upper bounds are found by forming dense subgraphs in which nodes are more likely to be in the same state. When G is a cycle or tree, we show an improvement by a factor of log(1/r). For grid, a graph with almost 2n edges, the improvement is by a factor of (1 − r)log(1/r), indicating drastic improvement compared to trees. When G has a larger number of edges, as in SBM, the improvement can scale in n.

Information propagation in V2V-enabled transportation networks is highly influenced by both vehicle mobility and wireless communication. The mobility patterns and communication conditions are not only heterogeneous, but also vary both temporally and spatially. In particular, realistic traffic flow changes with time, exhibiting sharp time-triggered transitions, due to external factors such as traffic lights, unpredictable disruptions (e.g., accidents), and planned disruptions (e.g., road-block). More specifically, traffic signals cause traffic synchronization, due to vehicles stopping during the red phase, and starting almost simultaneously during the green phase, which fundamentally alters the dynamics of V2V message propagation in a complex manner. In this paper, we propose a mathematical framework, starting from a continuous-time Markov chain, that characterizes the fraction of vehicles that have received a message over time and space in an arbitrary road network even when the traffic flow exhibits sharp time-triggered transitions. Our framework can accommodate arbitrary traffic synchronization patterns corresponding for example to the presence of an arbitrary number of traffic signals. The stochastic model for V2V message flow converges to a set of differential equations as the number of vehicles increases. The analytical characterization lends itself to a fast computation regardless of the number of vehicles and traffic synchronization patterns, while vehicular network simulators can only realistically simulate small-scale transportation networks. We find that V2V simulations of a statistical model with traffic synchronization and simulation of communications applied on a synthetic traffic trace well match our model solution.