BIGDATA: F: Latent Structure and Dynamics of Big Data

大数据带来了巨大的挑战。也许最大的挑战是从大量嘈杂的数据中提取小而有用的信息。应该使用什么方法来做这些，对于什么数据，这样提取是可伸缩的，产生的不是虚假的工件，而是可证明的可靠的预测知识？许多数据科学应用程序在这些问题上受阻。例如，预测和控制意见、（假）新闻和（错误）信息是一个现实问题，随着在线社交媒体渗透到日常生活中，这个问题正变得越来越高，影响越来越广泛。这个特殊的问题在很大程度上是由于一般不可能将那些天生与自己相似的人联系在一起的人与那些在社交网络中受到同伴影响的人分开，除了在某些特定的环境中。本项目的具体设置——具有潜在空间结构的真实网络——正是解决这些理论和实践难题的设置。该项目将在两个领域做出一系列贡献。首先，它将解决一个长期存在的问题，即获得一类满足现实主义四个要求的随机图模型：稀疏性、可交换性、投射性和无偏性/最大熵。在本课程中，将确定一组图结构性质，从而证明具有这些性质的无偏随机图具有潜在几何结构，从而严格地将随机图的离散组合结构与潜在流形的光滑几何联系起来。该项目将开发的框架来证明这一点，将非常通用，并适用于其他类型的大数据。对随机图的潜在几何性负责的性质被期望描述许多真实网络，这意味着这些网络将保证具有潜在的几何性。该项目的第二部分将侧重于开发可扩展的算法和软件，具有最佳的计算复杂度随数据大小线性扩展，并具有经过验证的准确性保证，以学习真实网络的潜在结构（如果网络有的话），并将这些算法应用于大型真实网络。这种潜在几何学习的结果将有可能将真实网络中的动态过程（例如社会网络中的传播现象）映射到潜在动态，而这种动态背后的潜在统计因素的知识可以用于在实践中以已知的精度界限预测和控制它。

Big data poses big challenges. Perhaps the biggest challenge is to extract small but useful information from big noisy data. What approach should be used to do that, and for what data, so that this extraction is scalable, and yields not spurious artifacts but provably reliable predictive knowledge? Numerous data science applications are blocked on these questions. For example, the prediction and control of opinions, (fake) news, and (mis)information is a practical problem that is becoming of increasingly high and broad impact these days of pervasion of online social media into everyday human life. This particular problem is largely blocked on general impossibility of disentangling those who naturally bond with others like themselves from those influenced by peers in social networks, except in some specific settings. The specific settings of this project -- real networks with latent-space structure -- are exactly the settings in which these theoretical and practical difficulties can be resolved.The project will make a series of contributions in two areas. First, it will resolve a long-standing problem of obtaining a class of random graph models satisfying four requirements of realism: sparsity, exchangeability, projectivity and unbiasedness/maximum-entropy. Within this class, a set of graph-structural properties will be determined such that unbiased random graphs that have these properties are proved to have latent-geometric structure, thus rigorously linking discrete combinatorial structure of random graphs to smooth geometry of latent manifolds. The framework that the project will develop to prove this, will be quite general and applicable to other types of big data. The properties responsible for latent geometricity of random graphs are expected to characterize many real networks, meaning that such networks will be guaranteed to have latent geometries. The second part of the project will focus on developing scalable algorithms and software, with optimal computational complexity scaling linearly with the data size, and with proved accuracy guarantees, to learn the latent structure of a real network if the network has it, and apply these algorithms to large real networks. The outcomes of this latent-geometric learning will make it possible to map dynamical processes in real networks, such as spreading phenomena in social networks, to latent dynamics, while the knowledge of latent statistical factors behind this dynamic can then be used to predict and control it in practice with known accuracy bounds.