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

点击翻译按钮获取中文摘要

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.