CAREER: Social Networks - Processes, Structures, and Algorithms

职业：社交网络 - 流程、结构和算法

• 批准号: 1452915
• 负责人: Grant Schoenebeck
• 金额: $ 50.5万
• 依托单位: Regents of the University of Michigan - Ann Arbor
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-07-01 至 2022-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1452915&HistoricalAwards=false
• 关键词: CAREER; Social; Networks; Processes; Structures

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.

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

项目成果

Optimal Local Bayesian Differential Privacy over Markov Chains

马尔可夫链上的最优局部贝叶斯差分隐私

• 发表时间: 2022
• 期刊: AAMAS '22: Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems
• 作者: Chakrabarti, Darshan and

Wisdom of the Crowd Voting: Truthful Aggregation of Voter Information and Preferences

群体投票的智慧：选民信息和偏好的真实汇总

• 发表时间: 2021
• 期刊: Advances in neural information processing systems
• 作者: Schoenebeck, Grant and