Clustering based on similarity across networks

Paper Title:

Multilayer Correlation Clustering

Published on:

25 April 2024

Primary Category:

Data Structures and Algorithms

Paper Authors:

Atsushi Miyauchi,

Florian Adriaens,

Francesco Bonchi,

Nikolaj Tatti

Bullets

Key Details

•

Introduces Multilayer Correlation Clustering, extending correlation clustering to multiple networks

•

Gives an O(L log n) approximation for the general case based on region growing

•

Presents a (2.5 + 2) approximation for the case with probability constraints on similarity

•

Experiments show algorithms are effective on real multilayer network data

Explore the topics in this paper

approximation algorithms

consistency

correlation clustering

graph clustering

multi-network clustering

AI generated summary

Clustering based on similarity across networks

This paper introduces a new clustering model that uses similarity information across multiple networks to find clusters that are consistent across all the networks. The model aims to minimize disagreements between the clustering and the similarity information on each network. The paper gives approximation algorithms for the problem, including an O(L log n) approximation where L is the number of networks and n the number of nodes. For an important special case with probability constraints, the paper presents a (2.5 + 2) approximation, leveraging existing approximations for standard correlation clustering. Experiments on real-world data demonstrate the effectiveness.