A temporal graph is an undirected graph where each edge is associated with a timestamp indicating when it occurs. As a fundamental topic in graph analysis, community search (CS) in temporal graphs has received much attention. Existing CS works on temporal graphs typically identify sets of vertices that form a
k
-core within a specific time window (temporal
k
-core). However, they overlook the duration of a temporal community, which is the continues time period that its members remain unchanged. Intuitively, the longer the duration of a temporal community, the higher its stability. Long-duration communities are useful in many areas, such as event detection and network analysis. In this paper, we introduce a novel community model, called temporal durable community (TDC), which is the temporal
k
-core with the longest duration in the temporal graph, and aim to efficiently find the TDC containing a query vertex. To solve this problem, we first propose a novel online algorithm based on binary search. We further develop two index structures that can quickly determine the duration of a given temporal
k
-core, followed by query algorithms. Experiments on ten real large temporal graphs show that our TDC model is effective for finding stable communities, and our index-based query algorithms are up to five orders of magnitude faster than the online algorithm.
Yingli Zhou, Yi-Ge Jiang, Yixiang Fang et al.· Proceedings of the VLDB Endo...· 0 citations
Large-scale A/B tests on social platforms suffer from inherent network interference, violating the Stable Unit Treatment Value Assumption (SUTVA) and distorting measured results. Industrial practices for mitigating network interference face a foundational trade-off. For scalability, they often rely on clustering static graphs, which serve as imperfect proxies for true interference pathways. Conversely, theoretically sound methods remain computationally intractable at production scale. This paper presents a production-ready framework deployed at TikTok, which integrates three core contributions to address these challenges: 1) Learned Interference Graph (LIG): Estimates interference probabilities using dynamic interaction patterns for more context-aware modeling. 2) Scalable Community Partitioning (SCP): A Spark-optimized ParLeiden implementation that performs billion-node graph clustering daily and generalizes effectively across diverse interaction types, achieving a purity score of 0.898 for group chat interactions. 3) Sensitivity-Enhanced Estimation (SEE): A multivariate system leveraging Controlled-experiment Using Pre-Experiment Data (CUPED) to mitigate variance inflation from cluster-based randomization. In live production tests, our framework reduces interference rates by 68.8%, correcting a biased treatment effect estimate from +1.44% to a statistically significant +2.08%. It also enables previously undetectable cross-ecosystem measurements, revealing a +0.2% lift in creator upload volumes driven by user-side treatments.
Yu-Han Li, Jian-Yu Ni, Ao Li et al.· Annual International ACM SIG...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
