The present study is a theoretical and experimental work for a new approach in the mathematical representation of a structure subjected to dynamic loading via Graph Theory tools applied to magnified video recordings. The mathematical properties of graphs and related parameters are illustrated in a simplified formulation in order to highlight the advantages associated to the proposed representation. A sensitivity analysis was carried out with several conventional Graph Theory parameters, which were tested to explore their potential of providing an anticipated signal of imminent collapse of the structure. Before extracting the above parameters by application of Graph Theory, the videos were processed by Motion Magnification technique, which provided a fundamental contribution in generating representative graphs of the analyzed structure and considerably improving the overall process results. The experimental application focused on historical buildings, in which the combination of high seismic vulnerability and lack of resources for effective structural monitoring is often a crucial issue. In particular, the proposed methodology was validated through experimentation on video recordings of a historic masonry cross vault subjected to shaking table tests up to final failure of the structure.