Recent work has shown that finite mixture models with$m$components are identifiable, while making no assumptions on the mixture components, so long as one has access to groups of samples of size$2m-1$which are known to come from the same mixture component. In this work we generalize that result and show that, if every subset of$k$mixture components of a mixture model are linearly independent, then that mixture model is identifiable with only$(2m-1)/(k-1)$samples per group. We further show that this value cannot be improved. We prove an analogous result for a stronger form of identifiability known as “determinedness” along with a corresponding lower bound. This independence assumption almost surely holds if mixture components are chosen randomly from a$k$-dimensional space. We describe some implications of our results for multinomial mixture models and topic modeling.

Modern-day social networks evolve over time, that is, new contacts appear and old contacts may disappear. They can be modeled as temporal graphs where interactions between vertices (people) are represented by time-stamped edges. One of the most fundamental problems in social network analysis is community detection and within community detection, one of the most basic primitives to model a community is a clique. Addressing the problem of finding communities in temporal networks, Viard et al. [TCS 2016] introduced Δ-cliques as a natural temporal version of cliques. Himmel et al. [SNAM 2017] showed how to adapt the well-known Bron-Kerbosch algorithm for listing static cliques to listing Δ-cliques. We continue this work and improve and extend this algorithm to list temporal k-plexes, a temporal version of k-plexes, which are one of many popular clique relaxations. We define a Δ-$k$-plex as a set of vertices with a lifetime, where during the lifetime each vertex has an edge to all but at most k–1 vertices at least once every Δ + 1 consecutive time steps. We develop an algorithm for listing all maximal Δ-$k$-plexes and perform experiments on real-world networks that demonstrate the practical feasibility of our approach. In particular, for the special case of listing Δ-1-plexes (Δ-cliques), we observe that our algorithm is significantly faster than the previous algorithm by Himmel et al