BIGDATA: Collaborative Research: IA: Novel Bootstrap Procedures for Efficient Large Social Network Analysis

了解社交网络的结构和动态对于发现任何异常行为并管理其影响至关重要。大多数现有方法将网络视为一系列快照，其中快照表示网络在给定时间段内的状态。因此，需要对每个快照分别执行不同的网络操作。在现实中，在线社交网络在不断发展，因此，网络运营应该随着网络的发展而自动执行，需要高效可靠地完成。从这个角度来看问题，使我们能够创建支持高级真实使用案例的解决方案，例如跟踪给定节点的邻居或跟踪网络连接如何及时演变以确定有效的营销活动。这些例子表明，随着大型网络随着时间的推移而发展，对于重要的网络统计数据需要有效的计算技术。为了解决这个问题，本项目中的研究人员使用Bootstrap和其他基于统计重新抽样的方法来补充现有的分布式进化社会图分析技术。最终目标是开发新的数据驱动工具，以便在需要时，不仅可以有效地计算统计网络模型的某些估计，而且可以可靠地量化它们的估计误差。这个项目的主要目标是开发新的高效和健壮的方法来检测大型稀疏网络上的异常和离群点。所得到的方法提供了以下功能：1)针对广泛的网络拓扑统计的计算高效的有限样本推理；2)灵活的数据驱动的网络结构和动态表征；以及3)全面量化大型网络的建模和估计中的不确定性，而不对网络模型规范施加限制条件。预期的进展既包括研究方法--用于大型稀疏网络的数据驱动非参数推理的新方法，也包括在数字通信时代对网络动力学和形成的知识的实质性增强。该项目可以让学生广泛接触大型网络的跨学科应用，并培养对跨学科关系的认识，从而增强他们的批判性思维能力，开辟新的职业道路，从而使学生显著受益。

Understanding the structure and dynamics of social networks is crucial for detecting any anomalous behavior and for managing its impacts. Most existing approaches view a network as a series of snapshots, where a snapshot represents the state of a network in a given time period. Therefore, different network operations need to be individually performed over each snapshot. In reality, online social networks are continuously evolving and therefore, network operations should be automatically performed as networks evolve and need to be done efficiently and reliably. Viewing the problem from this perspective allows us to create a solution that supports advanced, real-world use cases such as tracking the neighborhood of a given node or tracking how network connections evolve in time to determine effective marketing campaigns. These examples indicate the need for efficient computing techniques for important network statistics as the large networks evolve over time. To address this problem, the researchers in this project complement existing distributed evolving social graph analysis techniques with bootstrap and other statistical re-sampling based approaches. The ultimate goal is to develop novel data-driven tools so that when needed, not only certain estimates of statistical network models could be computed efficiently but their estimation errors are reliably quantified. This project primarily targets development of new efficient and robust methods for anomaly and outlier detection on large sparse networks. The resulting methodology provides the following functions: 1) a computationally efficient finite sample inference for an extensive range of network topology statistics; 2) a flexible data-driven characterization of network structure and dynamics, and 3) comprehensively quantifying uncertainty in modeling and estimation of large networks, without imposing restrictive conditions on network model specification. The expected advances are both in research methods - new approaches to data-driven nonparametric inference for large sparse networks and in substantial enhancement of knowledge of network dynamics and formation in the era of digital communication. The project can significantly benefit students by providing a broad exposure to interdisciplinary applications of large network and fostering awareness of interdisciplinary relationships -- hence enhancing their capacity for critical thinking and opening up new career paths.