LSS: A locality-based structure system to evaluate the spreader's importance in social complex networks

Assessing the importance of spreaders in networks is crucial for investigating the survival and robustness of networks. There are numerous potential applications, such as preventing outbreaks, spreading viruses on computer networks, viral marketing, and sickness spreading. These problems are usually unable to be solved by many heuristics with low time complexity. A number of tentative heuristics have been proposed for different application scenarios. However, we still lack an efficient heuristic to solve this type of problem effectively, for instance, low rating accuracy or high time complexity. To deal with this issue, this paper proposes a new heuristic called Locality-based Structure System (LSS), which is based on local information rather than global information of nodes in a network to determine the importance of spreaders. The proposed LSS takes into account the k-shell, degree, and number of triangles in a network. First, connectivity factors are computed based on the properties of nodes connected to them. Then, each node's contribution to the importance of lines is computed. Finally, the degree and k-shell of nodes, as well as their contribution to the importance of lines, are taken into account. The proposed LSS is validated on a set of real and synthetic complex networks, where the simulation results under the standard SIR model and Kendall correlation coefficient indicate that LSS can efficiently identify influential spreaders in numerous types of networks without requiring any advanced parameter settings.

Automated summary

Assessing the importance of spreaders in networks is crucial, but existing heuristics often lack efficiency in solving this problem effectively. This paper proposes a new heuristic called LSS, which determines the importance of spreaders based on local information of nodes. LSS considers the k-shell, degree, and number of triangles in a network. It computes connectivity factors based on node properties, evaluates each node's contribution to line importance, and takes into account node degree and k-shell. The validation on real and synthetic networks shows that LSS efficiently identifies influential spreaders without advanced parameter settings.