23/08/2020

In and out: Optimizing overall interaction in probabilistic graphs under clustering constraints

Domenico Mandaglio, Andrea Tagarelli, Francesco Gullo

Keywords: correlation clustering, interaction loss, uncertain graphs

Abstract Paper Similar Papers

Abstract: We study two novel clustering problems in which the pairwise interactions between entities are characterized by probability distributions and conditioned by external factors within the environment where the entities interact. This covers any scenario where a set of actions can alter the entities’ interaction behavior. In particular, we consider the case where the interaction conditioning factors can be modeled as cluster memberships of entities in a graph and the goal is to partition a set of entities such as to maximize the overall vertex interactions or, equivalently, minimize the loss of interactions in the graph. We show that both problems are NP-hard and they are equivalent in terms of optimality. However, we focus on the minimization formulation as it enables the possibility of devising both practical and efficient approximation algorithms and heuristics. Experimental evaluation of our algorithms, on both synthetic and real network datasets, has shown evidence of their meaningfulness as well as superiority with respect to competing methods, both in terms of effectiveness and efficiency.

The video of this talk cannot be embedded. You can watch it here:
https://dl.acm.org/doi/10.1145/3394486.3403190#sec-supp
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at KDD 2020 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 5:03 
 0
 0
 0
 0
 15:07 
 0
 0
 0
 0
 14:35 
 0
 0
 0
 0
 7:46 
 0
 0
 0
 0
 14:43 
 0
 0
 0
 0
 3:10 
 0
 0
 0
 0
 11:06 
 0
 0
 0
 0
 3:11 
 0
 0
 0
 0
 3:16 
 0
 0
 0
 0
 6:58 
 0
 0
 0
 0
 8:42 
 0
 0
 0
 0
 3:09 
 0
 0
 0
 0
 8:11 
 0
 0
 0
 0
 4:59 
 0
 0
 0
 0
 3:11 
 0
 0
 0
 0
 4:55 
 0
 0
 0
 0
 17:56 
 0
 0
 0
 0
 1:01 
 0
 0
 0
 0
 3:18 
 0
 0
 0
 0
 3:22 
 0
 0
 0
 0
 10:22 
 0
 0
 0
 0
 2:52 
 0
 0
 0
 0
 16:43 
 0
 0
 0
 0
 19:09 
 0
 0
 0
 0
 3:24 
 0
 0
 0
 0
 4:59 
 0
 0
 0
 0
 14:28 
 0
 0
 0
 0
 3:20 
 0
 0
 0
 0
 14:56 
 0
 0
 0
 0
 3:09 
 0
 0
 0
 0
 3:20 
 0
 0
 0
 0
 15:06 
 0
 0
 0
 0
 0:59 
 0
 0
 0
 0
 3:16 
 0
 0
 0
 0
 12:17 
 0
 0
 0
 0
 13:33 
 0
 0
 0
 0
 3:02 
 0
 0
 0
 0
 3:15 
 0
 0
 0
 0
 14:56 
 0
 0
 0
 0
 5:06