论文标题
精确的和采样方法，用于挖掘大型超图中的高阶基序
Exact and sampling methods for mining higher-order motifs in large hypergraphs
论文作者
论文摘要
网络图案是在系统中经常观察到的经常观察到的相互作用的复发图。他们阐明了跨各个领域的拓扑与复杂网络的动力学之间的相互作用。在这项工作中，我们专注于在非常大的超图中计算小型副饰面模式发生的问题，其中高阶交互连接了任意数量的系统单元。我们展示了与传统数据挖掘技术相比，如何直接利用高阶结构加快计数过程的速度。此外，随着超边的抽样，在基序频率的估计中以小错误的成本进一步提高了性能。我们在几个现实世界数据集上评估了我们的方法，这些数据集描述了面对面的互动，共同作者和人类交流。我们表明，我们的近似算法使我们能够更快地提取高阶图案，并且超出了精确方法的计算限制。
Network motifs are recurrent, small-scale patterns of interactions observed frequently in a system. They shed light on the interplay between the topology and the dynamics of complex networks across various domains. In this work, we focus on the problem of counting occurrences of small sub-hypergraph patterns in very large hypergraphs, where higher-order interactions connect arbitrary numbers of system units. We show how directly exploiting higher-order structures speeds up the counting process compared to traditional data mining techniques for exact motif discovery. Moreover, with hyperedge sampling, performance is further improved at the cost of small errors in the estimation of motif frequency. We evaluate our method on several real-world datasets describing face-to-face interactions, co-authorship and human communication. We show that our approximated algorithm allows us to extract higher-order motifs faster and on a larger scale, beyond the computational limits of an exact approach.
