Inference methods for message endpoint localization in networks.

Abstract

People often build or organize networks in order to establish lines of communication. The subjects might utilize a telephone or computer network, or perhaps even something much more low-tech where certain individuals are designated to deliver messages in person. When certain parties of interest are communicating, it is desirable to monitor these networks in order to discover their motives, identities, and locations. Presently, government and private agencies are investing heavily in the development of equipment for network surveillance and algorithms for gleaning useful information from collected data. This thesis develops several tools for inference in networks with a focus on determining the locations of the sender and receiver of an intercepted message. We begin by deriving a distance metric that allows comparisons between different network topologies. The metric quantifies the distance between networks by the total cost of edit operations (such as node or link insertion or deletion) necessary to make the two networks isomorphic. We derive this graph edit distance through a sort of embedding scheme, and show how to compute it with a binary linear program. Upper and lower bounds are computable in polynomial time through relaxation to an assignment problem and standard linear programming, respectively. We move next to the estimation of an intercepted message's source and destination in a network of unknown topology. Sensors placed on some links or nodes in the network are capable of indicating whenever a specific message passes their assigned elements with a limited degree of timing precision. The source and destination (endpoints) are localized using a possibly unordered sensor activation pattern along with some prior information on the unknown network topology. We first use a semidefinite programming driven Monte Carlo approach to build approximate endpoint posterior distributions. Maximum a posteriori endpoint estimates can then be read directly from these. Next we utilize a hierarchical Bayesian model and a recursive expectation-maximization algorithm to develop online techniques for endpoint localization. Finally, some preliminary derivations are given for the application of well-known Markov chain Monte Carlo algorithms to this problem.