A Reverse Reachable Set Based Approach for Motif Oriented Profit maximization in Social Networks
Poonam Sharma, Suman Banerjee · 2025
Read A Reverse Reachable Set Based Approach for Motif Oriented Profit maximization in Social Networks by Poonam Sharma, Suman Banerjee (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-19237.txt.
Introduction
Poonam Sharma and Suman Banerjee reframe social marketing profit around motifs, the small recurring patterns inside a network. Classic profit maximization picks seed users whose spread earns the most. Here, profit sits in motifs, and it pays out only once enough members of a motif have been reached.
The authors prove their motif-oriented problem is NP-hard, so exact answers are out of reach at scale. Their method builds on reverse reachable sets in three stages: estimating influence, choosing seeds, and scoring motif profit. Tests on a real social network dataset, plus time and space analysis, show the approach is workable. Marketers can thus target group patterns, not just people.
Catalog record
| CREATOR | Poonam Sharma, Suman Banerjee |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-19237
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Reverse Reachable Set Based Approach for Motif Oriented Profit maximization in Social Networks Poonam Sharma, Suman Banerjee Abstract Profit Maximization is one of the key objectives for social media marketing, where the task is to choose a limited number of highly influential nodes such that their initial activation leads to maximum profit. In this paper, we introduce a variant of the Profit Maximization Problem where we consider that instead of nodes, benefits are assigned to some of the motifs of the graph, and these benefit values can be earned once a given threshold count of nodes from the motifs is influenced. The goal here is to choose a limited number of nodes for initial activation (called ‘seed nodes’) such that the motif-oriented profit gets maximized. Formally, we call our problem the Motif Oriented Profit Maximization Problem. We show that the problem is NP-hard to solve optimally. We propose a Reverse Reachable Set-based framework to solve our problem. The proposed methodology broadly divides into three steps: KPT Estimation and ℛ ℛ \mathcal{RR} Set generation, Seed Set Selection, and Motif Oriented Profit Estimation. The proposed methodology has been analyzed to understand its time and space requirements. It has been implemented with real-world social network datasets, and the results are reported. We observe that the seed set selected by the proposed solution approaches leads to more profit compared to the seed sets selected by the existing methods. The whole implementation and data are available at: https://github.com/PoonamSharma-PY/MotifProfit. 1 Introduction In recent times, Online Social Networks play a pivotal role in spreading news, ideas, rumors, etc., and this happens due to the diffusion of information [ 2 , 1 ] . People tend to share the information through social media posts, and people who are in the friend (or follower) list may wish to like, share, comment, etc. on the post. If the person is influential, then there is a very high chance that many of the users of the network will come to know about the fact. This phenomenon has been exploited by commercial houses for promoting their brands. For this purpose, they choose a limited number of influential people from the network and distribute free (or discounted) products with the hope that they will spread positive words about the product due to word-of-mouth. This notion is called Viral Marketing through Social Media. In recent times, commercial houses spend a significant portion of their revenue on Social Media advertisements. To study the diffusion process in a social network, several models have been introduced and studied in the literature. Among them, the Independent Cascade Model is the most popular one. In the context of viral marketing, the key computational problem that arises is that given a social network, how can we effectively select a limited number of nodes for initial activation such that the influence gets maximized? Initially, this problem was posed by Domingos and Richardson [ 4 , 14 ] . Later, Kempe et al. [ 7 , 8 ] showed that this problem is NP-hard to solve optimally under the IC Model of diffusion. They proposed an iterative greedy approach based on marginal influence gain computation, which provides a (1-\frac{1}{e}) -factor approximate solution. This study triggers a significant amount of research in this direction, and a huge amount of literature is available. The proposed solution approaches for this problem can be classified into the following categories: Approximation Algorithms [ 12 ] , Heuristic Solutions [ 3 ] , Soft Computing-based Approaches, Reverse Reachable Set-based Approaches, and many more. In practice, social networks are formed by rational human beings, which means if a user is acting as a seed user, then (s)he must be incentivized. Also, in commercial advertising, the key objective is to maximize profit. Hence, the following problem is of immense importance: Given a social network, the cost and benefit of each user, and a fixed budget, how can we select a seed set within the budget to maximize the profit? This problem has been referred to as the Profit Maximization Problem. In the past decade, this problem has been studied extensively in the literature. In most of the studies, it has been considered that every user of the network has some benefit value that can be earned if the user is influenced. Now, consider the following scenario. A group of friends wants to dine in a restaurant. Now, any restaurant brand will be able to attract this group and earn some profit if that brand can influence the whole group. A small group of nodes in a network is called a motif. Sometimes it is important to consider influencing a whole motif rather than an individual user. To influence a motif, it may be sufficient to influence the majority of the users present in the motif. In this paper, we consider the problem of maximizing the profit of a commercial campaign by influencing the motifs. We call this problem the Motif Oriented Profit Maximization Problem. In this problem, we are given a social network where each user is assigned a selection cost, a set of motifs along with their corresponding benefit value, and a budget. This problem asks to choose a subset of nodes within the allocated budget such that the earned profit by maximizing the influence among the motifs is maximized. To the best of our knowledge, we are the first to study the Profit Maximization Problem under the motif-oriented setup. In particular, we make the following contributions in this paper: • We introduce and study the Motif Oriented Profit Maximization Problem for which there does not exist any literature. • We propose a reverse reachable set-based solution approach to solve our problem with a detailed analysis and illustration. • A number of experiments have been conducted on real-world social network datasets, and the results are compared with the existing methods to show the effectiveness and efficiency of the proposed solution approach. The rest of the paper has been organized as follows. Section 2 describes background information and defines the problem formally. Section 3 describes the proposed solution approaches with a detailed analysis. The experimental evaluation of the proposed solution approaches has been described in Section 4 . Finally, Section 5 concludes our study and gives future research directions. 2 Background and Problem Definition In this section, we describe the required preliminary concepts and subsequently define our problem formally. Initially, we start by describing the notion of social networks. 2.1 Social Networks A social network is defined as an interconnected structure among a group of people, which has been formally stated in Definition 1 . Definition 1 (Social Networks) A social network is often represented as a simple, (un)directed, weighted graph \mathcal{G}(\mathcal{V},\mathcal{E},\mathcal{P}) where the vertex set \mathcal{V} represents the set of users connected through the network, the edge set represents the social relationships, and the edge weight function \mathcal{P} maps each edge to its corresponding influence probability, i.e., \mathcal{P}:\mathcal{E}\longrightarrow(0,1] . For any edge (u_{i}u_{j})\in\mathcal{E} , it means that u_{i} and u_{j} are in the social relationship. We reserve n and m to denote the number of nodes and edges, respectively. For any edge (u_{i}u_{j})\in\mathcal{E} , its influence probability is denoted by \mathcal{P}(u_{i}u_{j}) . In our study, we assume