Influence maximization of temporal social networks(IMT)is a problem that aims to find the most influential set of nodes in the temporal network so that their information can be the most widely spread.To solve the IMT ...Influence maximization of temporal social networks(IMT)is a problem that aims to find the most influential set of nodes in the temporal network so that their information can be the most widely spread.To solve the IMT problem,we propose an influence maximization algorithm based on an improved K-shell method,namely improved K-shell in temporal social networks(KT).The algorithm takes into account the global and local structures of temporal social networks.First,to obtain the kernel value Ks of each node,in the global scope,it layers the network according to the temporal characteristic of nodes by improving the K-shell method.Then,in the local scope,the calculation method of comprehensive degree is proposed to weigh the influence of nodes.Finally,the node with the highest comprehensive degree in each core layer is selected as the seed.However,the seed selection strategy of KT can easily lose some influential nodes.Thus,by optimizing the seed selection strategy,this paper proposes an efficient heuristic algorithm called improved K-shell in temporal social networks for influence maximization(KTIM).According to the hierarchical distribution of cores,the algorithm adds nodes near the central core to the candidate seed set.It then searches for seeds in the candidate seed set according to the comprehensive degree.Experiments showthatKTIMis close to the best performing improved method for influence maximization of temporal graph(IMIT)algorithm in terms of effectiveness,but runs at least an order of magnitude faster than it.Therefore,considering the effectiveness and efficiency simultaneously in temporal social networks,the KTIM algorithm works better than other baseline algorithms.展开更多
复杂网络中,评估节点的重要性对于研究网络结构和传播过程有着重要意义.通过节点的位置,K-shell分解算法能够很好地识别关键节点,但是这种算法导致很多节点具有相同的K-shell(Ks)值.同时,现有的算法大都只考虑局部指标或者全局指标,导...复杂网络中,评估节点的重要性对于研究网络结构和传播过程有着重要意义.通过节点的位置,K-shell分解算法能够很好地识别关键节点,但是这种算法导致很多节点具有相同的K-shell(Ks)值.同时,现有的算法大都只考虑局部指标或者全局指标,导致评判节点重要性的因素单一.为了更好地识别关键节点,提出了EKSDN(Extended K-shell and Degree of Neighbors)算法,该算法综合考虑了节点的全局指标加权核值以及节点的局部指标度数.与SIR(Susceptible-Infectious-Recovered)模型在真实复杂网络中模拟结果相比,EKSDN算法能够更好地识别关键节点.展开更多
基金Thiswork is supported by theYouth Science and Technology Innovation Personnel Training Project of Heilongjiang(No.UNPYSCT-2020072)the FundamentalResearch Funds for the Universities of Heilongjiang(Nos.145109217,135509234)+1 种基金the Education Science Fourteenth Five-Year Plan 2021 Project of Heilongjiang(No.GJB1421344)the Innovative Research Projects for Postgraduates of Qiqihar University(No.YJSCX2022048).
文摘Influence maximization of temporal social networks(IMT)is a problem that aims to find the most influential set of nodes in the temporal network so that their information can be the most widely spread.To solve the IMT problem,we propose an influence maximization algorithm based on an improved K-shell method,namely improved K-shell in temporal social networks(KT).The algorithm takes into account the global and local structures of temporal social networks.First,to obtain the kernel value Ks of each node,in the global scope,it layers the network according to the temporal characteristic of nodes by improving the K-shell method.Then,in the local scope,the calculation method of comprehensive degree is proposed to weigh the influence of nodes.Finally,the node with the highest comprehensive degree in each core layer is selected as the seed.However,the seed selection strategy of KT can easily lose some influential nodes.Thus,by optimizing the seed selection strategy,this paper proposes an efficient heuristic algorithm called improved K-shell in temporal social networks for influence maximization(KTIM).According to the hierarchical distribution of cores,the algorithm adds nodes near the central core to the candidate seed set.It then searches for seeds in the candidate seed set according to the comprehensive degree.Experiments showthatKTIMis close to the best performing improved method for influence maximization of temporal graph(IMIT)algorithm in terms of effectiveness,but runs at least an order of magnitude faster than it.Therefore,considering the effectiveness and efficiency simultaneously in temporal social networks,the KTIM algorithm works better than other baseline algorithms.
文摘复杂网络中,评估节点的重要性对于研究网络结构和传播过程有着重要意义.通过节点的位置,K-shell分解算法能够很好地识别关键节点,但是这种算法导致很多节点具有相同的K-shell(Ks)值.同时,现有的算法大都只考虑局部指标或者全局指标,导致评判节点重要性的因素单一.为了更好地识别关键节点,提出了EKSDN(Extended K-shell and Degree of Neighbors)算法,该算法综合考虑了节点的全局指标加权核值以及节点的局部指标度数.与SIR(Susceptible-Infectious-Recovered)模型在真实复杂网络中模拟结果相比,EKSDN算法能够更好地识别关键节点.
