面向时间约束的动态社交网络影响力最大化问题研究

Social network plays an essential role in the spread of information on internet, and it is also a hot topic in academic society in recent years. Influence maximization problem is a fundamental issue in this field, which means to find a subset of influential individuals in a social network such that targeting them initially (e.g. to adopt a new product) will maximize the spread of the influence (further adoptions of the new product). Lots of works have been done for influence maximization problem on static social networks. Unfortunately, many researches point that dynamics is an inherent attribute of social networks and the spread range of information will be affected along with the change of time constraints and network topology. So that the current researches that start from static network topology are not practical enough to deal with the actual problems. Based on such problem, this project will study the time constrained influence maximization problem in dynamic social network. The content and innovations of the project include the following: 1. Modeling of dynamic social network for time constraint, which can be used to automatically build model of social network with time constraints and dynamics. 2. Algorithm for time constrained influence maximization in dynamic social network, as well as the heuristic rules and their optimization. 3. Empirical study on information spread in actual social networks, by which some inherent patterns of dynamic social network will be found, and the comparison between empirical study and theoretical study will offer feedback to the research.

社交网络在网络信息传播中扮演着重要角色，是近年国内外研究热点之一。影响力最大化问题是该领域基本问题，其研究目标是在大规模社交网络中寻找一个初始目标节点集合，使得从这些节点出发，达到目标信息传播的最大化。目前针对静态社交网络的影响力最大化问题已取得一定进展。但大量研究指出，社交网络具有动态性，其中信息传播范围是随着时间约束和网络拓扑结构的变化而变化的。因此，现有研究从静态网络拓扑结构出发，难以解决真实环境中的实际问题。因此，本课题拟研究面向时间约束的动态社交网络影响力最大化问题。 本课题研究内容和创新点包括：1、面向时间约束的动态社交网络建模方法，能够自动化地建立反映时间约束和动态性的社交网络模型。2、面向时间约束的动态社交网络影响力最大化分析算法、启发式规则及其优化。3、针对真实社交网络信息传播的经验研究，发掘实际社交网络动态性内在规律，并通过对比，对本课题方法进行反馈。

本项目的目标是通过相关研究，提出能够有效地描述面向时间约束的动态社交社交网络的方法，并对其进行影响力最大化分析。根据研究目标和任务的要求，本项目在研究过程中提出了基于现有网络模型，建立适用于描述动态社交网络的建模方法DynaDiffuse；并基于模型，提出具有较快速度和较高准确率的影响力最大化分析算法以及优化的启发式规则，该算法以及启发式规则能够高效地处理网络中的动态性和时间约束；然后，基于真实社交网络数据，对社交网络影响力最大化问题进行了经验研究，验证了DynaDiffuse的有效性。进一步地，为了适用于大数据环境，提出了一种分布式计算框架的高可靠性线性时序逻辑模型检测算法VCPLM。在本项目的支持下，课题组完成了项目申请书所规定的研究任务，实现了项目的研究目标。