Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Efficient comparison of massive graphs through the use of 'graph fingerprints'.

Bonner, S. and Brennan, J. and Theodoropoulos, G. and Kureshi, I. and McGough, A.S. (2016) 'Efficient comparison of massive graphs through the use of 'graph fingerprints'.', Twelfth Workshop on Mining and Learning with Graphs (MLG) at KDD'16. San Francisco, USA, 14 August 2016.

Abstract

The problem of how to compare empirical graphs is an area of great interest within the field of network science. The ability to accurately but efficiently compare graphs has a significant impact in such areas as temporal graph evolution, anomaly detection and protein comparison. The comparison problem is compounded when working with graphs containing millions of anonymous, i.e. unlabelled, vertices and edges. Comparison of two or more graphs is highly computationally expensive. Thus reducing a graph to a much smaller feature set – called a fingerprint, which accurately captures the essence of the graph would be highly desirable. Such an approach would have potential applications outside of graph comparisons, especially in the area of machine learning. This paper introduces a feature extraction based approach for the efficient comparison of large topologically similar, but order varying, unlabelled graph datasets. The approach acts by producing a ‘Graph Fingerprint’ which represents both vertex level and global level topological features from a graph. The approach is shown to be efficient when comparing graphs which are highly topologically similar but order varying. The approach scales linearly with the size and complexity of the graphs being fingerprinted.

Item Type:Conference item (Paper)
Full text:(AM) Accepted Manuscript
Download PDF
(316Kb)
Status:Peer-reviewed
Publisher Web site:http://www.mlgworkshop.org/2016/paper/MLG2016_paper_22.pdf
Date accepted:22 July 2016
Date deposited:15 September 2016
Date of first online publication:August 2016
Date first made open access:No date available

Save or Share this output

Export:
Export
Look up in GoogleScholar