CIF: Small: Modeling and Dynamic Analyzing for Multiplex Social Networks

在线社交网络的快速发展使其成为快速传播和影响信息的重要渠道之一。当信息通过在多个社交网站上拥有账户的重叠用户同时在多个社交网站上传播时，这种传播过程变得更加有效。单独分析每个网络将无法识别最具影响力的用户，从而给出错误的信息传播指标。目前，理解跨越多个具有多层的网络的行为，在这里被称为多路社交网络，在很大程度上仍未被探索。该项目旨在开发数学模型和技术来精确和高效地分析多路网络中的信息传播，在保持每个网络的内在属性的同时捕捉网络之间的外在相互依赖关系。该项目的核心在于利用新的数学技术来研究多层多依赖网络中的许多动态过程。这项研究将为理解在多元化社交网络中极快传播的基本属性奠定基础，为有效利用在线社交网络及其众包能力提供突破。此外，该项目开发的算法技术有望推动逼近理论和网络科学的研究前沿。这些发现还可能有益于其他领域，如网络免疫，提供疫情爆发的控制和病毒的遏制，并同样允许我们分析其他动态特征，如许多现代复杂网络系统中相互依赖的级联故障。该项目将涉及所有级别的学生，重点是通过实习计划吸引代表人数不足的群体的学生。本项目将通过以下三个主要研究任务来全面研究复合社会网络中的传播行为：1)通过一套新的图论技术对多重社会网络进行建模。该模型提供了一个统一的框架，以最简单的形式提取网络之间的相互依赖关系和每个网络的属性；2)分析信息传播的速度，并在存在重叠用户同时传播的情况下识别最具影响力的用户。研究了几种新的优化模型及其复杂性分析和近似算法；3)考虑到复杂网络的特性，设计了许多优化问题的近似最优解，因为许多现实世界的网络，从互联网到社会和生物网络，都是复杂的。这是一个新的研究方向，这种方法的成功将影响到许多现实生活中复杂网络问题的近似算法的设计。

The rapid growth of online social networks has made them become one of the most important channels for fast information propagation and influence. This propagation process becomes much more effective when information simultaneously spread on many social sites via overlapping users, who have accounts on multiples social networks sites. Analyzing each network separately will fail to identify the most influential users, and thus give erroneous indicators of information propagation. At present, understanding behavior that crosses multiple networks with multiple layers, dubbed here Multiplex Social Networks, is still largely unexplored. This project aims to develop mathematical models and techniques to precisely and efficiently analyze the information propagation in multiplex networks, capturing the extrinsic interdependencies between networks while preserving each network?s intrinsic properties.At the heart of this project lie novel mathematical techniques to study many dynamical processes in multi-layered multi-dependent networks. This research will lay a foundation in understanding the fundamental properties that contribute to an extremely fast propagation in multiplex social networks, providing a breakthrough in effectively using online social networks and their crowd sourcing capabilities. Furthermore, algorithmic techniques developed in this project are expected to advance research fronts in approximation theory and network science. The findings may also benefit other fields, such as network immunization, offering control of epidemic outbreaks and containment of viruses, and likewise allow us to analyze other dynamic features, such as cascading failures in many modern complex networked systems, which are interdependent. The project will involve students at all levels, with emphasis on attracting students from underrepresented groups via an internship program. The real-world applications will offer an ideal platform to engage undergraduate and K-12 students.This project will comprehensively investigate propagation behaviors in multiplex social networks by pursuing three primary research tasks: 1) modeling a multiplex social network via a new set of graph theory techniques. The model provides a unified framework to extract the interdependencies between networks and the properties of each network in the simplest form; 2) Analyzing the speed of information propagation and identifying the most influential users in the presence of simultaneous spreading via overlapping users. Several new optimization models along with their hardness complexity analyses and approximation algorithms will be investigated; 3) Devising near-optimal solutions for many optimization problems considering the properties of complex networks since many real-world networks, ranging from the Internet to social and biological networks, are complex. This is a novel research direction and success of this approach will impact the design of approximation algorithms for many real-life problems on complex networks.