Optimal disease outbreak detection in a community using network observability

July 6, 2016

Abstract: 

Given a network, we would like to determine which subset of nodes should be measured by limited sensing facilities to maximize information about the entire network. The optimal choice corresponds to the configuration that returns the highest value of a measure of observability of the system. Here, the determinant of the inverse of the observability Gramian is used to evaluate the degree of observability. Additionally, the effects of changes in the topology of the corresponding graph of a network on the observability of the network are investigated. The theory is illustrated on the problem of detection of an epidemic disease in a community. The purpose here is to find the smallest number of people who must be examined to predict the number of infected people in an arbitrary community. Results are demonstrated in simulation.

Background

A network is a set of items, which we call nodes, with connections between them, called edges. The interaction between agents in a network is represented by a graph G = (V, E). Each agent in a network is denoted as a node, and the edges represent interaction links between agents. The number of nodes is assumed to be N, and the number of edges to be M. The node set, V , consists of all nodes in the network. The edge set, E, is comprised of pairs of nodes {i, j}, where nodes i and j are adjacent. The neighbourhood set, Ni , of node i is composed of all agents in V adjacent to node i. The edges are encoded through the index mapping σ such that l = σ(i, j), if and only if edge l connects nodes i and j. The adjacency matrix is an N × N symmetric matrix with Aij = 1 when {i, j} ∈ E, and Aij = 0, otherwise. Here, we assume an undirected graph structure where {i, j} ∈ E ⇒ {j, i} ∈ E. B

Fig 1

Two different graph topologies of a network of 15 nodes: (a) dense and (b) sparse structures.

Conclusion

The work in this paper has been concerned with obtaining the optimal node selection for maximizing an index of observability for a network. The empirical observability Gramian has been used as a tool for improving the local observability of nonlinear systems. The observability index was chosen to be the determinant of the inverse of the observability Gramian. We proposed an optimization problem for obtaining the optimal node selection that provides the full state observability of a network. The optimization problem framed as a mixed integer nonlinear programming problem. The outer approximation algorithm was used as a relaxation method for solving a convex optimization problem with integer non-convex constrains.