AF: Small: Scalable Algorithms for Data and Network Analysis

AF：小型：用于数据和网络分析的可扩展算法

• 批准号: 1815254
• 负责人: Shanghua Teng
• 金额: $ 50万
• 依托单位: University of Southern California
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-06-01 至 2022-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1815254&HistoricalAwards=false
• 关键词: AF; Small; Scalable; Algorithms; Data

Data-based decision-making involving big input data sets require a lot of time for algorithms to process them. In computer science, efficient algorithms are generally considered to be the ones whose running time does not increase "too fast" when input size grows. "Scalable algorithms" are among the most efficient algorithms, because their running time is required to be nearly linear or even sub-linear with respect to the problem size. In other words, their complexity scales gracefully when the input size scales up. In the age of Big Data, efficient algorithms are in higher demand now more than ever before. While big data takes us into the asymptotic world envisioned by the pioneers of computer science, the explosive growth of problem size has also significantly challenged the classical notion of efficient algorithms: Algorithms that used to be considered efficient, according to the traditional polynomial-time characterization, may no longer be adequate for solving today's problems. It is not just desirable, but essential, that efficient algorithms should be scalable. Thus, scalability, instead of polynomial-time computability, should be elevated to the central complexity notion for characterizing efficient computation, and this will be the focus of algorithm design for network sciences and big data. This project will focus on the design and analysis of scalable algorithms. One of its primary objective is to build bridges between the area of algorithm design and the fields of network sciences and machine learning. If successful, the project will help to provide a rigorous algorithmic framework for designing new scalable data and network analysis algorithms. By focusing on notions of algorithmic efficiency --- such as scalability --- that respect the sensibilities of researchers in these disciplines as to what constitutes a practical algorithm in the age of big data, this project aims to increase the value of theoretical analyses to researchers in these fields. As this project combines ideas from many disciplines within one coherent research effort, lectures and tutorials presented on the fruits of the project will help cross-fertilize the disciplines within its scope. The development of theoretical algorithms that might have practical applicability should simplify education in algorithms for students beyond theoretical computer science, and allow discussion of practically important heuristics at early stages of computer science education. The interdisciplinary nature of this research will enable broader engagements with PhD students and researchers in network sciences, machine learning, numerical analysis, and social science and hence will enhance the chance to be successful in supporting and working with women and minority researchers.The technical goal of this project is to systematically extend the family of algebraic, numerical, and combinatorial techniques from the recent breakthroughs in Laplacian linear solvers and max-flows/min-cuts, to a wide-range of problems that arise in network analysis, data mining, and machine learning. This project aims to show that these techniques --- including advanced sampling, sparsification, and local exploration of networks --- will play increasing roles in improving algorithmic scalability. It contains several open questions and conjectures ranging from network analysis to distribution sampling to social influences towards this goal. By providing new algorithmic insights into various dynamic processes over graphs, the project also aims to improve the understanding of network facets beyond static graph structures in order to develop better algorithmic theory for network sciences.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

涉及大型输入数据集的基于数据的决策需要大量时间来处理它们。在计算机科学中，通常认为有效的算法是当输入大小增长时运行时间不会“太快”的算法。 “可伸缩算法”是最有效的算法之一，因为相对于问题大小，它们的运行时间几乎是线性甚至次线性的。换句话说，当输入大小扩大时，它们的复杂性优雅地缩放。在大数据时代，有效的算法现在比以往任何时候都更高。尽管大数据将我们带入计算机科学先驱所设想的渐近世界，但问题大小的爆炸性增长也显着挑战了经典的有效算法的概念：根据传统的多种态度表征，这些算法被认为是有效的，可能不再适合解决当今问题。不仅是理想的，而且重要的是，有效的算法应该可扩展。因此，可扩展性，而不是多项式时间的可计算性，应提升到表征有效计算的中心复杂性概念，这将是网络科学和大数据的算法设计的重点。该项目将集中于可扩展算法的设计和分析。 它的主要目标之一是在算法设计领域与网络科学和机器学习领域之间建造桥梁。 如果成功，该项目将有助于提供严格的算法框架，以设计新的可扩展数据和网络分析算法。 通过关注算法效率的概念 - 例如可扩展性 - - 尊重这些学科研究人员在大数据时代构成实际算法的敏感性，该项目旨在提高理论分析对这些领域研究人员的价值。 由于该项目将许多学科的想法结合在一个连贯的研究工作中，因此在该项目的果实上介绍的讲座和教程将有助于跨授予其范围内的学科。 可能具有实际适用性的理论算法的发展应简化理论计算机科学以外的学生的算法教育，并允许在计算机科学教育的早期阶段讨论实际重要的启发式方法。这项研究的跨学科性质将在网络科学，机器学习，数值分析以及社会科学方面与博士生和研究人员进行更广泛的交往，因此将增强与妇女和少数族裔研究人员的成功和合作的机会。该项目的技术目标是系统地扩展了与代数，数字和组合技术的局部关系，并延伸Max-Flows/min-Cuts，到网络分析，数据挖掘和机器学习中出现的大量问题。 该项目旨在表明这些技术 - 包括高级抽样，稀疏和对网络的本地探索 - 将在提高算法可扩展性方面发挥越来越多的作用。 它包含了几个开放性问题和猜想，从网络分析到分销抽样再到社会影响到这一目标。 通过对图形的各种动态过程提供新的算法见解，该项目还旨在提高对网络图形结构以外的网络方面的理解，以开发网络科学的更好的算法理论。该奖项反映了NSF的法规使命，并认为通过基金会的知识优点和广泛的critia criter criter criteria crietia criteria criter criteria criteria criteria crietia criteria crietia criteria crietia crietia crietia cristia均值得通过评估。

项目成果

Computational Analyses of the Electoral College: Campaigning Is Hard But Approximately Manageable

选举团的计算分析：竞选活动很困难，但大致可控

• DOI: 10.1609/aaai.v35i6.16668
• 发表时间: 2021
• 期刊: Proceedings of the AAAI Conference on Artificial Intelligence
• 作者: Dehghani, Sina;Saleh, Hamed;Seddighin, Saeed;Teng, Shang-Hua
• 通讯作者: Teng, Shang-Hua

A graph-theoretical basis of stochastic-cascading network influence: Characterizations of influence-based centrality

• DOI: 10.1016/j.tcs.2020.04.016
• 发表时间: 2020-07
• 期刊: Theor. Comput. Sci.
• 作者: Wei Chen;S. Teng;Hanrui Zhang

Capturing Complementarity in Set Functions by Going Beyond Submodularity/Subadditivity.

通过超越子模/子可加性来捕获集合函数中的互补性。

• 发表时间: 2019
• 期刊: Innovations in Theoretical Computer Science Conference
• 作者: Chen, Wei;Teng, Shang-Hua;Zhang, Hanrui
• 通讯作者: Zhang, Hanrui

Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis.

量子逻辑综合中 CNOT 电路的最佳空间深度权衡。

• 发表时间: 2020
• 期刊: Proceedings of the annual ACMSIAM symposium on discrete algorithms
• 作者: Jiang, Jiaqing;Sun, Xiaoming;Teng, Shang-Hua;Wu, Bujiao;Wu, Kewen;Zhang, Jialin
• 通讯作者: Zhang, Jialin