Network Filtering for Big Data: Triangulated Maximally Filtered Graph. (7th June 2016)

• Record Type: Journal Article
• Authors: Massara, Guido Previde; Di Matteo, T.; Aste, Tomaso
• Is Part Of: Journal of complex networks. Volume 5:Number 2(2017)
• Page Start: 161
• Page End: 178
• Publication Date: 2016-06-07
• Subjects: TMFG -- big data -- network filtering -- PMFG -- planarization algorithms -- correlation network -- Markov random fields -- Weighted Maximal Planar Graph (WMPG); Numerical analysis -- Periodicals; Computer networks -- Periodicals; Social networks -- Periodicals; 518.05
• DOI: 10.1093/comnet/cnw015
• Languages: English
• ISSNs: 2051-1310

Abstract

Abstract : We propose a network-filtering method, the Triangulated Maximally Filtered Graph (TMFG), that provides an approximate solution to the Weighted Maximal Planar Graph problem. The underlying idea of TMFG consists in building a triangulation that maximizes a score function associated with the amount of information retained by the network. TMFG uses as weights any arbitrary similarity measure to arrange data into a meaningful network structure that can be used for clustering, community detection and modelling. The method is fast, adaptable and scalable to very large datasets; it allows online updating and learning as new data can be inserted and deleted with combinations of local and non-local moves. Further, TMFG permits readjustments of the network in consequence of changes in the strength of the similarity measure. The method is based on local topological moves and can therefore take advantage of parallel and GPUs computing. We discuss how this network-filtering method can be used intuitively and efficiently for big data studies and its significance from an information-theoretic perspective.