Super mediator - A new centrality measure of node importance for information diffusion over social network

We propose an efficient method to discover a new type of influential nodes in a social network, which we name "super-mediators", i.e., those nodes which, if removed, decrease information spread. It is formulated mathematically as a problem of difference maximization of the average influence degree with respect to removal of a node, i.e., a node that contributes to making the difference large is influential. This definition requires use of information diffusion model for their identification and thus is "model-driven". The other definition which is more empirical is that super-mediators are those nodes that appear frequently in long diffusion sequences but much less frequently in short diffusion sequences. This definition does not require any model but does require abundant information diffusion data and thus is "data-driven". We attempt to characterize the property of super-mediators from various angles: how the resulting super-mediators are different between these two definitions and which is more reasonable, how super-mediators are compared with nodes identified by other centralities, e.g., betweenness, degree, closeness, etc., how super mediators are different from the solution of well-studied influence maximization problem, i.e., nodes capable of widely spreading information to other recipient nodes, and the solution of reverse-influence maximization problem, i.e., nodes capable of widely receiving information from other information source nodes. We conducted extensive experiments using three real world social networks. The major findings are (1) model-driven super-mediator degree has the best discrimination capability, while influence degree, reverse-influence degree, and data-driven super-mediator degree are much less discriminative (all flat for high ranked nodes), (2) model-driven super-mediators have high scores for either influence degree or reverse-influence degree, while data-driven super-mediators have high scores for both, and (3) model-driven super-mediators are closely correlated with betweenness centrality, but the strength of the correlation depends on the value of diffusion probability.