UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Network Filtering for Big Data: Triangulated Maximally Filtered Graph

Massara, GP; Matteo, TD; Aste, T; (2017) Network Filtering for Big Data: Triangulated Maximally Filtered Graph. Journal of Complex Networks , 5 (2) pp. 161-178. 10.1093/comnet/cnw015. Green open access

[img]
Preview
Text
BigDataNetworkFiltering_v7.4.pdf - ["content_typename_Accepted version" not defined]

Download (442kB) | Preview

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.

Type: Article
Title: Network Filtering for Big Data: Triangulated Maximally Filtered Graph
Open access status: An open access version is available from UCL Discovery
DOI: 10.1093/comnet/cnw015
Publisher version: http://dx.doi.org/10.1093/comnet/cnw015
Language: English
Additional information: This is a pre-copyedited, author-produced PDF of an article accepted for publication in the Journal of Complex Networks following peer review. The version of record, Massara, GP; Matteo, TD; Aste, T; (2016) Network Filtering for Big Data: Triangulated Maximally Filtered Graph. Journal of Complex Networks, is available online at: http://dx.doi.org/10.1093/comnet/cnw015.
Keywords: TMFG, Big Data, Network Filtering, PMFG, Planarization algorithms, Correlation Network, Markov Random Fields, Weighted Maximal Planar Graph (WMPG)
UCL classification: UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: http://discovery.ucl.ac.uk/id/eprint/1477623
Downloads since deposit
156Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item