报告简介 Abstract
Structure prediction is an important and widely studied problem in network science and machine learning, finding its applications in various fields. Despite the significant progress in prediction algorithms, the fundamental predictability of structures remains unclear, as networks’ complex underlying formation dynamics are usually unobserved or difficult to describe. As such, there has been a lack of theoretical guidance on the practical development of algorithms for their absolute performances. Here, for the first time, we find that the normalized shortest compression length of a network structure can directly assess the structure predictability. Specifically, shorter binary string length from compression leads to higher structure predictability. We also analytically derive the origin of this linear relationship in artificial random networks. In addition, our finding leads to analytical results quantifying maximum prediction accuracy, and allows the estimation of the network dataset potential values through the size of the compressed network data file.
嘉宾简介 About the Speaker
Yanqing Hu received his PhD degree from Beijing Normal University in 2011. He was a Postdoctoral Researcher at the Levich Institute, City University of New York, from 2011 to 2013. Currently, he is an Associate Professor in the school of data and computer science at Sun Yat-sen University. His current research interests mainly focus on using big data to explore the mechanisms inside complex systems, such as the spreading of human behavior, the resilience of brain and infrastructure networks, the network structure predictability and formation process, etc. Here is his homepage:
讲座海报 Poster
