Temporal graphs are structures which model relational data between entities that change over time. Due to the complex structure of data, mining statistically significant temporal subgraphs, also known as temporal motifs, is a challenging task. In this work, we present an efficient technique for extracting temporal motifs in temporal networks. Our method is based on the novel notion of egocentric temporal neighborhoods, namely multi-layer structures centered on an ego node. Each temporal layer of the structure consists of the first-order neighborhood of the ego node, and corresponding nodes in sequential layers are connected by an edge. The strength of this approach lies in the possibility of encoding these structures into a unique bit vector, thus bypassing the problem of graph isomorphism in searching for temporal motifs. This allows our algorithm to mine substantially larger motifs with respect to alternative approaches. Furthermore, by bringing the focus on the temporal dynamics of the interactions of a specific node, our model allows to mine temporal motifs which are visibly interpretable. Experiments on a number of complex networks of social interactions confirm the advantage of the proposed approach over alternative non-egocentric solutions. The egocentric procedure is indeed more efficient in revealing similarities and discrepancies among different social environments, independently of the different technologies used to collect data, which instead affect standard non-egocentric measures.
翻译:由于数据结构复杂,开采具有统计意义的具有统计意义的时间子子集,也称为时间模型,这是一项具有挑战性的任务。在这项工作中,我们展示了一种在时间网络中提取时间模型的有效技术。我们的方法基于以自我为中心的时间区的新概念,即以自我为中心、以自我节点为中心的多层结构。结构的每个时间层都由自我节点的第一阶邻和相继层的相应节点组成,它们有一个边缘连接。这一方法的力量在于将这些结构编码成一个独特的点矢量的可能性,从而绕过图形在寻找时间模型时的变形问题。这使我们的算法能够在替代方法方面挖掘大得多的模型。此外,通过关注特定节点相互作用的时间动态,我们的模型允许对可明显解释的时位模型进行连接。在一系列复杂的社会互动网络上进行实验,证实了拟议的方法在寻找时间模型时态模型时的优势,从而在寻求时间模型模型模型时,能够影响其他非中心类比标准型的模型的模型,从而影响非中心化的模型,在不同的类比性标准方法中可以独立地影响非中心化的模型的模型。