Algorithms for Finding Influential Nodes in Complex Networks Using Centrality Measures

Abstract

This thesis report focuses on algorithms for locating influential nodes in complex networks newlineby centrality measures. In complex networks, locating the seed nodes is essential newlinefor understanding information diffusion dynamics, with applications in various newlinedomains such as disease research, rumor control, social leadership, viral marketing, newlineand opinion tracking. The presence of seed nodes has the capacity to efficiently disseminate newlineinformation throughout most networks. Numerous centrality measures, including newlinedegree, betweenness, closeness, semi-local, clustering coefficient, PageRank, newlinetrust PageRank, and isolating centrality, have been proposed by researchers to compute newlineinfluential nodes in complex networks using regional and/or global data. However, newlinecentrality measures relying on high time complexity render global information newlineunsuitable for large-scale networks. Furthermore, the network structure is often overlooked newlineby most centrality measures, along with the attributes between nodes. newlineTo address these limitations, this thesis proposes the nearest neighborhood trust PageRank newline(NTPR) centrality measure according to the structural characteristics of node neighbors newlineand nearest neighbors. NTPR incorporates the degree ratio, node similarity, trust newlinevalue of neighbors, and nearest neighbors to determine influential nodes. Different newlinenetworks were used to evaluate the proposed centrality NTPR, where in the maximum newlineinfluence was calculated by leveraging influential nodes through SIR and independent newlinecascade models. newlineFurthermore, this thesis introduces mixed centrality measures that combine local and newlineglobal network structures. A generalized measure incorporating degree, the shortest newlinepath between vertices, and any global centrality has been introduced, enabling the newlineutilization of any measure defined based on the global structure of a network. Furthermore, newlinea measure called Local RASP (Local Relative Change of Average Shortest newlinePath) is introduced, which quantifies the relative change in the average shortest path newlineof a local network