[KDD 2020] In and Out: Optimizing Overall Interaction in Probabilistic Graphs under Clustering Constraints
Aug 13, 20206 views
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.