Identifying influential nodes in social networks via improved Laplacian centrality

Identifying influential nodes in social networks has significant applications in terms of social analysis and information dissemination. How to capture the crucial features of influential nodes without increasing the computational complexity is an urgent issue to be solved in the context of big data. Laplacian centrality (LC) measures nodal influence by computing nodes' degree, making it extremely low complexity. However, there is still significant room for improvement. Consequently, we propose the improved Laplacian centrality (ILC) to identify influential nodes based on the concept of self-consistent. Identifying results on 9 real networks prove that ILC is superior to LC and other 6 classical measures in terms of ranking accuracy, top-k nodes identification and discrimination capability. Moreover, the computational complexity of ILC has not significantly increased compared to LC, and remains the linear order of magnitude O(m). Additionally, ILC has excellent robustness and universality such that there is no need to adjust parameters according to different network structures. • The improved Laplacian centrality is suitable for large-scale data since it has a linear computational complexity. • ILC outperforms LC and many existing measures in ranking accuracy, top-k node identification, and discrimination capability. • ILC has excellent robustness and universality, there is no need to adjust parameters according to different networks.