Author(s)

HanYi Yang^1*, YiJia He²

Affiliation(s)

¹College of Cyber Security, Tarim University, Alar 843300, Xinjiang, China.

²College of Foreign Languages, Tarim University, Alar 843300, Xinjiang, China.

Corresponding Author

HanYi Yang

ABSTRACT

Aiming at the challenges of low identification accuracy and slow computation time in existing key node identification algorithms for complex networks, the paper proposes a key node identification algorithm based on local semi global triangular computation (LSTC). First, inspired by the structural stability of triangles in the physical world, the triangular patterns of nodes in complex networks and their importance are defined. Second, drawing on the third-order partition theory which highlights strong connections between a node and its third-order neighbors, the algorithm incorporates the influence of a node's local third-order neighbors when evaluating its importance. To validate the experimental performance of the proposed algorithm, the LSTC algorithm is compared with eight other algorithms of the same type using both the Susceptible–Infected–Recovered (SIR) model and the Linear Threshold (LT) model. Experimental results demonstrate that the proposed algorithm achieves the highest overall performance.

KEYWORDS

Complex network; Influential spreaders; Spreading ability; SIR epidemic model

CITE THIS PAPER

HanYi Yang, YiJia He. Key node identification algorithm based on local semi global triangle calculation. Journal of Computer Science and Electrical Engineering. 2025, 7(7): 38-48. DOI: https://doi.org/10.61784/jcsee3099.

REFERENCES

[1] Kempe D, Kleinberg J, Tardos é. Maximizing the spread of influence through a social network//Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. Washington, USA, 2023: 137-146.

[2] Wu P, Pan L. Scalable influence blocking maximization in social networks under competitive independent cascade models. Computer Networks, 2017, 123: 38-50.

[3] Leskovec J, Adamic L A, Huberman B A. The dynamics of viral marketing. ACM Transactions on the Web (TWEB), 2007, 1(1): 5-es.

[4] Freeman L C. Centrality in social networks: Conceptual clarification. Social network: critical concepts in sociology. Londres: Routledge, 2002, 1: 238-263.

[5] Lü L, Zhou T, Zhang Q M, et al. The H-index of a network node and its relation to degree and coreness. Nature communications, 2016, 7(1): 10168.

[6] Kitsak M, Gallos L K, Havlin S, et al. Identification of influential spreaders in complex networks. Nature physics, 2010, 6(11): 888-893.

[7] Wang M, Li W, Guo Y, et al. Identifying influential spreaders in complex networks based on improved k-shell method. Physica A: Statistical Mechanics and its Applications, 2020, 554: 124229.

[8] Sheikhahmadi A, Nematbakhsh M A. Identification of multi-spreader users in social networks for viral marketing. Journal of Information Science, 2017, 43(3): 412-423.

[9] Zareie A, Sheikhahmadi A, Jalili M, et al. Finding influential nodes in social networks based on neighborhood correlation coefficient. Knowledge-based systems, 2020, 194: 105580.

[10] Zhang J X, Chen D B, Dong Q, et al. Identifying a set of influential spreaders in complex networks. Scientific reports, 2016, 6(1): 27823.

[11] Guo C, Yang L, Chen X, et al. Influential nodes identification in complex networks via information entropy. Entropy, 2020, 22(2): 242.

[12] Kermack W O, McKendrick A G. A contribution to the mathematical theory of epidemics. Proceedings of the royal society of london. Series A, Containing papers of a mathematical and physical character, 1927, 115(772): 700-721.

[13] Buscarino A, Fortuna L, Frasca M, et al. Disease spreading in populations of moving agents. Europhysics Letters, 2008, 82(3): 38002.

[14] Ma L, Ma C, Zhang H F, et al. Identifying influential spreaders in complex networks based on gravity formula. Physica A: Statistical Mechanics and its Applications, 2016, 451: 205-212.

[15] Granovetter M. Threshold models of collective behavior. American journal of sociology, 1978, 83(6): 1420-1443.