Network data analysis
OA Version
Citation
Abstract
Frequently the graphs used to represent networks are inferred from data and, surprisingly, the uncertainty in their inferred topology is typically ignored. This dissertation makes signicant contributions toward remedying this issue in three main ways.
Let 𝜂 (G) be a function of a network, i.e. a network characteristic, of the graph G and let ^G be an inferred network. I provide an analytical method for approximating the probability P (𝜂 (^G) －𝜂 (G) ≤ x ) via Stein's method for a broad class of functions, the so-called motif count statistics. The first contribution of my research is to quantify the propagation of error from network uncertainty to network characterization, a problem for which no results currently exist. Particular attention is given to the case of network density.
When modeling the functional connectivity of a brain, dynamic networks may be inferred from ECoG data. Of interest is an understanding of the process of coalescence and fragmentation of these functional brain networks during epileptic seizure. The second contribution of my research is to develop a means for tracing the community structures of an inferred dynamic network as they are born, merged, fractured, and die over time.
In particular, I developed an algorithm which is robust to edge noise, yields well-defined spatio-temporal communities, and facilitates the connection of communities with a range of network motifs of various orders.
Models exist in which the rate of the emergence of a giant connected component, i.e. percolation, is manipulated through means of edge connection rules. However, such models are unable to account for (i) edge removal and (ii) the error associated with inferred
networks, i.e. type-I and II errors. The third contribution of my research is to develop a model for graph percolation which allows for birth, death, and edge noise. I developed a method which accommodates both edge removal and a noisy edge set and propose a statistical hypothesis test to identify the rate of percolation. The novel approach of monitoring
the relative size of the second component is found to be more robust than the first when
distinguishing between percolation rates in the presence of noise.