K-partitioning with imprecise probabilistic edges

Tom Davot (1, 2) , Sébastien Destercke (1) , David Savourey (1)

1 Heudiasyc - Heuristique et Diagnostic des Systèmes Complexes [Compiègne]
2 Labex MS2T - Laboratoire d'Excellence "Maîtrise des Systèmes de Systèmes Technologiques"

Partitioning a set of elements into disjoint subsets is a common problem in unsupervised learning (clustering) as well as in networks (e.g., social, ecological) where one wants to find heterogeneous subgroups such that the elements within each subgroup are homogeneous. In this paper, we are concerned with the case where we imprecisely know the probability that two elements should belong to the same partition, and where we want to search the set of most probable partitions. We study the corresponding algorithmic problem on graphs, showing that it is difficult, and propose heuristic procedures that we test on data sets.

Domains: Computer Science [cs]

Tom Davot, Sébastien Destercke, David Savourey. K-partitioning with imprecise probabilistic edges. 10th International Conference on Soft Methods in Probability and Statistics (SMPS 2022), May 2022, Valladolid, Spain. pp.87-95. ⟨hal-03665950⟩