Inferring missing network links from activity patterns with partial data
Inferring Hidden Structural Changes from Node-State Responses under Partial Network Observations
Social and Information Networks
Summary
Sometimes networks, like online social sites, don't have complete records of who connected with whom, especially when things change quickly. The authors introduce a method called HSCR that looks at how users’ activities change and uses what is known about the network to guess which new connections have been made but not recorded. This helps keep the network’s record accurate even when direct connection data is missing or delayed. They tested HSCR on several synthetic and real datasets and found it ranks true new links better than existing methods.
What this means in practice
- •For online platform engineers: Detect unrecorded user connections by analyzing activity changes to keep network data up to date despite incomplete logs.
- •For network analysts: Prioritize potential new connections for verification during delayed or partial structural recording in communication or information networks.
Authors
En Xu, Jingtao Ding, Yong Li
Abstract
Online platforms often expose activity signals even when records of the underlying connections are incomplete or delayed. These activity responses may retain indirect evidence of connections that formed during the observation period but are absent from the recorded topology. Recovering such hidden structural changes can help keep network records aligned with evolving interactions and support downstream network analysis. However, the effects of a change propagate through the network and may overlap, making state changes difficult to associate with specific connections. We propose the Hierarchical Structural Context Ranker (HSCR), which combines visible network structure with node-state changes to infer connections that have formed but remain unrecorded. By jointly modeling the topological context of state responses and associations among potential connections, HSCR converts distributed activity changes into evidence for distinguishing potential connections without prespecified dynamical equations or parameters. Experiments on five temporal-network benchmarks and a real temporal Reddit network validate its effectiveness. Across observation spans and structural-record delays, true added connections achieve a 36%-50% reduction in mean true rank relative to the corresponding best baselines. This work provides a principled way to prioritize unrecorded additions for structural verification and record maintenance in online communities, information networks, and other networked systems.