Anastasios Giovanidis

Bruno Baynat

Clémence Magnien

Antoine Vendeville

Ranking Online Social Users by their Influence

Keywords: social network, PageRank, influence, model, Markov chain, graph, Twitter, Weibo

We introduce an original mathematical model to analyse the diffusion of posts within a generic online social platform. The main novelty is that each user is not simply considered as a node on the social graph, but is further equipped with his/her own Wall and Newsfeed, and has his/her own individual self-posting and re-posting activity. As a main result using our developed model, we derive in closed form the probabilities that posts originating from a given user are found on the Wall and Newsfeed of any other. These are the solution of a linear system of equations, which can be resolved iteratively. In fact, our model is very flexible with respect to the modelling assumptions. Using the probabilities derived from the solution, we define a new measure of per-user influence over the entire network, the Ψ-score, which combines the user position on the graph with user (re-)posting activity. In the homogeneous case where all users have the same activity rates, it is shown that a variant of the Ψ-score is equal to PageRank. Furthermore, we compare the new model and its Ψ-score against the empirical influence measured from very large data traces (Twitter, Weibo). The results illustrate that these new tools can accurately rank influencers with asymmetric (re-)posting activity for such real world applications.

I. INTRODUCTION

O Nline Social Platforms (OSPs) play a major role in the way individuals communicate with each other, share news and get informed. Today such platforms host billions of user profiles. Although OSPs differ from one another, most of them share a common structure, which allows users to post messages on their Wall and read posts of others on a separate Newsfeed. Most OSPs also permit re-posting from Newsfeed to Wall, in order to facilitate information diffusion. With each re-post (or "share", or "re-tweet") the information becomes visible to a new audience, which may choose to adopt it or not, thus spreading further the post or halting its diffusion. In this way, posts originally generated by some user circulate inside the social network [START_REF] Goel | The structure of Online Diffusion Networks[END_REF]. When the post is gradually adopted by a considerable proportion of the users, we see large cascades of information appear, and we call such posts "viral" [START_REF] Dow | The Anatomy of Large Facebook Cascades, 7th int[END_REF].

Understanding how information spreads through OSPs is very important as it affects the opinion of the population over several subjects of every-day social life. Companies want to determine the set of most influential users ("influencers") for better marketing of their products [START_REF] Kempe | Maximizing the Spread of Influence Through a Social Network[END_REF], and they would like to predict information cascades [START_REF] Cheng | Can cascades be Predicted?, 23rd int. conf. on World wide web (WWW)[END_REF]. Such research is critical also because spreading of influence can have malevolent purposes instead [START_REF] Zannettou | The Web of False Information: Rumors, Fake News, Hoaxes, Clickbait, and Various Other Shenanigans[END_REF], such as the spread of misinformation ("fake news"). To be able to develop defence mechanisms against such social attacks, a concrete mathematical analysis of post diffusion through OSPs is necessary.

Existing literature on the topic has mainly focused on models for opinion dynamics that take only the social graph as input. These include the voter model [START_REF] Holley | Ergodic Theorems for Weakly Interacting Infinite Systems and the Voter Model[END_REF], the SI(R) [START_REF] Newman | Networks: An Introduction[END_REF]Ch. 17], the threshold and cascade models [START_REF] Kempe | Maximizing the Spread of Influence Through a Social Network[END_REF], bootstrap percolation [START_REF] Garetto | Generalised Threshold-Based Epidemics in Random Graphs: the Power of Extreme Values[END_REF], and the DeGroot [START_REF] Degroot | Reaching a Consensus[END_REF] model, among others. In each of these, the social graph structure together with simplified user interaction, has been assumed sufficient to describe the diffusion of a single opinion. However, the authors of the highly cited paper about the "million follower fallacy" [START_REF] Cha | Measuring user influence in Twitter: The million follower falacy[END_REF], argue that graph topological measures alone reveal very little about the true influence of a user in a platform; they use large traces from Twitter to support their claim. The authors in [START_REF] Wilson | Beyond Social Graphs: User Interactions in Online Social Networks and their Implications[END_REF] further use Facebook data to identify real indicators of user interactions, beyond social links. Our paper has the ambition to fill this gap between analysis and data-driven conclusions by introducing a new dynamic model which combines the information over the social graph together with user activity and the OSP structure, in order to explain more accurately how posts from different origins diffuse and compete among each other inside the social platform.

Viral marketing wants to identify users with high social influence [START_REF] Kempe | Maximizing the Spread of Influence Through a Social Network[END_REF]. To this aim, users are ranked based on certain impact measures, which mainly depend on user graph position (e.g. number of follower links), similar to the existing opinion models discussed above. For example, [START_REF] Newman | Networks: An Introduction[END_REF]Ch. 7] presents degree, eigenvector and Katz centrality, as well as PageRank score [START_REF] Brin | The anatomy of a large-scale hypertextual web search engine[END_REF], and [START_REF] Kang | Centralities in Large Networks: Algorithms and Observations[END_REF] alternatives for large-scale graphs. We claim that such measures are not suitable to rank the influence of social users, because they do not include user activity, or OSP structure and they will hence mislead when used to identify "influencers". We propose instead a new Ψ-score to rank users, based on our proposed model.

A. Main Contributions and Paper Structure

Our main contributions are summarised as follows:

• The entire OSP is described as a continuous-time Markov chain. This model is original in the sense that it combines (i) the social graph, with (ii) dynamic user posting and re-posting activity, and incorporates elements of (iii) the platform structure (Walls, Newsfeeds and the Newsfeed suggestion algorithm). The model can include various Newsfeed mechanisms (First-In-First-Out (FIFO), Random, Time-To-Live (TTL)) and user post sharing behaviour. Also, competition among posts to gain the user's attention on the Newsfeed is naturally included. • By analysing the above chain we result in a linear system of equations, which exactly describes the chain's behaviour in steady-state (Theorem 1, Theorem 2). This has as unknown variables the influence of a given user on the Wall and Newsfeed of any other. This system actually consists of the balance equations of posting activity on each Wall and Newsfeed and can be solved for an arbitrary input graph and arbitrary user activity rates. Theorem 3 provides its solution.

• An iterative method (Theorem 4) proposed to compute the system solution facilitates numerical implementation. It allows to implement a sparse algorithm, which scales well as the size of the social graph increases. • The solution gives rise to a new way to rank OSP users by their influence. We call the new ranking metric, the "Ψscore". The performance of our model and the Ψ-score is tested on two large real-world traces from famous social platforms, one from Twitter and another from Weibo. • We prove in Theorem 5 that in the homogeneous activity case where all users post and repost with the same rate a variant of the Ψ-score coincides with PageRank. The implementation code is made available online [15].

The paper is organised as follows. The social platform under study and the performance metrics of interest are introduced in Section II. The Markovian model describing the generic OSP and its balance equations are given in Section III. Here, we explain how these linear equations naturally constitute the Newsfeed and Wall balance equations, and show their exactness and general validity. The system's closed-form solution is provided in Section IV. In the same section we provide an iterative method that is computationally cheap and converges to this solution. In Section V we discuss relations with PageRank. The ranking algorithm based on the Ψ-score and its implementation for large data-traces is detailed in Section VI. Extended numerical experiments using synthetic data in Section VII verify the model's validity and robustness over modelling assumptions. Massive real-world traces from Twitter and Weibo are used to evaluate the Ψranking and the sparse algorithm, in Section VIII. Our Ψranking is further compared for these traces against standard user ranking metrics (number of followers, PageRank, and user posting rate). Conclusions are drawn in Section IX. The proof of exactness (Theorem 1) is made available in the Appendix.

B. Related Literature

In most relevant research on opinion dynamics, individuals are seen as agents whose relation is described by a social graph. Each agent has a certain opinion and at each step this opinion is updated through interaction with his/her direct peers. Such models can be grouped into two general categories.

1) Dynamics with Binary opinions: There are only two possible opinions that agents can take. A large amount of work descends from the voter model [START_REF] Holley | Ergodic Theorems for Weakly Interacting Infinite Systems and the Voter Model[END_REF], where opinion dynamics are based on imitation. The work in [START_REF] Yildiz | Binary Opinion Dynamics with Stubborn Agents[END_REF] studies a variation that includes agents with persisting opinions. For further extensions, see also [START_REF] Varma | Continuous time opinion dynamics of agents with multi-leveled opinions and binary actions[END_REF], [START_REF] Mukhopadhyay | Majority Rule Based Opinion Dynamics with Biased and Stubborn Agents[END_REF]. Another group of work is related to epidemic spread. An agent is "susceptible" when his/her opinion is 0 and becomes "infected" when he/she adopts opinion 1, through social interaction [START_REF] Newman | Networks: An Introduction[END_REF]. In [START_REF] Kempe | Maximizing the Spread of Influence Through a Social Network[END_REF] two opinion update mechanisms are studied: the threshold and the cascade.

2) Dynamics with Continuous opinions: Several works in the literature have inherited and extended the original model of DeGroot [START_REF] Degroot | Reaching a Consensus[END_REF]. In this, each agent updates his/her continuous opinion by forming per-step a weighted linear combination of the current opinions of his/her peers. Variations of this model consider the inclusion of persistent agents [START_REF] Grabisch | Strategic Influence in Social Networks[END_REF]. In [START_REF] Silva | Opinion Manipulation in Social Networks, Network Games, Control, and Optimization[END_REF] this update mechanism is used to formulate and solve an opinion manipulation problem. To account for more realistic social behaviour, the authors in [START_REF] Baccelli | Pairwise stochastic bounded confidence opinion dynamics: Heavy tails and stability[END_REF] consider opinion dynamics where agents interact in pairs only when their opinions are already close.

Data, OSPs, and Cascades: Instead of modelling opinion dynamics, recent works rather use available data to investigate more practically how posts spread within OSPs. The authors in [START_REF] Goel | The structure of Online Diffusion Networks[END_REF] describe diffusion patterns that arise in specific online domains. Data analysis of large Facebook cascades is performed in [START_REF] Dow | The Anatomy of Large Facebook Cascades, 7th int[END_REF]. Interestingly, the authors in [START_REF] Cheng | Can cascades be Predicted?, 23rd int. conf. on World wide web (WWW)[END_REF] propose ways to predict cascade growth using machine learning tools. The insufficiency of using graph-based only information to evaluate user influence is studied in [START_REF] Cha | Measuring user influence in Twitter: The million follower falacy[END_REF] and [START_REF] Wilson | Beyond Social Graphs: User Interactions in Online Social Networks and their Implications[END_REF].

User activity: In [START_REF] Spasojevic | When-To-Post on Social Networks[END_REF] the authors identify user activity as an important control tool for influence maximisation. Making extensive use of datasets, they study the appropriate times for a user to post or re-post in an OSP in order to maximise the probability of audience response. An interesting analytical effort to relate user activity with OSP design and post diffusion is made in [START_REF] Karimi | Smart Broadcasting: Do You Want to Be Seen?[END_REF]. The authors use temporal point processes to model posting and re-posting activity of a user. They highlight the importance of the Newsfeed in post propagation and map user activity to post visibility, building on the idea that a post can be adopted by a follower when it is visible on his/her Newsfeed and not pushed away by competing posts. Their model, however, treats only a single user Newsfeed and does not consider the dynamics of the entire social graph. Furthermore, the dynamics of the Newsfeed list are inaccurately mimicked by a FIFO queue. Another relevant line of research includes [START_REF] Reiffers-Masson | Timelines are Publisher-Driven Caches: Analyzing and Shaping Timeline Networks, SIG-METRICS Perform[END_REF] and [START_REF] Hargreaves | Fairness in Online Social Network Timelines: Measurements, Models and Mechanism Design[END_REF], where the authors study the bias of Facebook's News Feed algorithm. They consider a bipartite graph of a set of users following a set of publishers, and model post activity as Poisson. Newsfeeds are here again approximated by infinite queues with TTL or FIFO service.

Compared to these works, we propose here a more correct and complete OSP model; we accurately model Newsfeeds as lists, we consider here an arbitrary graph of any size and include re-posting -among other realistic features. Finally, we verify our model's validity by large real-world data traces.

II. SYSTEM DESCRIPTION

Let us first describe a generic social network platform, such as Facebook, Twitter or Weibo. A set of users generate and share some content, denoted as posts, through the platform. Each user has a list of followers and a list of leaders. A user can simultaneously be follower and/or leader of others. As a follower, he/she is interested in the content posted by his/her leaders. With each user two lists of posts are associated, namely a Newsfeed and a Wall. A user's Newsfeed is constantly fed by the content that all of his/her leaders post on their Walls. A user's Wall is fed (i) by his/her self-generated posts that draw influence from the "outside world", and (ii) by posts that he/she shares from his/her Newsfeed. Hence, a user's Wall is a list of self-posts and re-posts. The generic social network platform is illustrated in Figure 1.

A. Assumptions on the system and notations

We consider a constant number N of active users, forming the set N . Users are labelled by an index n = 1, . . . , N . We denote by F (n) and L (n) the list of followers and the list of leaders of user n. Without loss of generality, we draw the directed Follower-graph G = (N , E). Each pair of nodes (j, i) ∈ E, corresponds to a directed edge from j to i, when j is a follower of i, i.e., j ∈ F (i) . Such graph points to leaders. We denote by F the N × N adjacency matrix of the Followergraph, whose coefficients are given by: f j,i = 1 {j∈F (i) } , where 1 {.} is the indicator function. We assume that each user n has at least one leader, L (n) = ∅, ∀n. The Leader-matrix is by definition L := F T , so that i,j = f j,i . Note, that the case of self-loops is excluded, i.e. i,i = f i,i = 0, ∀i ∈ N .

The sizes of both Wall and Newsfeed are considered to be constant. We thus fix K ≥ 1 the size of a Wall (total number of posts on the Wall of each user) and M ≥ 1 the size of a Newsfeed. This is reasonable if we assume that only a certain number of most recent posts is considered relevant, and users don't tend to scroll down to access older posting history.

We denote by λ (n) [posts/unit time] the rate with which user n generates new posts on his/her Wall, and by µ (n) the rate with which user n visits his/her Newsfeed and selects one of the M entries to re-post on his/her Wall (note here that each visit implies re-posting). As a result, posts arrive on the n-th Wall with a total rate λ (n) + µ (n) [posts/unit time]. Additionally, we make the assumption that content posted on a users's Wall instantaneously appears on the Newsfeeds of his/her followers. As a result, the input rate of posts in the nth Newsfeed, is j∈L (n) (λ (j) + µ (j) ). Given that the two lists associated per user have fixed size, then with each new entry one element has to be removed from the list and replaced by the new one. For the user activity we require λ

(n) + µ (n) > 0, ∀n.
Finally, any post originally generated by a given user n takes as label the author's index n, and will keep this label throughout its lifespan inside the network.

B. Influence metric of interest

The aim is to estimate the influence of a specific user, say user i, over the entire network. In order to define the metric of interest, we first define the influence of user i on user n, denoted by q (n) i , as the expected percentage of posts of origin i found on the Wall of user n. They obviously satisfy for each Wall n, N i=1 q (n) i = 1, ∀n. We can also interpret q (n) i as the probability that, when picking at random a post from Wall n, this post is of origin i. These performance quantities will

News feed

User n

Wall

Wall

Wall Wall

User i User j

User k

Leaders of user n

Re-post Self-post

λ ( j) +µ ( j) λ (i) +µ (i) λ (k) +µ (k) … … λ (n) µ (n) K M
Fig. 1. The social platform from the point of view of user n.

be the output of the developed models. With the above, we propose the following metric of influence,

Ψ i = 1 N -1 n =i q (n) i ∈ [0, 1] . (1)
It corresponds to the average percentage of posts of origin i on the Walls of any user n = i. The suggested metric averages over all users in the network, but excludes the original user i.

It holds

N i=1 Ψ i < N/(N -1).
Although the defined measure is somewhat natural, we will see that a similar measure

Ψi = 1 N N n=1 q (n) i = (1 - 1 N )Ψ i + 1 N q (i) i , (2)
which does not exclude self-influence is very important, as it coincides with PageRank in the homogeneous activity case λ (n) = λ and µ (n) = µ for all n (see Theorem 5). For this variation N i=1 Ψi = 1. Other metric definitions are also possible. As an example, we could use the probability to find at least one post of label i on the Wall of user n. This is equal to 1 -(1 -q (n) i ) K , where the independence among slots holds for specific user behaviour and post replacement policies (e.g. random selection/eviction) as we will see next. Based on this we can define an alternative metric. In any case, by associating an influence score to each user, the social users can be ranked by decreasing order of their influence. From now on, we will call the expression in (1) (resp. ( 2)) which quantifies the influence of a user in the platform, the Ψ-score (resp. Ψ-score) of user i. In this work we will focus only on this metric, leaving others for future investigations.

III. MODEL

A. Markovian model

The model relies on the following assumptions:

• Poisson arrivals. For any user n the generation of new posts on his/her Wall follows a Poisson process with rate λ (n) and the re-posting activity from his/her Newsfeed follows a Poisson process with rate µ (n) . • Random selection. When a user visits his/her own Newsfeed, we assume that he/she selects at random one of the M entries to re-post on his/her Wall. • Random eviction. A novel entry on the Wall or Newsfeed list will push out an older entry of random position.

Thanks to these assumptions, the resulting models developed in the following are Markovian. Indeed, all inter-arrival times between posts and re-posts are exponential and all choices are probabilistic. The random selection/random eviction policy will be assumed throughout the solution process to derive the Newsfeed and Wall balance equations. Random selection models the case where users pick a post at random from their Newsfeeds, i.e. without order of preference. We will show later that our solution is actually robust to other selection choices, like the newest selection where a user always picks up the object from the top of his/her Newsfeed list (see Section III-G). Random eviction can model platforms which put new posts to Newsfeeds (and less realistically to Walls) in a random order. This could model the Facebook News Feed, where content curation algorithms decide the order of content appearance based on some background machine learning algorithms. In Twitter, however, both Newsfeeds and Walls normally show posts in a First-In-First-Out fashion, so the appropriate policy in this case would be the FIFO eviction i.e., the oldest object is removed from the list and the fresh content is placed at the top. We will show in Section III-G that this eviction policy (and others) satisfies the same balance equations as the random one. Alternative options for the selection and eviction policies will be compared to our solution by simulation in Section VII-B. Generalisation of our solution to realistic user behaviour or Newsfeed mechanisms is an important topic for future research.

B. Detailed model

The full state-description for this system is an N-tuple U := (U (1) , . . . , U (N ) ), where U (n) = (x (n) , y (n) ) is the state of user n (at a given time t, omitted in notations for sake of clarity). x (n) is the state of his/her Newsfeed and y (n) the state of his/her Wall. The random eviction and random selection assumptions allow to describe the systemstate evolution without using information over the order of posts in the lists. Then,

x (n) = (x (n) 1 , . . . , x (n) N ), where x (n) i
counts the number of posts with user-origin i found on the Newsfeed of user n. Similarly, y (n) = (y

(n) 1 , . . . , y (n) N ), where y (n) i
counts the number of posts with origin i found on the Wall of user n.

With all the assumptions described in Section III-A, the stochastic process with full state U is a continuous-time Markov chain model with finite state-space. This process obtains a unique stationary distribution. However, even for very small values of the system parameters the number of states will be enormous, whereas the state of a user's Newsfeed and Wall is coupled with the state of other users. As a result, any numerical method to find the solution, would be computationally intractable. For this reason we first introduce in the next subsections a state aggregation and a simple decoupling of the state-space that considerably reduce the solution complexity. Following that, we prove that the resulting balance equations we find are exact for the detailed model.

It is important to understand where the coupling between states of different users appears in the detailed model, before presenting the aggregated and decomposed model. Consider user n and focus on label i posts. A leader k of user n will re-post from his/her own Newsfeed to his/her own Wall a post of label i with probability x (k) i /M , due to the random selection policy. This post will appear immediately on the Newsfeed of user n, thus changing its state x (n) . Hence, the evolution of the state of user n depends not only on his/her own current state and on his/her own activity, but also on the current states of his/her leaders (in this example x (k) i ). Note here that the Markov process which describes the evolution of system state U is non-reversible [START_REF] Kelly | Reversibility and Stochastic Networks[END_REF]. To see this, we can use a simple example, given in Appendix A.

C. State aggregation

To simplify the solution process we first need to describe the state-space in a more compact way. To do so, we focus on posts from a particular user i and calculate the influence of this user i on the entire network. Of course, one can successively apply the technique to all i = 1, . . . , N in order to determine eventually the influence and Ψ-scores of everyone.

The state aggregation is as follows. On all N Walls and N Newsfeeds we consider only two types of posts; those of origin i, and those issued from other users labelled as -i.

In other words we aggregate the effect of all users except i. Remember that the detailed state of user's n Newsfeed was the N -dimensional vector x (n) . By applying the state-aggregation this is now described by (x

(n) i , x (n)
-i ), whose sum is equal to the Newsfeed size M , so that x

(n) -i = M -x (n)
i . As a result, the state of the Newsfeed of user n is reduced to a single integer

x (n) = x (n) i
with values ranging from 0 to M . Similarly, the state of user n's Wall becomes also 1-dimensional

y (n) = y (n) i
with values ranging from 0 to K.

D. Decomposition by mean-field approximation

After state aggregation, the states (x

(n) i , y (n)
i ) of different users n are always coupled among each other. We decompose here the state-description, to obtain 2N independent 1dimensional Markov Chains, each one associated with the Newsfeed and the Wall of a user. To do so, we use a "mean-field" approximation [START_REF] Gast | Refinements of Mean Field Approximation[END_REF]: for a given user n, the state transitions of his/her Newsfeed and Wall will still be a function of his/her own current state and activity, as well as the activity of all of his/her leaders. But they will not depend anymore on the current Newsfeed and Wall states of the user's leaders x More precisely, let us consider user n. We denote by p (n) i the steady-state probability for a post on Newsfeed n to be of label i, i.e., to originate from user i. Similarly, we have already defined in Section II-B q

(n) i
as the steady-state probability for a post on the Wall of user n to be of label i. These quantities for n = 1, . . . , N are the model unknowns after aggregation. Note that these probabilities are actually the ergodic means of the related user states, i.e., p

(n) i = E[ X (n) i M ] and q (n) i = E[ Y (n) i K ].
We distinguish here between the Newsfeed and Wall of user i (particularized user) and the Newsfeeds and Walls of users n = j = i. Consider the Newsfeed of user j; the state x (j) i can evolve as follows:

x (j) i f (j) + (x (j) i ) -→ x (j) i + 1 & x (j) i f (j) -(x (j) i ) -→ x (j) i -1.
In the above f (j)

+ and f (j)

-are the transition rates between the states, respecting the range 0 to M . The rate f

(j) + (x (j) i ) is f (j) + =   λ (i) 1 {i∈L (j) } + k∈L (j) µ (k) p (k) i   M -x (j) i M . (3)
Indeed, λ (i) is the rate with which user i generates a new own post on his/her Wall, post that instantaneously appears on the Newsfeed of user j, if i ∈ L (j) . A post of label i can as well appear in the Newsfeed of j through re-posting. This occurs when one of the j's leaders visits his/her own Newsfeed and re-posts a label i post on his/her own Wall. For leader k such event occurs with rate µ (k) x (k) i M , following the random selection policy. We propose that µ (k) p (k) i is an estimation of this rate and this is where the "mean-field" approximation that decomposes the state-space lies. Finally,

M -x (j) i M
is the probability that an incoming post (with label i) replaces an old post of label -i, by the principle of random eviction.

The rate f

i ) is defined in a similar manner as

f (j) -=   k∈L (j) ,k =i λ (k) + k∈L (j) µ (k) (1 -p (k) i )   x (j) i M . (4)
As a consequence, the rate transitions from x (j) i to +1 or -1 depend only on the current state of Newsfeed j and not that of its leaders. We can thus describe x (j) i as a 1-dimensional Markov Chain. Similar arguments hold for the Newsfeed state of user n = i. These simple Markov Chains are shown at the top part of Figure 2. From the stationary probabilities of the chain for Newsfeed n, we can derive the steady-state probabilities p

(n) i : p (n) i = M x (n) i =0 π(x (n) i ) x (n) i M . (5)
Observe that the unknown probabilities p

(n) i
depend on the steady-state solution of the 1-dimensional Markov chain, whose transition rates depend in their turn on the probabilities p (.) i (see e.g. ( 3)). As a result, the probabilities p (n) i result from the solution of a fixed-point problem.

For the Walls of users we can follow a similar process. In the Wall of user j = i, the state y (j) i can evolve as follows:

y (j) i g (j) + (y (j) i ) -→ y (j) i + 1 & y (j) i g (j)
-(y

(j) i ) -→ y (j) i -1.
In the above g

+ and g

(j)
-are the transition rates between the states, respecting the range 0 to K. The rate g

(j) + (y (j) i ) is g (j) + (y (j) i ) = µ (j) p (j) i K -y (j) i K . (6)
Indeed, the state of posts i on the Wall of user j = i can only evolve by reposting. Such posts enter the Wall j with average rate µ (j) p (j)

i , because the user re-posts with rate µ (j) and has p (j) i probability to choose posts of label i, due to random selection. This is again the "mean-field" approximation. The incoming post will replace an old post of label -i with probability

K-y (j) i K due to random eviction. The corresponding rate g (j) -(y (j)
i ) is defined in a similar fashion. Hence, the state evolution of posts i on the Wall of user j can be described by an independent 1-dimensional Markov Chain. We proceed similarly for the Wall of user n = i. These simple Markov chains are illustrated in detail at the bottom part of Figure 2. From the stationary probabilities of the chain associated with user's n Wall, we can derive the q

(n) i : q (n) i = K y (n) i =0 π(y (n) i ) y (n) i K . (7)
Note from ( 6) and Fig. 2 that the Wall probabilities q

(n) i do not result from a fixed-point solution, because they are directly expressed as a function of the Newsfeed probabilities p (n) i .

E. Derivation of the balance equations

Here we further develop and simplify the equations ( 5) and [START_REF] Holley | Ergodic Theorems for Weakly Interacting Infinite Systems and the Voter Model[END_REF]. We first consider the Markov chain associated with the Newsfeed of user n = j = i (see top right part of Fig. 2). To solve this birth-and-death process we define the quantity

τ j := λ (i) 1 {i∈L (j) } + k∈L (j) µ (k) p (k) i k∈L (j) ,k =i λ (k) + k∈L (j) µ (k) (1 -p (k) i )
.

Note that τ j depends on all probabilities p (k) i

for k ∈ L (j) . The steady-state probability of the Markov chain associated with the Newsfeed of user j can then be derived using τ j (see [27, Section 1.3, eq.1.9] and transition rates in Fig. 2):

π(x (j) i ) = π(0) M x (j) i τ x (j) i j ,
where π(0) is obtained by normalization (thanks to the Binomial formula):

π(0) = 1 (1 + τ j ) M .
Then, applying this result in (5) we get:

p (j) i = 1 (1 + τ j ) M M m=1 M m τ m j m M m :=m-1 = τ j (1 + τ j ) M M -1 m =0 M -1 m τ m j Binomial = τ j 1 + τ j .
By replacing the expression for τ j , we obtain the following very simple expression for posts of origin i in the Newsfeed of user j. The fixed-point is now visible: Following a similar reasoning, we get for the Newsfeed of any user n = i, the following equation:

  k∈L (j) λ (k) + µ (k)   p (j) i = λ (i) 1 {i∈L (j) } + k∈L (j) µ (k) p (k) i . ( 8
) User i y i (i) y i (i) y i (i) +1 y i (i) +1 y i (i) -1 y i (i) -1 K 0 … … λ (i) + µ (i) p i (i) ( ) K -y i (i) K µ (i) 1-p i (i) ( ) y i (i) K Wall User j ≠ i x i (i) x i (i) x i (i) +1 x i (i) +1 x i (i) -1 x i (i) -1 M 0 … … Newsfeed µ (k ) p i (k ) k∈L ( i ) ∑ M -x i (i) M λ (k ) + µ (k ) 1-p i (k ) ( ) ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ k∈L ( i ) ∑ x i (i) M y i ( j) y i ( j) y i ( j) +1 y i ( j) +1 y i ( j) -1 y i ( j) -1 K 0 µ ( j) p i ( j) K -y i ( j) K λ ( j) + µ ( j) 1-p i ( j) ( ) ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ y i ( j) K … … Wall x i ( j) x i ( j) x i ( j) +1 x i ( j) +1 x i ( j) -1 x i ( j) -1 M 0 λ (i) 1 i∈L ( j ) { } + µ (k ) p i (k ) k∈L ( j ) ∑ ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ M -x i ( j) M λ (k ) k∈L ( j ) k≠i ∑ + µ (k ) 1-p i (k ) ( ) k∈L ( j ) ∑ ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ x i ( j) M … … Newsfeed
  k∈L (i) λ (k) + µ (k)   p (i) i = k∈L (i) µ (k) p (k) i . (9)
As a result, the set of N equations ( 8) and ( 9) constitute the new equations of the fixed point, whose solution gives the required Newsfeed probabilities p

(n) i for n = 1, . . . , N .
In the same fashion, the steady-state probabilities for the Wall can be directly derived from the steady-state probabilities for the Newsfeed through the following equations:

λ (j) + µ (j) q (j) i = µ (j) p (j) i , (10)
λ (i) + µ (i) q (i) i = λ (i) + µ (i) p (i) i . (11)

F. Explanation of the balance equations

Interestingly, equations ( 8)-( 9) and ( 10)-( 11) allow for a simple intuitive interpretation: they balance the incoming and outgoing flow of posts of origin i on each Newsfeed and Wall list. More precisely, equation ( 8) equalizes the incoming rate and the outgoing rate of posts of origin i in the Newsfeed of user j (for j = i). Here, k∈L (j) λ (k) + µ (k) is the average number of posts per unit of time that enter the Newsfeed of user j. From the random eviction policy, each of these arriving posts replaces a post of origin i with probability p (j) i . Indeed, by assuming that post and re-post processes are Poisson, the PASTA property holds which tells us that arriving posts see the Newsfeed in steady-state. As a result, the left-hand side of equation ( 8) is just the outgoing rate of posts of origin i in the Newsfeed of user j. Now looking at the right-hand side of this equation, µ (k) is the average number of posts per unit of time that arrive on the Newsfeed of user j because a leader k of j reposts something on his/her Wall. Each of these posts is of origin i with probability p (k) i , due to the random selection policy in Newsfeeds. In addition, if i is a leader of j, the λ (i) self-posts of i per unit of time also appear on the Newsfeed of j. As a result, the right-hand side of equation ( 8) is the incoming rate of posts of origin i in the Newsfeed of user j.

Similarly, equation ( 9) equalizes the incoming rate and the outgoing rate of posts of origin i in the Newsfeed of user i. The only difference is that a new post that has just been created by i does not appear on his/her own Newsfeed.

Equation ( 10) equalizes the incoming rate and the outgoing rate of posts of origin i in the Wall of user j. Indeed λ (j) +µ (j) is the average number of posts per unit of time that enter the Wall of user j. Each of these posts replaces a post of origin i with probability q (j) i , due to the random eviction policy in Walls and the PASTA property. As a result, the left-hand side of equation ( 10) is the outgoing rate of posts of origin i from the Wall of user j. Obviously, µ (j) p (j) i is the average number of posts of origin i per unit of time that arrive on the Wall of user j, due to the random selection policy in Newsfeeds.

Similarly, equation [START_REF] Cha | Measuring user influence in Twitter: The million follower falacy[END_REF] equalizes the incoming and outgoing rate of posts of origin i on the Wall of user i. We just have to add at the incoming rate the λ (i) self-posts per unit of time from i.

The balance equations involve the expected percentage of posts on the Newsfeeds and Walls of users and have been derived based on an approximation (mean-field) on the rates of state transition. We prove in the following Theorem that, under some tighter assumptions, these equations are actually exact. However, note here that the detailed distribution of the number of posts on Newsfeeds and Walls π(x), π(y), from the birth-and-death processes in Fig. 2 are an approximation.

Theorem 1 (Exactness). For Poisson posting and re-posting activity with λ (n) , µ (n) > 0, ∀n ∈ N , strongly connected Follower graph and the random selection / random eviction policy, the equations ( 8)-( 9) and ( 10)-( 11) describe exactly the original detailed model in steady-state.

The proof can be found in Appendix B, and is based on the conservation law of posts in the Newsfeed and in the Wall of each user.

The balance equations further give an important structural property of the steady-state solution as a side product.

Corollary 1 (Insensitivity in list size). In view of ( 8)-( 9) and ( 10)-( 11), the steady-state probabilities to find posts from user i on the Newsfeed of any user n (p (n) i , n = 1, . . . , N ) as well as on the Wall of any user n (q (n) i , n = 1, . . . , N ), depend neither on the size M of the Newsfeed, nor on the size K of the Wall.

G. Alternative selection and eviction policies

Looking at the model through the balance equations enables us to relax random selection and random eviction assumptions, and introduce alternative policies. We will show now that a number of different policies satisfy the same balance equations, thus granting generality to the result.

1) Random selection / FIFO eviction: Let us modify the eviction policy in both Newsfeeds and Walls, and replace "Random" by a more realistic FIFO policy: now, a new post enters at the top of the list and evicts the oldest post out of the list. To do so, we define φ (j) i as the new outgoing rate of posts of origin i in the Newsfeed of user j. This will replace the left-hand side of eq. ( 8)). From Little's law,

φ (j) i = X (j) i /T (j) i , (12)
where

X (j) i
is the average number of posts of origin i in the Newsfeed of user j, and T (j) i is the average time a post of origin i stays in the Newsfeed of user j.

The total arrival rate of posts in the Newsfeed of user j is k∈L (j) λ (k) + µ (k) . The mean time between two successive arrivals in the Newsfeed of user j is thus the inverse of this quantity. As a result any post arriving in the Newsfeed of user j will stay on average M times this mean value:

T (j) i = M k∈L (j) λ (k) + µ (k) . (13) Since X (j) i = M p (j) i
per definition, we conclude that:

φ (j) i = p (j) i k∈L (j) λ (k) + µ (k) [FIFO evict], (14)
which has the same expression as the left-hand side of equation [START_REF] Newman | Networks: An Introduction[END_REF]. In other words, when we replace the "Random" eviction policy by the FIFO eviction policy in the Newsfeed, equation [START_REF] Newman | Networks: An Introduction[END_REF] does not change. We can easily show by a similar reasoning that equations ( 9), ( 10) and ( 11) remain also unchanged under the FIFO eviction policy. We now show that the set of balance equations remain the same also if we choose a TTL (Time-To-Live) eviction principle [START_REF] Hargreaves | Fairness in Online Social Network Timelines: Measurements, Models and Mechanism Design[END_REF], [START_REF] Gast | TTL approximations of the cache replacement algorithms LRU(m) and h-LRU, Perform[END_REF]. Here, each post stays at the Newsfeed for a fixed amount of time T before leaving. In this case, the size of the list is not constant M , but rather varies over time. By Little's law, the mean Newsfeed size is equal to

M (j) = T k∈L (j) (λ (k) + µ (k) ), (15)
where again

k∈L (j) (λ (k) + µ (k)
) is the total arrival rate of posts in Newsfeed j. Then in [START_REF] Wilson | Beyond Social Graphs: User Interactions in Online Social Networks and their Implications[END_REF] we substitute X

(j) i = M (j) p (j) i and T (j) i = T , to get φ (j) i = p (j) i k∈L (j) λ (k) + µ (k) [TTL evict]. (16)
2) Newest selection / Random eviction: We come back to our original model with a "Random" eviction policy, and where Newsfeeds are of limited size M and Walls are of limited size K. We have proved in Theorem 1 that the steadystate probabilities p (j) i and q (j) i , being solutions of the system (8)-( 11)) depend neither on M nor on K. In order to change the selection policy from "Random" to "Newest", we just have to take M = 1. Indeed, when the size of Newsfeeds is unitary, the "Random" selection will necessarily choose the newest (i.e. latest, freshest) entry of the Newsfeed to repost on the Wall of a user. As a result, the system (8)-( 11) remains true also under the "Newest" selection policy.

Further extensions that incorporate user preferences towards posts of specific origins, or that consider user engagement metrics are very interesting topics for future research. Since the balance equations are derived based on the conservation law of posts on Newsfeeds (see Theorem 1 and its proof in the Appendix) the latter can be the basis to analyse various alternative post selection and eviction policies.

IV. CLOSED FORM SOLUTION

A. Linear system

We can re-write ( 8)-( 9) and ( 10)- [START_REF] Cha | Measuring user influence in Twitter: The million follower falacy[END_REF] for posts with label i in a compact form and summarize our findings as follows.

Theorem 2 (Linear System). The unknown column vectors p i := (p

(1) i , . . . , p (N ) i
) T and q i := (q

(1) i , . . . , q (N ) i
) T are the solution of the following linear system

p i = A • p i + b i (17) q i = C • p i + d i . (18)
In the above, A and C are N × N matrices independent of i, whereas b i and d i are N-column vectors that depend on i. Hence, a standard linear system should be resolved for each i. The entries of the above matrices and vectors are summarised in Table I. It is interesting to note that a j,j = 0 for all j, b i,i = 0, C is diagonal, and also there is a unique positive d j,i entry for i = j.

TABLE I ENTRIES FOR THE MATRICES/VECTORS OF THE LINEAR SYSTEM.

A a j,k :=

µ (k) ∈L (j) (λ ( ) +µ ( ) ) 1 {k∈L (j) } b i b j,i := λ (i) ∈L (j) (λ ( ) +µ ( ) ) 1 {i∈L (j) } C c j,k := µ (j) λ (j) +µ (j) 1 {j=k} d i d j,i := λ (i) λ (i) +µ (i) 1 {j=i}
The matrix A is non-negative. In addition, it is row substochastic, meaning that the sum of all its rows is less than or equal to 1, with at least one row sum strictly less than 1 (if we reasonably assume that at least one user injects selfposts). Another interesting property is that A is a weighted version of the Follower-matrix F = L T , so that if 1 {j∈F (k) } = 1 {k∈L (j) } = 0 ⇒ a j,k = 0. There are cases however where j follows , but a j, = 0 in the matrix A, because µ ( ) = 0.

Hence, users that never re-post from their Newsfeed alter the possibilities of post propagation in the graph. This is why we call A, the propagation matrix.

B. Closed-form solution Theorem 3 (Solution). If the spectral radius ρ(A) < 1, then the solution of the linear system ( 17)-( 18) is unique,

p i = (I N -A) -1 b i (19) q i = C (I N -A) -1 b i + d i . ( 20
)
Proof. This results directly from [29, Chapter 6, Lemma 2.1], that we also include in Appendix C.

An interesting observation is that the inverse (I N -A) -1 involved in the derivation of p i (relation [START_REF] Grabisch | Strategic Influence in Social Networks[END_REF]) is independent of i. Thus, in the solution process the inverse should be calculated only once, and then applied to the expressions in ( 19)-( 20) for labels i = 1, . . . , N .

We would like to know under which conditions a solution to the linear system exists, in other words when does ρ(A) < 1 holds true, based on the specific structure of the non-negative matrix A given in Table I. We show the following property. (cs1) When λ (n) > 0, ∀n, then ∀j and k ∈ L (j) , a j,k < µ (k) / ∈L (j) µ ( ) , so that r(j) < 1, ∀j. Then the matrix is strictly sub-stochastic, and ρ(A) ≤ max N j=1 r(j) < 1. (cs2) In this case, suppose the length of a particular cycle is γ > 1 and the participating nodes are n 1 , . . . , n γ . Then at least one row sum r(j) < 1, j ∈ {n 1 , . . . , n γ }. By direct application of the Al'pin, Elsner, van den Dreissche bound [31, Theorem A], we conclude that ρ(A) < 1. An additional condition for this bound is that r(j) > 0, ∀j, which is satisfied when L (j) = ∅, ∀j ∈ N and not all leaders of some user have µ (k) = 0. Remark 1. A special instance of (cs2) is when A is irreducible and λ (j) > 0 for at least one j ∈ N .

C. Fixed-point algorithm

For large N it can be practically very difficult to calculate the inverse (I N -A) -1 . A different way to proceed in order to solve the system ( 17) is to use an iterative approach.

Theorem 4. For the two cases of Lemma 1 and any initialization vector p i (0), the discrete-time linear system [START_REF] Baccelli | Pairwise stochastic bounded confidence opinion dynamics: Heavy tails and stability[END_REF] converges towards the fixed-point solution [START_REF] Grabisch | Strategic Influence in Social Networks[END_REF] when t → ∞.

p i (t) = A • p i (t -1) + b i . ( 21
)
Fig. 3. Example graph with adjacency matrix: the edge j → i here means that j refers to i (PageRank) or that j follows i, i.e. 1 {j∈F (i) } = 1 {i∈L (j) } = 1 (Newsfeed), and we set i,j = 1 in the leader matrix L.

The rate of convergence is the spectral radius of A, ρ(A),

min j=1...N r(j) ≤ ρ(A) ≤ max j=1...N r(j), (22)
where r(j) =

∈L (j) µ ( ) / ∈L (j) (λ ( ) + µ ( ) ).
In the homogeneous case where µ ( ) = µ, λ ( ) = λ ∀ , it holds ρ(A) = µ λ+µ . Proof. We first write p i (t) as a function of p i (0) and t,

p i (t) = A t p i (0) + t-1 n=0 A n b i .
We need to find the limiting value p i := lim t→∞ p i (t). For the two cases in Lemma 1 we have ρ(A) < 1, so that from [30, pp.137-138, or Theorem 5.6.12] it holds A ∞ := lim t→∞ A t = 0. Additionally, from [29, Chapter 6, Lemma 2.1] (see Lemma 2) the limit of the matrix series for t → ∞ converges to (I N -A)

-1 . Hence, the iteration converges to the solution [START_REF] Grabisch | Strategic Influence in Social Networks[END_REF], and is independent of the initialisation p i (0). The error is defined as (t) = p i (t) -p i , where p i solves [START_REF] Varma | Continuous time opinion dynamics of agents with multi-leveled opinions and binary actions[END_REF]. Then from [START_REF] Baccelli | Pairwise stochastic bounded confidence opinion dynamics: Heavy tails and stability[END_REF] we get (t) = A t (0), which tends to zero with rate that is dominated by the largest eigenvalue. From ([30, Theorem 8.1.22]) min N j=1 r(j) ≤ ρ(A) ≤ max N j=1 r(j), where r(j) is the sum of row j.

Note that once the Newsfeed-vector p i := lim t→∞ p i (t) has been obtained, the Wall-vector q i can be calculated from relation [START_REF] Mukhopadhyay | Majority Rule Based Opinion Dynamics with Biased and Stubborn Agents[END_REF]. The influence score for user i, i.e. the value Ψ i is then directly derived from [START_REF] Giovanidis | Performance Analysis of Online Social Platforms[END_REF]. We need to solve for all i's to derive all scores {Ψ i } N i=1 , however notice that the matrices A and C are the same for all users, and only b i and d i differ.

V. EXAMPLE AND RELATION WITH PAGERANK

In this section we show and prove that PageRank [START_REF] Brin | The anatomy of a large-scale hypertextual web search engine[END_REF] is a special case of the Ψ-score variant in (2), for uniform activity of all users. As an illustrative example, we use the toy-graph in Fig. 3, which is strongly connected. For notation, columnvector e has 1's in all entries, and column-vector e i has all entries 0, except position i with value 1. PageRank: The famous PageRank score π (column-vector) is calculated [START_REF] Whang | Scalable Data-Driven PageRank: Algorithms, System Issues, and Lessons Learned[END_REF] based only on the graph topology,

π = βWπ + (1 -β) e N . (23)
Here, W = LD -1 out , where D out is a diagonal matrix with nonzero entries the out-degrees of the nodes [deg [START_REF] Giovanidis | Performance Analysis of Online Social Platforms[END_REF] out , . . . , deg

(N ) out ].
Its inverse multiplies on the right the leader-adjacency matrix L, so that the matrix LD -1 out is column-stochastic, i.e. the sum of all columns is 1. For the toy example in Fig. 3,

W =     0 1/2 1 0 1/3 0 0 1/2 1/3 0 0 1/2 1/3 1/2 0 0     .
With probability (1 -β) the random surfer teleports from his/her current state, to any other state chosen uniformly at random. This trick is useful to avoid dead-ends. We can solve iteratively [START_REF] Karimi | Smart Broadcasting: Do You Want to Be Seen?[END_REF] Ψ-score: For the sake of comparison, we let all λ (i) = λ and µ (i) = µ, for i = 1, . . . , N . Furthermore, let us choose values of µ and λ such that β = µ/(λ + µ). In this homogeneous case, only the graph topology is important and the Newsfeed system of equations in ( 17) is written for row-vector p T i as

p T i = βp T i W + (1 -β)W (i,:) , ∀i ∈ N . ( 24
)
Here, the unknown row vector multiplies W from the left. Note that A = βW T in [START_REF] Varma | Continuous time opinion dynamics of agents with multi-leveled opinions and binary actions[END_REF]. Furthermore, the teleportation is towards the row-vector W (i,:) , where W (i,:) is the i-th row of the matrix W. There are N such systems of equations ( 24), one for each node i ∈ {A, B, C, D}. For each user i, we can calculate his/her influence column-vector p i on the Newsfeed of every other user, by power iteration as in [START_REF] Baccelli | Pairwise stochastic bounded confidence opinion dynamics: Heavy tails and stability[END_REF], and gather our findings in matrix P. Having calculated p i for each node, we replace in [START_REF] Mukhopadhyay | Majority Rule Based Opinion Dynamics with Biased and Stubborn Agents[END_REF], which in our homogeneous case becomes

q i = βp i + (1 -β)e i , (25)
so we get the influence of i on every Wall in the network. All column-vectors of Wall-influence are grouped in matrix Q. Using the Ψ-score definition in (2), Ψi = N n=1 q

(n) i /N for origin i, we average over all entries of column i in the Q matrix including self-influence at the diagonal. Repeating for i ∈ {A, B, C, D} we get ΨA , ΨB , ΨC , ΨD = [0.331, 0.223, 0.223, 0.223], equal to the PageRank π score.

Theorem 5. In the homogeneous case of uniform user activity with λ (n) = λ and µ 2) is PageRank π i with damping factor β = µ λ+µ ∈ (0, 1) (teleportation 1 -β = λ λ+µ ). Proof. To show this, let us first write the homogeneous activity Newsfeed and Wall equations of all users in matrix form, using the influence matrices P and Q. From ( 24) and ( 25)

(n) = µ , ∀n ∈ N , the score Ψi = N n=1 q (n) i /N from (
P T = βP T W + (1 -β)W, (26)
Q T = βP T + (1 -β)I, (27)
where as discussed W := β -1 A T from Table I. Using [START_REF] Kelly | Reversibility and Stochastic Networks[END_REF] we can derive the score column-vector Ψ defined in (2)

Ψ = 1 N Q T e = β 1 N P T e + (1 -β) 1 N e. ( 28
)
We solve (26) over P T and do the following manipulation

P T = (1 -β)W(I -βW) -1 ( * ) = (1 -β)W ∞ t=0 (βW) t = 1 -β β ∞ t=1 (βW) t = 1 -β β (I -βW) -1 -I , (29)
where (*) uses Lemma 2 in Appendix, because βW (the matrix A T ) is column sub-stochastic. Replacing the above in (28)

Ψ = (1 -β) 1 N (I -βW) -1 -I e + (1 -β) 1 N e. = (1 -β)(I -βW) -1 e 1 N ⇒ Ψ = βW Ψ + (1 -β)e 1 N . (30)
The last equation is the same as PageRank in [START_REF] Karimi | Smart Broadcasting: Do You Want to Be Seen?[END_REF].

Since activity is homogeneous here, then µ/(λ + µ) is the probability that some user reposts and λ/(λ + µ) the probability that some user posts. Then the score of a user is fed from the reposts of its direct followers and its own self-posts.

The greatest powers of our method and the Ψ-score, however, are revealed when ranking users with asymmetric activity.

• Suppose a scenario with the same toy-graph and activities µ = 2 for all users re-posting, but λ A = λ B = λ D = λ = 0.105, λ C = 3λ = 0.315 for posting. Then λ, µ are again such that µ/(λ + µ) = β = 0.95, but user C posts with 3-times higher frequency than the others. After solving the system (17)-( 18 . This behaviour of user C results again in him/her ranking higher than the other users, by not sharing anything on his/her Wall.

From the above examples, we can safely conclude that the Ψ-score is much more expressive than PageRank: it incorporates the user posting and reposting activity in an appropriate way in the score. This is shown more emphatically in Section VIII for real world traces, where the user Ψscores are quite different from other scores in practice (e.g. PageRank, #Followers). For its calculation one derives the p i and q i vectors, which contain detailed information of the influence of i on any Newsfeed and Wall in the network. To obtain such fine grained information, we pay in complexity; to derive the Ψ i -score for user i using Theorem 4 every iteration in (21) includes a weighted matrix-vector multiplication plus a vector addition to find p i . Such iteration is very similar to the power method that calculates the PageRanks. Since we need to solve the system for every user i = 1, . . . , N , to calculate all the Ψ-scores requires N -times the complexity that PageRank would need. Other algorithms with lower complexity or faster convergence that work for PageRank (see e.g. [START_REF] Whang | Scalable Data-Driven PageRank: Algorithms, System Issues, and Lessons Learned[END_REF]) could also apply for the Ψ-score. This is a very interesting topic for future investigations.

VI. IMPLEMENTATION AND NUMERICAL ASPECTS

For the numerical implementation we coded the following programs, that we make available in [15]: (A) an algorithm to derive the Ψ-rank for each user from the balance equations of the model; two versions are coded, one for small OSP sizes and a sparse one for real-world sizes, (B) a discrete-event simulator, to simulate over time the behaviour of an OSP with arbitrary input traffic and user/platform policies, and (C) an emulator, which takes a real data-trace as input and outputs empirical Ψ-scores.

A. Ψ-ranking by the model

We remind the reader that the Ψ-score of user i's influence in the social platform was introduced in (1), as a function of the q (j) i 's (j = 1, . . . , N ), i.e. the steady-state Wall probabilities. These values have been derived in closed form, through the balance equations. The two methods to calculate them, one using Theorem 3 with matrix inversion and a second using Theorem 4, are coded in [15] for small OSP sizes. The algorithm takes as input the vector of all posting and reposting rates λ = (λ 1 , . . . , λ N ) and µ = (µ 1 , . . . , µ N ), as well as the graph G and outputs the Ψ-scores.

Since the size N of real-world social graphs is of the order of millions of users, an efficient algorithm that runs in reasonable time-scales is necessary to calculate these scores for all users in the platform. A tedious matrix inversion (I N -A) -1 is not recommended for such cases, as it is computationally very expensive -typically of the order of O(N 3 ).

We have programmed here another algorithm to calculate the Ψ-score in large graphs, which implements a sparse version of the iterative solution introduced in Theorem 4. It computes first the p i 's by involving at each iteration a matrix-vector multiplication A • p i and then a vector addition b i , which take into account the sparsity of both the propagation matrix A, and each vector b i . Sparsity comes from the fact that the number of leaders and followers of any user i is very small compared to the total population N ; as a second step -to calculate the q i 's we also use the fact that C is diagonal and sparse, and d i has a single non-zero element. We can break the user set in subsets of users and parallelise the computational process on several machines, because solving for the influence of one user i does not affect the process of solving for others.

B. Discrete-event simulator

Additionally, we have developed our own discrete-event simulator (also available in [15]) to validate the mathematical analysis through simulation, and to evaluate the robustness of the modelling assumptions presented in Section III-A against alternative traffic and policies. Unlike the code in the previous section VI-A which solves the model's balance equations, the simulator precisely implements the behaviour of the generic OSP over time as described in Section II: i) The global state description consists of dynamic lists (of length K for Walls and M for Newsfeeds); ii) A variety of selection and eviction policies are implemented ("Random", in a first phase, and "Newest", FIFO, "Popular" later to evaluate robustness); iii) Self-and re-posts can be generated according to Poisson or other processes. As such, the simulator does not decouple the state space, does not estimate average probabilities, and does not rely on Markovian assumptions. For each simulation we set M = 20 and K = 10 and ran long enough simulations to reach the steady-state with small confidence intervals. More specifically, in all experiments, we let the simulator run for a total of 300 000 events (self-and re-posts).

C. Emulator (Trace-based empirical influence)

Finally, we have coded the emulator, which uses a real datatrace as input from Twitter, Weibo or other platform. The emulator differs from the simulator in the sense that it does not simulate the post propagation or specific policies, rather it directly outputs numerical values of influence, as read from the post sequence in the trace. To do so, we first pre-process the available data trace, so that each line of the input is just the quadruple [PostID, TimeStamp, UserID, RePostID], where the fourth entry is -1 in case of an original post, else the PostID of the original post which was reposted. The program calculates the influence of each user i on another user j directly from data q emu [i][j], as the percentage of time that posts with origin i are found on the Wall of user j. With these empirical values we derive the empirical score Ψ emu i for all users in the trace. The empirical influence is determined by the Wall occupancy periods divided by the total duration of the data-trace, and no further information about the social graph is necessary. We provide the emulator code in [15].

VII. NUMERICAL EVALUATION

A. Influence of graph topology and posting rates

In this section we evaluate the performance of our analytical model and the Ψ-score of influence for various types of graphs:

• Binary Tree: We use a perfect undirected binary tree of depth 9, which includes N = 1023 nodes. Specifically, the 0-node is the root, and there are 512 leaves at level-9. • Scale-free: We build an undirected scale-free network of N = 50, 000 nodes with power-law degree distribution exponent 2.5, using a configuration model. • Erdös-Rényi (E-R): For the undirected random graph with binomial degree distribution, we choose again N = 50, 000 nodes with mean degree 3 neighbours per node. The evaluation for these graphs is illustrated in Fig. 4. We start with the binary tree.

Node position: For the binary tree, we evaluate the Ψscore on the nodes of each level {0, 1, . . . , 9}, where level-0 is the root level. Regarding user activity, we apply here the homogeneous case where all nodes have the same (λ, µ) pair. We evaluate for two activity choices (0.25, 1) and (1, 0.25) and plot the score-per-level at Fig. 4a. We observe that each level has a different score. The highest score is attributed to the parents of the leaf nodes (level-8), whereas the smallest score to the leaf nodes (level-9). The root node also gets a lower score, being a boundary one. Note that the Ψ-score will coincide with PageRank in this homogeneous case.

q-influence: Our model goes beyond PageRank even in the homogeneous activity case, to further explain in detail how each node's influence is distributed among the nodes of the network, through the vector q i . In Fig. 4b we plot the influence q-vector for (λ, µ) = (0.25, 1) and three types of nodes i = {leaf (level-9), leaf's parent (level-8), root (level-0)}. Specifically, we select a single branch which spans the tree from root (level-0) to leaf (level-9), and plot the influence of i on each level of this branch, i.e. q (j) i for j = 0, . . . , 9. There are several noteworthy observations. For the chosen activity values, self-influence q (i) i is the highest for all three node types. Interestingly, the influence on direct neighbours is considerably higher than indirect ones, in all three cases. The leaf's parent collects the largest part of its Ψ-score from its influence on the leaf, because the latter does not have any other direct neighbours to be influenced by. On the other hand, the influence of the leaf to its parent is considerably less.

Increasing the leaf's posting rate: Our model generalises PageRank, since it can calculate the Ψ-scores for nodes with asymmetric activity. We allow the λ leaf of a given leaf to increase between [0.25, 2.5], whereas all others keep their posting activity λ = 0.25, and we calculate the new Ψ-scores of all nodes. In Fig. 4c we illustrate how the score evolves for the leaf node, its parent and the root node. We see that as λ leaf increases the Ψ leaf increases and the Ψ leaf s parent decreases. In fact, for λ leaf > 1, the ranks are inverted and the leaf node becomes more influential than its parent. The root's score does not change much, because of its distance from the leaf (9 levels away). As a conclusion the leaf has a naturally low score due to its position but can improve it by increasing its posting rate.

Scale-free: Next, we evaluate the Ψ-scores for the nodes of the scale-free graph. We first fix the same pair (λ, µ) = (0.25, 1) for all nodes and select a specific target node with degree = 20. For this node, we increase its posting rate λ 20 ∈ [0.25, 2.5] and plot the change of its Ψ-score, as well as the score of some of its neighbours and non-neighbours in Fig. 4d. In this graph the degree plays an important role and for homogeneous λ and µ the Ψ-scores are almost proportional to the degree, as can be expected from its relation with PageRank. But, as in the tree case, we observe that the score of the target node increases as λ 20 increases, whereas the score of its direct neighbours diminishes. The effect is more pronounced for a neighbour with degree 1, since the target node is the only neighbour that can be influenced by this one; the effect is less strong but still visible for a neighbour of degree 4. Other nodes of same degree 1 and 4 that are not direct neighbours of the target node do not exhibit a change in their score.

The importance of re-posting rate µ can be visualised in Fig. 4e where we fix (λ, µ) = (0.25, 1) for all nodes, but decrease µ 20 of the same target node with degree 20 as before, while keeping λ 20 = λ fixed. In this scenario, we observe that as the target's re-posting decreases, its score increases, while the scores of its direct neighbours with degree 1 and 4 decrease as expected. The reduction is more pronounced for the degree 1 direct neighbour. Again, the scores of nodes further away are less sensitive to changes in µ 20 .

A tragedy of the commons: We have seen in the tree and scale-free graph that a node can improve its score if it posts with a larger λ i . The same phenomenon can be observed in the Erdös-Rényi case. We will study now what happens when more and more nodes adopt such strategy and increase their posting rates in this example of E-R graph. For Fig. 4f we consider a random graph where initially all nodes have λ < µ, specifically (λ, µ) = (0.25, 1). These nodes are marked with orange colour and we call them "listeners". Gradually more and more nodes adopt the strategy to increase their posting rate and decrease their re-posting rate to (1, 0.25) in order to improve their individual score. These nodes are marked with blue and we call them "influencers". The plot illustrates how the average score of listeners and influencers changes as the number of influencers gradually increases. For 5, 000 influencers and 45, 000 listeners, the influencers' average score is much higher than that of the listeners and their strategy to change activity bears fruit. But, as the number of influencers increases, both types get a smaller score because there are less nodes in the graph willing to be influenced. As soon as the influencers become the majority, the score of both types becomes less than the initial average score when everyone was a listener. At the extreme case where everyone is an influencer, the average Ψ-score is three times less than the other extreme where everyone is a listener. We observe here a typical case of the tragedy of the commons.

B. Robustness

We further evaluate the robustness of the model with respect to the modelling assumptions. For this purpose, we first show the convergence time of our simulator to the theoretical value. We then modify our simulator to take into account inter-arrival distributions alternative to Poisson, as well as selection and eviction policies other than random.

a) Convergence: We evaluate the convergence speed of the simulator to the solution of the balance equations by increasing the number of iterations T iter and plotting the relative error; this is the ratio of the 2-norm of the difference between simulated and analytical values, divided by the 2norm of the analytical values. We choose for the experiment a ring graph of N = 8 with random λ i ∈ [0, 1], µ i ∈ [0, 1] per user and random association of 4 followers on average per node. The convergence till a relative error of 1.5% is shown in Fig. 5a. b) Alternative inter-arrival times: In Fig. 5a, we plot in addition to the exponential inter-arrival case, also the convergence of the simulator to the solution from the balance equations when applying alternatively the following two distributions for both posting and re-posting: (i) hyperexponential (with same mean but higher variance than Poisson) and (ii) deterministic (with same mean and zero variance). The figure shows that the hyper-exponential converges to the same solution as the Poisson albeit more slowly. It exhibits a 1.6% relative error compared to the analytical solution for T iter = 10 7 . The convergence for fixed interval process is non-monotone with a relative error of 5% for T iter = 10 7 . Intuitively, since the balance equations are based on the conservation law of posts, these will hold for any arrival distribution that guarantees convergence to some steady-state distribution p and q. c) Policies: We use here a complete graph with a varying number N of users, and set (λ, µ) = (10, 5). We programmed our simulator (see VI-B) to test alternative policies for user selection and post eviction, based on age and post-popularity. In (III-G) we showed that certain alternatives give the same balance equations as the basic "Random/Random" policy; specifically the "newest selection" policy, where a user always chooses to re-post the most recent post on his/her Newsfeed, and the "FIFO (oldest) eviction" where the new post enters the top of the list and pushes out the oldest one. Figure 5b shows that indeed "Random/Random", "Newest/Random", "Random/FIFO (oldest)" and "Newest/FIFO" have the same average performance, as these curves coincide. Furthermore, we test the "least popular (resp. most popular) selection", where the user chooses to re-post from his/her Newsfeed the post with the maximum (resp. minimum) current global number of re-posts. These policies use extra information on re-post history. We observe in Fig. 5b that with such choices, the absolute difference with a random policy becomes higher. The comparison is more pronounced when we observe the individual influences on a complete graph with 16 users in Fig. 5c. Interestingly, all policies behave similarly, except the "most popular" selection, which tends to give all influence to a single user. We conclude that our model is robust regarding the choice of selection and eviction policies when only local information involved. For other cases further investigations should shed more light on this very interesting question.

VIII. NUMERICAL RESULTS FROM REAL-WORLD TRACES

Traces: We evaluate our model and Ψ metric using two real datasets, one from Twitter and the second from the Weibo social platform. The first trace found in Kaggle is referred to as Russian 1 . It contains roughly 2 million (re-)tweets emitted from 180, 000 users during the Russian presidential elections of 2018. The second trace referred to as Weibo 2 comes from [START_REF] Zhang | Social Influence Locality for Modeling Retweeting Behaviors[END_REF] and contains roughly 34 million messages exchanged over the Chinese microblogging platform Sina Weibo. For both traces, user IDs are anonymised. Posts are ordered in time and their content is removed. Each line contains: [PostID, TimeStamp, UserID, RePostID]. Basic statistics for both datasets are summarised in Table II. The related friendship graphs are both sparse with an average in-degree (#Followers) of 5.70 for Russian and 236.9 for Weibo and their degree distribution is heterogeneous and close to a power law. Their statistics are summarised in Table III.

Methodology: Before starting, we need to extract some information from the traces. For each available data trace the input vectors of user activity λ i , µ i , ∀i can be estimated as the sample means of each user's posting activity, λi , μi , ∀i i.e., the ratio of the number of posts or re-posts over the total trace duration; the social follower graph G if not provided should also be inferred from the available traces, as we will show later in the case of Russian.

For each trace, we want to show how well our model can evaluate user influence in the respective platform. First, we rank the users based on the model influence Ψ model , where we use the sparse version of the code described in Section VI-A with input ( λ, μ, G), and compare this list with the ranking based on user empirical influence, as derived from the emulator Ψ emu in Section VI-C. The empirical influence q emu [i][j] in a trace is equal to the percentage of time that posts of origin i occupy the first position on the Wall of user j, assuming a FIFO principle and K = 1 Wall size.

As a second step we compare the model ranking, with the ranking based on alternative influence measures: the user (i) number of followers (in-degree), (ii) post activity λ, (iii) PageRank [START_REF] Brin | The anatomy of a large-scale hypertextual web search engine[END_REF].

To compare two ranking lists between each other we use two types of plots: A 2D scatter plot, where each point corresponds to a user and is the tuple of his/her predicted rank based on the Ψ emu (x-axis) and the Ψ model (y-axis); in such plots we also visualise the distance of the rankings from the line x = y, which describes the ideal perfect match of ranks. The second type of plot illustrates a metric similar to the Jaccard index to compare the two rankings, called "Common users proportion". More precisely, if {u 1 , . . . , u X } are the top-X UserIDs according to the emulator list, whereas {v 1 , . . . , v X } are the top-X UserIDs for the model list, we define the proportion of common users at depth X of the emulator list by

C X = |{u 1 , . . . , u X } ∩ {v 1 , . . . , v X }| X .
1 Available at https://www.kaggle.com/borisch/russian-election-2018-twitter 2 Available at https://aminer.org/influencelocality from the paper [START_REF] Zhang | Social Influence Locality for Modeling Retweeting Behaviors[END_REF]. Note that the quantity C X converges to 1 as X grows to N , because the two full lists contain the same set of users. But for some given X < N (e.g. top-10), the curve shows how well the model manages to rank users in relation to the emulator in the top-X positions.

A. First Dataset -Russian

To apply our sparse algorithm (see VI-A) we estimate user activity by the sample means ( λ, μ), i.e. the number of posts and reposts per user in the trace divided by the total time window (57 days). The user graph needed as input is not directly available for Russian and we have to find a way to recover it. For this we use the following heuristic:

Star G User i is considered to be a follower of user j iff i has reposted a post of origin j at least once. With Star we make the simplifying assumption that a user only reposts content created by his/her direct leaders. This approach short-circuits the diffusion paths of posts as it links directly original authors to all the re-posters, drawing a network with star-shaped communities. The Star graph statistics are given in Table III. We chose to follow this approach because the data-trace does not contain extra information over the IDs of "relay"-users. In such traces we can only know and store the original author and the total set of users each post reached, but not the paths. Note here that inferring graphs from data is a subject of active research and alternative methods can be found in the recent literature [START_REF] Newman | Network Structure from Rich but Noisy Data[END_REF]. For the time being we will use the Star-network as input; in the Weibo section, we will benefit from a real known graph.

The evaluation of the Russian model against the emulator is provided in Table IV, and in Figure 6. The top plot in Figure 6 shows the scatter plot of ranking based on Ψ model and Ψ emu ; note here that the points at the left correspond to higher influence rank (1st, 2nd,...) compared to points at the right, which are less significant. We observe a very good fit between the two rankings in the entire domain, and even for the top ranks (1st, 2nd,...) at the left part of the plot, which are of practical interest, e.g. for a company targeting high-influencers. At the bottom plot we illustrate four curves: each of them plots the Common users proportion between the user ranking from the emulator and the ranking from (i) the model influence Ψ model using the Star graph, (ii) user post rate, (iii) user number of followers from the model, and (iv) user PageRank from the Star graph with damping factor β = 0.85. We observe that our model (i) explains much better than the other metrics the ranking by the emulator, and is able to find 80% of emulator top-X users, in the largest part of the X range. The two curves (iii) and (iv) which describe only the graph structure perform much lower. Finally, in this specific example, the curve (ii) about user posting rate has no considerable importance in explaining influence, as such ranking seems unrelated to the emulator.

Precise results for the top-10 Ψ emu ranked users are shown in Table IV. We observe a very good fit between actual values of Ψ model and Ψ emu . Specifically, the model manages to find 7-out-of-10 influencers in the emulator top-10 list. An important observation comes from the two last columns of the table, namely the user number of followers and the user posting rate. We see that neither the number of followers nor the posting frequency follows the ranked order of the top influencers, in support of our observations already in Figure 6. By inspection, the user with maximum #followers (7833 followers in Star = 7833 users who shared posts originating from him/her) is ranked 2 nd by the emulator and 5 th by the model, whereas the user with maximum posting rate is ranked 9 th by the emulator and 4 th by the model. Impressively, we find in the list a top-influencer (ranked 8 th by the emulator) with low posting rate (e.g. 6.13 • 10 -7 [posts/sec] ≈ 0.00221 [posts/day]) and relatively low #followers (1235 "followers" in Star). Hence, neither the #followers as a measure of importance in the social graph, nor the posting rate as an activity measure are alone sufficient to rank users by influence. Our Ψ-score mixes user activity with graph position.

For Russian, an important part of the user influence is already present in the Star-graph, due to the way we chose to draw it (all users who shared a post are assumed as followers of its original author). The correlation between the influence score Ψ model and Star in-degree (#followers), is very high, equal to 0.82, whereas the correlation between Ψ model and posting activity λ is only 0.11. For the above reasons, we study the second dataset ( Weibo), accompanied by its true social graph.

B. Second Dataset -Weibo

For the second dataset (Weibo) we have access to the underlying friendship graph i.e., who follows whom. The graph statistics are given in Table III 3 . We use this Real graph to compute values of influence from our model Ψ model , whereas the Ψ emu is derived directly from the trace. The Weibo trace is special, because of the way it was collected to serve the study of cascades (see [START_REF] Zhang | Social Influence Locality for Modeling Retweeting Behaviors[END_REF]); the authors isolated and kept in the dataset only certain (approx. 200K) microblog episodes, which were massively re-posted. Specifically, as can be seen from Table II there are 10× more users than the Russian, but only 3.5% of users post, in comparison to 99.5% who re-post. The number of original posts is very small compared to much larger (100×) number of re-posts, meaning that the trace has a small user set of potentially very large influence. Here, we expect user activity to play an important role in determining influence, not just graph structure. On the other hand, the Real graph contains 291 million (M) edges (see Table III), most of which are never observed to be active in the available trace for post forwarding. In fact the trace contains ≈ 33M re-posts. Even if each repost passed through a different edge from the Real graph, there would be 291 -33 = 258M edges unused. Let us see how our model behaves in this particular case.

User ranking for Weibo using the model and the emulator are shown in Figure 7 and Table V. Specifically, Figure 7 (left) presents the scatter plot for ranking by Ψ model and Ψ emu . The fit for high influencers is good, but worsens as we move to the right in the low influence ranks, but the points are always centered around the line x = y. This behaviour is partly due to the specific trace and partly due to numerical issues; the massive size and density of the Weibo graph and the asymmetry in activity slowed-down computation of Ψ model , when using our sparse algorithm for the model, and we had to trade-off accuracy for run-time.

Figure 7 (centre) shows the Common users proportion metric between the rank list from Ψ emu and the ranking from: (i) #followers, (ii) PageRank (with β = 0.85), (iii) post rate, and (iv) the model Ψ model . The performance of Ψ model is again the best and it can explain around 60% of the user top-X ordering by Ψ emu . The reason for the lower performance compared to Russian Star is that, in the Real graph most of the edges do not participate in the post diffusion described in the Weibo trace. Our model in this paper does not include contextual preferences towards users or topics, but rather gives equal probability to all posts visible in the Newsfeed to be re-posted. We believe that a pre-processing of the real graph to keep only active relationships (edges) could significantly improve the model performance. Even in this unfavourable situation, however, we observe once again that our model using the Real graph outperforms the other three measures in explaining the top-X influencers found in the emulator ranking list. Interestingly, the graph-related measures of indegree (#followers) and PageRank behave very badly, whereas the post rate explains much better the empirical influence; this is to be expected because only cascades of posts from specific origins are kept in the trace. The Ψ metric from our model combines both graph position and user activity to give a better estimation of social influence. Finally, Figure 7 (right) compares ranking by the model with ranking by the post rate and the in-degree. Although Ψ model and post rate performance seem very close in the (centre) plot, less than 80% of the Ψ model ranking can be explained just by the post rate. This means that the Ψ model cannot be replaced simply by the post rate -even in this special case of dataset, because it contains different information over user influence.

Finally, referring to Table V, we see that the model with Real graph input finds 5-out-of-10 top influencers common with the emulator. From the #followers and activity λ columns, we verify again that the influence Ψ-score cannot be explained by #followers (in-degree) or activity only, but rather by an appropriate combination of the two, summarised in Ψ model .

IX. CONCLUSIONS

In this work we have introduced an original Markovian model that analyzes the diffusion of posts in a generic social platform, and quantifies the influence of a given user over any other. By resolving it we have derived closed-form expressions for metrics of influence, which allow to rank users based on the novel Ψ-score; the latter summarises the combined effect of user position in the graph with user activity. These results constitute a novel powerful toolbox that can be further exploited to understand and design social platforms. To highlight the importance of these results we have implemented a sparse version of the solution algorithm in [15] and have applied it to massive data traces from real OSPs (Twitter and Weibo).

The model-based Ψ-ranking is verified to correspond well with the empirical influence as read from the traces, a fact which validates our model for real world applications. As a consequence, we believe that the model can serve as a test and prediction tool for many social platform types and user activity scenarios, when no trace is available. It is flexible enough to further include extra OSP features (post-filtering, "likes", etc), or the balance equations could be modified to consider user preference towards posts from specific leaders or origins. The Ψ-score, itself, is shown more suitable to rank user influence compared to standard centrality metrics (#followers, PageRank, user activity) and cannot be substituted by any of them. Hence, it enriches the literature with a novel important measure that can combine user position in the graph with user activity to adequately rank user influence inside a platform. Finally, with rate µ (c) we return to the initial state and the cycle is complete. However, the rate to traverse the cycle in reverse order is 0, since there is no way we can transition from the initial state, to the next state news = (a, a, a) and walls = (a, a, b), because a post from b can appear on the c Wall only by re-posting, which is impossible in this case.

[B. Proof of Theorem 1] We will show that (8) is exact (i.e., holds without any approximation). The proof is based on the conservation law of posts in the Newsfeed. The same methodology can be used to prove exactness for the other three equalities ( 9), [START_REF] Degroot | Reaching a Consensus[END_REF], [START_REF] Cha | Measuring user influence in Twitter: The million follower falacy[END_REF].

Let us observe the Newsfeed of user n at the steady-state. This user has a set of leaders L (n) with index k = 1, . . . , L. Each leader has a posting activity, described by a homogeneous Poisson process (HPP) N (k) p with rate λ (k) and a re-posting activity described by a HPP N (k) r with rate µ (k) respectively. The superposition of all 2L processes is itself a HPP N of rate k∈L (n) (λ (k) + µ (k) ). This is the process of total incoming posts in the Newsfeed of user n. By fixing the time origin at t 0 = 0 and a time interval (0, T ] we count N ((0, T ]) incoming posts N ((0, T ]) = L k=1 N (k) p ((0, T ]) + N (k) r ((0, T ]) . [START_REF] Elsner | Bounds for the Perron root using max eigenvalues[END_REF] We can write for the re-posts of user k (and similar for posts)

N (k) r ((0, T ]) = s 1 (0,T ] (t s ), (32)
where user k reposted at random time instants 0 < t 1 < . . . < t S ≤ T , and the event count S = N (k) r ((0, T ]). We focus on posts of origin i. The state of the Newsfeed n related to this type of posts at t ∈ (0, T ] is denoted by X • Incoming posts of origin i to Newsfeed n: Each leader k when re-posting will choose at random a post from his/her own Newsfeed. This is the random selection assumption. We can model the choice of user k to re-post content with label i at time t < T as a Bernoulli random variable . [START_REF] Zhang | Social Influence Locality for Modeling Retweeting Behaviors[END_REF] This is itself a random process, which depends on the current state of the leader's Newsfeed X

The expected number of posts of origin i through leader k is

E N (k) r,i ((0, T ]) = E s 1 (0,T ] (t s )Z (k) i (t s ) = E s E 1 (0,T ] (t s )Z (k) i (t s ) t s , X (k)
i (t s ) = E s 1 (0,T ] (t s ) X For the expected total incoming number of posts of origin i in Newsfeed n, we consider re-posts of origin i through the L leaders, plus self-posts by user i, if user i is a leader of n,

E [N in,i ((0, T ])] = = λ (i) T 1 {i∈L (n) } + L k=1 E T 0 X (k) i (t) M µ (k) dt , (36)
where we used the fact that E[N (i)

p ([0, T ])] = λ (i) T because it is a HPP of rate λ (i) .

• Outgoing posts of origin i from Newsfeed n: Each of the posts of any origin entering the Newsfeed of user n (say at time t) will replace at random an existing post present on the list. This is the random eviction assumption. The evicted post will be of origin i with probability X This is itself a random process, which depends on the current state of the Newsfeed n. The outgoing process of posts of origin i from Newsfeed n results from thinning the total

i

  (t) but rather on their average probabilities in steady-state, which at this stage are unknown values.

Fig. 2 .

 2 Fig. 2. Aggregated continuous-time Markov Chain model results in 2N birth-and-death processes.

Lemma 1 .

 1 It holds ρ(A) ≤ 1. Strict inequality is guaranteed in the following non-exclusive non-exhaustive cases (cs): (cs1) λ (n) > 0, ∀n ∈ N . (cs2) For every cycle in the Leader-graph, at least one participating user has a leader k with positive self-post rate.Proof. Let us denote the row sums of A by r(j), j = 1 . . . N . Then r(j) ≤ 1 by definition from TableI. It is known that ([30, Theorem 8.1.22]) the following bounds are valid for the spectral radius of a non-negative matrix: min N j=1 r(j) ≤ ρ(A) ≤ max N j=1 r(j). The right-hand side in our case is 1 and the first part is proven.

  to find the PageRanks [π A , π B , π C , π D ] = [0.331, 0.223, 0.223, 0.223], whose sum equals 1. We observe that node A has highest PageRank, whereas the other three nodes have equal PageRank.

  ) for these new parameter values, we can calculate the new Ψ-score using (2), to get Ψ A , Ψ B , Ψ C , Ψ D = [0.234, 0.156, 0.451, 0.159]. User C is now ranked first with users A, B and D following; our score takes the increased posting activity into account. • In another scenario with the same toy-graph and activities µ A = µ B = µ D = µ = 2, µ C = 0, and λ = 0.105 for all users, user C decides to stop re-posting anything. We can again solve the system (17)-(18) and get the new scores Ψ A , Ψ B , Ψ C , Ψ D = [0.122, 0.231, 0.468, 0.179]

1 Fig. 4 .

 14 Fig. 4. Top: Tree. (a. left) Ψ-score per tree level, (b. centre) q-influence vector over a branch, (c. right) Change of Ψ-scores by increase of λ leaf , Bottom: Change of Ψ-scores in a scale-free graph when (d. left) λ deg=20 increases, (e. centre) µ deg=20 decreases, (f. right) E-R graph tragedy of commons.

  Convergence for various arrival distributions

  Fig. 5. (a)-(c): Sensitivity with respect to modeling assumptions.

Fig. 6 .

 6 Fig. 6. User ranking comparison for Russian. (a) top: Scatter plot between Rank(Ψ model ) and Rank(Ψ emu ) -points on the left rank higher (1st, 2nd, etc.), (b) bottom: Common users proportion with reference to Rank(Ψ emu ).

Fig. 7 .

 7 Fig. 7. User ranking comparison for Weibo. (a) left: Scatter plot between Rank(Ψ model ) and Rank(Ψ emu ) -points on the left rank higher (1st, 2nd, etc.), (b) centre: Common users proportion with reference to Rank(Ψ emu ), (c) right: Common users proportion with reference to Rank(Ψ model ).

i

  (t) ≤ M and is itself a continuous-time process. The states of the leaders are denoted by X

i

  (t) ≤ M , k = 1, . . . , L. Furthermore, the arrival process of posts of origin i through leader k is the counting process N(k) r,i , for k = 1, . . . , L. It holds N (k) r,i ((0, T ]) ≤ N (k)r ((0, T ]).

Z

X

  results from thinning the re-post process N (k) r of user k based on the random variable[START_REF] Zhang | Social Influence Locality for Modeling Retweeting Behaviors[END_REF], and we writeN (k) r,i ((0, T ]) = s 1 (0,T ] (t s )Z

  (k) i (t s ).

  By the smoothing formula for HPP of rate µ (k) [35, Th.7.1.7],

i

  (t)/M . We define as above the Bernoulli random variableZ (n) i (t) = 1 , with probability

X

TABLE II BASIC

 II STATISTICS ON BOTH DATASETS.

		Russian	Weibo
	Time window	57 days	1 216 days
	# users	181 621	1 340 816
	# posts	674 292	232 978
	# reposts	1 271 073	33 307 189
	Mean #posts/user	3.71	0.17
	Mean #reposts/user	7.00	24.84
	Max #posts	4 834	3 718
	Max #reposts	2 811	1 032
	% users with #posts > 0	54.45	03.55
	% users with #reposts > 0	63.60	99.54
	TABLE III
	STATISTICS OF INPUT SOCIAL GRAPHS.
		Russian (Star)	Weibo (Real)
	#nodes	181 621	1 340 816
	#edges	517 421	291 761 716
	mean #followers (in-degree)	5.70	236.90
	max #followers (in-degree)	7 868	431 385
	max #leaders (out-degree)	389	8 107

TABLE IV TOP

 IV -10 INFLUENCERS IN RU S S I A N AS RETURNED BY THE EMULATOR AND COMPARED WITH THE MODEL (STAR GRAPH).

	User	Ψ emu	Ψ model	Rank	Rank	#Follow	λ[s -1 ]
	ID #	10 -3	10 -3	emu	model	Star	10 -7
	20905367	12.02	10.23	1	3	6 676	42.9
	82299300	11.29	7.03	2	5	7 833	96.0
	494076761	7.35	13.80	3	2	6 963	439.3
	615422017	5.33	13.82	4	1	5 474	639.5
	174953869	5.13	5.81	5	7	1 742	118.5
	711363811	4.79	4.12	6	15	1 309	8.2
	36309919	4.44	5.23	7	9	4 516	118.5
	1867848452	4.15	4.60	8	12	1 235	6.1
	34200559	3.68	7.96	9	4	3 571	982.8
	50597428	3.36	3.64	10	20	1 156	8.2

TABLE V TOP

 V -10 INFLUENCERS IN WE I B O AS RETURNED BY THE EMULATOR AND COMPARED WITH THE MODEL (REAL GRAPH).

	User	Ψ emu	Ψ model	Rank	Rank	Follow	λ[s -1 ]
	ID #	10 -3	10 -3	emu	model	Real	10 -6
	519514	37.08	63.88	1	2	459	31.7
	490872	24.68	93.99	2	1	595	35.4
	1004172	13.30	7.05	3	23	520	2.0
	482551	11.53	47.56	4	3	1247	11.0
	110361	7.07	13.19	5	5	288	10.3
	244531	7.05	12.33	6	7	312	10.4
	296675	6.77	8.30	7	17	347	8.7
	980392	6.70	5.94	8	27	230	6.2
	153610	6.22	2.93	9	54	81	3.6
	821785	6.21	11.32	10	11	1084	2.7

The friendship graph contains users that do not appear in the trace; since no further information is available over their activity we ignore them.

ACKNOWLEDGMENT

The authors would like to thank the anonymous reviewers for their insightful comments that helped improve the work.

1]. This work is funded by the ANR (French National Agency of Research) partly by the "FairEngine" project under grant ANR-19-CE25-0011, and partly by the "Limass" project under grant ANR-19-CE23-0010. The authors are with the Sorbonne

incoming process N ((0, T ]) shown in [START_REF] Elsner | Bounds for the Perron root using max eigenvalues[END_REF] based on (37). Using arguments similar to [START_REF] Brémaud | Probability Theory and Stochastic Processes[END_REF], the expected number of posts of origin i which leave Newsfeed n up to time T is

λ (k) + µ (k) . (38)

• Newsfeed conservation law: The way we modelled the Newsfeed, no post is lost and hence all incoming posts will eventually leave the Newsfeed. The conservation law for posts of origin i up to time T states that

i (T ) is the count of origin i posts on the Newsfeed n at time t = 0 and t = T , respectively.

• Taking expectations: By taking expectation on both sides of the conservation law, we reach the equation

where, E[X

] is cancelled out, because we have assumed that at t = 0 the system is already in steadystate. Let us divide both side in (40) by the window size T . At the left-hand side of (40) we get using (36)

The detailed Markov chain has finite state-space (finite users and size M of Newsfeeds), and we assume that the Follower graph is strongly connected and that λ (n) , µ (n) > 0, ∀n ∈ N , hence the chain is ergodic. Since we assume that we observe the chain at its steady-state, then during (0, T ] it behaves according to its stationary distribution, and it holds

At the right-hand side of (35) -and also in (36), (38)we can use Tonelli's theorem to interchange integration and expectation, so that , its spectral radius is ρ(A) < 1 if and only if (I N -A) -1 exists, which can be written as the series