Brief Announcement: Distributed Butterfly Analysis using Mobile Agents

Butterflies, or 4-cycles in bipartite graphs, are crucial for identifying cohesive structures and dense subgraphs. We propose distributed agent-based algorithms for Butterfly Counting in a bipartite graph G((A, B), E), where the agents first determine their partition for which they construct a spanning tree and elect a leader in O(n log λ) rounds with O(log λ) bits of memory per agent. A novel meeting mechanism between adjacent agents enhances efficiency and removes the need for prior graph knowledge, requiring only the highest agent ID (λ) among n agents. Building on these foundations, agents count butterflies per node in O(Δ) rounds and compute the total butterfly count of G in O(Δ + min{|A|, |B|}) rounds.