Paper published: Enumerating Temporal CliquesNews ·
One sentence summary: Find all regular meetings in time stamped message data.
Slightly more precise: Given a set of time stamped bilateral messages between persons, enumerate all combinations of a time frame T and a set S of persons such that each pair of persons in S communicate regularly during the time frame T.
Message data between individuals nowadays is ubiquitous and our techniques can also be applied to physical proximity data between persons. What we showed in this paper is that a certain notion of sparseness, which we usually can observe in social networks, transfers over in a more drastic form to time stamped message data arising in such social networks. We can use this sparseness property to efficiently enumerate all the meetings that occur. This is in general a computationally hard (NP-hard) task.
Read our paper (orig, arXiv) and try our code!