CAREER: Social Networks - Processes, Structures, and Algorithms

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

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.