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.