A Novel Triangle Count-Based Influence Maximization Method on Social Networks

Introduction

Online social networks (OSNs) such as Twitter, Facebook, and LinkedIn have revolutionized the way people communicate, share, and propagate information. Billions of people worldwide are connected on a single platform through social media that allow rapid information spreading as well as influence individuals on decision making. Recently, OSNs have become an effective platform that provides services such as marketing products and services, brand building, opinion generation, and business promotion (Saggu & Sinha, 2020). One of the important advantages of social media marketing (Tanantong & Ramjan, 2021) is that it helps organizations to communicate with people directly. This direct communication will help companies to strengthen their relationship with people, which helps future business development. In addition, since the individuals in social media are connected with their friends and family, individuals' opinions about a company or a product may influence his/her friends and families, which ultimately helps maximize revenue.

Realizing the potential applications of ONSs in business, identifying a small set of influential individuals has received significant attention. It is formally called the influence maximization (IM) problem. The chosen influential nodes must produce maximal influence spread under a given diffusion model (Li Y. et al., 2018). Viral marketing (Leskovec et al., 2007a; Saggu & Sinha, 2020), recommender systems (Bansal & Baliyan, 2019; Verma et al., 2021; Le et al., 2021), information monitoring, and rumor and epidemic control (Wu & Pan, 2017) are its popular applications. The influence maximization primarily aims to achieve the word-of-mouth effect (Trusov et al., 2009) to influence maximum users from a set of influential users. However, the main problem of influence maximization is how to select the top-k most influential users, also called seed set, in a network so that the product will attain the maximum attention.

Considering influence maximization as an algorithmic problem, Domingos and Richardson (2001) proposed a probabilistic solution utilizing the Markov random field. Assuming IM is an optimization problem, Kempe et al. (2003) presented a greedy hill-climbing method and proved that the problem is NP-hard, and the objective function is submodular. The proposed solution guarantees a near-optimal solution within (1-1/e) of the optimal influence spread. Despite the optimal solution, the number of Monte Carlo simulations required for this greedy algorithm significantly increases the computational time and reduces its scope on large networks.

Many methods have been proposed in the last decade to improve the effectiveness and efficiency of the IM problem. Those methods can be classified into submodularity-based greedy approaches (Leskovec et al., 2007b), centrality-based heuristic approaches (Tang J. et al., 2018), influence-path-based approaches (Rossi et al., 2018), and reverse reachable set-based approaches (Borgs et al., 2014). However, one of the major drawbacks of those methods is that the effect of community structure in networks is received less attention, which can severely affect the influence spreading. Community structure is a significant property of real-world complex networks. Community structures represent dense regions, which signify highly interconnected nodes in the network (Girvan & Newman, 2002; Fortunato & Hric, 2016). Recent studies underline that the presence of community structure significantly affects the effectiveness of IM methods (Shang et al., 2015; Stegehuis et al., 2016).