More Web Proxy on the site http://driver.im/

research-article

Finding robust and influential nodes from networks under cascading failures using a memetic algorithm

Authors:

Minghao ChenAuthors Info & Claims

Volume 589, Issue C

https://doi.org/10.1016/j.neucom.2024.127704

Published: 17 July 2024 Publication History

Abstract

In the research of complex networks, how to find a set of nodes in the network with the most extensive range in the propagation process, i.e., the Influence Maximization (IM) problem, is one of the focal topics. Existing studies mainly consider the information dissemination process on networks and how to select diffusive nodes efficiently, but little attention has been paid to changes related to the network structure. In reality, networked systems are exposed to uncertain interferences and even destructive sabotages, and cascading failures are one common destruction that can cause networks to collapse even if only a small number of nodes fail. In the case of various complex environmental factors, how to select robust and influential nodes, i.e., the robust influence maximization (RIM) problem, is of great importance in promoting the realistic application of the influence maximization problem. This paper investigates the RIM problem under cascading failures to address the shortcomings in previous studies. Based on existing research, a new performance evaluation metric, R _S-cf, is designed to assess the level of robust influence in a numerical form. For solving the seed determination problem, a Memetic algorithm towards the RIM problem under cascading failures, MA-RIM_CF, is designed to find nodes with stable information propagation capability guided by R _S-cf. Experiments have been conducted on both synthetic and realistic networks to validate the performance of the algorithm. Results indicate that MA-RIM_CF can obtain competitive candidates over existing approaches, and seeds with robust and influential abilities are generated to solve diffusion dilemmas.

References

[1]

R. Albert, A.L. Barabási, Statistical mechanics of complex networks, Rev. Mod. Phys. 74 (1) (2002) 47–97.

[2]

S. Boccaletti, V. Latora, Y. Moreno, Complex networks: structure and dynamics, Phys. Rep. 424 (4-5) (2006) 175–308.

[3]

P. Erdős, A. Rényi, On the evolution of random graph, Publ. Math. Inst. Hung. Acad. Sci. 5 (1960) 17–61.

[4]

S.H. Strogatz, Exploring complex networks, Nature 410 (6825) (2001) 268–276.

[5]

A.L. Barabási, R. Albert, Emergence of scaling in random networks, Science 286 (1999) 509–512.

[6]

X.F. Wang, G. Chen, Complex networks: small-world, scale-free and beyond, IEEE Circuits Syst. Mag. 3 (1) (2003) 6–20.

[7]

M.E.J. Newman, The structure and function of complex networks, SIAM Rev. 45 (2) (2003) 167–256.

Digital Library

[8]

D.J. Watts, S.H. Strogatz, Collective dynamics of small-world networks, Nature 393 (6638) (1998) 440–442.

[9]

A.L. Barabási, E. Bonabeau, Scale-free networks, Sci. Am. 288 (5) (2003) 60–69.

[10]

M.E.J. Newman, Assortative mixing in networks, Phys. Rev. Lett. 89 (20) (2002).

[11]

M.E.J. Newman, M. Girvan, Finding and evaluating community structure in networks, Phys. Rev. E 69 (2004).

[12]

L.F. Costa, J.O.N. Oliveira, G. Travieso, F.A. Rodrigues, P.R.V. Boas, Analyzing and modeling real-world phenomena with complex networks: a survey of applications, Adv. Phys. 60 (3) (2011) 329–412.

[13]

R.M. Bond, C.J. Fariss, J.J. Jones, A. Krame, C. Marlow, J. Settle, A 61-million-person experiment in social influence and political mobilization, Nature 489 (7415) (2012) 295–298.

[14]

M. Grassi, E. Cambria, A. Hussain, F. Piazza, Sentic web: A new paradigm for managing social media affective information, Cogn. Comput. 3 (2011) 480–489.

[15]

W. Chen, Y. Wang, S. Yang, Efficient influence maximization in social networks, in: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2009, pp. 199-208.

[16]

P. Domingos, M. Richardson, Mining the network value of customers, in: Proceedings of the seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2001, pp. 57-66.

[17]

M. Azaouzi, W. Mnasri, L.B. Romdhane, New trends in influence maximization models, Comput. Sci. Rev. 40 (2021).

[18]

D. Kempe, J. Kleinberg, E. Tardos, Maximizing the spread of influence through a social network, In: Proceedings of the ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2003, pp. 137-146.

[19]

F. Gursoy, D. Gunnec, Influence maximization in social networks under deterministic linear threshold model, Knowl. -Based Syst. 161 (2018) 111–123.

[20]

J.R. Lee, C.W. Chung, A fast approximation for influence maximization in large social networks, in: Proceedings of the 23rd International Conference on World Wide Web. 2014: 1157-1162.

[21]

M. Gong, C. Song, C. Duan, L.J. Ma, B. Shen, An efficient memetic algorithm for influence maximization in social networks, IEEE Comput. Intell. Mag. 11 (3) (2016) 22–33.

[22]

G. Wu, X. Gao, G. Yan, G. Chen, Parallel greedy algorithm to multiple influence maximization in social network, ACM Trans. Knowl. Discov. Data 15 (3) (2021) 1–21.

[23]

N. Sumith, B. Annappa, S. Bhattacharya, Influence maximization in large social networks: Heuristics, models and parameters, Future Gener. Comput. Syst. 89 (2018) 777–790.

[24]

L. Ma, J. Li, Q. Lin, Reliable link inference for network data with community structures, IEEE Trans. Cybern. 49 (9) (2018) 3347–3361.

[25]

