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

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

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.