Computer networks are complex systems, and dynamically monitoring their structure in search for anomalies is both a challenging and important task for cyber security. In a computer network, new edges are connections from a host or client to a computer or server that has not been connected to before and can provide strong statistical evidence for detecting anomalies. However, performing meaningful anomaly detection on the arrivals of new edges is non-trivial as new edges can be indicative of both legitimate and illegitimate activity and occur with a considerable heterogeneity between network hosts.
This thesis presents a framework aimed at modelling normal new edge activity and performing anomaly detection in a large computer network graph. Specifically, the main contribution consists of a Bayesian method for modelling the intensity of new edges, simultaneously addressing the rate of occurrence of new edges and any underlying latent structural relationship between the clients and servers in the network. What constitutes normal behaviour for some hosts might be very unusual for some others and so examining existing network structure is key for accurately predicting likely future interactions. For this purpose, a notion of similarity between clients and servers is developed, first under hard-thresholding with a clustering model, and then extended to soft-thresholding in a flexible latent feature space. Finally, the model is used to construct an anomaly detection method, which successfully identifies some known compromised machines when demonstrated on real computer network data.