在线社交网络中时间敏感信息的高效传播策略研究

Social networks are experiencing an explosive growth. It has become an important and powerful means of medium for information dissemination. Because social networks have complex structure, super-large scale, highly diversified and highly dynamic users, the understanding towards the information dissemination in social networks is still very much limited. Existing research mainly focuses on information diffusion in the long term, but little work has been done for the time-critical information diffusion. We aim to study the key issues of efficient dissemination for time-critical information in online social networks. This project has three major tasks: 1) Develop a predictive model to characterize the information diffusion process in online social networks. This model should include temporal dimension that describes how information is diffused over time. 2) Design efficient real-time information diffusion methods that can disseminate information in online social networks before the deadline and with minimal cost. 3) Design fast information diffusion algorithms that can disseminate information in the networks within a given social distance. This project will lead to a deeper understanding about how information is diffused along both spatial and temporal dimensions in online social networks. It will help to design more efficient and effective algorithms for online social networks. Moreover, the algorithms developed in this project can be applied to online social networks and bring social and economic impact.

在线社交网络正在经历爆炸式的发展，它已成为一种重要的信息传播媒介，是扩散时间敏感、受众广泛信息的有力工具。由于在线社交网络结构复杂、规模庞大、高度异构且动态变化，并且用户呈现多样性，目前对于信息传播过程的理解还非常有限。已有研究通常关注信息的长期扩散影响，而忽略了信息的扩散速度。本课题研究在线社交网络中时间敏感信息的高效传播策略，建立包含时间动态的信息传播预测模型，刻画信息如何随着时间的推移而扩散，预测消息扩散概率和扩散时间；设计时间敏感信息的实时传播算法，给定截止时间，寻找最小的种子集合，使得在截止时间内，网络中至少给定比例的用户被该信息所影响；设计时间敏感信息的快速传播算法，在一定的社交距离约束下，寻找最小的种子集合发布消息，使得至少给定比例的用户被该息所影响。研究成果可直接应用于社交网络的信息传播，具有较强的理论和实际研究价值。

影响最大化是在线社交网络的一个基本研究问题，它是指如何选取一些有影响力的用户做为初始的种子节点发布消息，实现信息在网络中的有效扩散，从整体上最大程度地影响其他用户。但是已有的研究通常认为一个用户只会影响它的邻居节点一次，且不考虑时间和代价约束。在真实世界里，人们会在一段时间内反复影响其好友，有时信息的传播也会付出一些代价。我们利用用户在线模型提出了时间和代价受限制的影响力模型TCIO。在TCIO模型中，种子节点的选取受限于预算，并且在消息过期之前，每个节点会根据邻居节点的上线模式反复影响邻居节点，证明了该问题是NP难问题，并且TCIO具有影响力扩散的单调性和子模性。我们设计了贪心算法来解决该问题。为了降低计算复杂度，优化种子节点选取过程，我们提出了算法GMAI，利用影响力权重有效地近似计算影响力的增加。.研究者提出了许多影响力最大化的算法，然而已知算法都是串行执行，在大规模社交网络将花费很长时间。我们研究了两类大规模社交网络影响力最大化的问题：没有预算限制的影响力最大化和有预算限制的影响力最大化。分别为这两类问题提出基于社团的最大度算法和最大度开销比例算法。两种方法都可并行地运行于Hadoop平台。我们在各种规模的社交网络进行了实验，实验结果表明所提出的算法具有良好的可扩展性，并且性能优于传统的启发式算法。.混合车载网络融合了车载网络和移动通信网络，提出了一种混合节点部署方案，该方案考虑路边节点数量有限的条件下，如何通过优化路边节点的部署位置，以满足尽可能多的车辆节点的通信需求，从而最大化路边节点的部署效益；提出了一种基于社交性的混合部署策略，通过分析混合车载网络具有社区性质，并利用该特性进行最优部署；通过分析真实车辆的轨迹数据并且通过提取车辆间的“接触”和运用社区发现理论发现了其中的社交性，提出了社区合作度的概念去衡量整个社区中消息传递的合作的概率。.在智能电网中，智能电表是收集用户用电量的设备。智能电表为控制中心提供了一种及时准确监测电力供应和消耗的高效手段。然而，通过非可信的公共网络收集用户的用电情况面临着严重的隐私问题。我们为智能电网中的电表数据收集提出一种轻量的隐私保护方案，该方案有轻量级、无需可信第三方进行密钥生成和密钥管理和可扩展的特点，可应用于通过公共网络连接的大规模用户。