大规模社会网络影响传播关键技术研究

In recent years, with the in-depth research of Web 2.0 techniques, social network has been widely used as an important medium for communication, knowledge sharing and information spreading. As one of the key issues in the field of social network analysis, influence spread also faces serious challenges, such as massive social network data, dynamic social network topology and diverse influence propagation pattern. However, previous studies are still insufficient in terms of algorithm efficiency, scalability and diversity of propagation model. To address these challenges, in this project, we propose to analyze the characteristics of social network topology and the demands of real-world applications for influence propagation, research on novel influence propagation models and design effective algorithms according to different propagation objectives. We will (1)analyze the evolutionary pattern of real-world online social networks, and design a topology-aware influence maximization algorithm, (2) propose different seed node selection strategies under multi-object competitive scenarios based on different influence propagation objectives, and (3) investigate the differences of influence propagation models under limited and unlimited valid range and design optimal seed node selection strategy for specified valid influence range scenarios. The answer to these problems can properly improve the efficiency and utility of influence propagation strategy for realworld applications.

近年来，随着Web 2.0技术的飞速发展，社会网络已经成为交互沟通、知识共享和信息传播的重要媒介。作为社会网络分析的关键技术之一，影响传播技术也面临着全新的挑战：社会网络数据规模海量、社会网络拓扑的动态变化性强和影响传播方式多种多样。已有的影响传播研究在算法执行效率、可扩展性和传播模型多样性等方面仍存在不足。针对上述问题，课题将结合社会网络拓扑结构特性和实际应用对影响传播的真实需求，研究新型影响传播模型，根据不同的影响传播目标设计高效的影响传播方案。具体包括：（1）分析和挖掘大规模社会网络拓扑结构的演化特征，研究拓扑变化感知的影响最大化算法；（2）针对不同竞争模式的影响传播目标，提出针对多目标竞争的种子节点选择策略；（3）研究有效传播范围有限定和无限定情况下信息传播方式的差异，设计指定有效影响范围的种子节点最优方案。通过解决这些科学问题，有效提高实际传播场景下影响传播方案的效率和实用性。

本项目针对大规模社会网络影响传播关键技术展开研究。针对社会网络拓扑结构的动态演化特征，构建了动态影响最大化EIM问题，并基于择优连接原则和局部性原则，研究了拓扑变化感知的剪枝算法；针对现实社会网络中存在的多目标竞争场景，提炼出最小代价获胜的竞争模式，并设计了相应的种子节点选择策略；针对指定有效影响范围的影响传播模型，证明了其影响传播函数具备子模特性，并设计和实现了一种基于效能的种子节点最佳选择方案。通过上述研究，对目前学术界的影响传播问题研究进行了深化，同时拓宽了影响最大化问题的适用场景。课题组按照研究计划推进研究工作，完成了课题拟定目标，在动态影响最大化、最小代价获胜、指定范围影响最大化等方面取得了多个关键技术突破。截止2017年底课题组共在国内外学术期刊、学术会议上发表学术论文12篇，其中SCI检索4篇、EI检索5篇。培养博士研究生4人，硕士研究生3人。