Title: Revealing the Predictability of Intrinsic Structure in Networks

Time: 10:00 a.m. Tuesday, April 18, 2019

Location: Conference Room 3016 Gezhi Building

Structure prediction in networks is among the most important and widely studied problems in network science and machine learning, which has enormous contribution to various fields from recommendation systems, biology to social media. Despite the significant progress in prediction algorithms, the fundamental predictability of structures remains unclear as networks’ complex underlying formation dynamics are usually unobserved. Hence to date there has been a lack of theoretical guidance on the practical development of algorithms for their absolute performance. Here, for the first time, we find that the shortest compression length for a network structure increases linearly with the structure predictability. We observe such linear relation from networks across different domains including social, economic, biological and infrastructure networks, hinting at a possible universal class among empirical networks. In addition, our finding leads to analytical results for maximum prediction accuracy adjustable for different requirements and allows the estimation of the network dataset potential commercial values through the size of the compressed network data file.