基于控制集理论的社交网络影响最大化问题研究

The problem of influence maximization is the key problem in the field of information spread in social network. It aims to find an initial node set of smaller size in the network, such that by targeting this set, one maximizes the expected spread of influence in the network. These initial nodes usually have great social influence, accelerating information diffusion and enlarging social public opinion, and thus play a great role in information spread. This project mainly studies the influence maximization problem in large-scale social network by using dominating set theory of graphs. Our main goal is to design efficient algorithms for finding most influential nodes in large-scale social network. The contents include: (1) Analyze the rule of information diffusion in social network and translate the influence maximization problem into parametric domination problem; (2) Based on the structural characteristics of social networks, design efficient algorithms for computing parametric dominating set of graphs; (3) Study the theory and algorithm of parametric domination problem on dynamic graphs and solve the influence maximization problem in large-scale social networks. This project can provide theoretical basis for network marketing, public opinion guidance, and rumor control.

影响最大化问题是社交网络信息传播领域研究的关键问题，旨在寻找网络中规模较小的初始节点集，使得从这些节点出发进行信息传播最终影响到的节点最多。这些初始节点通常具有较大的社会影响力，可以加速信息扩散、放大社会舆论，从而在信息传播中发挥着巨大作用。本项目拟通过图的控制集理论与方法，对大规模社交网络影响最大化问题进行研究，其主要目的是设计求解大规模社交网络中最具影响力节点的高效算法，研究内容包括：（1）分析社交网络信息传播规律，将影响最大化问题转化为图的参数控制集问题；（2）结合社交网络结构特征，设计求解图参数控制集的高效算法；（3）研究动态图的参数控制集理论及算法，解决大规模社交网络影响最大化问题。该项目研究可对网络营销、舆论引导、谣言控制等提供理论依据。

本项目以图的控制集理论为基础展开研究社交网络影响最大化问题，重点分析了社交网络节点影响力度量、影响最大化算法以及网络中重要节点刻画，主要取得的研究成果有：1) 利用图的控制集理论，分析了网络结构变化对控制集以及节点影响力的影响，将影响最大化问题转化为图的2-距离2-控制集问题。提出了一种基于独立级联模型下通过影响力传播路径快速计算节点影响力期望指标的算法，该算法可以快速计算出具有高影响力的节点。2) 考虑了节点影响力覆盖范围重叠问题，提出了基于节点相似性和二阶期望折减的影响最大化算法，使得所选种子节点集的影响传播范围可以优于现有的启发式算法。另外，针对动态网络，提出了融合社团划分和影响力期望值指标的方法。3) 在经典控制集问题的基础上构建了模糊图控制问题的数学模型，提出了计算模糊图控制集的线性规划算法和贪婪算法；引入并研究了图的2-彩虹控制稳定度的问题，刻画了具有特定稳定度值的图结构性质；通过放电规则，得到了部分格子状网络的2-彩虹控制数，刻画了其重要节点的分布。