Learning automata-enabled ant colony optimization for group influence maximization in social networks: a two-stage approach

Motivated by the collective decision-making scenario, the group influence maximization (GIM) problem aims at identifying a seed user set from a social network so that the number of social network groups influenced through them, is maximized. The existing GIM algorithms are unable to balance computation speed and solution quality, which is measured in terms of group influence spread achieved. In this paper, we have proposed a two-stage algorithm called 2S-LAACO, to overcome the challenge. 2S-LAACO uses a novel heuristic named connectedness-based maximum group coverage (MGC-c) in the first stage for search space reduction and a learning automata-enabled ant colony optimization in the second stage to identify the seed set. Additionally, we have introduced a group influence spread estimation function to efficiently measure the group influence spread of a candidate seed set in 2S-LAACO. According to the experiment conducted on three real-world datasets, 2S-LAACO not only outperforms its heuristic-based competitors in terms of group influence spread but also achieves a group influence spread comparable to that of the high-performing greedy technique, despite having a lower computational cost. The experiment also demonstrates that the seed users chosen by the proposed MGC-c heuristic-based ranking alone are able to influence more groups than the existing heuristic-based algorithms with comparable time complexities.