Computational Problems in Artificial Intelligence and Network Science: Probabilistic Analyses, Graph-Theoretic Characterizations, and Algorithmic Solutions

人工智能和网络科学中的计算问题：概率分析、图论表征和算法解决方案

• 批准号: RGPIN-2014-04848
• 负责人: Gao, Yong
• 金额: $ 2.33万
• 依托单位: University of British Columbia
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2016
• 资助国家: 加拿大
• 起止时间: 2016-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=611283
• 关键词: Computational; Problems; Artificial; Intelligence; Network

In Artificial Intelligence (AI) and the emerging field of network science, many computationally-hard problems have a natural graph-theoretic or logic formulation. A deep understanding of the nature of these problems and their underlying graph-theoretic structures is indispensable to design well-founded algorithmic solutions and effective modelling tools for (logic) reasoning and problem-solving in AI, and to analyze real-world social, information, and biological networks. My research in the next five years will be centered around two themes, dealing with algorithmic and modelling problems arising in the study of systems and environments that are dynamic, networked, with incomplete information, and sometimes with multiple interacting entities. The first theme focuses on several algorithmic problems related to robust solutions to constraint satisfaction problems and defeasible reasoning with incomplete information. These problems plays an important role in the areas of constraint programming, satisfiability testing, and argumentation in AI. Algorithmic problems with solution concepts of a similar flavor, such as those in graphical games and AI planning in dynamic environments, will also be considered. My research will strive to understand the probabilistic behavior of the various solution concepts, the algorithms for finding such solutions, and the graph-theoretic constructs that characterize tractable subclasses of these problems. The chief goal is to gain insights into the power and limitation of data-reduction and branching rules that are essential for designing and enhancing general-purpose exact algorithms and fixed-parameter tractable algorithms for these problems. The focus of the second theme is on problems from network science, concerning generative random models, graph-theoretic characterizations, and algorithms for community structures widely believed to play a critical role in understanding the organizing principle of a real-world complex network and the dynamic processes taking place in the network. My research under this theme has three main goals: (I) to design generative random models to overcome the difficulties that existing network models have in characterizing the statistics of higher-order structures of a network; (II) to develop, by using sound graph-theoretic constructs, a systematic approach for characterizing community structures that have rich internal structures and are robust against network changes; and (III) to design efficient algorithms for identifying such network communities. The proposed research is expected to be of great practical value and significantly advance our knowledge. The research on the probabilistic behavior of random problem instances and the underlying graph-theoretic structures will offer a unique and novel perspective on several problems that are important in modelling computing tasks in dynamic and networked environments. The work on community structures will help bring the rich body of knowledge from research in graph theory into (social) network analysis. The algorithms and modelling tools developed in the proposed research should be useful for researchers (and practitioners in the software industry) to design better online social networks, to implement more sophisticated software for network analysis, to develop more effective systems to solve real-world optimization problems, and to tackle computational problems in multi-agent systems, bioinformatics, and sociology.

在人工智能（AI）和新兴的网络科学领域，许多计算困难的问题都有一个自然的图论或逻辑公式。深入了解这些问题的本质及其底层图论结构对于设计有充分依据的算法解决方案和有效的建模工具，用于人工智能中的（逻辑）推理和问题解决，以及分析现实世界的社会，信息和生物网络是必不可少的。我在未来五年的研究将围绕两个主题，处理算法和建模问题中出现的系统和环境的研究是动态的，网络化的，不完整的信息，有时与多个相互作用的实体。 第一个主题集中在几个算法问题有关的鲁棒解决方案的约束满足问题和不完全信息的可废止推理。这些问题在人工智能中的约束编程、可满足性测试和论证等领域起着重要的作用。也将考虑具有类似风格的解决方案概念的数学问题，例如动态环境中的图形游戏和AI规划。我的研究将努力了解各种解决方案的概念，算法的概率行为，找到这样的解决方案，以及图形理论的结构，这些问题的易处理的子类的特点。主要目标是深入了解数据简化和分支规则的能力和局限性，这些规则对于设计和增强这些问题的通用精确算法和固定参数易处理算法至关重要。 第二个主题的重点是网络科学的问题，涉及生成随机模型，图论特征和社区结构的算法，被广泛认为在理解现实世界复杂网络的组织原理和网络中发生的动态过程中发挥着关键作用。我在这一主题下的研究有三个主要目标：（一）设计生成随机模型，以克服现有网络模型在表征网络高阶结构统计方面的困难;（二）通过使用合理的图论结构，开发一种系统的方法来表征具有丰富内部结构并对网络变化具有鲁棒性的社区结构;以及（III）设计用于识别这样的网络社区的有效算法。 预计所提出的研究将具有很大的实用价值，并显着推进我们的知识。对随机问题实例的概率行为和底层图论结构的研究将为动态和网络环境中建模计算任务中的几个重要问题提供独特而新颖的视角。社区结构的工作将有助于将图论研究中丰富的知识体系带入（社会）网络分析。在拟议的研究中开发的算法和建模工具应该是有用的研究人员（和从业人员在软件行业）设计更好的在线社交网络，实现更复杂的软件网络分析，开发更有效的系统来解决现实世界的优化问题，并解决计算问题的多智能体系统，生物信息学和社会学。