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 . https://doi.org/10.1080/0952813X.2017.1280089
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 |
DOI: | https://doi.org/10.1080/0952813X.2017.1280089 |
URI: | http://hdl.handle.net/10138/232264 |
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 generalisation network summarisation GRAPHS WEB 113 Computer and information sciences data mining data science |
Peer reviewed: | Yes |
Usage restriction: | openAccess |
Self-archived version: | acceptedVersion |
Total number of downloads: Loading...
Files | Size | Format | View |
---|---|---|---|
article.pdf | 2.468Mb |
View/ |