More Like this

1. Butterfly Counting in Bipartite Networks

   https://doi.org/10.1145/3219819.3220097  

   Sanei-Mehri, Seyed-Vahid; Sariyuce, Ahmet Erdem; Tirthapura, Srikanta (August 2018, Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining)

   We consider the problem of counting motifs in bipartite affiliation networks, such as author-paper, user-product, and actor-movie relations. We focus on counting the number of occurrences of a "butterfly", a complete 2x2 biclique, the simplest cohesive higher-order structure in a bipartite graph. Our main contribution is a suite of randomized algorithms that can quickly approximate the number of butterflies in a graph with a provable guarantee on accuracy. An experimental evaluation on large real-world networks shows that our algorithms return accurate estimates within a few seconds, even for networks with trillions of butterflies and hundreds of millions of edges. 

   more » « less
2. Parallel Algorithms for Butterfly Computations

   Shi, Jessica; Shun, Julian (January 2020, Symposium on Algorithmic Principles of Computer Systems)

   Butterflies are the smallest non-trivial subgraph in bipartite graphs, and therefore having efficient computations for analyzing them is crucial to improving the quality of certain applications on bipartite graphs. In this paper, we design a framework called ParButterfly that contains new parallel algorithms for the following problems on processing butterflies: global counting, per-vertex counting, per-edge counting, tip decomposition (vertex peeling), and wing decomposition (edge peeling). The main component of these algorithms is aggregating wedges incident on subsets of vertices, and our framework supports different methods for wedge aggregation, including sorting, hashing, histogramming, and batching. In addition, ParButterfly supports different ways of ranking the vertices to speed up counting, including side ordering, approximate and exact degree ordering, and approximate and exact complement coreness ordering. For counting, ParButterfly also supports both exact computation as well as approximate computation via graph sparsification. We prove strong theoretical guarantees on the work and span of the algorithms in ParButterfly. We perform a comprehensive evaluation of all of the algorithms in ParButterfly on a collection of real-world bipartite graphs using a 48-core machine. Our counting algorithms obtain significant parallel speedup, outperforming the fastest sequential algorithms by up to 13.6× with a self-relative speedup of up to 38.5×. Compared to general subgraph counting solutions, we are orders of magnitude faster. Our peeling algorithms achieve self-relative speedups of up to 10.7× and outperform the fastest sequential baseline by up to several orders of magnitude. 

   more » « less
3. Siamese Learning-Based Monarch Butterfly Localization

   https://doi.org/10.1109/DSLW53931.2022.9820497  

   Shoouri, Sara; Yang, Mingyu; Carichner, Gordy; Li, Yuyang; Hamed, Ehab A.; Deng, Angela; Green, Delbert A.; Lee, Inhee; Blaaw, David; Kim, Hun-Seok (May 2022, 2022 IEEE Data Science and Learning Workshop (DSLW))
4. A Practical Method for Butterfly Motion Capture

   https://doi.org/10.1145/3561975.3562940  

   Chen, Qiang; Lu, Tingsong; Tong, Yang; Fang, Yuming; Deng, Zhigang (November 2022, Proceeding of ACM SIGGRAPH Conference on Motion, Interaction, and Games 2022)

   Simulating realistic butterfly motion has been a widely-known challenging problem in computer animation. Arguably, one of its main reasons is the difficulty of acquiring accurate flight motion of butterflies. In this paper we propose a practical yet effective, optical marker-based approach to capture and process the detailed motion of a flying butterfly. Specifically, we first capture the trajectories of the wings and thorax of a flying butterfly using optical marker based motion tracking. After that, our method automatically fills the positions of missing markers by exploiting the continuity and relevance of neighboring frames, and improves the quality of the captured motion via noise filtering with optimized parameter settings. Through comparisons with existing motion processing methods, we demonstrate the effectiveness of our approach to obtain accurate flight motions of butterflies. Furthermore, we created and will release a first-of-its-kind butterfly motion capture dataset to research community. 

   more » « less
5. Traveling discontinuity at the quantum butterfly front

   https://doi.org/10.21468/SciPostPhys.15.2.042  

   Aron, Camille; Brunet, Éric; Mitra, Aditi (January 2023, SciPost Physics)

   We formulate a kinetic theory of quantum information scrambling in the context of a paradigmatic model of interacting electrons in the vicinity of a superconducting phase transition. We carefully derive a set of coupled partial differential equations that effectively govern the dynamics of information spreading in generic dimensions. Their solutions show that scrambling propagates at the maximal speed set by the Fermi velocity. At early times, we find exponential growth at a rate set by the inelastic scattering. At late times, we find that scrambling is governed by shock-wave dynamics with traveling waves exhibiting a discontinuity at the boundary of the light cone. Notably, we find perfectly causal dynamics where the solutions do not spill outside of the light cone. 

   more » « less