We focus on the \(\alpha \) -domination problem, which is capable of modeling influence phenomena in social networks. It formally asks for a minimum cardinality subset of vertices of a given graph such that any vertex is either included in this subset or at least a fraction \(\alpha \) of its neighbors is ( \(0<\alpha \le 1\) ). We address the search for solutions of high quality within a tight margin of computation time by designing, firstly, a Greedy Randomized Adaptive Search Procedure and, secondly, a Configuration Checking metaheuristic. The latter excels in terms of solution quality and speed and is able to outperform an integer programming formulation solved by the commercial solver Gurobi on a majority of tested instances which have thousands of vertices.