III: Small: Robustness in Social Network Analysis: Models, Inference, and Algorithms

“社交网络分析”这个新兴领域专注于从这些社交网络数据中提取有用的见解。已实现或设想的应用程序范围广泛，从了解人类交互背后的本质和驱动力，到目标产品或活动建议，甚至国土安全。与其他网络（如交通或计算机网络）相反，大量的不确定性和噪音实际上总是与社交网络数据相关：与个人有关的数据通常无法观察到，或者被错误地观察到。该项目的主要目标是了解此类噪声数据的风险和影响，并设计对噪声和缺失数据具有更强鲁棒性的网络分析算法。考虑到数学模型在社交网络分析中的重要性，该项目的一个密切相关的线索是分析典型社交网络模型与现实世界数据之间的契合度，特别是关于高级连接属性。项目网站将用于传播作为项目一部分收集的研究原型和数据。具体来说，将探索整合pi在机器学习和理论计算机科学方面的专业知识的三个相互关联的研究重点：(1)标准随机图模型如何很好地适应现实世界的社交网络数据，特别是关于扩展和频谱特性？既然答案很可能是“糟糕”，那么基于要求局部或全局结构的修改如何解决这个问题呢？(2)当学习某些传染行为时，缺少对扩散或激活过程的观察对推断的社会网络有什么影响？如何通过考虑数据丢失可能性的算法来减轻这种影响？(3)如果观察到的社会网络数据具有显著的（可能是非随机的）噪声，在什么条件下可以保证算法输出的稳定性？正确的答案要有多“明显”才不会被数据中的噪音所掩盖？能更有效地找到“显而易见”的答案吗？提出的研究有可能影响社会网络推理和优化的解决方式。pi致力于一系列活动，其中包括将本科生纳入拟议的研究，并向当地高中生伸出援助之手，以产生更广泛的影响。

The burgeoning field of "Social Network Analysis" focuses on extracting useful insights from such social network data. Implemented or envisioned applications range from learning about the nature and driving forces behind human interactions, to targeted product or activity recommendations and even homeland security. Contrary to other networks, such as transportation or computer networks, massive uncertainty and noise are practically always associated with social network data: data pertaining to individuals are often not observable, or are observed incorrectly. The primary goal of this project is to understand the risks and implications of such noisy data, and to design network analysis algorithms that are significantly more robust to noise and missing data. Given the importance that mathematical models play in social networks analysis, a closely related thread of the project is to analyze the fit between typical social network models and real-world data, in particular regarding high-level connectivity properties. The project website will be used to disseminate research prototypes and data that are collected as part of the project.Specifically, three connected research thrusts that integrate the PIs' expertise in machine learning and theoretical computer science will be explored: (1) How well do standard random graph models fit real-world social network data, in particular with regard to expansion and spectral properties? Since the answer likely is "poorly," how well do modifications based on requiring local or global structure remedy this problem? (2) What is the impact of missing observations of diffusion or activation processes on the inferred social networks when learning from some contagious behavior? How can this impact be mitigated by algorithms that take the possibility of missing data into account? (3) If social network data are observed with significant (and possibly non-random) noise, under what conditions can stability of an algorithmic output be ensured? How "obvious" does the right answer have to be to not get obscured by noise in the data? Can "obvious" answers be found more efficiently? The proposed research has the potential to impact the way in which social network inference and optimization are addressed. The PIs are committed to a suite of activities, among them inclusion of undergraduate students in the proposed research and outreach to local high school students, for broader impacts.