Explore the vast range of titles available.

Social Networks consist of nodes representing users and edges representing interaction among them. They are widely used platforms for information diffusion among various nodes, and influential nodes play a vital role in quickly spreading messages. In viral marketing, information diffusion means to spread information about products, events, and many more to achieve maximum information spread. One of the challenges of information diffusion on social networks is influence maximization, which deals with identifying an optimal number of nodes whose collective influence spread in a social network is maximum. Researchers studied it at an overall network or a community level and as a Competitive Influence Maximization problem where more than one competitor is involved in the information diffusion process. The main highlights of this survey paper are related to various concepts required to be understood in the field of information diffusion and its application in Competitive Influence Maximization. This survey paper focuses on information diffusion and its applications, major factors affecting it, and research challenges in this domain. It also covers the essential concepts of influence maximization and its different types. In addition, variants of competitive influence maximization studied by various researchers in the past two decades are also given. The survey paper also covers various information diffusion models and their extended versions for competitive scenarios, datasets used, and challenges ahead in the Competitive Influence Maximization research domain.

The top k-influencers problem, as a social influence maximization (SIM) problem, seeks out the best k actors, called the seed set, in a network with the greatest expected Influence Spread (IS). This problem is formulated as a mean-maximization of the IS with no consideration for the variance of the IS. Consequently, it is a risk-blind influence maximization (RBIM) problem. The variance minimization problem has a considerable tendency toward trivial solutions in the absence of a known exogenous threshold of the IS, which makes the formulation ineffective. As an alternative strategy to overcome the trivial solution challenge, risk-averse influence maximization (RAIM) is being investigated and compared empirically with RBIM based on theoretical findings from the literature. RAIM searches for the best k actors under a known diffusion process, whose conditional value-at-risk (CVaR) measure of the IS is maximized. RAIM lacks an approximation algorithm due to the absence of a proven submodularity feature for CVaR. Moreover, no metaheuristic framework was tuned under all of the IC, WC, LT, and TR diffusion models, despite numerous algorithmic contributions to RBIM. Thus, a Genetic Algorithm Framework for Influence Maximization (GAFIM) is proposed by drawing inspiration from the genetic algorithms proposed for RBIM but under all of the IC, WC, LT, and TR diffusion models. A novel approach to tuning GAFIM has been developed employing a community detection algorithm and applied to RAIM and RBIM. Based on the tuning results, the seed set size has a remarkable effect on GAFIM’s performance and highlights its superiority over the algorithms it was inspired by. Furthermore, a comparison to the closest genetic algorithm published in the literature demonstrates that GAFIM outperforms it by a factor of at least 20 in terms of efficiency while achieving a higher quality result. Having completed the quality investigation of GAFIM with satisfactory results, the comparison experiments support intriguing distinctions between RAIM and RBIM in the dominance factor, dominance rate, and dominance mutuality. The variance of the IS and the propagation time/median of the IS prepare the dominance factor(s) for RAIM/RBIM. According to the results, the significant dominance rates (48% vs. 65%), the unreciprocated dominance pattern in dominating the other problem in its dominance area (66% vs. 91%), the complete dominance pattern in dominating without being dominated (9% vs. 34%), and being nondominated (35% vs. 52%) are not as probable for RBIM as for RAIM.

Background The process of rumor spreading among people can be represented as information diffusion in social network. The scale of rumor spread changes greatly depending on starting nodes. If we can select nodes that contribute to large-scale diffusion, the nodes are expected to be important for viral marketing. Given a network and the size of the starting nodes, the problem of selecting nodes for maximizing information diffusion is called influence maximization problem. Methods We propose three new approximation methods (Dynamic Degree Discount, Dynamic CI, and Dynamic RIS) for influence maximization problem in dynamic networks. These methods are the extensions of previous methods for static networks to dynamic networks. Results When compared with the previous methods, MC Greedy and Osawa, our proposed methods were found better than the previous methods: Although the performance of MC greedy was better than the three methods, it was computationally expensive and intractable for large-scale networks. The computational time of our proposed methods was more than 10 times faster than MC greedy, so they can be computed in realistic time even for large-scale dynamic networks. When compared with Osawa, the performances of these three methods were almost the same as Osawa, but they were approximately 7.8 times faster than Osawa. Conclusions Based on these facts, the proposed methods are suitable for influence maximization in dynamic networks. Finding the strategies of choosing a suitable method for a given dynamic network is practically important. It is a challenging open question and is left for our future work. The problem of adjusting the parameters for Dynamic CI and Dynamic RIS is also left for our future work.

Given a social network with diffusion probabilities as edge weights and a positive integer k, which k nodes should be chosen for initial injection of information to maximize the influence in the network? This problem is popularly known as the Social Influence Maximization Problem (SIM Problem). This is an active area of research in computational social network analysis domain, since one and half decades or so. Due to its practical importance in various domains, such as viral marketing, target advertisement and personalized recommendation, the problem has been studied in different variants, and different solution methodologies have been proposed over the years. This paper presents a survey on the progress in and around SIM Problem. At last, it discusses current research trends and future research directions as well.

