在影响力最大化问题中,现有的基于贪婪和网络结构中心性的方法难以在准确度和时间复杂度之间取得平衡。针对已有算法的局限性,提出了一种改进的正余弦优化搜索的影响力最大化算法DSCA。该方法考虑了节点二跳邻居,结合优化算法的位置更新概念与动态小范围搜索对单个节点进行细致优化。使用正余弦搜索与对齐、突变算子在排序的基础上进行节点搜索。在4个网络上的实验表明,方法较先前的基准方法传播范围更广、时间复杂度更低,证明了该算法的优越性和准确性。
In the influence maximization problem, existing methods based on greed and the centrality of network structure are difficult to strike a balance between accuracy and time complexity. Aiming at the limitations of existing algorithms, an improved sine-cosine optimization search influence maximization algorithm DSCA is proposed. This method takes into account the two-hop neighbors of nodes, and combines the position update concept of the optimization algorithm with dynamic small-range search to optimize a single node. The sine-cosine search, alignment and mutation operators are used to search nodes based on ordering. Experiments on four networks show that the proposed method has wider propagation range and lower time complexity than the advanced benchmark method, which proves the superiority and accuracy of the proposed algorithm.
[1] Kempe D, Kleinberg J, Tardos E. Maximizing the spread of influence through a social network[C]. The 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2003: 137-146.
[2] Li W, Li Y, Liu W, et al. An influence maximization method based on crowd emotion under an emotion-based attribute social network[J]. Information Processing & Management, 2022, 59(2): 102818.
[3] Leskovec J, Krause A, Guestrin C, et al. Cost-effective outbreak detection in networks[C]. Proceedings of The 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Jose California, USA: ACM, 2007: 420-429.
[4] Guo C, Yang L, Chen X, et al. Influential nodes identification in complex networks via information entropy[J]. Entropy, 2020, 22(2): 242.
[5] Wang Z, Sun C, Xi J, et al. Influence maximization in social graphs based on community structure and node coverage gain[J]. Future Generation Computer Systems, 2021, 118: 327-338.
[6] Alshahrani M, Fuxi Z, Sameh A, et al. Efficient algorithms based on centrality measures for identification of top-K influential users in social networks[J]. Information Sciences, 2020, 527: 88-107.
[7] Liu P, Li L, Fang S, et al. Identifying influential nodes in social networks: a voting approach[J]. Chaos, Solitons & Fractals, 2021, 152: 111309.
[8] Zareie A, Sheikhahmadi A, Jalili M, et al. Finding influential nodes in social networks based on neighborhood correlation coefficient[J]. Knowledge-Based Systems, 2020, 194: 105580.
[9] Sun P G, Miao Q, Staab S. Community-based k-shell decomposition for identifying influential spreaders[J]. Pattern Recognition, 2021, 120: 108130.
[10] Wang S, Liu J, Jin Y. Finding influential nodes in multiplex networks using a memetic algorithm[J]. IEEE Transactions on Cybernetics, 2021, 51(2): 900-912.
[11] Cui L, Hu H, Yu S, et al. DDSE: a novel evolutionary algorithm based on degree-descending search strategy for influence maximization in social networks[J]. Journal of Network and Computer Applications, 2018, 103: 119-130.
[12] Gong M, Yan J, Shen B, et al. Influence maximization in social networks based on discrete particle swarm optimization[J]. Information Sciences, 2016, 367-368: 600-614.
[13] Mirjalili S. SCA: A sine cosine algorithm for solving optimization problems[J]. Knowledge-Based Systems, 2016, 96: 120-133.
[14] Domingos P, Richardson M. Mining the network value of customers[C]. Proceedings of The 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2001: 57-66.
[15] Qiu L, Tian X, Zhang J, et al. LIDDE: A differential evolution algorithm based on local-influence-descending search strategy for influence maximization in social networks[J]. Journal of Network and Computer Applications, 2021, 178: 102973.
[16] Singh S S, Kumar A, Singh K, et al. LAPSO-IM: a learning-based influence maximization approach for social networks[J]. Applied Soft Computing, 2019, 82: 105554.
[17] Kianian S, Rostamnia M. An efficient path-based approach for influence maximization in social networks[J]. Expert Systems with Applications, 2021, 167: 114168.
[18] Jiang Q, Song G, Cong G, et al. Simulated annealing based influence maximization in social networks[C]. Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence. San Francisco, California, USA: AAAI Press, 2011: 127-132.
[19] Biswas T K, Abbasi A, Chakrabortty R K. An MCDM integrated adaptive simulated annealing approach for influence maximization in social networks[J]. Information Sciences, 2021, 556: 27-48.
[20] Wang L, Ma L, Wang C, et al. Identifying influential spreaders in social networks through discrete moth-flame optimization[J]. IEEE Transactions on Evolutionary Computation, 2021, 25(6): 1091-1102.
