Network comparison via optimal transport of Markov chains

Speaker: Professor Andrew Nobel
Affiliation: University of North Carolina, Chapel Hill (USA)

Abstract

Networks are commonly used to represent and study pairwise interactions between a collection of objects or individuals under study, and are objects of study in their own right. In this talk I will describe a procedure called NetOTC (network optimal transition coupling) to compare and align two given networks. The networks of interest may be directed or undirected, weighted or unweighted, and may have distinct vertex sets of different sizes. Given two networks and a cost function relating their vertices, NetOTC finds a transition coupling of their associated random walks with minimum expected cost. The minimizing cost quantifies the difference between the networks, while the optimal transport plan itself provides soft alignments of the vertices and edges of the two networks. Coupling of the full random walks ensures that NetOTC captures local and global information about the networks and preserves edges. I will present some basic theoretical properties of NetOTC, and describe experiments supporting its practical use.