Change point detection on graphs

Graphs have become an essential tool in the manipulation of data in countless different domains for their ease of interpretation and the many properties they are able to store about a given system, ranging from the representation of the connections that the users of a social network have built in time to the interaction between cells in a living organism or atoms in the matter that makes up our universe. However, many of the applications of graphs concern real-time evolving communities which undergo countless transformations, among which only some are of interest due to the strong impact they have on its structure. For instance, an increased number of connections in a social network between a restrict group of users could indicate the formation of a community, and the same phenomena in a biological setting can give important indications on what role a certain protein plays in a particular organism. As such, it is of extreme importance to detect changes in the structure of a graph in an ever changing environment, but the task presents many practical obstacles; for once, a brute-force approach consisting in storing the graph at set instants of time is extremely inefficient and sometimes unfeasible due to memory limitations, and even if that were possible there is still the problem of extracting the features one is interested in from the graph at every timestep. In this work a method based on the existing literature is proposed, which can detect in real time change points in the graph structure, overcoming the previously mentioned limitations. An extensive analysis is conducted both on synthetic and real world data and possible applications of this method are analyzed and discussed.