Summarisation of weighted networks

Show full item record



Zhou , F , Qu , Q & Toivonen , H 2017 , ' Summarisation of weighted networks ' Journal of Experimental and Theoretical Artificial Intelligence , vol 29 , no. 5 , pp. 1023-1052 . DOI: 10.1080/0952813X.2017.1280089

Title: Summarisation of weighted networks
Author: Zhou, Fang; Qu, Qiang; Toivonen, Hannu
Contributor: University of Helsinki, Department of Computer Science
Belongs to series: Journal of Experimental and Theoretical Artificial Intelligence
ISSN: 0952-813X
Abstract: Networks often contain implicit structure. We introduce novel problems and methods that look for structure in networks, by grouping nodes into supernodes and edges to superedges, and then make this structure visible to the user in a smaller generalised network. This task of finding generalisations of nodes and edges is formulated as network Summarisation'. We propose models and algorithms for networks that have weights on edges, on nodes or on both, and study three new variants of the network summarisation problem. In edge-based weighted network summarisation, the summarised network should preserve edge weights as well as possible. A wider class of settings is considered in path-based weighted network summarisation, where the resulting summarised network should preserve longer range connectivities between nodes. Node-based weighted network summarisation in turn allows weights also on nodes and summarisation aims to preserve more information related to high weight nodes. We study theoretical properties of these problems and show them to be NP-hard. We propose a range of heuristic generalisation algorithms with different trade-offs between complexity and quality of the result. Comprehensive experiments on real data show that weighted networks can be summarised efficiently with relatively little error.
Date: 2017
Subject: Weighted networks
network mining
network summarisation
113 Computer and information sciences
data mining
data science

Files in this item

Total number of downloads: Loading...

Files Size Format View
article.pdf 2.468Mb PDF View/Open

This item appears in the following Collection(s)

Show full item record