polito.it
Politecnico di Torino (logo)

Change point detection on graphs

Giuseppe Luca Tommasone

Change point detection on graphs.

Rel. Alfredo Braunstein. Politecnico di Torino, Corso di laurea magistrale in Physics Of Complex Systems (Fisica Dei Sistemi Complessi), 2018

Abstract:

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.

Relatori: Alfredo Braunstein
Anno accademico: 2017/18
Tipo di pubblicazione: Elettronica
Numero di pagine: 56
Informazioni aggiuntive: Tesi secretata. Full text non presente
Soggetti:
Corso di laurea: Corso di laurea magistrale in Physics Of Complex Systems (Fisica Dei Sistemi Complessi)
Classe di laurea: Nuovo ordinamento > Laurea magistrale > LM-44 - MODELLISTICA MATEMATICO-FISICA PER L'INGEGNERIA
Ente in cotutela: LightOn (FRANCIA)
Aziende collaboratrici: NON SPECIFICATO
URI: http://webthesis.biblio.polito.it/id/eprint/8038
Modifica (riservato agli operatori) Modifica (riservato agli operatori)