MEBC: social network immunization via motif-based edge-betweenness centrality

摘要

Immunization of social networks has attracted increasing attention over the last decade. Various algorithms have been proposed based on the topological structure of networks, such as the degree and betweenness of nodes. However, most of these studies have only observed the basic topological structure at the level of individual nodes, ignoring higher-order structures captured by network motifs, which may lead to insufficient performance. Besides, immunization based on the connectivity pattern of nodes such as the degree in a social network may cause integrity problems and also interfere in other users’ regular activities because the absence of the hub nodes can greatly impair the connectivity of the network. Thus, we introduce the edge-betweenness as a metric of social network immunization that is much more effective than other traditional measures and reflects the significant role that edges play in reducing the damage and cost of the immunizing process. In this paper, a new network immunization algorithm is proposed by combining higher-order structures and edge-betweenness to select an edge set to be immunized. We conduct extensive experiments on real-world networks to show that the new algorithm can significantly improve the effectiveness of the immunization and reduce the impact of the structure of the network.