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
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=588055
• 关键词: 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）和新兴的网络科学领域，许多计算困难的问题都有一个自然的图论或逻辑公式。对这些问题的本质及其潜在的图论结构的深刻理解是为人工智能中的（逻辑）推理和问题解决设计有充分基础的算法解决方案和有效的建模工具，以及分析现实世界的社会、信息和生物网络所必不可少的。我在未来五年的研究将围绕两个主题，处理在动态的、网络化的、信息不完全的、有时有多个相互作用的实体的系统和环境的研究中出现的算法和建模问题。