Bringing density to link streams reveals meaningful groups in contact traces

Link stream is a graph extension that include time information, i.e. each link between two nodes has a starting and ending time. Just like in graphs, looking at dense subsets in link streams reveals relevant groups and exhibits a community structure. However, most existing papers dealing with link stream community structures rely on series of graphs, each one being a time aggregation, instead of link streams. This is problematic because the right aggregation time is hard to determine and too much information might be lost if the aggregation is too broad. By considering a link centric perspective, we are able to overcome these problems. We propose a method that uncovers directly a partition in Link streams. To this end, we consider groups of links instead of group of nodes, which leads to an easier definition of a partition. Thus, the problematic time aggregation in series of graph is avoided. To validate each group in the link partition, we introduce a new metric, inspired by the density, that allow us to design several criteria and therefore highlight important groups in the partition and discard non-significant one.
We apply both methods on several real world datasets and uncover meaningful groups.