Efficient Historical Butterfly Counting in Large Temporal Bipartite Networks via Graph Structure-aware Index

Summary: Proposes the first graph-structure-aware indexing for historical butterfly counting in temporal bipartite networks, combining two novel indices whose space scales with counts of butterflies and wedges. Adds index compression and unbiased approximation, proves asymptotic gains on power-law graphs, and achieves up to 10^5x query speedups with modest memory. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13823
Venue: VLDB
Year: 2025
Pagerank: 4.1945683e-05
Overall Rank: 10,563 | 26.52%
DOI: 10.14778/3725688.3725693

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,300	Scalable Approximate Biclique Counting over Large Bipartite Graphs	2026	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1,484	Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks	2019	VLDB	0.00011714263
3,987	COMMIT: A Scalable Approach to Mining Communication Motifs from Dynamic Networks	2015	SIGMOD	6.5605514e-05
4,139	On Querying Historical K-Cores	2021	VLDB	6.415046e-05
4,171	Butterfly Counting on Uncertain Bipartite Graphs	2022	VLDB	6.3879236e-05
4,459	Efficient Bi-triangle Counting for Large Bipartite Networks	2021	VLDB	6.1651553e-05
4,481	Efficient Temporal Butterfly Counting and Enumeration on Temporal Bipartite Graphs	2024	VLDB	6.1485442e-05
4,970	On Querying Connected Components in Large Temporal Graphs	2023	SIGMOD	5.7945079e-05
5,540	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB	5.4498271e-05
5,773	I/O-Efficient Butterfly Counting at Scale	2023	SIGMOD	5.3319911e-05
7,451	Scalable Approximate Butterfly and Bi-triangle Counting for Large Bipartite Networks	2023	SIGMOD	4.7263711e-05
7,576	Querying Structural Diversity in Streaming Graphs	2024	VLDB	4.7064285e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,843	Butterfly-Core Community Search over Labeled Graphs	2021	VLDB	5.8823824e-05
4,459	Efficient Bi-triangle Counting for Large Bipartite Networks	2021	VLDB	6.1651553e-05
6,183	Efficient Core Maintenance in Large Bipartite Graphs	2023	SIGMOD	5.1667703e-05
11,062	Maximum Balanced (k, e)-Bitruss Detection in Signed Bipartite Graph	2024	VLDB	4.1945683e-05
5,474	Efficient Load-Balanced Butterfly Counting on GPU	2022	VLDB	5.4881807e-05
5,773	I/O-Efficient Butterfly Counting at Scale	2023	SIGMOD	5.3319911e-05
11,042	Efficient Index for Temporal Core Queries over Bipartite Graphs	2024	VLDB	4.1945683e-05
7,451	Scalable Approximate Butterfly and Bi-triangle Counting for Large Bipartite Networks	2023	SIGMOD	4.7263711e-05
1,484	Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks	2019	VLDB	0.00011714263
4,481	Efficient Temporal Butterfly Counting and Enumeration on Temporal Bipartite Graphs	2024	VLDB	6.1485442e-05