6533b851fe1ef96bd12a989e

RESEARCH PRODUCT

k-Truss Decomposition for Modular Centrality

subject

description

There is currently much interest in identifying influential spreaders in complex networks due to many applications concerned, such as controlling the outbreak of epidemics and conducting advertisements for commercial products, and so on. A plethora of centrality measures have been proposed over the years based on the topological properties of networks. However, most of these classical centrality measures fail to select the most influential nodes in networks with a modular structure despite that it is an omnipresent property in real-world networks. Few authors have introduced centrality measures tailored to networks with community structure. In a recent work, we have shown that, in this case, the centrality of a node should be represented by a two-dimensional vector. The first component quantifies the local influence of the node in its community, while the second component quantifies the global influence of the node on the communities which it is linked to. In order to compute the so-called modular centrality, one needs to know the community structure of the network. Unfortunately, in most cases, it is unknown and a community detection algorithm must be used. The majority of these algorithms are computationally intensive and sometimes they are inappropriate for large networks. In this paper, a community detection method based on the k-truss decomposition is used. Thanks to its nice structural and computational properties, it is well-adapted to large networks. Furthermore, we present a new ranking measure based on the weighted combination of both components of the modular centrality. Using the Susceptible-Infected-Recovered (SIR) model in epidemic spreading simulations, we show that substantial improvements can be gained in order to identify the influential spreaders with significantly less computational cost and complexity.