CAREER: Social Networks - Processes, Structures, and Algorithms

这个项目旨在对复杂而战略性的网络过程、网络结构和网络属性的算法进行严格的理论理解。社交网络是一个抽象概念，用于通过成对的社交互动来研究社会结构，并已被证明在分析局部行动如何影响全球趋势方面很有用。更好地理解社交网络有望更好地理解和影响广泛的现象，包括：个人和公司采用什么技术/实践，信息是如何传输和聚合的，以及网络结构如何与代理人在网络中搜索的能力相关。在所有这些情况下，个人的活动都可以产生全球范围的影响。这个项目寻求开发新的算法和理论框架，以帮助充分利用这些数据。这个项目将开发和应用理论计算机科学的传统工具、见解和方法，包括泛函分析、图论、组合学、线性代数、概率分析、线性和半定程序层次结构、复杂性理论、这个项目将通过以下方式改变我们使用社交网络数据的方式：1)开发所需的技术工具，以更好地理解特定的复杂和战略过程(包括上述过程)；2)识别可有效验证并有助于理解网络过程中的细微差别的网络结构；3)通过明确考虑代理人的战略推理来提高我们对某些网络过程的理解。该项目的技术内容将直接应用于相关领域，如概率、经济学、社会学和统计物理。此外，这个项目的一个关键目标是超越更糟糕的情况分析；如果成功，这将为将理论计算机思想输出到许多学科铺平道路，在这些学科中，由于其固定在最坏情况下的难度，目前它们的应用受到限制-特别是在以生物学和流行病学等网络为特征的领域。PI计划开发课程，向高中生介绍计算机科学主题，并让本科生参与他的研究。

This project seeks to develop a rigorous theoretical understanding of complex and strategic network processes, network structure, and algorithms for network properties.   Social networks are an abstraction used to study social structure via pair-wise social interactions, and have proven useful in analyzing how local actions affect global trends.  Better understanding of social networks promises a better understanding of and the ability to influence a wide range of phenomena, including:  what technologies/practices people and firms adopt, how information is transmitted and aggregated, and how network structure relates to the agents' ability to search within the network.  In all of these instances individuals' activities can have a global-scale impact, which is mediated by a network.  The increasing presence of computer-accessible data (e.g., websites, user-generated content, usage data from telecommunications, apps, web-browsing, etc.)  has rekindled an interest in this field because of the new ability to gather data to test theories on a large scale.  This project seeks to develop new algorithms and theoretical frameworks to help fully make use of these data. This project will develop and apply traditional tools, insights, and approaches from theoretical computer science including functional analysis, graph theory, combinatorics, linear algebra, probabilistic analysis, linear and semidefinite program hierarchies, complexity theory, and game theory to the study of network processes and structure.  This project will transform the way we use social network data by: 1) developing the technical tools required to achieve a better understanding of specific complex and strategic processes (including those mentioned above), 2)  identifying network structures that are efficiently verifiable and are useful for understanding nuances in the network processes,  and 3)  improving our understanding of certain network processes by explicitly accounting for agents' strategic reasoning.  The technical content of this project will have direct applications to related fields such as probability, economics, sociology, and statistical physics.  Additionally,  a key goal of this project is to move beyond worse-case analysis; if successful, this will pave the way to exporting theoretical computer ideas to many disciplines where their current application is limited due to its fixation on worst-case hardness---in particular fields that feature networks such as biology and epidemiology. The PI plans to develop curriculum to introduce computer science topics to high school students and involve undergraduates in his research.