大数据结构与关系的度量与简约计算

The ability to store and analyze Big Data is a crucial capability of a powerful country in the new century. This project aims at the weakness on common scientific questions, general methodology, and theoretical analysis of real-time algorithm in the current research of big data. We start from three key features about big data: Volume, Variety, and Velocity, and focus on the measurement and simplification of time complexity, space complexity, and relationship complexity for big data in the whole project. We plan to propose new measurement of time complexity which relies on the incremental data size instead of the whole data size, discover novel algorithm design framework based on it, and implement them in real scenario. We then consider the method of the compression for network data, and try to summarize the general relationship between compression ratio and distortion rate. We also plan to construct cause-and-effect diagram based on the analysis of the different relationship among multi-source data. That’s the way to excavate knowledge and then design the prediction model based on the revealed knowledge. Our goal is to obtain breakthrough in the performance of the algorithms with significant impact and implement them in the real scenario with at least ten millions magnitudes. The project is devote to produce original works with international influence, and contribute to the formation of basic theory and methodology in data science.

大数据储备和分析的能力是未来新型国家的核心战略能力。本项目注意到当前大数据研究在共性问题提炼、方法论框架、实时数据算法理论上存在的不足，从大数据“海量、实时、多样”三大特征出发，聚焦网络大数据这一对象，以数据复杂性的度量和约简作为贯穿全项目的主线。项目研究大数据在时间、空间和关联关系上的简约计算，拟提出一种不依赖于数据总体规模的流数据算法复杂性度量方法和指标，探索流数据实时快速算法设计的思想和框架，并在一些经典算法问题中实现；探索网络数据压缩的方法，总结压缩比和失真率的统计规律甚至一般性关系；分析多源数据各特征项之间的关联、因果和互预测关系，建立因果图，挖掘知识，设计基于“显式知识”的预测模型；在一两个具有重大应用价值的预测问题上突破当前算法性能，并在覆盖千万量级以上真实用户的系统中进行实施。项目定位为产出具有相当国际影响力的原创型学术成果，为数据科学基础理论和基本方法论的形成做出贡献。

项目从时间简约、空间简约和关联简约三个角度对网络大数据，特别是社交网络这一重要应用场景进行研究，在模型、算法等基础理论方面取得了一系列有特色的研究成果，得到国内外同行广泛认可和跟进，形成了一定的学术影响力并在相关场景进行了示范落地。项目组在STOC, FOCS, SODA, NIPS, ICML等CCF A类会议和Nature Commun., PNAS, Sci. Reports, IEEE TKDE, JMLR, Science China等顶级期刊发表高质量论文40余篇，发表SCI收录论文100余篇，SCI单篇最高引用超300次。获得北京市科学技术（技术发明类）二等奖一项，项目组成员作为程序委员会主席或本地主席组织了CIKM, AAIM, AAAC, SMP等著名会议，作为秘书组织“数据科学与计算智能”香山科学会议等。.取得的代表性研究成果包括：1）设计了针对未知参数市场模型运行时间多项式量级的在线均衡学习算法，给出了组合多臂老虎机在线学习算法后悔度上界的理论分析，提出了有理论保证的贪心在线学习、在线聚类算法，证明了小世界模型复杂传播的随机路由下界；2）提出了具有良好局部性和低计算代价的图小波神经网络，大幅降低了传统图卷积算子的参数个数和复杂度，在图半监督学习任务上显著超过了图灵奖得主Yann LeCun等人提出的谱图卷积神经网络，被研究同行评价为“期待已久的工作”；3）提出了结构一致性度量指标对网络的“可被预测的程度”进行刻画，通过分析推荐网络的演化结构特征，基于该链接关系构建个性化推荐模型，解决了因系统演化引起的偏好漂移的影响；4）提出了社团结构挖掘的引力模型，设计了基于局部结构特征和传播动力学特征的大规模网络节点影响力排序算法、重要链路及意见领袖挖掘算法，为从微观、介观和宏观层面研究网络结构提供了分析方法，部分研究结果已落地应用；5）大幅拓展了社会网络中影响力传播最大化的研究范围，提出并研究了非次模、在线、具有鲁棒性的影响力最大化等模型，从理论上证明了不同模型求解的计算复杂性，并为多种模型设计了多项式时间近似算法。.项目组成员沈华伟晋升研究员并入选北京智源人工智能研究院青年科学家和中科院青促会优秀会员，陈端兵晋升教授，陈卫当选IEEE会士，项目负责人孙晓明当选CCF理论计算机专委会主任。博士生庞亮获得中文信息学会优秀博士论文奖，何昆获中科院院长特别奖。