动态多关系网络中影响力最大化问题的研究

Influence maximization in complex networks is an important topic in complex network analysis. There are many issues to be solved, such as how to model influence propagation, and how to utilize the relationships of varied links and temporal information in the process of influence maximization. Firstly, this project studies the influence propagation model of dynamic and multi-relational networks so as to reflect the dynamics, temporality and the changes of its topology structure of all links type. And on this basis, this project studies the importance of nodes in the different type of links and correlation between nodes. Furthermore, we intend to design the influence maximization algorithm based on the multiple relations and analyze the influence of overlapping nodes. Finally, It proposes the incremental algorithm about influence between nodes by making use of the dynamic of the network, which reduces time and space complexity of the algorithm, and it determines the propagation range of the nodes between adjacent time periods, removes the nodes which can't be propagated and extracts the key information of the network. This project will intensify the research results of influence maximization and it has great theoretical significance and application values in the areas of social network analysis, viral marketing and so on.

动态多关系网络的影响力最大化是复杂网络分析中的重要课题。其中，如何设计网络的影响力传播模型，如何利用各种类型链接之间的相关关系以及网络的时序信息进行影响力最大化算法的设计等诸多问题亟待解决。首先，本项目拟研究动态多关系网络的影响力传播模型，使之反映网络的动态性、时序性以及各类链接的拓扑变化。在此基础上，研究节点在不同类型链接中的重要性、节点之间的相关性、节点的重叠影响力问题并利用网络的多关系性进行影响力最大化算法的设计。最后，研究如何利用网络的动态性设计出节点之间影响力的增量式计算方法并确定相邻时间段内节点的影响力传播范围，去除目标节点明显不可能传播到的节点，提取出网络的关键信息，以此降低算法的时空复杂度。本项目的研究一方面可以检验和丰富动态多关系网络影响力最大化问题的研究成果，另一方面对指导社交网络分析、商品营销等领域的应用开发有着重要的理论意义和应用价值。

本项目主要研究动态多关系网络的影响力传播模型，使之反映网络的动态性、时序性以及各类链接的拓扑变化，并提出了相关算法。首先，本项目研究节点在不同类型链接中的重要性、节点之间的相关性、节点的重叠影响力，并利用网络的多关系性进行影响力最大化算法的设计；在此基础上提出了一种基于竞争转移概率的最小成本影响力最大化算法，在模型中为每个节点设置一个一维向量，存放着该节点选择不同竞争对手的概率。在传播的过程中，提出了基于传播概率的影响力传播模型，该模型并不关心该节点被哪一个竞争对手所激活，而通过对所有的竞争对手设置不同的权重来激活网络中其余的节点。在影响力传播过程中，根据每一个节点的性价比进行种子节点的选取，最终依据竞争转移概率进行影响力的评价。另外本项目对网络进行渗流模拟，计算渗流后网络的主连通分量随着传播概率改变的趋势，并且求得主连通分量大小增加开始变快的相变点，从而计算网络自身传播影响力的固有能力。通过相变值与种子节点集合大小的换算，求得当前网络最佳的种子节点集合大小。将种子节点集合大小限制在最佳大小范围内即可获得最佳的影响力。接下来本项目提出了基于节点影响力传播范围的影响力最大化算法，并将提出的算法与一些经典的算法进行影响力比较，也获得了较好的结果。最后本项目针对影响力最大化中如何对种子节点的影响力进行有效的衡量进行了分析。通过分析发现，节点的影响力不仅只与自身的度有关，还与自身的核数，以及阶邻居的度与核数有关。基于此观点，提出了基于节点混合重要性的影响力最大化算法。本项目的研究一方面可以检验和丰富动态多关系网络影响力最大化问题的研究成果，另一方面可有效指导社交网络分析、商品推荐等领域的应用开发。