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
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=651515
• 关键词: 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中的问题是必不可少的，并且可以分析现实世界中的社会，信息，信息和生物网络。我未来五年的研究将集中在两个主题围绕两个主题围绕，并处理在动态，网络，网络，不完整信息的系统和环境中产生的算法和建模问题，有时以及多个交互实体。 **第一个主题侧重于与不完整信息的限制性解决方案有关的多种算法问题，以限制满意度问题和可不可行的推理。这些问题在AI中的约束编程，可满足性测试和论证方面起着重要作用。还将考虑使用类似风味的解决方案概念的算法问题，例如图形游戏中的算法和动态环境中的AI计划。我的研究将努力理解各种解决方案概念的概率行为，找到此类解决方案的算法以及表征这些问题的可拖动子类的图理论构建体。主要目的是洞悉数据还原和分支规则的功率和局限性，这些规则对于设计和增强通用的精确算法和固定参数可处理算法至关重要。 **第二个主题的重点是网络科学的问题，涉及有关社区结构的生成随机模型，图理论特征和算法，被人们普遍认为在理解现实世界中复杂网络的组织原理以及网络中发生的动态过程方面起着至关重要的作用。 我以该主题为主题的研究有三个主要目标：（i）设计生成的随机模型，以克服现有网络模型在表征网络高阶结构的统计数据方面遇到的困难； （ii）通过使用声音图理论结构来开发一种系统的方法，用于表征具有丰富内部结构并与网络变化的社区结构的表征； （iii）设计有效的算法来识别此类网络社区。 关于随机问题实例和基础图理论结构的概率行为的研究将为几个问题提供独特而新颖的观点，这些问题对于在动态和网络环境中对计算任务进行建模很重要。关于社区结构的工作将有助于将图理论研究中的丰富知识带入（社会）网络分析。拟议研究中开发的算法和建模工​​具对于研究人员（以及软件行业的从业人员）设计更好的在线社交网络，以实施更复杂的软件进行网络分析，开发更有效的系统来解决现实世界中的优化问题，并解决现实世界中的计算问题，以解决多样性的系统，生物信息和社会学。