Collaborative Research: Zero Forcing on Graphs: Computation and Applications

合作研究：图上的零强迫：计算和应用

• 批准号: 1719841
• 负责人: Michael Young
• 金额: $ 6万
• 依托单位: Iowa State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-07-15 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1719841&HistoricalAwards=false
• 关键词: Collaborative; Research; Zero; Forcing; Graphs

The concept of networks is a mathematical term used to analyze relationships between objects (e.g. people, places, and things). Of particular importance is the study of how influence propagates throughout networks, especially how one can deduce the influence of an entire network by monitoring a few members. The objective of this project is to establish a comprehensive knowledge base for developing, implementing, and applying computational methods related to this phenomenon. As a result, this research has strong connections to applications related to social networks, electrical power networks, and quantum systems. This project also supports a concerted effort to engage underrepresented groups within the research. Hence, the impact of this educational component includes the development of underrepresented groups within the next generation of STEM researchers.The main technical contribution of this project is the integration of combinatorial optimization, spectral graph theory, and numerical analysis techniques to examine zero-forcing in networks. In particular, the research team will incorporate branch decomposition techniques and linear and integer programming techniques to significantly increase the computational efficacy of algorithms to solve zero-forcing problems on graphs. The models and algorithms that result from this study will be validated using experimental data and also by data attainable publicly like electrical grid data. This research will significantly advance the knowledge base of combinatorial optimization, integer programming, and spectral graph theory while also contributing to the increased scalability and efficiency for solving computationally hard problems related to the aforementioned applications.

网络的概念是一个数学术语，用于分析对象（例如人，地点和事物）之间的关系。 特别重要的是研究影响力如何在整个网络中传播，特别是如何通过监视少数成员来推断整个网络的影响力。 该项目的目标是建立一个全面的知识库，用于开发，实施和应用与此现象相关的计算方法。 因此，这项研究与社交网络、电力网络和量子系统相关的应用有着密切的联系。 该项目还支持协同努力，使代表性不足的群体参与研究。 因此，这一教育部分的影响包括下一代STEM研究人员中代表性不足的群体的发展。该项目的主要技术贡献是组合优化，谱图理论和数值分析技术的整合，以检查网络中的迫零。 特别是，研究团队将结合分支分解技术和线性和整数规划技术，以显着提高算法的计算效率，以解决图上的迫零问题。从这项研究中得出的模型和算法将使用实验数据以及可公开获得的数据（如电网数据）进行验证。 这项研究将显着推进组合优化，整数规划和谱图理论的知识基础，同时也有助于提高可扩展性和效率，解决与上述应用程序相关的计算困难的问题。