Abstract Billboard Advertisement is a popular out-of-home advertising technique adopted by commercial houses. Companies own billboards and offer them to commercial houses on a payment basis. Given a database of billboards with slot information, we want to determine which k slots to choose to maximize the influence. We call this the Influential Billboard Slot Selection ( $$\textsc {IBSS}$$ IBSS ) Problem and pose it as a combinatorial optimization problem. We show that the influence function considered in this paper is non-negative, monotone, and submodular. The incremental greedy approach based on the marginal gain computation leads to a constant factor approximation guarantee. However, this method scales very poorly when the size of the problem instance is very large. To address this, we propose a spatial partitioning and pruned submodularity graph-based approach divided into the following three steps: pre-processing, pruning, and selection. We analyze the proposed solution approaches to understand their time, space requirements, and performance guarantees. We conduct extensive experiments with real-world datasets and compare the performance of the proposed solution approaches with the available baseline methods. We observe that the proposed approaches lead to more influence than all the baseline methods within a reasonable computational time.

Analysis of large-scale networks for different structural patterns (also called motifs) remains an active area of research in the domain of graph data management and mining. In the past three decades, research has led to a large volume of literature in this area. However, the literature in the context of a signed bipartite graph is limited. In this paper, we study the problem of counting the balanced motifs in a signed bipartite graph. Specifically, We design an efficient algorithm BB2K for counting balanced (2, k)-bicliques. Previous studies for balanced bicliques in a signed bipartite graph focus on a set enumeration-based approach. We observe that the set enumeration-based approaches are expensive as they need to discard a large number of structures, which are not balanced. We take a different approach where we systematically group the symmetric and asymmetric wedges and count the balanced bicliques by counting on those wedges in such a way that we eliminate the generation of unbalanced structures completely. We conducted experiments with nine real-life datasets, and the experimental results demonstrate that our algorithm BB2K is more than 100× faster than the baseline SBCList++ - an adaptation of the state-of-the-art algorithm BCList++ combined with the filtering technique to filter out unbalanced bicliques. We have also shown the scalability of the proposed algorithm by using datasets of different sizes in our experiments.

Social media advertisement has emerged as an effective approach to promoting commercial house brands. Hence, many of them have started using this medium to maximize the influence among the users and create a customer base. In recent times, several companies have emerged as influence providers, providing a certain number of views based on the budget provided by a commercial house. In this process, the influence provider tries to exploit the information diffusion phenomenon of a social network. In this problem, the challenge is how to allocate the seed nodes among the advertisers so that the regret of the allocation is minimized. The input to the problem is a set of advertisers with their respective influence, demand, and budget, a social network along with the selection cost of the users, and the goal here is to allocate the seed nodes among the advertisers that minimize the regret. In this context, we introduce a noble regret model for social media advertisement. Two efficient heuristic solution approaches have been proposed. Both methodologies have been analyzed to understand their time and space requirements. The proposed solution approaches have been implemented with real-world social network datasets, and a number of experiments have been conducted. From the experiments, we have observed that the proposed solution approaches lead to the allocation of seed nodes, resulting in much less regret than the baseline methods.