摘要
社交网络影响最大化问题是指如何寻找网络中有限的初始节点,使得影响的传播范围最广。一些贪心算法可以得到较好的影响范围,但是因时间复杂度太高而不适用于大型社交网络。基于度中心性的启发式算法简单但准确度不高;基于介数中心性、接近中心性等全局指标的启发式算法可以较好地识别影响力最大的节点,但计算复杂度也过高。考虑网络节点深层次结构对影响扩散的作用并权衡计算复杂度与准确度,定义了3-layer局部中心度,以计算节点的潜在影响力值。基于线性阈值模型,启发选择一部分种子节点:每一次都选取潜在影响力最大的节点作为种子节点进行激活;运用贪心算法选取剩下的一部分种子节点:每一次都选取具有最大影响增量的节点作为种子节点进行激活。实验表明,该混合算法具有很好的激活范围以及非常低的时间复杂度。
Influential maximization in a social network is the problem of finding the limited initial nodes which can maxi- mize the spread of influence. Some greedy algorithms can get wide spread of influence,but have too high cost to be ap- plied in large-scale social networks. The heuristic method based on degree centrality is simple but of low accuracy. Heu- ristic algorithms based on global metrics such as hetweenness centrality and closeness centrality can better identify the most influential nodes, but the computational complexity of which is much high too. As a tradeoff between the low-accu- rate degree centrality and other time-consuming measures, we defined the 3-layer local centrality for computing the po- tential influence of nodes. Based on linear threshold model, we selected some seed nodes through the heuristic algorithm in which the node with maximal potential influence is selected at each step, and we chose another seed nodes by the greedy algorithm in which the node with the largest influence increment is chosen at each time. The experimental results show that our hybrid algorithm has good spread of influence and low time complexity.
出处
《计算机科学》
CSCD
北大核心
2014年第1期59-63,共5页
Computer Science
基金
国家自然科学基金(61272109)资助
