Cut-Vertex-Based Influence Maximization Problem in Social Network

Abstract

Influence maximization problem is an important issue in social network analysis, the diversity of social network structure has continuously injected vitality into the influence maximization problem, which has been a hot issue in academic circles for nearly two decades. The research on the existing problem of influence maximization mainly focuses on the characteristics of the node, and rarely considers the influence maximization problem from the perspective of social networks connectivity. As a bridge between connected components, the cut-vertex is the core of connectivity. To this end, this paper comprehensively considers the characteristics of node and connectivity of social networks, and proposes a heuristic algorithm based on cut-vertex to solve the influence maximization problem. The algorithm uses degree and connected components to evaluate the influence of nodes, which solves the problem of overlapping influences to a certain extent. Based on the susceptible-infected-recovered model, this paper conducts related experiments on four open source datasets. In the algorithm comparison experiment, the influence maximization algorithm based on the cut-vertex performs well in terms of the running time, influence spread range and seed enrichment, which verifies the practicality and effectiveness of the algorithm.

Keywords

• |social networks|cut-vertex|influence maximization