M.N. Al-Andoli, S. Tan, W.P. Cheah, Distributed parallel deep learning with a hybrid backpropagation-particle swarm optimization for community detection in large complex networks, Inf. Sci. 600 (2022) 94–117.

Digital Library

[26]

L. Ma, M. Huang, S. Yang, An adaptive localized decision variable analysis approach to large-scale multiobjective and many-objective optimization, IEEE Trans. Cybern. 52 (7) (2021) 6684–6696.

[27]

M. Gong, J. Yan, B. Shen, J. Ma, Q. Cai, Influence maximization in social networks based on discrete particle swarm optimization, Inform. Sci. 367 (2016) 600–614.

Digital Library

[28]

S. Wang, X. Tan, A Memetic algorithm for determining robust and influential seeds against structural perturbances in competitive networks, Inform. Sci. 621 (2023) 389–406.

[29]

M. Yang, X. Wang, M. Huang, A novel evolutionary algorithm based on judgment-rule evolution strategy for structural balance in signed social networks, IEEE Trans. Emerg. Top. Comput. Intell. 6 (4) (2021) 805–817.

[30]

P. Holme, B.J. Kim, C.N. Yoon, S.K. Han, Attack vulnerability of complex networks, Phys. Rev. E 65 (5) (2002).

[31]

S. Wang, J. Liu, Y. Jin, Finding influential nodes in multiplex networks using a memetic algorithm, IEEE Trans. Cybern. 51 (2) (2019) 900–912.

[32]

L. Ma, Z. Shao, X. Li, Influence maximization in complex networks by using evolutionary deep reinforcement learning, IEEE Trans. Emerg. Top. Comput. Intell. 6 (1) (2022) 136–149.

[33]

X. He, D. Kempe, Stability and robustness in influence maximization, ACM Trans. Knowl. Discov. Data 12 (6) (2018) 1–34.

[34]

Y. Gong, S. Liu, Y. Bai, Efficient parallel computing on the game theory-aware robust influence maximization problem, Knowl. -Based Syst. 220 (2021).

[35]

W. Chen, T. Lin, Z. Tan, M. Zhao, X. Zhou, Robust influence maximization, in: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016, pp. 795-804.

[36]

S. Wang, J. Liu, A memetic algorithm for solving the robust influence maximization problem toward network structural perturbances, Chin. J. Comput. 44 (6) (2021) 1153–1167. ([In Chinese, English abstract]).

[37]

S. Wang, J. Liu, Enhancing the robustness of complex networks against edge-based-attack cascading failures, IEEE Congr. Evolut. Comput. (2017) 23–28.

[38]

A.E. Motter, Cascade control and defense in complex networks, Phys. Rev. Lett. 93 (9) (2004).

[39]

A.E. Motter, Y.C. Lai, Cascade-based attacks on complex networks, Phys. Rev. E 66 (6) (2002).

[40]

C. Wang, J. Zhao, L. Li, L. Jiao, J. Liu, K. Wu, A multi-transformation evolutionary framework for influence maximization in social networks, IEEE Comput. Intell. Mag. 18 (1) (2023) 52–67.

[41]

J. Shang, S. Zhou, X. Li, L. Liu, H. Wu, CoFIM: a community-based framework for influence maximization on large-scale networks, Knowl. -Based Syst. 117 (2017) 88–100.

Digital Library

[42]

S. Wang, X. Tan, Finding robust influential seeds from networked systems against structural failures using a niching memetic algorithm, Appl. Soft Comput. (2023).

[43]

P. Crucitti, V. Latora, M. Marchiori, Model for cascading failures in complex networks, Phys. Rev. E 69 (4) (2004).

[44]

K. Zhang, H. Du, M.W. Feldman, Maximizing influence in a social network: improved results using a genetic algorithm, Phys. A 478 (2017) 20–30.

[45]

Q. Jiang, G. Song, C. Gao, Y. Wang, W. Si, K. Xie, Simulated annealing based influence maximization in social networks, in: Proceedings of the AAAI Conference on Artificial Intelligence, 25 (1) (2011) 127-132.

[46]

A.M. Farid, Symmetrica: Test case for transportation electrification research, Infrastruct. Complex. 2 (2015) 1–10.

[47]

S. Cai, S. Wang, Z. Ou, A Memetic Algorithm to solve the Robust Influence Maximization Problems against Cascading Failures, in: Proceedings of the Companion Conference on Genetic and Evolutionary Computation, 2023, pp. 119-122.

Cited By

Recommendations

Constructing Robust and Influential Networks Against Cascading Failures via a Multi-objective Evolutionary Algorithm
Advances in Swarm Intelligence
Abstract
The influence maximization problem and robustness optimization of networks are hot-spots in the current research. Existing studies have rather investigated the problems of network robustness optimization or influence maximization separately, ...
Towards identifying influential nodes in complex networks using semi-local centrality metrics
Abstract
The influence of the node refers to the ability of the node to disseminate information. The faster and wider the node spreads, the greater its influence. There are many classical topological metrics that can be used to evaluate the influencing ...
Finding robust influential seeds from networked systems against structural failures using a niching memetic algorithm
Abstract
There has been a growing interest in analyzing the dynamics and characteristics of networked systems, and the influence maximization problem is a recent hotspot to determine influential seeds from nodal members. Widespread applicable ...
Highlights
- The robustness of the influence diffusion process against node-based attacks has been investigated and evaluated.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Neurocomputing

Neurocomputing Volume 589, Issue C

Jul 2024

191 pages

Issue’s Table of Contents

Elsevier B.V.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 17 July 2024

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents