Cédric David Dupuis
email: david.c.dupuis@gmail.com

Du Mouza

Nicolas Travers

Gaël Chareyron

Cédric Du Mouza

Real-Time Influence Maximization in a RTB Setting

Keywords: Real-Time Bidding, Influence Maximization, Social Network

come   L'archive ouverte pluridisciplinaire

Introduction

Influence Maximization (IM) is a trend topic since Kempe et al. [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF], known as a maximum coverage problem of social networks. The goal is to find the smallest subset of individuals in a social network, whom when targeted with a piece of information will maximize its diffusion through social influence. Thus, IM aims at maximizing the influence impact of a set of users. "Influence" is "the power of causing an effect in indirect or intangible ways" (Merriam-Webster). In other words, a user can be influenced if he saw the ad, interacted with it, purchased the product or was encouraged to do so in the future.

Today, real-time bidding (RTB) outpaced other advertising strategies in terms of online advertising [START_REF] Spencer | The arrival of real-time bidding[END_REF][START_REF] Yuan | Real-time bidding for online advertising: Measurement and analysis[END_REF] and social network services (SNS). RTB is an online auction system which allows advertisers to bid in real time for ad locations on a webpage loaded by users and thus to target them efficiently. In RTB, advertisers see a stream of users, one at a time and have less than 100 ms [START_REF] Yuan | Real-time bidding for online advertising: Measurement and analysis[END_REF][START_REF] Xxx | RTIM: A real-time influence maximization strategy[END_REF] to decide to bid or not. The bidders do not know what the auction landscape looks like and consequently cannot oversee future connections.

In addition, RTB ad targeting relies essentially on web page content and users' profile. However, it lacks the social value of each customer as suggested by Domingos and Richardson [START_REF] Domingos | Mining the network value of customers[END_REF]. As far as we know no RTB algorithm attempts to find an IM solution to improve bidding decisions. Thus, the aim of our approach is to develop an IM algorithm capable of running with RTB constraints. It is worth noting that IM could integrate the bidding aspect in order to improve RTB, but this approach is left for future work.

Traditional IM algorithms, based on propagation models, propose various optimization technic to statistically choose a seed set of users that maximizes influence. Even if some IM algorithms compute it in real time, none of them can work within a real-time bidding environment and satisfy its requirements.

Interestingly, the IM problematic in an RTB context is a twofold issue. First, influence maximization needs to take into account time with real-time bidding constraints: a short time, no exchange with the past, no time windows, incompleteness of the stream (not all users are connected). Second, to maximize the impact of an ad campaign, it is necessary to know in advance how much user it requires to target in the social network to guarantee a sufficient coverage. In fact, it is necessary to define the more accurate budget to define the best seed set size which maximizes the influence on the social network.

Indeed, whereas existing algorithms take hours or days to find a seed set up to 200 seeds in a large social network [START_REF] Arora | Debunking the myths of influence maximization: An in-depth benchmarking study[END_REF], they do not cope with ad campaign requirements with thousands of users or take into account the fact that chosen users can be available online or not. The maximization problem needs to rely on both propagation and real-time decision.

This article targets the issue with the following constraints: -Real-Time Bidding: only an online user can be targeted, -Processing Time: 100 ms to choose to target a user or not, -Social Networks: the propagation influence score relies on a social network containing millions of users and relationships, -Influence Maximization: thousands of users must be targeted just by appending them in real time while maximizing scores of large seed sets. -Ad campaign guarantee: the size of the ad campaign is set in advance in correlation to the social network to give a guarantee of its influence score.

Therefore, an IM algorithm is necessary to target influential users in an RTB environment, capable of deciding in real time which users are worth targeting. To achieve this we propose the Real-Time Influence Maximization (RTIM). It is an IM algorithm which decides in real time the effectiveness of an online user u, while static IM models only verify if this user u has been chosen in the pre-computed seed set. Our main contributions are as follows:

-We propose an elegant approach for real-time influence maximization focusing on the stream of online users, -We provide a deep analysis of users' influence scores for various social network datasets in order to showcase users' behavior in IM, -We give a model to give the estimation of the seed-set size in order to guarantee the influence efficiency of an ad campaign on the network, -We set up a thorough experimental setting for RTIM and IMM models on different social networks.

In this article, we first review the literature on influence maximization. We then explain the two stages of our algorithm: pre-processing and live, how they relate to each other and allow us to solve the influence maximization problem under RTB constraints. We follow on the RTIM implementation and we go through the experimental process which compares our dynamic algorithm with a static approach. We then present a methodology to estimate the impact of an ad campaign which gives the estimation of the influence of a seed-set size.

IM State of the Art

Influence Maximization takes place in a social network graph G = (V, E) where V is the set of vertices (users), E the set of directed edges (influence relationships). In this graph G, a user is activated if he has successfully been influenced by a neighbor and therefore influences his own outgoing neighbors. A targeted user is a user who is not yet activated but for whom a piece of information is shown to be propagated.

IM's goal is to produce a seed set S of targeted users which maximizes its influence on G. The optimal seed set (final result) is defined as S * .

Propagation models

Kempe et al. [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF] propose two common propagation models: Independent Cascade (IC) and Linear Threshold (LT). The IC model considers that each user can be influenced by a neighbor independently of any of his other neighbors.

The LT model considers that a user is activated if the sum of successful influence probabilities from his neighbors is greater than his activation threshold.

Under the IC model, time unfolds in discrete steps. At any time step, each newly activated node u i ∈ V a , ∀i ∈ V gets one independent attempt to activate each of its outgoing neighbors v j ∈ Out(u i ), ∀j ∈ V {i} with a probability p(u, v) = e ij . In other words, e ij denotes the probability of u i influencing v i .

As explained in [START_REF] Goyal | Learning influence probabilities in social networks[END_REF] there is a real challenge in acquiring real-world data to build datasets containing accurate influence probabilities. Therefore theoretical edge weight models may be assumed, like in the following edge weight's models for the IC model:

-Constant: Each weight e ij has a constant probability. In most solutions [START_REF] Chen | Scalable influence maximization for prevalent viral marketing in large-scale social networks[END_REF][START_REF] Cohen | Sketch-based influence maximization and computation: Scaling up with guarantees[END_REF][START_REF] Galhotra | Holistic influence maximization: Combining scalability and efficiency with opinion-aware models[END_REF][START_REF] Galhotra | ASIM: A scalable algorithm for influence maximization under the independent cascade model[END_REF][START_REF] Goyal | CELF++: Optimizing the greedy algorithm for influence maximization in social networks[END_REF][START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF], p is set at 0.01 or 0. where In(v j ) is the number of neighbors that influence u. Thus, all neighbors that influence u i do so with the same probability. Therefore, it is easier to influence a user with a low in-degree [START_REF] Chen | Scalable influence maximization for prevalent viral marketing in large-scale social networks[END_REF][START_REF] Chen | Efficient influence maximization in social networks[END_REF][START_REF] Cohen | Sketch-based influence maximization and computation: Scaling up with guarantees[END_REF][START_REF] Galhotra | Holistic influence maximization: Combining scalability and efficiency with opinion-aware models[END_REF][START_REF] Galhotra | ASIM: A scalable algorithm for influence maximization under the independent cascade model[END_REF][START_REF] Cheng | Imrank: influence maximization via finding self-consistent ranking[END_REF][START_REF] Cheng | Static greedy: solving the apparent scalability-accuracy dilemma in influence maximization[END_REF][START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF][START_REF] Tang | Influence maximization in near-linear time: A martingale approach[END_REF][START_REF] Tang | Influence maximization: Near-optimal time complexity meets practical efficiency[END_REF].

-Tri-valency Model: Here, the weight of edges is randomly chosen from a list such as {0.001, 0.01, 0.1} [START_REF] Chen | Scalable influence maximization for prevalent viral marketing in large-scale social networks[END_REF][START_REF] Cheng | Imrank: influence maximization via finding self-consistent ranking[END_REF][START_REF] Jung | Irie: Scalable and robust influence maximization in social networks[END_REF]. In very large or dense networks, the tri-valency model may actually have edge weights far greater than the weighted cascade model due to the number of neighbors each user has.

For the LT model, the general edge weight rule is that the sum of the weights must equal one. Therefore, the WC model applies to LT. Additional alternative models can be found in [START_REF] Bhattacharya | Influence maximization in large social networks: Heuristics, models and parameters[END_REF] with an extensive IM state-of-the art.

The IC model is very useful to model information diffusion when a single exhibition to a piece of information from one source is enough to influence an individual. It is also a simpler model to study than LT. The LT model doesn't change the fundamental approach of our algorithm and we believe that it should be simple to extend it to LT. For these reasons, we limit our approach to IC. In addition, we define the edge weights using the WC model, because it corresponds better to the simulation of the diversity of influence between individuals in a real-world social network.

Properties

Kempe et al. [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF] prove that the influence maximization problem is a monotone and sub-modular function. It is also an NP-Hard problem under both the IC and LT models. Chen et al. [START_REF] Chen | Scalable influence maximization for prevalent viral marketing in large-scale social networks[END_REF] prove that computing the influence score of a seed set is #P-Hard under the IC model.

For both IC and LT models, adding users to the seed set always increases its global influence score which corresponds to the positive monotone property.

Moreover, the propagation function f is sub-modular if it satisfies a natural diminishing returns property i.e., the marginal gain from adding an element v to a set S is at least as high as the marginal gain from adding the same element to a superset of S. Formally, a sub-modular function satisfies: ∀S ⊆ T ⊆ Ω and

x ∈ Ω\T, f (S ∪ {x}) -f (S) ≥ f (T ∪ {x}) -f (T )
. This sub-modular property is essential as it guarantees that a greedy algorithm will have a (1 -1/e -ϵ) approximation to the optimal value [START_REF] Nemhauser | An analysis of approximations for maximizing submodular set functions-i[END_REF]. Many IM algorithms of the state-ofthe art rely on this theoretical guarantee to validate their strategy.

Computing score

Influence Score: Authors in [START_REF] Zhang | Probabilistic solutions of influence propagation on social networks[END_REF] elaborate the exact influence spread function for the IC model as an inclusion-exclusion based equation. We generalize their inclusion-exclusion based equation into equation 1.

In Equation 1, the influence score of a seed set S, of size k, is defined as the sum of activation probabilities a S (v) of any node v ∈ V when users in S are targeted. The activation probability of a user is the probability that there exists a path between that user and any targeted user. As we write in Equation 1, the probability that a path exists is the union of the existence of any path between a user and any targeted user. It's clear here that computing this formula is exponential in complexity.

σ(S) = ∑ vi∈V a S (v i ) = ∑ vi∈V P( ∪ pj ∈Puv i p j ), P uvi = {all paths event existence between u and v i } (1)
Determining the seed set S of k users among N which provides the maximum global influence score σ(S) is a NP-hard problem since it requires computing the global influence score of any combination of k users, so there are

( N k )
combinations to test for any given k. Even when assuming the seed set is known, computing its global influence score has been proven to be #P-Hard [START_REF] Jung | Irie: Scalable and robust influence maximization in social networks[END_REF]. Due to the exponential nature of computing the influence score, Kempe et al. [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF] offer an alternative which consists in running n = 10, 000 influence propagation simulations and averaging the scores into a final influence score result. This is called the Monte Carlo approach and we write an influence score computed with this method as σ M C (). This estimation method allows us to produce a good approximation for the influence score and we can thus efficiently compute: σ M C (S) ∼ σ(S)

Algorithms

Clearly presented by in [START_REF] Arora | Debunking the myths of influence maximization: An in-depth benchmarking study[END_REF] and [START_REF] Aslay | Influence maximization in online social networks[END_REF] there are three main categories of IM algorithms: greedy, sampling and approximation.

GREEDY [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF], CELF [START_REF] Leskovec | Cost-effective outbreak detection in networks[END_REF] and CELF++ [START_REF] Goyal | CELF++: Optimizing the greedy algorithm for influence maximization in social networks[END_REF] are all three lazy-forward algorithms which take advantage of the sub-modularity property of the IM problem and thus guarantee an approximation of (1 -1/e -ϵ). To find S * they start with S = ∅ and incrementally add node v which brings the largest marginal gain: [START_REF] Leskovec | Cost-effective outbreak detection in networks[END_REF][START_REF] Goyal | CELF++: Optimizing the greedy algorithm for influence maximization in social networks[END_REF] attempt to remedy this by storing certain scores to take advantage of the sub-modular property and avoid recomputing other scores but this doesn't provide any significant gain in runtime. Thus, those greedy algorithms do not scale for large seed sets or large graphs.

σ M C (S ∪ v) > σ M C (S), until |S| = k. However, continuously computing σ M C (S) is costly. CELF
Borg et al.'s method [START_REF] Borgs | Maximizing social influence in nearly optimal time[END_REF] (referred to as RIS: Reverse Influence Sampling), TIM, TIM+ [START_REF] Tang | Influence maximization: Near-optimal time complexity meets practical efficiency[END_REF], or IMM [START_REF] Tang | Influence maximization in near-linear time: A martingale approach[END_REF] use topological sampling. In the transpose graph, they generate a set R of size θ of random paths of greatest influence by picking users uniformly at random (Reverse Reachable (RR) sets). Using a greedy method, they build S * by continuously adding to S * the user who covers the greatest number of RR sets and removing them from R. As shown by [START_REF] Arora | Debunking the myths of influence maximization: An in-depth benchmarking study[END_REF] sampling algorithms are significantly faster because σ M C (S * ) is only computed once the final solution is found. However, their theoretical guarantee depends on θ which is computed by ϵ in (1 -1/eϵ) and l which determines their runtime factor l 2 * log(n). Experimentally they use ϵ = 0.5 and l = 1 which means that precision is sacrificed for scalability.

Approximation algorithms such as EaSyIM [START_REF] Galhotra | Holistic influence maximization: Combining scalability and efficiency with opinion-aware models[END_REF], IRIE [START_REF] Jung | Irie: Scalable and robust influence maximization in social networks[END_REF], SIMPATH [START_REF] Goyal | SIMPATH: an efficient algorithm for influence maximization under the linear threshold model[END_REF], LDAG [START_REF] Chen | Scalable influence maximization in social networks under the linear threshold model[END_REF] or IMRANK [START_REF] Cheng | Imrank: influence maximization via finding self-consistent ranking[END_REF], SSA-Fix [START_REF] Huang | Revisiting the stop-and-stare algorithms for influence maximization[END_REF], offer heuristics to compute σ(S). Instead of computing the union of all paths as indicated in Equation 1 they consider the most probable path. RLP [START_REF] Liang | Influence maximization in signed social networks with opinion formation[END_REF] uses live edges and propagation paths to optimize computation time. They can run select the top k influential users. While scalable they do not provide theoretical guarantees [START_REF] Arora | Debunking the myths of influence maximization: An in-depth benchmarking study[END_REF].

Mining and learning strategies try to enhance the extraction of seed sets. DIEM [START_REF] Tian | A learning approach for topic-aware influence maximization[END_REF] proposes to learn propagation models on the influence graph to produce a prediction model. C2IM [START_REF] Singh | C2im: Community based context-aware influence maximization in social networks[END_REF] focuses on influence communities' extraction in order to ease the connection to the influencers. [START_REF] Wu | Factorization bandits for online influence maximization[END_REF] proposes the factorization of bandits' methods in order to predict influencers through iterations of reward strategies. However it hardly scales in seed set sizes (generally 50) and, moreover, models are not designed to be time dependent and flexible.

OIM [START_REF] Lei | Online influence maximization[END_REF], AIM [START_REF] Tong | Adaptive influence maximization in dynamic social networks[END_REF] and TAIM [START_REF] Tong | Time-constrained adaptive influence maximization[END_REF] are recent works on real-time influence maximization which need to be noticed. They propose adaptative strategies that compute the seed set dynamically by incrementally watching the influence impact of users on time windows and choose the optimal one on this setting. OPIM [START_REF] Tang | Online processing algorithms for influence maximization[END_REF] also proposed an extension of Borg's solution [START_REF] Borgs | Maximizing social influence in nearly optimal time[END_REF] by deriving in real time the approximated seed set and then choose the node with the largest marginal coverage. Even if those strategies properly approximate the seed set influence iteratively, it cannot fit with RTB constraints for which a decision must be made on a single user (bid) and not on a set of users at once. Thus it cannot be an approximation on the whole graph but a local decision at once.

Conclusions:

All of these algorithms provide proper scientific solutions to solve the IM problem. The common rule is that an algorithm which has high accuracy will take weeks to find its seed set and vice versa an algorithm which runs in a couple of hours will have less accuracy. However, these algorithms compute the seed set in a static graph environment and assume that every user must be available at any time to be targeted. This approach is not appropriate to graphs with more than tens of millions of users with proportionally many edges [START_REF] Arora | Debunking the myths of influence maximization: An in-depth benchmarking study[END_REF]. There exists a large number of specific IM contributions which have been listed in [START_REF] Bhattacharya | Influence maximization in large social networks: Heuristics, models and parameters[END_REF]. It shows clearly that very few contributions have been made regarding the analysis of the IM challenge in a stream of online users. We must notice [START_REF] Wang | Real-time influence maximization on dynamic social streams[END_REF] which proposes an interesting solution with sliding windows that computes local Influence Maximization. However it does not scale up for large seed set lists; more than 100 while thousands are required.

Therefore, none of the existing IM solutions can perform well under realtime bidding constraints. Indeed it requires that all users in S appear during the campaign to guarantee the maximization of the static IM strategies. These algorithms compute the seed set in a static environment rather than a dynamic one, as we hope to achieve, with RTB constraints.

To this end, we offer RTIM, Real-Time Influence Maximization which targets influential users in real time, henceforth generating a seed set of influencers under real-time bidding constraints. To ensure this, RTIM takes place in two stages: a pre-processing stage and a live stage which we now present.

RTIM Approach

RTIM is meant to perform in an RTB environment. The latter, consists of users who, through their devices connected to the Internet, are navigating on websites. As soon as a user arrives on a webpage which sells its ad slots through a real-time bidding environment, the IM algorithm has to determine whether it is useful for targeting. In minutes, millions of users are quickly navigating through many dozens of websites each leading for any RTB advertising agency to a continuous stream of online users [START_REF] Yuan | Real-time bidding for online advertising: Measurement and analysis[END_REF]. Advertisers can only target, with advertisements, users who appear in the stream and target them under 100 ms which corresponds to the bidding platform delay. As we know, these users, all belong to a very large social network through which they may be sharing information and influencing one another. It is therefore in the advertiser's interest to take advantage of the social network value of each user that appears in the RTB stream. In addition, these same advertisers, with large budgets seek to acquire or convert (i.e., activate) many users, most through targeting.

The originality of our approach lies in its ability to target users who appear in this dynamic stream by estimating whether they will have a significant gain based on previously targeted users in the same stream and belonging to the same social network. Thus providing a solution to the influence maximization problem and producing a large set of users for a realistic ad campaign. While traditional approaches determine the best seed set of targeted users, at the cost of expensive computation, by processing a static graph in which any user is considered online and available for targeting at any given moment. Contrary to these solutions, RTIM allows us to adapt our influence maximization strategy to an advertisement campaign taking place in an RTB streaming environment and which requires targeting tens of thousands of users.

Furthermore, we choose to compare RTIM with the static algorithm IMM ("Influence Maximization with Martingales" [START_REF] Tang | Influence maximization in near-linear time: A martingale approach[END_REF]). Indeed, IMM has proven that it can compute an effective seed set in a reasonable time regardless of the graph size. Even more so, it can compute large seed set sizes of tens of thousands of users as an RTB advertising campaign requires it.

Static algorithms, such as IMM [START_REF] Tang | Influence maximization in near-linear time: A martingale approach[END_REF], correspond to an optimistic approach where they assume that the users from their pre-computed seed set will necessarily be online in the stream. However, without integrating a probabilistic model based on real and precise figures about the connection rate of the different users, which is hardly possible on large social networks like Twitter, many users of the pre-defined seed set won't be available to target during the advertisement campaign. In contrast, our greedy approach, which can be considered as a pessimistic approach, allows us to dynamically fill our seed set with online users of interest for the advertisement campaign.

Our RTIM algorithm is composed of two steps. First a pre-processing step which computes the influence score of every user in the graph. Second, when reading the dynamic stream in real-time (called the "live stage"), for each user in the stream, we determine whether his influence score is high enough or the probability of him being activated by a previously targeted user is low enough. When a user is targeted during this live stage, we update the activation probability of the users in his neighborhood.

3.1

Step I: Pre-Processing -Building the Influence Graph First, we attribute a weight to each edge which estimates the influence that depends on the number of incoming edges of a vertex. This influence estimation between direct neighbors is commonly adopted in influence propagation [START_REF] Ohsaka | Fast and accurate influence maximization on large networks with pruned monte-carlo simulations[END_REF]. We call this graph the influence graph G I (V, E, w I ) defined formally as follows:

Definition 1 (Influence graph) Consider G(V, E) the social graph where V is the set of vertices and E ⊆ V 2 the set of oriented edges. The influence graph for G is the graph G I (V, E, w I ) with the same sets of vertices and edges and a weighted function w I : E → R such that for an edge e ij from vertice v i to v j :

w I (e ij ) = 1 indegree(v j )
Figure 1 depicts the influence graph for a social network between 5 users. For instance, user u 2 who follows or is influenced by users u 1 , u 3 and u 5 has each of his incoming edge e ∈ E weighted by: w I (e 12 ) = w I (e 32 ) = w I (e 52 ) = 1/3 = 0.33

To estimate the influence score, we use the Monte Carlo approach by running n simulations, where n is a large number (10, 000 in [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF]). The influence score of each user u is the average number of users activated for all simulations.

For each single simulation, we test the existence of each outgoing edge of a user (i.e. followers of u 1 ) in G by generating a random number r ∈ [0, 1] and checking whether r reaches the activation probability, so that r < w I (e ij ). If it is, the edge e ij exists with probability w I (e ij ). For example, for user u 1 we test his followers, the two edges e 12 and e 13 are tested with random values that give 0.3 < w I (e 12 ) and 0.6 > w I (e 13 ). Consequently, only u 2 is considered activated since we can consider that a path exists between u 1 and u 2 . When a neighbor is activated, we can then recursively test each of the neighbor's outgoing edges with the same method. We stop when no more neighbors are activated (the influence propagation stops along the edges). That is, u 2 cannot reactivate a node already activated by u 1 . For instance, with 0.7 > w I (e 23 ) and 0.4 < w I (e 25 ), user u 5 is activated. Recursively, we test the edge e 53 . In our example, the influence score of user u 1 (for the first simulation) is equal to 2 with activated users: u 2 and u 5 .

Since the simulations are all independent and the graph data structure is only read during the process, we can run the n simulations in parallel. However running 10,000 Monte Carlo simulations for each user u ∈ G remains extremely costly when considering real large advertisement campaigns where the expected seed set reaches tens of thousands of users. Consequently, this computation must be performed offline.

We store all the values in a vector I of user influence scores:

∀u i ∈ G, I i = σ M C (u i )

Step II : User targeting at runtime

With the influence score computed in the pre-processing step, RTIM is able to select, during the RTB stream, users to target. Consider the temporal stream of users T in which appears every online connection event of the users u ∈ G. Since a user can only be targeted when he appears in the stream, we need to decide in real-time whether he is worth targeting or not. To make this decision, our RTIM algorithm takes into consideration two criteria: i) Is the user influential enough? ii) What is the probability that he was already activated by the ad through one of his influential and targeted neighbors?

To verify these two criteria, we set two thresholds, θ I and θ A , respectively the minimum influence score and the activation probability. Whenever a user is online, we check whether his influence score is important enough to be a potential target for the advertisement campaign or not. If his influence score is above the influence threshold θ I (i.e., considered to be an influencer) we check the probability for this user to be presented the advertisement by the users he follows (i.e., already activated). If this probability is above the threshold θ A , we value that it is not worth presenting the advertisement since it is very likely that it has already been presented to a user he follows who will have influenced him. Otherwise, the user is targeted and added to the seed set.

When we target a user who satisfies these two thresholds, his activation probability is set to 1. This change, which impacts the activation probability of other users in the network, must be taken into account.Therefore, from the targeted user, we update the activation probability of neighboring users by propagating his influence. This will enable us to make better targeting decisions for future users who appear in the stream.

Figure 2 illustrates the stream of online users and their interconnected graph. T is a basic example of an RTB stream where users appear one at a time in discrete steps (in red/bold) and can only be targeted when available. As soon as RTIM makes a decision to target or not the user, he is no longer available. When the first user u 2 appears (time t 1 ), we verify his influence score I 2 . His activation probability is necessarily 0 because he is the first user in T . If I 2 > θ I then we consider that u 2 tries to activate his followers u 1 , u 3 and u 5 , and propagate to their own neighbors. Then we update their activation probability. Assume that u 1 is activated (A 1 > θ A ) while u 3 and u 5 are not.

When user u 4 is online (t 2 ), his influence score is insufficient to be targeted. We skip him and wait the for the following online user. Then, when user u 3 appears in the stream (t 3 ), he is considered to be an influencer (I 3 > θ I ) and not activated by u 2 (A 3 < θ A ). As for u 2 , he is targeted and propagates the activation probability to his neighbors u 1 , u 2 , u 5 and u 4 . When u 5 appears in T at t 4 , even if I 5 is higher than θ I , he is considered to be influenced by both u 2 and u 3 (assume that A 5 > θ A ). Thus it is not worth targeting him.

By applying the whole stream of users T , our approach generates the seed set S * where every user u ∈ G verifies θ I and θ A . The key point resides in the fact that RTIM maximizes the influence of connected users while removing those who are too close to users already targeted.

We present the different algorithms, within RTIM, which are required for the runtime processing, in the following section.

RTIM Model

Traditional influence maximization algorithms, like IMM, have an optimistic approach since they determine statically the users to target based on the final global influence score of the set of targeted users. So they assume with a probability of 1 that these users will connect within the advertisement campaign period. If the advertisement campaign is not time-limited, i.e., we consider an infinite stream of users online, these solutions potentially maximize the total score of the campaign. However, with a limited time window for the advertisement campaign, not all these users will likely appear online.

RTIM's strategy is quite different since it considers that the probability that a user will appear in the stream is undefined. Therefore, the decision of targeting a user is done in real-time when he is available, considering whether this user is a good "influencer" while not already having been influenced by other users during the campaign. So RTIM can be considered as a pessimistic algorithm since we decide to add a user to the final seed set instantaneously, even if a "better" user to add to the seed set appears later in the stream.

Upon targeting a user, his activation probability is immediately set to 1 because he is considered to be activated on the spot. This change in the targeted user's status means that other users around him are likely to also be activated through his influence. In the following part, we discuss the activation probability graph which allows us to update the activation probability of neighboring users, with respect to time (i.e., the user position in the stream). Activation probability graph. At time t 0 , when T starts, we create the activation probability graph as the influence graph G I described in Section 3.1.

We can adopt the matrix representation for the graph in the following:

M G I (V, E) = A G × InDeg V
where A G is the adjacency matrix, i.e., A G [i, j] = 1 if there exists an edge from user u i to user u j , 0 otherwise, and InDeg V is the indegree vector, with

InDeg V [i] = 1
indegree(ui) . The activation probability vector AV is initialized as the -→ 0 vector.

Activation probability updates.

Consider we have at time t k-1 > t 0 , an activation probability vector AV (t k-1 ). Then assume that at time t k , a user u i connects and we decide to target him. So his activation probability AV (t k-1 )[i] is now set to 1. This probability update impacts other probabilities in the graph. Indeed, users who follow u i are now more likely to see this advertisement and consequently we may avoid targeting them in the future. We must update other activation probabilities through influence propagation according to existing links in the graph to obtain the AV (t k ) probability vector.

Definition 2 (Activation probability propagation)

Consider the social graph G(V, E) and its influence graph G I (V, E, w I ) as stated in Section 3. The activation probability vector AV (t k ) for G at t k is recursively defined as:

{ AV (0) (t k ) = M G I (V, E) × AV (t k-1 ) AV (i+1) (t k ) = M G I (V, E) × AV (i) (t k )
So, after targeting a user u i (AV (t k-1 )[i] = 1) the vector is recursively combined with the activation probability graph M G I in order to propagate the activation while obtaining a convergence after i iterations:

AV (t k ) = AV (∞) (t k ) = M G I (V, E) × AV (∞) (t k )
This model corresponds to a Matrix population model [START_REF] Leslie | On the Use of Matrices in Certain Population Mathematics[END_REF] 1 . Thus, we can guarantee its convergence since the Eigenvalues of M G I (V, E) are real strictly positive (the matrix is real, asymmetric and non-diagonal). Moreover the propagation is an increasing and monotone function bounded to -→ 1 . As the stream of users goes by RTIM will take less risk and target the best user when available because there is no certainty that a better user will appear later on. On the contrary, if the stream is infinite, then the probability that a user will appear is necessarily 1 and thus IMM, on an infinite stream, will always perform better than RTIM.

The aim of RTIM is to determine in real-time if a user is a good influencer while not already having been influenced by other users. To achieve this, our model relies on the probability a targeted and activated user has of influencing and activating other users. The issue is to determine the proper thresholds in order to fill the seed set both efficiently and effectively.

To target influencers, we need to determine users worth targeting but also when users are considered activated by influencers. For this we define the threshold θ I as the minimum influence score for which we can consider the top-k influencers. Therefore, we propose to set θ I to the influence score of the k th influencer. We also define the activation probability threshold θ A which is the likelihood of a user being activated. By default we set θ A to 0.5. Any user whose activation probability is greater than θ A is considered to have been activated and therefore will have attempted himself to propagate the information provided by an influencer and is therefore not worth targeting.

During the live stage, we need to update the current online user's activation probability while checking if he is a worthwhile influencer. To achieve this, we need to compute all of the most reliable paths between this user and any activated neighbor of depth less than d. For that user, if his influence score is above θ I and his activation probability is below θ A , the user is targeted. Otherwise we ignore him.

In Equation 1 we explained that the probability of a user v being activated by any node u ∈ S is the probability of all paths between v and any user in S, (i.e., a S (u) = P( ∪ pj ∈Puv i p j )). Here, we consider S = u, where u is the online user who has just been targeted and considered activated.

Notice that if we consider the paths between u and v as being independent then we obtain equation 2:

A[u] = P( ∪ pj ∈Puv p j ) = 1 - ∏ wi∈P d uv (1 -w i ), w i ∈ P d uv = {all path weights of length d f rom u to v} (2)
1 Not a Markov chain since the sum of a column can exceed 1: for v ∈ Nu do 3:

M G I (V, E) = A G ×InDeg V Algorithm 1
A[v] ← 1 -(1 -A[v]) * (1 -p *
: Initialize A ← -→ 0 2: while |S| < k do 3: u ← next(T ) 4: if I[u] ≥ θ I and A[u] ≤ θ A then 5: ActivationScores(G, u, 1, d) 6: S ← S ∪ u
This theoretical bias is validated if we consider the paths to be of length no more than 2. This is true because between two nodes all paths of length 2 are necessarily independent. Therefore, we use Equation 2 with a maximum depth of 2 to update the activation probability of a user. Due to the directed property of the influence graph, for algorithmic and computational purposes it is easier to update the activation probabilities of a recently targeted and activated user. Hence, when a user is targeted, we update the activation probabilities of all his neighbors up to a maximum depth d.

Algorithm 1 illustrates updates of activation probabilities. For each neighbor v of user u, we propagate his activation probability (line 3). Then, while the depth of propagation is sufficient we follow the propagation recursively (line 4&5). In the worst case, it runs in O(|V | d ) when all users are interconnected. Since in most cases, our networks are not dense (see Table 1), updating the activation probabilities is done very fast (see Table 4) and we set d to 2. However, it is not necessary to be extremely fast for very large and dense networks, such as Twitter, as updating the activation probabilities can take place in a separate thread during the live stage.

For the live stage of RTIM, we consider that if any neighbor (of depth d) of a user is targeted then we update his activation probability. First, Algorithm 2 initializes the activation probabilities to the 0 vector (line 1). Then, while the Consider Figure 2 as an example. Its influence score vector I is:

I ⊤ = [ 2.3423 3.0232 3.7802 1.6932 2.

]

During the live stage, we read the RTB stream T with maximum seed size k = 3, θ A = 0.5 and θ I = 3.0, as example settings. At t = 0, we initialize the activation probability vector to A 0 = -→ 0 (line 1). At t = 1, the first user in T , u 2 , has I[u 2 ] = 3.0232 > θ I and A[u 2 ] = 0, so we target him and update the activation probability of his neighbors. Which gives us:

A 1 ⊤ = [ 0

Influence Analysis

Our model is experimented with empirical datasets of different sizes: Live-Journal, Youtube and Twitter. These graph datasets have interesting properties that can be exploited in order to understand the impact of the Real-Time Bidding environment on the influence maximization interactions of users.

To achieve this, we need to understand the way more closely that users are interconnected for each dataset and study their topologies. We can see in Table 1 the global statistics that highlight the different sizes. We see here the graph composition of all three datasets (# nodes and # edges), and node degrees (mean, variance and standard deviation).

We can see that Youtube is the "smallest" graph with fewer connections (mean degree of 10) but with a high variation of degree compared to its size. LiveJournal is highly connected with a high number of edges and a mean degree of 34. However, users are more homogeneously connected with a low variance and standard deviation. Twitter, on the other hand, is the biggest graph in which users can have varying numbers of connections with a mean degree of 70 but a variance of 6.4M and a standard deviation of 2.5k. This analysis helps understand the subtle performance of RTIM for each dataset.

As for the distribution of users' influence score, to estimate the influence score of each user we applied Monte Carlo simulations on each dataset for every node in the social networks. The result of each MC influence score is a correct approximation of the real score.

Figure 3 shows the distribution of influence scores for our graph datasets (reduced to 10 5 but analysis was done on all users). These distributions can be characterized by a standard Zipf-Mandelbrot distribution [START_REF] Mandelbrot | The fractal geometry of nature[END_REF], traditionally used for distribution of ranked data. It is defined by:

B (r 0 + r) α
where r is, here, the rank of the influencer. r 0 is a constant representing the number of top influencers. B corresponds to the starting score modifier and α is the decreasing speed of scores.

Table 2 gives the corresponding values for those Zipf-Mandelbrot distributions and the Pearson Xi-Square values (observation probabilities).

Youtube and Twitter behave similarly with a huge r 0 (resp. 11 and 6) leading 100 to 750 top influencers. We can see that Twitter has more top influencers with a high score and then drops faster than Youtube. LiveJournal behaves differently with very few top influencers compared to Youtube or Twitter. The low value r 0 shows that top influencers' score decreases faster at the beginning of the curve.

However, the decreasing speed of the influence score α witnesses really high values (resp. 0.78 and 0.99) which means that it is harder to become a top influencer on Twitter than Youtube. Likewise, the number of influencers is really high with a B value between 10 4 and 10 6 leading to a long tail which only starts after more than 10 5 for Youtube and 2 × 10 5 users for Twitter.

On the other hand, LiveJournal's score curve decreases slower than the others with an α of only 0.395 giving the idea that the number of connections between users are closer to the average than Twitter or Youtube. Consequently, the long tail is reached more slowly than the others (4 × 10 5 users).

This conclusion is interesting in order to understand the impact of these social networks on influence maximization. Indeed, targeting top influencers in real-time requires choosing influencers according to their estimated score. For instance, users from the long tail are pretty identical and cannot be differentiated from each other, thus the decision to target or not an influencer depends on α which tells us how much influencers' score evolves.

Experiments

All of our experiments are run on a server of make Intel(R) Xeon(R) CPU E5-2680 v4 @ 2.40GHz with 56 CPUs and 462Gb of RAM memory.

We wish to show in this section the impact of choosing influencers in a realtime bidding stream of users. In order to do this, we need to compute users' influence scores, generate multiple streams of users with varying distributions and compare the final solution of each algorithm for different graph datasets.

Experimental process

Since RTIM is an IM algorithm which runs under RTB constraints, we want to compare it to an existing IM algorithm. We choose IMM [START_REF] Tang | Influence maximization in near-linear time: A martingale approach[END_REF] because in [START_REF] Arora | Debunking the myths of influence maximization: An in-depth benchmarking study[END_REF] it is proven to have the best compromise between computation speed, scalability and accuracy. In particular, IMM can compute seed sets with thousands of users on our largest dataset. We run all algorithms in a specific experimental process involving three stages: pre-processing, live stream generation and live stream process. The code for IMM is provided by [START_REF] Arora | Debunking the myths of influence maximization: An in-depth benchmarking study[END_REF] in C++.

Stage I: Pre-processing. First, we run IMM in its entirety and add k users to its seed set S IM M . Recall that IMM states that every user in the graph appears equiprobable, and more precisely assumes that they will appear in the stream. However, during the ad campaign, it is more likely that not all the users will be available online. Since our objective is to target a large number of users in the stream, as would happen in a marketing campaign, we set k = 10, 000. We compute IMM's optimal seed using ϵ = 0.1. It can do this in seconds and very easily scale to large graphs (see [START_REF] Arora | Debunking the myths of influence maximization: An in-depth benchmarking study[END_REF] for a proper analysis of IMM performance).

RTIM uses the Monte Carlo approach to compute the influence score of each user in the graph. We run n parallelized simulations per node (n = 10, 000). Even so, for large graphs, this operation can take several days, so to make it scalable we limit it to a depth of 3 on large graphs to reduce pre-processing time to a few hours at most. Thanks to the graph topology with a high connectivity (see Section 5), the Monte Carlo simulations converge faster. As a counterpart we lose in influence score precision but believe the error to be negligible. The influence scores of each user are stored in a vector I for future use.

Stage II: Live stream generation. It's during this stage that we read our RTB stream and both algorithms have the opportunity to target influential users. Since no real streams of connected users are available online, we simulate users' behavior in the social networks with different distributions. To the best of our abilities, we haven't found well-founded models for RTB social stream generation. So, we simulate the RTB stream of users in the three different social networks by randomly picking users based on two distributions. Notice that a user can appear several times in the stream. Here are the two distributions:

-Uniform: we suppose that all users have equal probability of appearing in the stream. This distribution can be considered to be the worst case where highly connected users can appear as frequently as poorly connected users or where top influencers can appear as frequently as low influencers. -Log: we suppose that users who have more in/out edges in the graph are more likely to be connected. User probability of being in the stream is:

P (u i ∈ S) = log(deg ui ) ∑
ui∈V log(deg ui ) where deg ui is the degree of u i , the sum of in-degree and out-degree. We apply a logarithm on the number of edges per user in order to give users with a low influence score a reasonable probability of showing up in the stream. In fact, due to the distribution of edges in the graph, some users are highly connected to other ones and represent the large majority of online users in the stream even though this does not reflect the reality. This Log stream can be considered to be the best case where highly linked users are more likely to be present in the stream, and potentially top-influencers.

Moreover each stream is a subset of the total number of users, we choose 10% of the total number of users. In this setting, we ensure that all the users are not necessarily available online during the ad campaign:

|T | = 10% × |V |
Table 3 gives for each stream the proportions of influence scores and size in our experiments. As expected Uniform distributions contains lower influence scores while Log focuses more on higher scores (more than 10). As seen in Figure 5, LiveJournal produces lower scores so does the stream. According to Twitter it witnesses a huge amount of low scores with more than 80% in both Uniform and Log distributions. It is due to the large stream (above 4M connections) and stick to the distribution of Twitter scores. However, with respect to the proportions even with 1.20% of the stream, the number of high influence scores is higher than LiveJournal and Youtube.

Stage III: Live stream process. For IMM, if a user in the stream belongs to S IM M , he is targeted and added to the seed set S * IM M . A user is targeted only once, even if he appears twice. At the end of the stream: S * IM M = S IM M ∩ T For each user u i in the stream, RTIM will verify its targeting conditions. It will check that the user's activation probability ap(u i ) is below the activation threshold θ A , and if his influence score σ M C (u i ) is greater than the influence threshold θ I . If both conditions are satisfied then u i is targeted instantaneously (see Algorithm 2). At which point he is added to the final seed set S * RT IM and we update the activation probability of his neighbors up to depth 2 (see Algorithm 1). The update operation can be done by a separate thread.

Table 4 gives the time spent to target and update propagation probabilities in the network. It shows that the average targeting time is very low with a constant time wrt. the number of users and the update time is less than 100 ms which satisfies our real-time requirement, and in most of the case far less (median). However, some updates on large dense graphs can take up to 411 ms. This is still negligible since a user cannot influence another in less than half a second.

Stage IV: Seed Sets Evaluation

To compare the performance of both IM algorithms we compute and compare

Stream of users

Seed set score Fig. 5 Seed set score evolution with Youtube the live stage, the score of the seed set is computed for every 100 users added to the seed set, or 1,000 for large seed sets on Twitter.

Experimental results

Youtube. In the following, we see the evolution of the seed set during the stream both for influence score and size. Figure 4 and 5 give the results produced with a stream of 2.27 × 10 5 connected users over the Youtube dataset.

Figure 4 shows the evolution of the seed set size. We clearly see that IMM hardly finds pre-defined influencers, especially for the Uniform distribution. RTIM evolves almost linearly with twice as many seeds for the Uniform distribution and 3.3 times more for the Log one. According to the Log distribution, RTIM finds more influencers and reaches k faster. The sudden stop of the RTIM seed set at 1.89 × 10 5 users is due to the fact that the marketing campaign is over with a full seed-set of k = 10, 000 users.

Figure 5 shows that RTIM produces seed sets with higher scores than IMM. Uniform and Log streams witness different evolution. In fact, IMM hardly finds influencers in the Uniform distribution where highly connected users are less likely to be available online. This explains why IMM's seed set evolves slowly. On the other hand, RTIM targets users according to their local influence on the graph and thus has more targeting opportunities.

According to the Log distribution, IMM is closer to RTIM since topinfluencers are more present in the stream. Consequently, it takes time for IMM to reach this goal by the end of the stream with a similar score (1,105 less), while RTIM stopped earlier when the seed set size reached k. This confirms the fact that IMM is better at maximizing k than RTIM in an infinite stream, however, in a finite campaign this is not the case.

Interestingly, the score growth is higher at the beginning of the stream and we observe a logarithmic evolution of the score. In fact, during the stream process finding new influencers is more unlikely since they have already been selected (IMM) or activated by targeted neighbors (RTIM). Since the evolution of size is almost linear (Figure 4), this logarithmic evolution of the seed set score confirms the fact that chosen users bring less influence than previous chosen ones, explained by the sub-modular property of the IM problem.

LiveJournal. This dataset is evaluated with a stream of 4 × 10 5 online users.

Figure 6 shows the evolution of seed set sizes. We can see that IMM finds very few expected influencers and produces 8.5 times fewer seeds for the Uniform stream (resp. 7 for the Log stream) than RTIM. In fact, RTIM targets influencers more easily than IMM. This is explained by the specific distribution of scores we explained in Section 5 with a very slow decreasing of the scores (α = 0.395). It is confirmed by the fact that LiveJournal has a low degree standard deviation and variance. Thus RTIM adapts locally to the users' connection with similar scores while IMM only focuses on pre-chosen seeds.

We can see in Figure 7 that the evolution of seed set scores are really different from the Youtube dataset. Pre-determined seeds have a huge impact on the final seed set score since very few influencers appears in the stream while RTIM has the opportunity to choose a "similar" score in the neighborhood.

We can also see that RTIM obtains a lower seed set score for the Uniform distribution than the Log one. It is due to the fact that RTIM Log fills the seed set more quickly after only 2.38 × 10 5 users in the stream. The impact of the specific distribution of scores of LiveJournal and the fact that users have high mean degrees (with a low variance) give more chances for common users (lower scores) to ease information propagation.

Twitter. Seed sets produced for the Twitter dataset are presented in Figure 8 and9. The stream is composed of 4.17 × 10 6 connected users.

Figure 8 shows that RTIM seed sets evolve very quickly for both Uniform and Log streams. This is due to the huge amount of high score users of the Twitter distribution (B = 1.7 × 10 6 -Section 5), consequently RTIM targets

Stream of users

Seed set score Fig. 9 Seed set score evolution with Twitter any user in the stream that reaches the threshold θ I . On the other hand, IMM evolves more slowly, 10 times less for Uniform (resp. 3.5 times less for Log). RTIM fulfills the ad campaign k = 10, 000 after 4 × 10 6 users in the stream.

In Figure 9 the seed set scores evolve similarly to the Youtube dataset (Figure 5) with close scores for the Log stream, even if the gap is higher due to huge seed set scores (600,000 less). The effect of the high decrease of the influence score (α = 0.99 in Table 1) is observable here where IMM targets high influencers that have sufficient impact to grow rapidly while RTIM targets good influencers to guarantee a global impact in a minimum amount of time.

Conclusions

Our experiments showed that RTIM provides better seed sets score while maximizing the score in a minimum of time while IMM succeeds in maximizing on the whole dataset. The impact of the live stream distribution between Uniform and Log is such that both methods behave clearly better on users with very high degrees (top influencers) however IMM is more sensitive to this setting.

The seed set score curve is logarithmic, this is due to the sub-modular property of the influence maximization problem. Indeed, the more users we add to the final seed the smaller the marginal gain to the overall seed set.

We saw that the distribution of users' influence score has an impact on the effectiveness of both IMM and RTIM methods. First, the decrease of those scores is in favor of RTIM when α is low (LiveJournal) where IMM makes a choice on similar influencers while RTIM targets only available ones. Second, graphs with very high influence scores (induced by B) give RTIM more choices of influencers (even with average scores) and so it fills up the seed set quickly.

Seed-Set Size Guarantee to Maximize Ad Campaigns

Although finding the optimal seed set of size k to maximize the influence of a network is the focus of Influence Maximization, one other issue is to determine in advance the correct value for k. In fact, making the choice of top-k influencers for an ad campaign is crucial in order to give a guarantee of the budget to reach a sufficient number of users on the network.

The choice of the seed-set size will help advertisers to decide how much they wish to influence of social networks. With a guarantee of efficiency, they will determine the impact of the ad campaign in advance and maybe more if the IM algorithm performs better than expected.

The issue is for a given seed set size to guarantee or estimate its influence score; the number of activated users. For instance, on the Twitter network with tens of millions of users, rather than targeting millions of users to reach everyone (100%); we may only want to target tens of thousands of users to reach 25% of the social network.

However, as discussed in the state-of-the-art, finding seed set in a network of N users, there are 2 N total seed sets to test in a brute force approach to search for the optimal seed set S * and by setting k there are ( N k ) combinations. As fat as we know, no existing IM paper has established a method of determined the proper seed set size, nor do existing IM algorithms offer guarantees of finding a seed set capable of covering a given portion of the network.

Expected Seed Set Size

We denote k * p the expected seed set size which influences a sufficient number of users in the graph given by the rate p. Thus k * p is the seed set size that guarantees to reach r × |V | users, where p is a percentage between 0 and 1.

Although the expected k * p , is bounded between 1 and p × |V |, we can infer that k * p is at least equal to the number of connected components in G in order to reach disconnected communities of users.

In order to give k * p , we propose an approach that estimates them. It consists in randomly sampling as many users necessary to influence p × |V | users. We apply propagation models on each sampled user in order to see if he activates his neighborhood or not. The final sample size is a possible seed-set size k ′ p . This random sampling is performed until convergence of the sample size.

Of course, to give a better approximation of k * p , activated users during a sampling cannot be targeted. The number of uniformly chosen users that activate p × |V | users is an estimation k * p . The expected seed-set size is then computed using the average of the results for each iteration, where I is the number of iterations required to reach convergence:

k * p ≈ ∑ i∈I k ′ p (

Preliminary Experiments

To achieve those simulations, we used the Nethept and HepPh [START_REF] Goyal | CELF++: Optimizing the greedy algorithm for influence maximization in social networks[END_REF] graph datasets composed of 15,200 nodes (resp. 12,006) and 61,300 edges (resp. 80,578). We ran experiments using various edge weighting methods, like Weighted Cascade (like in RTIM) as well as edge weights in [0.01, 0.1, 0.3, 0.5, 0.7, 0.8, 0.9] to test the effect of weights on the size of k * p . Reach is the number p and its correspondence in number of users who are activated by a sample.

Tables 5 and6 give results of simulations of k * p for each edge weights strategy according to the given reach p. We can say that p corresponds to the goal of an ad campaign. We can see that the seed set size increases the smaller the edge weights are. For constant weights, when those values are higher than 0.3 reaching at least of half the network requires very low seed set sizes, 360 for Netept where the number of edges is lower than HepPh, and a size of 2 for HepPh which is the number of connected components.

It also shows that the WC weight model requires to target 7,589 users to reach 100% of users in Hep and 5,778 users must be targeted to reach 100% of users in Phy which corresponds to half the number of users in the graph.

It is interesting to notice that most of state-of-the-art algorithms deal with small seed set sizes (mostly 300) in order to make it scalable in terms of computation time. We show in these experiments that it requires far more users to influence at least half the number of users. However, remind that we give an expected seed set size and not the optimal one which means that any IM algorithm must give a higher influence score to be efficient.

Conclusion

Our approach offers an approximation of k * p which would provide a valuable indicator of the budget of an online advertising strategy given how much it would cost to target k * number of users during the campaign. Moreover it gives a threshold of efficiency of IM algorithms.

Conclusion

In this article we have shown that it is possible to answer the influence maximization problem in a real-time bidding environment, which up to now has not been applied to IM algorithms. We have shown that static IM algorithms, such as IMM, can solve this problem in a reasonable time with a seed set of 10,000 influencers. However, RTIM is a solution that competes static IM by using a dynamic IM algorithm based on the local influence of each user. With streams or ad campaign of finite size can outperform static algorithms.

It is important to note that the RTB environment is more complex so than the constraints which we used. For instance, a user who was targeted should not have seen the ad, click on it, or even convert. Indeed, the influence probability for a targeted user is equal to 1. For future works, we propose to extend RTIM to answer more RTB constraints. Contrary to IM algorithms, RTIM could choose to target another user if a previous user who was targeted was not considered as activated. We can therefore, make RTIM much more interactive with dynamic user behavior while static solutions cannot.

In addition, should the graph be updated, it is not difficult to recompute local influence scores, if necessary, or keep targeting users in the live stream. Whereas, static IM needs to recompute the seed set for each new graph.

We can also improve RTIM by adapting the θ I threshold when processing the live stream. In fact, online user behavior, such as periodicity connections, has an impact on the final seed set score.

Fig. 1 Fig. 2

 12 Fig. 1 Influence graph G I with weighted edges

  .54125 1.0 0.4257 0.25 0.54125 ] At t = 2, user u 4 has I[u 4 ] = 1.6932 < θ I . We ignore him because his influence score is too low. At t = 3, for u 3 , I[u 3 ] = 3.7802 > θ I and A[u 3 ] = 0.4257 < θ A , so we target u 3 , and update the activation probability vector:A 2 ⊤ = [ 0.7303 1.0 1.0 1.0 0.7303 ]In the remainder of the stream T , A[u 5 ] = 0.7303 > θ A and u 4 is already targeted (A[u 4 ] = 1.0), so S * = {u 2 , u 3 }. Notice how the final seed set size is less than the maximum seed set size k = 3. It is due to the time-dependent live stream which prevents filling the seed set.

  Fig. Seed set size evolution with Youtube

0 1 • 10 5 2 • 10 5 3 • 10 5 4 Fig. 6 1 • 10 5 2 • 10 5 3 • 10 5 4 Fig. 7

 1234612347 Fig. 6 LiveJournal's seed set size evolution

0 1 • 10 6 2 • 10 6 3 • 10 6 4 Fig. 8 1 • 10 6 2 • 10 6 3 • 10 6 4 • 10 6 0 5 • 10 6 1 • 10 7

 12348123067 Fig. 8 Seed set size evolution with Twitter

Weighted Cascade (WC):

  1. Some define p ∈ [0.01, 0.1] [5,26]. -In this model, e ij =

	1
	|In(vj )|

  Updating activation probabilities

Require: a graph G, nodes u and v, user v's activation probability A[v], the set of user u's neighbors Nu, current path weight p, depth d 1: procedure ActivationScores(G, u, p, d) 2:

Table 2

 2 Zipf-Mandelbrot parameters for graph datasets

	Dataset	B	r 0	α	X 2 -Pearson value
	Youtube	8 × 10 4	11	0.78	0.976
	LiveJournal	1.55 × 10 3	0	0.395	0.971
	Twitter	1.7 × 10 6	6	0.99	0.969

Table 3

 3 Streams' influence score distributions

		Youtube	LiveJournal	Twitter
	Influence score	Uniform	Log	Uniform	Log	Uniform	Log
	1 ≤ I ≤ 2	37.79%	19.92%	37.43%	17.78%	86.33%	80.55%
	2 < I ≤ 5	43.25%	40.69%	36.71%	39.42%	12.02%	16.13%
	5 < I ≤ 10	11.01%	18.88%	17.18%	26.27%	1.13%	2.12%
	10 < I ≤ 100	7.46%	18.71%	8.66%	16.45%	0.48%	1.08%
	100 < I ≤ 1, 000	0.47%	1.71%	0.03%	0.08%	0.04%	0.10%
	1, 000 < I	0.02%	0.10%	0.00%	0.00%	0.00%	0.02%
	Stream size	226,978	399,796	4,165,223

Table 4

 4 Target and update activation probabilities time

		Targeting time	Activation time
		Average	Average	Median	Max
	Youtube	0.5 µs	70.3 ms	6.30 ms	193.4 ms
	LiveJournal	1.0 µs	61.1 ms	6.03 ms	192.0 ms
	Twitter	3.1 µs	85.9 ms	44.5 ms	411.1 ms

Table 5

 5 i) I. Nethept expected Seed Set Sizes k * p according to the reach

		Reach		Seed Set Size by edge weight models
	%	# users	0.01	0.1	0.3	0.5	0.7		0.8	0.9	WC
	100	15,233.00	14,919	12,183	7,768	5,037	3,292	2,669	2,173	7,589
	95	14,471.35	14,159	11,428	7,024	4,320	2,657	2,114	1,724	6,912
	90	13,709.70	13,399	10,680	6,312	3,680	2,162	1,703	1,384	6,331
	80	12,186.40	11,886	9,220	4,982	2,586	1,375	1,044	824	5,318
	70	10,663.10	10,377	7,806	3,777	1,687	758		525	373	4,428
	60	9,139.80	8,874	6,434	2,693	948	275		124	48	3,622
	50	7,616.50	7,378	5,114	1,730	360	26		13	9	2,883
		Reach		Seed Set Size by edge weight models
	%	# users	0.01	0.1	0.3	0.5	0.7	0.8	0.9	WC
	100	12,006.0	10,915	6,817	3,378	1,806	940	655	440	5,778
	95	11,405.7	10,316	6,222	2,792	1,241	450	243	123	5,213
	90	10,805.4	9,720	5,636	2,232	749	118	3	2	4,708
	80	9,604.8	8,534	4,498	1,208	15	2	2	2	3,820
	70	8,404.2	7,360	3,408	339	2	2	2	2	3,057
	60	7,203.6	6,197	2,376	2	2	2	2	2	2,391
	50	6,003.0	5,048	1,408	2	2	2	2	2	1,811

Table 6

 6 HepPh expected Seed Set Sizes k * p according to the reach

Acknowledgements This research is supported and financed by Kwanko. We thank them for their contributions.