Summarisation of weighted networks

Näytä kaikki kuvailutiedot

Permalink

http://hdl.handle.net/10138/232264

Lähdeviite

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

Julkaisun nimi: Summarisation of weighted networks
Tekijä: Zhou, Fang; Qu, Qiang; Toivonen, Hannu
Muu tekijä: University of Helsinki, Department of Computer Science
Kuuluu julkaisusarjaan: Journal of Experimental and Theoretical Artificial Intelligence
ISSN: 0952-813X
Tiivistelmä: 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.
URI: http://hdl.handle.net/10138/232264
Päiväys: 2017
Avainsanat: Weighted networks
network mining
generalisation
network summarisation
GRAPHS
WEB
113 Computer and information sciences
data mining
data science
Tekijänoikeustiedot:


Tiedostot

Latausmäärä yhteensä: Ladataan...

Tiedosto(t) Koko Formaatti Näytä
article.pdf 2.468MB PDF Avaa tiedosto

Viite kuuluu kokoelmiin:

Näytä kaikki kuvailutiedot