Influence maximization (IM) is the problem of selecting a small subset of users with the aim of maximizing influence spread to help marketers in promoting their products. None of the existing ...literature considers the scenario that a marketing company wants to promote multiple products in multiple networks or a network with the different channel of interactions simultaneously. Considering this scenario, we introduce multiple influence maximization across multiple social networks (MIM2) problem. This problem considers the assumption that an influential user can accept multiple products for free and non-influential users have enough purchasing power to adopt multiple promotions from their social interactions. It is also important to consider the role of overlapping users to spread the influence across networks. To address these issues, we propose a unified framework to analyze and represent the MIM2 problem. More specifically, first, we perform a mapping to couple a set of networks into a multiplex network via direct linkage strategy. Second, we propose a heuristic method to find the most influential user over multiple product diffusion multiplex networks. Third, we prove that MIM2 problem is NP-hard and expected influence spread function is sub-modular under traditional diffusion models. Finally, the experimental results show that the advantage of proposed IM problem over existing IM problems.
•A novel MIM2 algorithm is proposed to maximize influence spread across multiple social networks.•The algorithm is self-decisive in finding the budget of each product.•The algorithm relies on multiple products and multiple networks simultaneously.•Classical Linear Threshold and Independent Cascade diffusion models are utilized.•The proposed algorithm is a trade-off between quality and efficiency.
The main purpose in influence maximization, which is motivated by the idea of viral marketing in social networks, is to find a subset of key users that maximize influence spread under a certain ...propagation model. A number of studies have been done over the past few years that try to solve this problem by considering a non-adversarial environment in which there exists only one player with no competitor. However, in real world scenarios, there is always more than one player competing with other players to influence the most nodes. This is called competitive influence maximization. Motivated by this, we try to solve the competitive influence maximization problem by proposing a new propagation model which is an extension of the Linear Threshold model and gives decision-making ability to nodes about incoming influence spread. We also propose an efficient algorithm for finding the influential nodes in a given social graph under the proposed propagation model which exploits the community structure of this graph to compute the spread of each node locally within its own community. The aim of our algorithm is to find the minimum number of seed nodes which can achieve higher spread in comparison with the spread achieved by nodes selected by other competitor. Our experiments on real world and synthetic datasets show that our approach can find influential nodes in an acceptable running time.
Influence maximization (IM) has drawn significant attention in recent years. Most existing IM methods primarily focus on homogeneous networks, and do not take into account the heterogeneity and the ...attributes of different types of nodes in heterogeneous networks. However, heterogeneous networks are ubiquitous in real world, encompassing rich semantics and complex structural information. Additionally, the clustering characteristics inherent in a network have a critical and substantial impact on the process of information diffusion, which is often overlooked in IM models designed for heterogeneous networks. To address the challenges posed by the heterogeneity and clustering structure in heterogeneous networks, we propose a novel deep learning framework based on a self-supervised clustered heterogeneous graph transformer for IM in heterogeneous networks, which we have named SCHGT-IM. SCHGT-IM aggregates the heterogeneity and clustering information in heterogeneous networks and incorporates a clustered cascade (CC) model as an information diffusion model to enhance the realism of simulations. We evaluate the performance of SCHGT-IM in comparison with that of state-of-the-art IM models using three academic heterogeneous networks extracted from the DBLP dataset. The experimental results on influence spread demonstrate that SCHGT-IM is superior to fourteen state-of-the-art algorithms and is highly effective in selecting influential seed nodes of different types from heterogeneous networks.
•A self-supervised clustered HGT method SCHGT-IM for IM on heterogeneous network is proposed.•SCHGT-IM integrates cluster information from heterogeneous networks.•SCHGT-IM includes information diffusion model, named the clustered cascade model.•SCHGT-IM outperforms fourteen state-of-the-art algorithms.
The influence maximization problem grapples with issues such as low infection rates and high time complexity. Many existing methods prove unsuitable for large-scale networks due to their time ...complexity or heavy reliance on free parameters. This paper introduces a solution to these challenges through a local heuristic that incorporates shell decomposition, node representation. This strategic approach selects candidate nodes based on their connections within network shells and topological features, effectively reducing the search space and computational overhead. The algorithm employs a deep learning-based node embedding technique to generate a low-dimensional vector for candidate nodes, calculating the dependency on spreading for each node based on local topological features. In the final phase, influential nodes are identified using results from previous phases and newly defined local features. Evaluation using the independent cascade model demonstrates the competitiveness of the proposed algorithm, highlighting its ability to deliver optimal performance in terms of solution quality. When compared to the Collective-Influence (CI) global algorithm, the presented method has a significant improvement in the differential infection rate due to its faster execution.
•Using deep learning-based node embedding technique to reduce the search space•Identifying influential nodes based on global diffusion and spreading scores•Applying autoencoder-based node embedding to learning representation graph
Recently, a new business model called online group buying is emerging into our daily lives. For example, the online business platforms provide people group-discount coupons which will be issued for ...at least k buyers grouping for a purchase. With the coupon link widely shared over the social platforms, they hope to promote people into groups to facilitate more purchases. Inspired by aforementioned real-world scenario with grouping constraint of a given minimum number of group members (κ-grouping constraint), in this paper, we analyze and model the diffusion-group behavior, and propose the κ-grouping joining influence maximization (κ-GJIM) problem. Our problem aims to choose budgeted seeds to maximize the number of κ-grouping joiners by social influence, where a κ-grouping joiner is a person who can group with at least κ−1 (κ≥2) like-mind partners. We prove that this problem is NP-hard. We also prove that the computation of objective is #P-hard and then propose an efficient method to estimate the objective. We show that κ-GJIM is a non-submodular optimization problem, and then design two algorithms to solve it. At last, the experiments based on real-world datasets show that our methods provide good strategies for maximizing the influence with κ-grouping constraint.
To meet the requirement of social influence analytics in various applications, the problem of influence maximization has been studied in recent years. The aim is to find a limited number of nodes ...(i.e., users) which can activate (i.e. influence) the maximum number of nodes in social networks. However, the community diversity of influenced users is largely ignored even though it has unique value in practice. For example, the higher community diversity reduces the risk of marketing campaigns as you should not put all your eggs in one basket; the diversity can also prolong the effect of a marketing campaign in the future promotion. Motivated by this observation, this paper investigates Community-diversified Influence Maximization (CDIM) problem to efficiently find k nodes such that, if a message is initiated and spread by the k nodes, the number as well as the community diversity of the activated nodes will be maximized at the end of propagation process. This work proposes a metric to measure the community-diversified influence and addresses a series of computational challenges. Two algorithms and an innovative CPSP-Tree index have been developed. This study also investigates the situation that community definition is not specified. The effectiveness and efficiency of the proposed solutions have been verified through extensive experimental studies on five real-world social network datasets.
•A new problem, named community-diversified influence maximization (CDIM), is introduced in this paper.•A deliberately designed metric has been proposed in this paper to evaluate the CDIM.•Two algorithms (greedy and upper bound) are developed in this paper to solve the CDIM problem effectively.
Network dismantling Braunstein, Alfredo; Dall’Asta, Luca; Semerjian, Guilhem ...
Proceedings of the National Academy of Sciences - PNAS,
11/2016, Volume:
113, Issue:
44
Journal Article
Peer reviewed
Open access
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.
•Deals with Budgeted Influence Maximization Problem.•Community-based solution approach has been proposed.•Tested with three social network datasets.•Results have been compared with other ...methodologies.
Given a social network of users with non-uniform selection cost, and a fixed budget, which nodes should be chosen for initial activation to maximize the influence in the network, such that the total selection cost does not exceed the budget? This problem is known as the Budgeted Influence Maximization Problem or BIM Problem, in short. Though the problem appears to be realistic one, there are very few studies available in the literature. In this paper, we propose ComBIM, a community-based solution approach for solving the BIM problem. The proposed methodology has four steps: first, community detection to understand the inherent structure of the social network, second, budget distribution to divide the total budget among the communities based on the number of nodes and their selection costs, third, seed selection for influence maximization and finally, budget transfer, in which unutilized budget of one community is transferred to another community. We implement the proposed methodology with three publicly available social network datasets. We have compared the obtained results with that of other methodologies from the literature and observe that ComBIM can achieve the better influence spread, while taking reasonable time for seed set selection.
Influence maximization has recently received significant attention for scheduling online campaigns or advertisements on social network platforms. However, most studies only focus on user influence ...via cyber interactions while ignoring their physical interactions which are also essential to gauge influence propagation. Additionally, targeted campaigns or advertisements have not received sufficient attention. To address these issues, we first devise a novel holistic influence diffusion model that takes into account both cyber and physical user interactions in an effective and practical way. Based on the new diffusion model, we formulate a new problem of holistic influence maximization , denoted as HIM query, for targeted advertisements in a spatial social network. The HIM query problem aims to find a minimum set of users whose holistic influence can cover all target users in the network, which belongs to a set covering problem. Since the HIM query problem is NP-hard, we develop a greedy baseline algorithm and then improve on this algorithm to reduce the computational cost. To deal with large networks, we also design a spatial-social index to maintain the social, spatial and textual information of users, as well as developing an index-based efficient solution. Finally, we conduct extensive experiments using one synthetic and three real-world datasets to validate the efficiency and effectiveness of the proposed holistic influence diffusion model and our developed algorithms.
Selecting influential users in a network is essential to spread information quickly. Identifying influential users is very useful for viral marketing and brand communication. Influence maximization ...(IM) is selecting a few influential users in the network who can maximize the influence spread. Many existing algorithms address IM in single-layer networks. However, the study of IM in multi-layer networks is gaining importance after the advancement and rapid growth in the usage of online social networks. Studying IM in multi-layer networks in the context of viral marketing will be interesting. Motivated by this, this paper investigates the K＋＋ Shell decomposition algorithm to find the k set of influential nodes (seed nodes) in a multi-layer network. The proposed model prunes the nodes based on degree and assign reward points to their neighbors. We conducted a comparative study of various IM algorithms and reported the results. We observed that the K＋＋ Shell decomposition algorithm outperforms other algorithms on various real-time datasets under various settings and environments.
PDF