We study the network dismantling problem, which consists of determining a minimal set of vertices in which removal leaves the network broken into connected components of subextensive size. For a large class of random graphs, this problem is tightly connected to the decycling problem (the removal of vertices, leaving the graph acyclic). Exploiting this connection and recent works on epidemic spreading, we present precise predictions for the minimal size of a dismantling set in a large random graph with a prescribed (light-tailed) degree distribution. Building on the statistical mechanics perspective, we propose a three-stage Min-Sum algorithm for efficiently dismantling networks, including heavy-tailed ones for which the dismantling and decycling problems are not equivalent. We also provide additional insights into the dismantling problem, concluding that it is an intrinsically collective problem and that optimal dismantling sets cannot be viewed as a collection of individually well-performing nodes.

The effective use of limited resources for controlling spreading processes on networks is of prime significance in diverse contexts, ranging from the identification of “influential spreaders” for maximizing information dissemination and targeted interventions in regulatory networks, to the development of mitigation policies for infectious diseases and financial contagion in economic systems. Solutions for these optimization tasks that are based purely on topological arguments are not fully satisfactory; in realistic settings, the problem is often characterized by heterogeneous interactions and requires interventions in a dynamic fashion over a finite time window via a restricted set of controllable nodes. The optimal distribution of available resources hence results from an interplay between network topology and spreading dynamics. We show how these problems can be addressed as particular instances of a universal analytical framework based on a scalable dynamic message-passing approach and demonstrate the efficacy of the method on a variety of real-world examples.

Derived from the idea of word-to-mouth advertising and with applying information diffusion theory, viral marketing attracts wide research interests because of its business value. As an effective marketing strategy, viral marketing is to select a small set of initial users based on trust among close social circles of friends or families so as to maximize the spread of influence in the social network. In this paper, we propose a new community-based influence maximization method for viral marketing that integrates community detection into influence diffusion modeling, instead of performing community detection independently, to improve the performance. We first build a comprehensive latent variable model which captures community-level topic interest, item-topic relevance and community membership distribution of each user, and we propose a collapsed Gibbs sampling algorithm to train the model. Then we infer community-to-community influence strength using topic-irrelevant influence and community topic interest, and further infer user-to-user influence strength using community-to-community influence strength and community membership distribution of each user. Finally we propose a community-based heuristic algorithm to mine influential nodes that selects the influential nodes with a divide-and-conquer strategy, considering both topic-aware and community-relevant to enhance quality and improve efficiency. Extensive experiments are conducted to evaluate effectiveness and efficiency of our proposals. The results validate our ideas and show the superiority of our method compared with state-of-the-art influence maximization algorithms.

Influence maximization, defined by Kempe et al. (SIGKDD 2003 ), is the problem of finding a small set of seed nodes in a social network that maximizes the spread of influence under certain influence cascade models. The scalability of influence maximization is a key factor for enabling prevalent viral marketing in large-scale online social networks. Prior solutions, such as the greedy algorithm of Kempe et al. (SIGKDD 2003 ) and its improvements are slow and not scalable, while other heuristic algorithms do not provide consistently good performance on influence spreads. In this article, we design a new heuristic algorithm that is easily scalable to millions of nodes and edges in our experiments. Our algorithm has a simple tunable parameter for users to control the balance between the running time and the influence spread of the algorithm. Our results from extensive simulations on several real-world and synthetic networks demonstrate that our algorithm is currently the best scalable solution to the influence maximization problem: (a) our algorithm scales beyond million-sized graphs where the greedy algorithm becomes infeasible, and (b) in all size ranges, our algorithm performs consistently well in influence spread—it is always among the best algorithms, and in most cases it significantly outperforms all other scalable heuristics to as much as 100–260% increase in influence spread.

In recent years, with the rapid development of online social networks, an enormous amount of information has been generated and diffused by human interactions through online social networks. The availability of information diffused by users of online social networks has facilitated the investigation of information diffusion and influence maximization. In this paper, we focus on the influence maximization problem in social networks, which refers to the identification of a small subset of target nodes for maximizing the spread of influence under a given diffusion model. We first propose a learning automaton-based algorithm for solving the minimum positive influence dominating set (MPIDS) problem, and then use the MPIDS for influence maximization in online social networks. We also prove that by proper choice of the parameters of the algorithm, the probability of finding the MPIDS can be made as close to unity as possible. Experimental simulations on real and synthetic networks confirm the superiority of the algorithm for finding the MPIDS Experimental results also show that finding initial target seeds for influence maximization using the MPIDS outperforms well-known existing algorithms.

Motivated by the application of viral marketing , the topic-aware influence maximization (TIM) problem has been proposed to identify the most influential users under given topics. In particular, it aims to find k seeds (users) in social network G , such that the seeds can maximize the influence on users under the specific query topics and diffusion model such as independent cascade (IC) or linear threshold (LT). This problem has been proved to be NP-hard, and most of the proposed techniques suffer from the efficiency issue due to the lack of generalization. Even worse, the design of these algorithms requires significant specialized knowledge which is hard to be understood and implemented. To overcome these issues, this paper aims to learn a generalized heuristic framework to solve TIM problems by meta-learning. To this end, we first propose two topic-aware social influence propagation models based on IC and LT model, respectively, which is conducive to better advertising injections. We then encode the feature of each node by a vector and introduce a model, called deep influence evaluation model , to evaluate the user influence under different circumstances. Based on this model, we can construct the solution according to the influence evaluations efficiently, rather than spending a high cost to compute the exact influence by considering the complex graph structure. We conducted experiments on generated graph instances and real-world social networks. The results show the superiority in performance and comparable quality of our framework.