Complex Network Seminar: Zhang -- Toward the Predictability of Complex Networks

Speaker: Prof.  Zi-Ke Zhang, Zhejiang University 

Title: Toward the Predictability of Complex Networks 

Abstract: In this talk, we establish network predictability theory by
mapping link prediction onto a spin glass model, where network partitions correspond to
spin configurations, and predictability equals the system's average energy.  Using the
cavity method from statistical physics, we prove that global predictability decomposes
into individual link contributions, enabling an efficient local sampling algorithm that
reduces the computational complexity of evaluating individual link contributions from
being dependent on the entire network to only its local neighborhood, scaling with the
average degree.  We derive exact results for canonical network models: ER networks
exhibit universal predictability of 0.5 regardless of algorithm choice, establishing the
random baseline, while structured networks show predictability controlled by their prior
parameters.  We introduce the predictability index, which quantifies the maximum
achievable performance without information loss and accurately predicts algorithm
performance under random division.  Analysis of real networks validates our framework,
revealing how degree heterogeneity and structural patterns govern predictability.  This
physics-based approach provides both theoretical insights into link prediction limits
and practical tools for assessing network reconstruction potential, with implications
for applications from biological network inference to social network analysis.