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 .

Title: Summarisation of weighted networks
Author: Zhou, Fang; Qu, Qiang; Toivonen, Hannu
Contributor organization: Department of Computer Science
Discovery Research Group/Prof. Hannu Toivonen
Helsinki Institute for Information Technology
Finnish Centre of Excellence in Algorithmic Data Analysis Research (Algodan)
Date: 2017
Language: eng
Number of pages: 30
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.
Subject: Weighted networks
network mining
network summarisation
113 Computer and information sciences
data mining
data science
Peer reviewed: Yes
Usage restriction: openAccess
Self-archived version: acceptedVersion

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