Nouamane Arhachoui
email: nouamane.arhachoui@lip6.fr

Esteban Bautista
email: esteban.bautista-ruiz@lip6.fr

Maximilien Danisch

Anastasios Giovanidis
email: anastasios.giovanidis@lip6.fr

Lionel Tabourier
email: lionel.tabourier@lip6.fr

Scalable Algorithms to Measure User Influence in Social Networks

Keywords: Social Networks, PsiScore, Ranking, Algorithms, Influence

Measuring user influence in social networks is crucial for a variety of applications. While traditional centrality metrics evaluate structural graph importance, a more recent metric known as the ψ-score takes into account users' posting and re-posting activities to provide richer information. The ψ-score is a powerful tool that generalizes PageRank for non-homogeneous node activity. However, for large datasets with N users, it becomes computationally expensive, requiring solving N linear systems of N equations. To tackle this issue, we propose three new scalable algorithms that can quickly approximate the ψ-score. The Power-ψ and Push-ψ algorithms are based on a novel equation that shows it is sufficient to solve one system of equations of size N to calculate the ψ-score. These algorithms take advantage of the fact that the solution of such a system can be recursively and distributedly approximated. Consequently, the ψ-score, which summarizes the nodes' structural and behavioral information, can be computed as quickly as PageRank. The third proposed algorithm is Push-NF. Despite aiming to solve all N systems to extract additional information on the information dynamics, it still manages to converge to the accurate user ranking faster than the current state-of-the-art alternative. To validate the effectiveness of our proposed algorithms, we release them as an open-source Python library and test them on various real-world datasets.

Introduction

Context

Measuring the importance of an individual in a network has been a focus of interest in Social Network Analysis for long. Indeed, a wealth of metrics have been developed to quantify this idea, including the well-known closeness centrality in the 1950s [START_REF] Bavelas | Communication patterns in task-oriented groups[END_REF] or the betweenness centrality in the 1970s [START_REF] Freeman | A set of measures of centrality based on betweenness[END_REF].

Nowadays, the ubiquitous nature of Online Social Platforms (OSPs) makes it all the more important to have relevant measurements available. For instance, it is essential for social scientists to identify the main leaders of opinion in a network in order to gain a better understanding of the dynamics that determine the roots of political polarization [START_REF] Alvim | A multi-agent model for polarization under confirmation bias in social networks[END_REF]. Also, it is crucial for companies to identify the so-called influencers that are believed to play a key role in the emergence of new trends [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF] and thus are targeted to develop effective marketing strategies [START_REF] Bok | Hot topic prediction considering influence and expertise in social media[END_REF]. From a technical perspective, machine learning algorithms also rely on the identification of a reduced set of users with features present throughout the network, which is critical in reducing the number of parameters and avoiding the curse of dimensionality [START_REF] Musto | Context-aware graph-based recommendations exploiting personalized pagerank[END_REF][START_REF] Cabannes | Overcoming the curse of dimensionality with laplacian regularization in semi-supervised learning[END_REF].

In this context, many OSPs may be described using a comparable structure: users have access to a wall and a news feed, they can publish messages (posts) on their wall, while their news feed shows the messages posted by other specific users, known as their leaders (or followees). This archetype is well illustrated by Twitter, Facebook or Weibo among others. Users can also re-post messages from their news feed to their wall, which is the main mechanism allowing posts to spread around the network [START_REF] Goel | The structure of online diffusion networks[END_REF]. A crucial issue is to quantify the extent to which their posts and re-posts circulate throughout the network and are accessible to others, as this process can be understood as the measure of their influence.

To address the aforementioned challenge, a variety of centrality metrics have been proposed to rank network nodes according to their structural relevance [START_REF] Wan | A survey on centrality metrics and their network resilience analysis[END_REF]. But given the potentially massive size of these networks, it is crucial that these measures remain scalable. For instance, betweenness centrality measures to what extent a node falls on shortest paths between others and thus its potential to control communication, however the most efficient algorithms have a temporal complexity in O(N M ) [START_REF] Brandes | A faster algorithm for betweenness centrality[END_REF] (where N is the number of nodes and M the number of edges) which makes it inappropriate for large OSPs. In addition to that, most centralities are unsuitable for assessing influence in OSPs, as they rely on a static description of the social network, while these are known to be dynamic platforms, where the activity of users is typically bursty. Nonetheless, these scores do not include user posting and sharing activity. The importance of this information is emphasized in [START_REF] Cha | Measuring user influence in twitter: The million follower fallacy[END_REF], which demonstrates that people with the most followers (in-degree) may not necessarily create the most retweets or views. Therefore, influence is not solely based on the number of followers, which is mainly related to a user's popularity. In the same line of inquiry, the authors in [START_REF] Wilson | Beyond social graphs: User interactions in online social networks and their implications[END_REF] ask th question: "Are social links valid indicators of real user interaction?" and underline the difference between these two ideas by examining a significant user trace from Facebook. It is thus essential to get past simple structural measures.

A new metric, coined as ψ-score, has been recently introduced in [START_REF] Giovanidis | Ranking online social users by their influence[END_REF] to overcome this limitation. The diffusion of information model presented in [START_REF] Giovanidis | Ranking online social users by their influence[END_REF] takes into account users behaviors by including activity features for each user. The ψ-score results from this model and provides a more accurate ranking metric of user influence in OSPs by integrating both structural information related to the graph and user activity. For instance, if users post and re-post content at different frequencies, the model incorporates this variation in the users' activity, thus yielding a more meaningful ranking metric. Furthermore, it was shown in [START_REF] Giovanidis | Ranking online social users by their influence[END_REF]Theorem 5] that the ψ-score is equivalent to PageRank when user activity is homogeneous, i.e., when all users create the same number of posts within a given time interval and share at the same rate within that interval. As a consequence, the ψ-score can be seen as a generalization of the PageRank, which is designed to situations where we have access to the nodes activity in the network.

Goal and contributions

A limitation of the ψ-score calculation as described in [START_REF] Giovanidis | Ranking online social users by their influence[END_REF] is that it does not scale to large graphs. Indeed, it requires the resolution of N linear systems of N equations each, where N denotes the number of users in the network. In contrast, PageRank only requires finding the solution of a single system with N variables. This paper addresses this shortcoming by proposing new ψ-score calculation algorithms that solve this issue.

For that purpose, we reorganize these N systems into a single one whose solution can be used to easily derive the ψ-score for all users. Then, we propose two different algorithms to solve this new system:

-Power-ψ which is based on power-iteration rules in order to approximate the solution (see also the conference version of this work [START_REF] Arhachoui | A fast algorithm for ranking users by their influence in online social platforms[END_REF]). This process allows approximating the sum of a geometric series for vectors without computing any matrix inversion. -Push-ψ, an algorithm inspired by the push-flow algorithm for PageRank [START_REF] Whang | Scalable data-driven pagerank: Algorithms, system issues, and lessons learned[END_REF][START_REF] Andersen | Local graph partitioning using pagerank vectors[END_REF].

It uses an approximation vector and a residual representing the difference between the exact solution and the approximation. During each push iteration, the approximated score of a node is updated and its residual is pushed to the residual of its neighbors in order to be minimized.

In addition to this contribution, we also propose to use the push method to make a tool to analyze the influence mechanisms at a finer grain. For this purpose, we describe another push-based algorithm, named Push-NF, that aims to solve the original N linear systems presented in [START_REF] Giovanidis | Ranking online social users by their influence[END_REF] instead of using the new system. While it does not allow to avoid the scalability issue aforementioned, by solving all N systems, Push-NF can not only extract the influence of each user on the entire network but also their influence on a specified individual. This feature provides valuable information for various applications, such as identifying opinion leaders or understanding information flow dynamics between specific users.

Finally, we provide an open-source software library1 to facilitate the implementation of the ψ-score. This comprehensive library includes its initial baseline implementation as well as implementations of each of the improved algorithms proposed in this paper. By making this library available to the community, we aim to encourage the widespread use of the ψ-score in various fields and its adaptation to each developer's specific needs. In particular, the psi-score library can be used to compare the metric with PageRank, since they are equivalent when the network activity is homogeneous.

Related Works

Centrality measures have been largely used in various fields of network science, including of course social network analysis [START_REF] Landherr | A critical review of centrality measures in social networks[END_REF][START_REF] Correa | Visual reasoning about social networks using centrality sensitivity[END_REF][START_REF] Miller | Talking politics on facebook: Network centrality and political discussion practices in social media[END_REF], but also transportation networks for example to improve traffic monitoring [START_REF] Puzis | Augmented betweenness centrality for environmentally aware traffic monitoring in transportation networks[END_REF], communication networks to design routing protocols [START_REF] Hui | Bubble rap: social-based forwarding in delay tolerant networks[END_REF] or to improve network control [START_REF] Tizghadam | Betweenness centrality and resistance distance in communication networks[END_REF], or even in biology, where they allow for instance to point out critical proteins in metabolic networks [START_REF] Ashtiani | A systematic survey of centrality measures for protein-protein interaction networks[END_REF]. Another essential application of centrality measures is information retrieval: with the expansion of the web, there is an ever-increasing need for algorithms that allow to look for precise information in a very large database. Among those, the most famous example is certainly the PageRank [START_REF] Page | The pagerank citation ranking: Bringing order to the web[END_REF][START_REF] Langville | Google's PageRank and beyond: The science of search engine rankings[END_REF]. Although these metrics are commonly used to rank nodes of a network [START_REF] Wan | A survey on centrality metrics and their network resilience analysis[END_REF], they only consider the network structure. For instance, PageRank can be described in non-technical terms as a random walk on a graph with a probability of teleporting on a random node at each step, so it does not take into account aspects such as node activity.

A standard way to compute the PageRank in a graph is to rely on a power iteration method [START_REF] Langville | Google's PageRank and beyond: The science of search engine rankings[END_REF]Chapter 4]. Various existing algorithms, such as Push [START_REF] Whang | Scalable data-driven pagerank: Algorithms, system issues, and lessons learned[END_REF] or methods using Chebyshev polynomials [START_REF] Bautista | A local updating algorithm for personalized pagerank via chebyshev polynomials[END_REF], exploit the random walk interpretation of PageRank to speed up its calculation. The Push method [START_REF] Whang | Scalable data-driven pagerank: Algorithms, system issues, and lessons learned[END_REF] iterates through nodes by allowing each of them to update the approximation of its own PageRank value and its neighbors values. The method proposed in [START_REF] Bautista | A local updating algorithm for personalized pagerank via chebyshev polynomials[END_REF] uses Chebyshev polynomials to approximate the PageRank vector more efficiently than the known power-method introduced with the metric [START_REF] Page | The pagerank citation ranking: Bringing order to the web[END_REF].

In a short version of this work [START_REF] Arhachoui | A fast algorithm for ranking users by their influence in online social platforms[END_REF], we have investigated the algebraic limitations of the ψ-score and proposed a novel approach to have it as scalable as the PageRank is. However, we acknowledge that other strategies to accelerate graph eigenvalue-based measures have the potential to further improve the performance of our method. Moreover, they can also give us insight into the mechanisms of social influence from an individual to another. Therefore, in this study, we aim to build upon this work by considering the Push method and integrating it with our approach. Our goal is to create a novel algorithm that not only addresses the limitations of the ψ-score but also surpasses the existing methods in terms of speed.

Outline of the paper

In Section 2, we describe the principles underlying the definition of the ψ-score and to what extent it measures the spread of influence on a social platform, as well as the baseline algorithm to compute it. Section 3 introduces the Power-ψ algorithm, which improves upon the baseline by reducing the number of equations to solve. In section 4, we present the Push-* approach, which provides an alternative way to compute the ψ-score and also allows to compute the influence between nodes at the individual scale. Finally, in Section 5, we evaluate numerically the different algorithms under study in terms both of accuracy to approximate the result and in terms of time efficiency of the process.

Measuring the Influence of OSP Users

The authors of [START_REF] Giovanidis | Ranking online social users by their influence[END_REF] proposed a model to describe the diffusion of posts on a generic social platform. Within this model, each user is not only a node of the social graph, but is also characterized by his or her own Wall and Newsfeed, as well as his or her own posting and re-posting activities. Using this spreading model, they compute in closed form the probabilities that a particular user's posts will appear on the Wall and Newsfeed of any other user. This allows them to derive a measure of influence in the network, that they name the ψ-score of a node.

In this section, we first give some basic elements of description of the OSP and the notations, summarized in Table 1, that will be used afterwards. Then, we detail the spreading model proposed in [START_REF] Giovanidis | Ranking online social users by their influence[END_REF] and describe how the ψ-score is defined in this context. Note however that this score is not restricted to the specifics of this model and can be defined on any network where nodes can be characterized with their activity rate. Posting activity. As mentioned above, users are also characterized by their posting and re-posting activities. Let λ represent the vector of posting activity over the vertex set. Thus, λ (n) represents the number of wall posts per unit of time (posting frequency) created by user n. Similarly, let µ represent the vector of re-posting activity of the vertices. Then, µ (n) refers to the frequency with which user n checks their Newsfeed and selects one of the current posts uniformly at random for re-posting on their Wall.

The ψ-score: metric of influence

Here we present the ψ-score following the way it was introduced in [START_REF] Giovanidis | Ranking online social users by their influence[END_REF]. It measures the nodes' influence in the OSP, not only based on the graph structure but also on the nodes activity, as a user who shares information more frequently is bound to have more influence than users who don't. Similarly, a user whose posts are shared often by their followers is also bound to have higher influence. The score can be computed from the graph structure and the activity vectors λ and µ only, however it is helpful to describe the information spreading process that inspired it in order to have a better understanding of its meaning.

Information spreading model. In [START_REF] Giovanidis | Ranking online social users by their influence[END_REF], the authors present the ψ-score as a natural way to evaluate influence within the context of a specific information spreading model on the OSP. In short, the model can be described as follows: a user in the network posts at a constant rate on his or her wall while messages from their leaders appear on their news feed, replacing a random older post. Regularly, this user selects randomly a post from his or her news feed to re-post it on the wall. This process is summarized in Figure 1. Again, we underline that this is not necessarily a lifelike description of information spreading on an OSP, nonetheless it is realistic enough to give a good intuition of the interpretation of the ψ-score and other intermediary quantities that are defined further.

Precisely, this model is a continuous-time Markov chain relying on the following set of assumptions:

-Poisson arrivals: any user n posts on his/her wall according to a Poisson process with rate λ (n) , and re-posts from the news feed to the wall according to a Poisson process with rate µ (n) . -Random selection policy: we suppose that when a user checks his/her news feed, he/she randomly selects one of the listed posts to re-post on their wall. -Random eviction policy: a new entry on the wall or on the news feed list replaces an older entry chosen at random.

Influence quantification. Now that the hypotheses of the model are set, we focus on how to quantify the influence of a user. The authors of [START_REF] Giovanidis | Ranking online social users by their influence[END_REF] introduce two vectors related to the influence of user i in N , which can be computed from the activity attributes of the nodes:

-p i = (p (1) i p (2) i • • • p (N ) i ) T where, for n ∈ N , p (n) i
represents the expected proportion of posts from user i on the news feed of user n. -q i = (q

(1) i q (2) i • • • q (N ) i
) T where, for all n ∈ N , q (n) i represents the expected proportion of posts from user i on the wall of user n.

So, q

(n) i can be understood as the influence of user i on user n, which means that the more posts from i appear on the wall of n, the greater is i's influence on n. This is used to define the influence of user i throughout the whole network as the average influence of i has on all other users. This concept is formalized by the ψ-score of user i, which is defined as

ψ i = 1 N n∈N q (n) i . (1)
ψ-score computation. In order to calculate the influence score ψ i of user i, we have to compute all entries of vector q i as they appear in its definition (1). However, q i is not directly available: a system of equations must be solved to determine the complete vector q i . Precisely, each q

(n) i can be obtained from p (n)
i , so we have to compute the vector p i . p i is the solution to a fixed-point problem, which is determined in [START_REF] Giovanidis | Ranking online social users by their influence[END_REF]Section III]. This fixed-point problem and the derivation of the q i vector are summarized in the following linear system, that we present in a matrix form:

p i = A.p i + b i (2) q i = C.p i + d i (3)
where

                 A ∈ R N ×N + , a ji = µ (i) ℓ∈L (j) (λ (ℓ) +µ (ℓ) ) 1 {i∈L (j) } , b i ∈ R N + , b ji = λ (i) ℓ∈L (j) (λ (ℓ) +µ (ℓ) ) 1 {i∈L (j) } , C ∈ R N ×N + , c ji = µ (j) λ (j) +µ (j) 1 {j=i} , d i ∈ R N + , d ji = λ (i) λ (i) +µ (i) 1 {j=i} .
As shown in [START_REF] Giovanidis | Ranking online social users by their influence[END_REF]Theorem 4], it is possible to solve (2) using a power iteration method as what is typically done to compute the PageRank. It consists in applying iteratively the following equation:

p i (t) = Ap i (t -1) + b i (4)
t being the current iteration. As t → ∞, the algorithm converges towards the solution p i (t) independently of the initialization p i (0) because A is a substochastic matrix2 . The algorithm 1 given in [START_REF] Giovanidis | Ranking online social users by their influence[END_REF] uses this equation to compute the vector p i .

Algorithm 1: Power-NF: Power method to compute the news feed probabilities p i related to user i. input : origin user i, N × N matrix A, vector b i , p-tolerance ε output:

vector p i p i ← b i ; t ← 0; gap ← 1; while (gap > ε) do p old i ← p i ; p i ← Ap old i + b i ; gap ← p i -p old i ; t ← t + 1; end return p;
Now, ranking the N users requires to compute ψ i for each i ∈ N , i.e., the complete vector

ψ = (ψ 1 , ψ 2 , • • • , ψ N ) T ∈ R N + .
To solve the linear system (2), the iterative approach in (4) must be used N times for each origin i ∈ N . Then, mapping each vector p i to q i thanks to (3) and finally using (1) gives the vector ψ with all the ψ-score values.

As a side note, which will be useful for comparison purposes, the paper [17] also establishes a relationship between the ψ-score and the PageRank. Indeed,the vector ψ equals the PageRank vector π in the scenario of homogeneous activity, meaning that ∀n ∈ N , λ (n) = λ and µ (n) = µ. In that specific case, the PageRank damping coefficient α is given by α = µ λ+µ [START_REF] Giovanidis | Ranking online social users by their influence[END_REF]Theorem 5].

Problem Statement. The algorithm 1 for the ψ-score vector computation -which we are going to refer to as Power-NF in this paper -is highly time-consuming. By contrast with PageRank, which demands solving 1 system of N equations, we need to solve N systems of N equations separately. This is particularly challenging when attempting to calculate the ψ-score in large real-world networks in a reasonable time.

Consequently, the problem discussed in this work is the following: given a directed social graph G = (N , E) and the vectors λ and µ which contain the information about the nodes posting and sharing activities, can we design an algorithm that computes the ψ-score of all nodes in the graph with a comparable speed to PageRank?

The Power-ψ Algorithm

In this section, we provide a first algorithm to compute the ψ-score which is faster than the baseline algorithm 1. The principle here is to reformulate the equations as presented in Section 2.2 to reduce the computational cost from solving N linear systems of size N to solving a single linear system of size N that includes all users. It will allow to use the power iteration method to approximate the solution of the new linear system, which can also benefit from distributed computing. We call this process Power-ψ: an algorithm for the derivation of the ψ-score that is comparable to the PageRank in terms of computational complexity, while benefiting from the score expressiveness because of the addition of the node activity information.

Expressing the ψ-score with a single linear system

We describe the ψ-score of the network in terms of the matrices P, Q, B, D, which are defined in Table 1. This matrix notation enables a vectorized expression of the ψ-score vector:

ψ T = 1 N 1 T Q (5)
We remind that the matrix Q contains the q i = (q

(1) i q (2) i • • • q (N ) i
) T vectors, which components q (n) i represent the influence of user i on user n. So, the task of obtaining the ψ-score is equivalent to computing a matrix Q, the columns of which require having the vectors p i , according to Eq. 3. Now, finding each p i is equivalent to solving a linear system, as can be seen in Eq.( 2). The equations ( 2) and (3) call to the matrices A and C, which are themselves derived from the adjacency matrix of the graph and the posting and re-posting activities of the users (λ and µ). Using [17, Lemma 2] each system solution can be written as

p i = (I -A) -1 b i = ∞ t=0 A t b i (6)
Eq. ( 6) is a linear equation in b i , which implies that the solution in matrix form for all users is

P = (I -A) -1 B = ∞ t=0 A t B (7)
Thus, by using Eq. ( 3) in its matrix form and the series in eq. ( 7), we can develop Eq. ( 5):

ψ T = 1 N 1 T Q = 1 N 1 T (CP + D) = 1 N 1 T C(I -A) -1 B + D = 1 N 1 T C ∞ t=0 A t B + D = 1 N ∞ t=0 1 T CA t B + 1 T D
Let us define c T := 1 T C and d T := 1 T D. c and d are vectors in R N + (the diagonals of the matrices C and D). This allows to formulate the following equation to compute the ψ-score:

ψ T = 1 N ∞ t=0 c T A t B + d T (8)
Eq. ( 8) demonstrates that it is not essential to solve N linear systems of size N to calculate the ψ-score. Instead, it is sufficient to solve a single N -dimensional linear system, which is written as the infinite sum of matrix-vector multiplications.

There is a drawback to this new approach, which is the fact that we do not compute explicitly the values of p i and q i , which quantify the influence at the individual level. As (8) demonstrates, these are not required any longer to calculate the ψ-score, however they include valuable information for practical applications, where evaluating the influence of a specific user on others is important.

Convergence and truncation of the sum

We state here that the infinite sum in Eq. ( 8) may be evaluated using a power iteration method. To show this, let us define:

s T t = t τ =0 c T A τ , s = lim t→∞ s t , (9)
where T denotes the matrix transpose and t is the iteration index. We emphasize that Eq. ( 9) converges if A's spectral radius is strictly lower than 1 (which is a standard property of geometric series). Lemmas 1 and 2 in [START_REF] Giovanidis | Ranking online social users by their influence[END_REF] guarantee this convergence, using the fact that A is a sub-stochastic matrix. Consequently, the sum in 8 may be truncated to a finite number of terms to approximate the ψ-score.

Now, let us evaluate the approximation error made when truncating the sum. The recursive expression associated with the truncated sum is

s T t = s T t-1 A + c T (10)
where s 0 = c. This allows us to define the following gap parameter

ε t = s T t -s T t-1 (11)
which is used to stop the algorithm. Any norm can be used, we opt for using the L 1 -norm because it is standard when approximating series with power iterations [START_REF] Page | The pagerank citation ranking: Bringing order to the web[END_REF]. So practically, we terminate the iterations when the following condition is met:

ε t ≤ ε (12)
A key question here is to evaluate how the tolerance ε impacts the approximation of the ψ-score. To answer this question, we define ψ t to approximate ψ by substituting ( 10) with (8) in t terms. Then, we define the difference δ t between two ψ-score approximations truncated at consecutive steps:

δ t = ψ T t -ψ T t-1 (13)
Now, we describe δ t as a function of ε t and identify an upper-bound relation between the two to deduce a convergence condition on the vector ψ t from the one on s t . Indeed, we know from ( 8) that

ψ T t -ψ T t-1 = 1 N (s T t B + d T ) - 1 N (s T t-1 B + d T ) = 1 N (s T t -s T t-1 )B ( 14
)
Eq. ( 14) then allows to deduce that:

δ t = 1 N (s T t -s T t-1 )B ≤ 1 N s T t -s T t-1 ∥B∥ ⇒ δ t ≤ ε t ∥B∥ N (15)
Using this upper bound, we can choose a tolerance ε that ensures the ψ-score evolution does not deviate by more than δ. Precisely, if the algorithm is terminated by the condition ε t ∥B∥ ≤ ε, then δ t is smaller than ε N . The corresponding power iteration algorithm is designated as Power-ψ and described in Algorithm 2.

Relationship between ψ-score and PageRank

In this section, we discuss the relationship between the ψ-score in the homogeneous activity scenario and PageRank, which highlights the contrast between our proposed method and the usual power-iteration algorithm for PageRank.

Algorithm 2: Power-ψ: Power method to compute the ψ-score vector.

input : N × N matrices A and B, size N vectors c and d, s-tolerance ε output: vector ψ with the ψ-score of all users s ← c;

B norm ← ∥B∥; t ← 0; gap ← 1; while (gap > ε) do s old ← s; s T ← s T old A + c; gap ← B norm ∥s old -s∥; t ← t + 1; end ψ T ← 1 N s T B + d T ; return ψ;
Let π denotes the PageRank vector and W = D -1 out L is the random walk transition matrix, where L is the adjacency matrix of the graph that points to the leaders and D out is the diagonal matrix whose entries (i, i) are the out-degree of node i. Theorem 5 in [START_REF] Giovanidis | Ranking online social users by their influence[END_REF] ensures that, in the homogeneous activity scenario, where ∀i, λ (i) = λ and µ (i) = µ, ψ = π with α = µ λ+µ as the PageRank damping factor.

In the homogeneous activity case, the vectors and matrices in the ψ-score equation of Eq. ( 8) are as follows:

       A = αW B = (1 -α)W c = α1 d = (1 -α)1
So, after replacing A and c by their expression in Eq. ( 10), we obtain

s T t = αs T t-1 W + α1 T (16)
By substituting the above expression in Eq. ( 8) and using the homogeneous values for B and d we get

ψ T t = 1 N s T t (1 -α)W + (1 -α)1 T = 1 N (αs T t-1 W + α1 T )(1 -α)W + (1 -α)1 T = α 1 N (s T t-1 (1 -α)W + (1 -α)1 T ) W + (1 -α) N 1 T = αψ T t-1 W + (1 -α) N 1 T (17)
The power method for PageRank computation translates as

π T t = απ T t-1 W + 1 -α N 1 T . ( 18
)
so, we can see that we find similar expressions, consistently with the result from [START_REF] Giovanidis | Ranking online social users by their influence[END_REF]Theorem 5]. Now, the proposed Power-ψ algorithm in the general case uses a power iteration to first estimate the series s up to a truncation based on the desired tolerance. Following convergence, the product by B and addition of d at the end of Algo. 2 prevent superfluous matrix-vector multiplications. This is the main implementation difference compared to PageRank power iteration. As shown above, both approaches converge to the same result in the homogeneous situation; however, the tolerance for ψ-score is defined on the s-vector, whereas for PageRank, it is defined on π itself.

Computational complexity

We analyze the computational complexity of the Power-ψ algorithm. The main computational cost of the algorithm is the power iteration, which is performed until the convergence condition is met. Let us denote k(ε) the number of iterations required to reach convergence. Each iteration requires a matrix-vector multiplication, which is of complexity O(M ) where M is the number of non-zero entries in the matrix, i.e. the number of edges in G. There is also a vector addition, which is of complexity O(N ), and a scalar-vector multiplication, which is in O(N ). So the total complexity of each iteration is in O(M + N ). The total complexity of the algorithm is then O(k(ε)(M +N )). This result is comparable to the complexity of the PageRank power iteration, which is also in O(k(ε)(M + N )).

Push approach for influence quantification

In this section, we design a push-based algorithm approach to our problem of influence quantification on a social network. This approach can be applied to two different sets of equations with two distinct purposes. On the one hand, we can use it on Equation (10) in a similar manner as what has been done for PageRank [START_REF] Whang | Scalable data-driven pagerank: Algorithms, system issues, and lessons learned[END_REF][START_REF] Andersen | Local graph partitioning using pagerank vectors[END_REF]. In this case, the goal is to find more efficiently the vector s, which in turn allows for the direct calculation of the ψ-score of each node. On the other hand, the push method can also be employed to solve Equation ( 2), and the purpose here is to compute faster the ψ-score of a single user; by providing p i and q i , it gives much more details about the mechanism of influence on the network at an individual level. Note that the application of the push approach to our problem is the main theoretical addition to the shorter version of this work [START_REF] Arhachoui | A fast algorithm for ranking users by their influence in online social platforms[END_REF].

Intuition behind the push approach

The push method can be thought of as a message-passing algorithm. The intuitive general idea is to iteratively propagate information across the graph, in order to calculate the importance of each node based on its connections to other nodes.

Practically, it works by initializing a residual value for each node and its approximate score, where the residual represents the amount of information that still needs to be propagated from that node to its neighbors. The algorithm then iteratively updates the approximate score for each node based on the residual that it gets from its neighbors. At each iteration, a node "pushes" its residual to its neighbors, proportionally to the strength of the connection between the two nodes (encoded by the matrix A in the case of ψ-score and the propagation matrix for PageRank). The node then updates its own approximate score based on the residuals that it received from its neighbors. This process continues until the residuals converge towards 0, indicating that the approximate score vector has converged to the actual score.

Note that the push method can be implemented in a distributed way since each node updates its own score, making it very efficient at solving linear systems of a large number of equations.

General formulation of the approach Push-*

Let us first rewrite equation ( 10) as follows:

s = A T .s + c (19)
so that it has exactly the same form as Eq. ( 2). Now, while they contain and return different quantities, Eq. ( 2) on p i and ( 19) on s, they allow us to describe the application of the push method on both of them with some generic notations:

x = M.x + r (20)
where x ∈ R N is the unknown vector, r ∈ R N and M ∈ R N ×N . In the case of Eq. ( 2), x = p i , M = A and r = b i and in the case of Eq. ( 19), x = s, M = A T and r = c. Taking advantage of this formal similarity, from now on we refer to the method and algorithm that we develop as Push-*, then we will describe them as Push-NF for Eq. ( 2) and Push-ψ for Eq. ( 19) when necessary.

It is important here to notice that Equation [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF] does not have the same form as the one that computes the PageRank since r has different components while the second term of the PageRank equation is homogeneous. Consequently, we cannot use the push-based algorithm described in [START_REF] Whang | Scalable data-driven pagerank: Algorithms, system issues, and lessons learned[END_REF] or [START_REF] Andersen | Local graph partitioning using pagerank vectors[END_REF]. Thus we adapt the method to the specific case under consideration.

Let us first observe that the solution x is a function of the vector r, so that we can re-write Eq. ( 20) as

x(r) = M.x(r) + r (21)
Rearranging this equation, it becomes

x(r) = (I -M) -1 r = ∞ n=0 M n r (22)
The next step is key and specific to the push method. Let χ u be the unit vector with only the u-th entry equal to 1 and all the other components equal to 0. Also, we denote r(u) the u-th entry of r. Using only Eq. ( 21) and Eq. ( 22) (which is linear), we have the following expressions:

x(r) = x (r -r(u)χ u + r(u)χ u ) = x (r(u)χ u ) + x (r -r(u)χ u ) = M.x(r(u)χ u ) + r(u)χ u + x (r -r(u)χ u ) = M ∞ n=0 M n r(u)χ u + r(u)χ u + x (r -r(u)χ u ) = ∞ n=0 M n Mr(u)χ u + r(u)χ u + x (r -r(u)χ u ) = x (Mr(u)χ u ) + x (r -r(u)χ u ) + r(u)χ u = x (r -r(u)χ u + Mr(u)χ u ) + r(u)χ u = r(u)χ u + x(r ′ ), ( 23
)
where we define the vector r ′ as

r ′ := r -r(u)χ u + Mr(u)χ u . (24)
So, we have derived a new expression of the solution as the sum of two components:

x(r) = r(u)χ u + x(r ′ ) ( 25
)
where the first part is an approximation of the solution x(r) and the second, x(r ′ ) can be interpreted as a residual and denoted x ′ .

Convergence of the residual

Following the above approach, we can put ( 24) and ( 25) in an iterative algorithm to derive the solution of ( 20) with a convergence criterion related to the residual. The problem is that the exact expression of the residual x(r ′ ) is not available. However, we know its argument r ′ from [START_REF] Langville | Google's PageRank and beyond: The science of search engine rankings[END_REF]. In addition, r → x(r) is a linear map, as shown by Eq. ( 22), so that x(0) = 0, where 0 is a vector of 0. Thus, we set a convergence criterion related to the infinite norm of the residual argument of the form ∥r ′ ∥ ∞ < ε. Now, we investigate if we can bound the volume of the residuals. As long as ∥M∥ < 1, we have that

∥x(r ′ )∥ = ∞ n=0 M n x ′ ≤ ∞ n=0 M n • ∥x ′ ∥ ≤ ε • ∞ n=0 ∥M∥ n = ε 1 -∥M∥ , (26)
Note that this inequality is true for the L 1 norm of a right sub-stochastic matrix, such as A, and for the L ∞ norm of a left sub-stochastic matrix. In the case of Eq. ( 2) (Push-NF), M = A and in the case of Eq. ( 19) M = A T (Push-ψ). So, we have the following cases of induced norms in the case of Push-NF:

∥x(r ′ )∥ 1 ≤ ε 1 -∥A∥ 1 = ε 1 -max 1≤u≤N v∈F (u) A(v, u) , (27)
in the case of Push-ψ:

∥x(r ′ )∥ ∞ ≤ ε 1 -∥A T ∥ ∞ = ε 1 -max 1≤u≤N v∈L(v) A T (u, v) (28)
Where F(u) designates the set of followers of user u while L(v) is the set of leaders of user v.

As a consequence, we can choose the tolerance ε to be an upper bound of ε 1-∥M∥ as a convergence criterion by taking the appropriate norm for M.

The Push-* algorithm

We propose our Push-* algorithm following this expression to derive the solution x(r) of the generic equation. Each iteration of Push-* works as follows: the u-th entry of the approximation vector is incremented by r(u) > ε, which will be then set to 0 as indicated by the first part of [START_REF] Langville | Google's PageRank and beyond: The science of search engine rankings[END_REF]. Next, for every v follower (respectively leader) of u for (2) (respectively for [START_REF] Hui | Bubble rap: social-based forwarding in delay tolerant networks[END_REF]), the value M(v, u).r(u) > 0 is added to r(v) (second part of ( 24)). The algorithm stops when the value of the residual is small enough according to what has been discussed in Section 4.3.

Numerical evaluation

In this section, we evaluate the performances of the three algorithms presented in this work: Power-ψ, Push-ψ and Push-NF. We compare their performances to the baseline algorithm Power-NF described in [START_REF] Giovanidis | Ranking online social users by their influence[END_REF]. In the case where the posting and re-posting activities of nodes are identical for all nodes, the ψ-score is equivalent to the PageRank, it allows us to compare the results to the ones obtained with the PageRank in this homogeneous scenario.

First, we briefly present the package which has been developed and released for this project. Second, we describe the different datasets that are investigated in the experiments. Then we precise some important elements of the experimental protocol, before reporting the results of the performance evaluation.

The psi-score Python package

The psi-score project is a software library that we have developed in Python. It is open source and licensed under the terms of the MIT license, allowing free usability. It is currently available at the address https://github.com/NouamaneA/ psi-score.

This package is a practical tool for the community to easily use the ψ-score metric in projects without the need to develop each algorithm individually. All methods mentioned in this work are accessible: the baseline Power-NF as well as the proposed algorithms Power-ψ, Push-ψ and Push-NF. To simplify its usage, the project has a similar Application Programming Interface (API) as the one used in scikit-network [START_REF] Bonald | Scikit-network: Graph analysis in python[END_REF] and scikit-learn [START_REF] Buitinck | API design for machine learning software: experiences from the scikit-learn project[END_REF].

Datasets

For the numerical evaluation of our methods, we choose four real-world datasets which are listed in Table 2. Three of them are publicly available in the KONECT project 3 [22] which is a network dataset repository. These three datasets do not include any information about the nodes activity in the network so we decided to generate λ and µ uniformly at random. The last dataset has been downloaded from Kaggle dataset repository4 [START_REF] Chumichev | Russian election 2018 -twitter user activity[END_REF]. It is a Twitter trace that contains a million tweets and retweets from 181,621 users during the 2018 Russian elections, we can therefore derive the actual posting and re-posting activities (respectively λ and µ) of all users.

Experiments

Unit of comparison. The complexity of the methods is compared using the number of messages required to reach a targeted tolerance ε, which is the number of vector entries updated at each iteration during the process. We use the term "messages" because we can interpret each update as a signal that propagates across the network from a node to one of its neighbors. By contrast with the computation time, this measure has the advantage of allowing the comparison between sequential and distributed algorithms, regardless of the technology used to implement them. Note here that each one of the algorithms (Power-ψ, Power-NF, Push-* and PageRank) have a different notion of tolerance, depending on the criterion of convergence. Specifically, for Push-* we name it r-tolerance because the convergence is based on the norm of the residual vector, as expressed by the equation ∥x ′ ∥ ∞ < ε. For Power-NF we name it p-tolerance because the convergence is based on the norm of the news-feed p-values. For Power-ψ we refer to stolerance because the convergence is based on the norm of the series s-values. For PageRank we consider π-tolerance because the convergence is based on the norm of the PageRank vector. Also, we underline that further processing is needed after convergence to eventually derive the resulting ψ-scores. So, when we set some value ε for the x-tolerance according to a specific method, we obtain some approximation of the ψ-score ψ ε , however we are interested in evaluating the relative error of this method compared to the exact value ψ true , defined as follows:

error = ∥ψ true -ψ ε ∥ 2 ∥ψ true ∥ 2 (29)
Note that to compute the ψ true vector, we use the solver from the sparse module of the SciPy Python library [START_REF] Virtanen | SciPy 1.0 Contributors: SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python[END_REF] which employs matrix factorization to solve the system [START_REF] Buitinck | API design for machine learning software: experiences from the scikit-learn project[END_REF].

Design of the experiments. We conducted three series of experiments to evaluate the performance of our proposed algorithms. The first series of experiments aims to validate their ability to approximate the exact ψ-score by comparing the approximation error of the algorithms to the exact ψ-score value. In the second series, we aim at validating the algorithms ability to return the actual user ranking based on the ψ-score. In the third series, we compare the algorithms' performance with that of Power-NF, in terms of messages, which is the unit of comparison previously defined. To do this, we used the Kendall τ correlation coefficient to compare the rankings returned by each algorithm to the rankings returned by the true ψ-score values.

Scenarios. For each series of experiments, we consider two scenarios: (i) In the heterogeneous scenario, we set the activity parameters λ and µ to be heterogeneous. It means that in the cases of ego-Twitter, DBLP and Twitter-ICWSM, where no temporal activity data is available, we draw λ and µ uniformly at random in the interval [0, 1]. In the case of Russian, we use the actual activities measured on the dataset. (ii) In the homogeneous scenario, we set the activity parameters λ and µ to be homogeneous, i.e., we set λ = 0.15 and µ = 0.85 for all nodes. According to Section 3.3, this corresponds to the case where the ψ-score is equivalent to the PageRank with a damping factor α = 0.85 (which is a typical value for the damping factor). Besides, we run in this scenario the experiments on the giant connected component of the graph, as the equivalence between the ψ-score and the PageRank is ensured only within these settings, as stated in [START_REF] Giovanidis | Ranking online social users by their influence[END_REF].

Series 1: quality of the ψ-score approximation. In the first series of experiments, we evaluate the accuracy of our proposed algorithms in approximating the ψ-score vector by measuring the error and comparing them to Power-NF in both scenarios and to PageRank in the homogeneous scenario only.

The corresponding results for the heterogeneous and homogeneous activity scenarios are respectively presented in Figure 2 and Figure 3. The x-axis of the figure represents the fixed p-, s-, rand π-tolerance for each algorithm, while the y-axis represents the computed error from equation [START_REF] Page | The pagerank citation ranking: Bringing order to the web[END_REF]. Notably, the Power-ψ method exhibits significantly lower approximation error than the other algorithms, which can be attributed to the fact that the measured gap at each iteration is multiplied by ∥B∥ to ensure that the gap in the ψ-score approximation is below the chosen tolerance when the algorithm converges. We also notice that the power method is systematically more accurate than the corresponding push method: the error committed with Power-ψ is lower than the one of Push-ψ and similarly, the error with Power-NF is lower than with Push-NF. It is expected, as the tolerance is more directly related to the quantity targeted with a power method than it is with a push method, since the latter bases its convergence on the norm of the residual. In the homogeneous scenario, Figure 3 shows that Power-ψ is more accurate than PageRank in the sense that a similar tolerance implies a lower error.

Series 2: quality of the ranking approximation. When using centrality measures, we are in general less concerned by the absolute value of the score than we are by the ordering of the nodes. Thus, to evaluate how the error presented in the first series of experiments translates in terms of ranking, we investigate in this series the quality of the approximations in view of the ranking that they produce.

To assess this, we compute the correlation between the rankings produced by each algorithm to the one generated by the exact ψ-score using Kendall's τ correlation coefficient. Introduced in [START_REF] Kendall | A new measure of rank correlation[END_REF], this metric is used to measure the similarity between two rankings. It involves counting the number of concordant and discordant pairs (resp. n C and n D ) between the two rankings x and y, as well as the number of ties t x and t y within each ranking. Then, the coefficient is computed as follows:

τ (x, y) = n C -n D (n C + n D + t x )(n C + n D + t y )
The results of this series of experiments in the heterogeneous and homogeneous scenarios are respectively displayed in Figure 4 and Figure 5. We represent Kendall's τ scores as a function of the tolerance on all four datasets and for each algorithm. As can be seen, all three proposed algorithms (Push-ψ, Push-NF, and Power-ψ) perform very well in terms of user ranking, in the sense that the Kendall τ scores are very close to 1, even with relatively high tolerance values. This means that the algorithms are able to effectively rank users in the same way as the actual ψ-score does. In the homogeneous activity scenario, we notice a decrease in the ranking quality of Push-NF when increasing the tolerance: a significant drop occurs around a tolerance of 10 -2 in the cases of DBLP, ego-Twitter and Russian and around a tolerance of 10 -3 concerning Twitter-ICWSM.

Series 3: message complexity. In the third series of experiments, we focus on the scalability of these algorithms by evaluating their performance in terms of the number of messages required to achieve a given level of precision in approximating the result. It is worth noticing that achieving the same precision for all algorithms is not always possible. This is because, as discussed previously, the tolerance is not equivalent for all algorithms, so the resulting approximation error on the exact score may vary. To compare the performances of the algorithms to the baseline, we run them with various tolerance parameters (the same ones used in the first series of experiments) and measure the number of messages required to reach convergence. We then calculate the relative error using [START_REF] Page | The pagerank citation ranking: Bringing order to the web[END_REF] to compare the algorithms performance under a specific level of precision. Note that the message-based complexity can be simply related to the number of iterations of a power method. Indeed, a complete iteration consists of sending M messages through the network, where M is the number of edges in the network. So the value k(ε) mentioned in 3.4 is related to the total number of messages n mes sent by the relation k

(ε) = n mes /M .
The results of this series of experiments are respectively reported in Figure 6 and7 for the heterogeneous and homogeneous scenarios. Consistently with the findings of the short version of this work [START_REF] Arhachoui | A fast algorithm for ranking users by their influence in online social platforms[END_REF], we observe that Power-ψ significantly outperforms Power-NF due to the reduced number of equations to solve. The Push-* algorithms also bring some very interesting results, as Push-NF requires fewer messages than Power-NF, and Push-ψ requires fewer messages that Power-ψ. The authors of [START_REF] Bautista | A local updating algorithm for personalized pagerank via chebyshev polynomials[END_REF] reported a specificity of push methods, which is that they are not competitive to obtain very precise approximations as they require a large number of messages to decrease the error. Such a trend is confirmed by the DBLP and Russian datasets. We even notice a peculiar trend in Figure 6-d

) with

Russian, for which we do not succeed in improving the approximation error even when largely increasing the number of messages of the push methods. This might be due to the fact that, unlike the other datasets, the activity parameters λ and µ are measured from the dataset (see Section 5.2) itself and we noticed that almost half of the nodes in this social network are inactive. However, we do not notice such a dramatic trend with datasets ego-Twitter and Twitter-ICWSM. An important observation in Figure 7 is that Power-ψ and Push-ψ converge faster than PageRank in the homogeneous scenario. This makes the ψ-score a very interesting alternative to PageRank for ranking users in social networks as its complexity has been reduced to the same level as PageRank.

Finally, the overall picture that we draw from these experimental investigations is that push methods are steadily faster than power methods but allow less control over the error committed on the ψ-score. Consequently, we suggest that both methods will not be used for the same applications, depending on the precision or speed required for the computation. Also, in the case of the datasets investigated, the fact that the push methods are limited to larger error does not significantly impact the algorithms performance at ranking users, as we have seen in the previous series of experiments.

Conclusion and future work

In conclusion, the ψ-score is a powerful metric that generalizes PageRank for nonhomogeneous node activities. It combines the structural information of the graph with the temporal information of the users' activities to rank their influence in the social network. In this work, we have proposed three scalable algorithms for approximating the ψ-score. The Power-ψ and Push-ψ algorithms take advantage of a novel equation that reduces the system we need to solve for the ψ-score calculation, while the Push-NF algorithm provides additional insights on the information dynamics at the individual level. Through our experiments, we have shown that these algorithms perform well on various real-world datasets both in terms of precision of the approximation and in terms of speed; however, someone interested in controlling the error committed will favor power methods while someone interested in time efficiency will favor push-methods. We have released them as an open-source Python package for the research community to use and improve upon.

This score suits many real-world applications. It has been especially designed to evaluate the notion of influence on online social platforms, typically microblogging social networks. Indeed, while the PageRank only takes into account the structural information, the ψ-score also considers nodes posting and re-posting activities, which are known to be important features on these platforms. It could thus help identify influential users on social networks. However, it could also be an interesting score to evaluate influence in other contexts, such as scientific citation networks, where an author posting corresponds to a new publication and re-posting would be a citation. Here as well, we expect the users' activity to have a significant effect on their visibility and influence in the network.

This study opens several interesting avenues for future work. A possibility is to investigate in what way the heterogeneous patterns of activities in real networks affect the spread of influence on the platform: for instance, does it allow some specific posts to reach some distant users faster? Another one could be to measure to what extent the idealized process underlying the ψ-score definition differs from the actual diffusion process and possibly identify anomalous behaviors from these differences. For instance, we can think that if a post of a user is largely re-posted while he or she has a relatively low ψ-score, it might convey a specific message which is worthy of analysis.

Fig. 1 .

 1 Fig. 1. A small example of the Online Social Platform from the point of view of user i.

Algorithm 3 :

 3 Push-*: the Push algorithm for x input : N × 1 vector r, N × N matrix M, ε output: Calculate the N × 1 vector x(r) Initialization: x(v) = 0, for v = 1, . . . , N ; FIFO ← CreateFIFO(); for user u with x(u) > ε do FIFO.add(u); Mark(u) end while FIFO not empty do u ← F IF O.pop() ; x(u) ← x(u) + r(u) ; for user v in M(:, u) > 0 do r(v) ← r(v) + M(v, u) • r(u); if r(v) > ε and (v not marked) then FIFO.add(v); Mark(v); end end r(u) ← 0; Unmark(u); end

Fig. 2 .

 2 Fig. 2. (i) Heterogeneous scenario. Experiment 1 with a) DBLP, b) ego-Twitter, c) Twitter-ICWSM and d) Russian: Precision assessment of the proposed algorithms compared to the baseline.

Fig. 3 .

 3 Fig. 3. (ii) Homogeneous scenario. Experiment 1 with a) DBLP, b) ego-Twitter, c) Twitter-ICWSM and d) Russian: Precision assessment of the proposed algorithms comto the baseline.

Fig. 4 .

 4 Fig. 4. (i) Heterogeneous scenario. Experiment 2 with a) DBLP, b) ego-Twitter, c) Twitter-ICWSM and d) Russian: Evaluation of the algorithms ability to return an accurate ranking compared to the one returned by the exact ψ-score. 1 means a perfect correlation, 0 means no correlation at all and -1 means a full anti-correlation.

Fig. 5 .

 5 Fig. 5. (ii) Homogeneous scenario. Experiment 2 with a) DBLP, b) ego-Twitter, c) Twitter-ICWSM and d) Russian: Evaluation of the algorithms ability to return an accurate ranking compared to the one returned by the exact ψ-score/PageRank. 1 means a perfect correlation, 0 means no correlation at all and -1 means a full anti-correlation.

Fig. 6 .

 6 Fig. 6. (i) Heterogeneous scenario. Experiment 3 with a) DBLP, b) ego-Twitter, c) Twitter-ICWSM and d) Russian: Comparison of the proposed algorithms with the baseline (Power-NF) in terms of the number of messages to reach convergence.

Fig. 7 .

 7 Fig. 7. (ii) Homogeneous scenario. Experiment 3 with a) DBLP, b) ego-Twitter, c) Twitter-ICWSM and d) Russian: Comparison of the proposed algorithms with the baselines Power-NF and PageRank in terms of the number of messages to reach convergence.

Table 1 .

 1 Notations used in the paper

	Notation	Description
	ψi	ψ-score of user i
	ψ	ψ-score column-vector
	p	(n) i	impressions of i on the Newsfeed of n
	q i (n)	(influence) impressions of i on the Wall of n
	pi	vector with every p	(n) i
	qi	vector with every q	(n) i
	P	matrix with pi as column i
	Q	matrix with qi as column i
	bi	input vector of normalized posting activity
	di	vector with the posting ratio of a user i
	B	matrix with bi as column i
	D	diagonal matrix with di as column i
		1	column-vector of R N full of ones, i.e. (1 1 • • • 1) T
	2.1 Network user model and notations
	Network structure. The platform is represented as a directed and unweighted
	graph denoted G = (N , E). Its vertices represent the users in the OSP and its edges represent the follower-leader relations: (i, j) ∈ E means that user i follows user j. The cardinalities of N and E are denoted |N | = N and |E| = M . Note that a social platform where the relationships between users are reciprocal (as for
	instance, friendships on Facebook) can also be described by this representation,
	by connecting users with edges in both directions.

Table 2 .

 2 Datasets used for evaluation

	Dataset name	Type	#Nodes #Edges Sources
	DBLP	Citation Network 12 590	49 759	[25]
	Twitter-ICWSM Social Network 465 017 834 797	[15]
	ego-Twitter	Social Network 23 370	33 101	[26]
	Russian	Social Network 181 621 515 419	[13]

https://github.com/NouamaneA/psi-score

A sub-stochastic matrix is a real square matrix having each row summing to a value strictly lower than 1.

http://konect.cc/

https://www.kaggle.com


Wei Fang

Panyue Zhang

Tao Zhang

David Carmona Requeson

Morgane Poser

Upgrading volatile fatty acids

Keywords:

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Current situation with increasing resource demand and limited natural resources has directed attention to exploring recourse recovery from organic wastes [START_REF] De | Bio-based chemicals value added products from biorefineries[END_REF]. Anaerobic digestion provides an efficient method for resource recovery from organic wastes, where complex polymers are digested and transferred into useful products such as biogas [START_REF] Van Lier | Anaerobic Wastewater Treatment[END_REF]. Such conversion of waste into valuable products also offers an alternative approach to reduce the amount of wastes. Instead of biogas, more exactly methane, volatile fatty acids (VFAs) are recognized as a product with higher added value, because they are widely used as building blocks in chemical industry, such as in the food, pharmaceutical and petrochemical industries. Moreover, harvested VFAs can also be used as carbon source in biological processes of nutrient removal from wastewater [START_REF] Agler | Waste to bioproduct conversion with undefined mixed cultures: the carboxylate platform[END_REF]. More than 6.0 million tons dry sludge every year is produced from wastewater treatment plants (WWTPs) in China [START_REF] Wu | Enhancement of volatile fatty acid production by co-fermentation of food waste and excess sludge without pH control: the mechanism and microbial community analyses[END_REF], and the cost of sludge treatment accounts for 30%-50% of the total operation cost in WWTPs. Anaerobic fermentation for VFA production is a possible route for stabilization and resource recovery of sewage sludge. Recently, an increasing number of studies on VFA production from sewage sludge have been carried out, but insufficient C/N ratio limited the hydrolysis of sewage sludge and VFAs production [START_REF] Esteban-Gutierrez | From sewage sludge and agri-food waste to VFA: individual acid production potential and upscaling[END_REF][START_REF] Lee | A review of the production and applications of waste-derived volatile fatty acids[END_REF][START_REF] Wu | Enhancement of volatile fatty acid production by co-fermentation of food waste and excess sludge without pH control: the mechanism and microbial community analyses[END_REF], because the C/ N ratio of sewage sludge is only around 6-9, much lower than the desired C/N ratio for anaerobic fermentation around 20-30 [START_REF] Cheng | Fermentative biohydrogen and biomethane co-production from mixture of food waste and sewage sludge: effects of physiochemical properties and mix ratios on fermentation performance[END_REF][START_REF] Li | Solid-state anaerobic digestion for methane production from organic waste[END_REF][START_REF] Zhang | Reviewing the anaerobic digestion of food waste for biogas production[END_REF].

Co-fermentation has attracted attention because of some unique advantages, such as more balanced nutrients and the dilution of inhibition compounds [START_REF] Mata-Alvarez | A critical review on anaerobic co-digestion achievements between 2010 and 2013[END_REF]. It has been proposed T 2.2. Batch test of anaerobic fermentation Batch tests for VFA production were conducted in anaerobic test bottles with a working volume of 400 ml at 30 °C. In each test bottle, the initial TS concentration of substrate was set as 5% and the inoculum amount was determined by setting an inoculum to substrate ratio of 2 on VS weight. To inhibit the activity of methanogens, 2-Bromoethanosulfophate of 19 mmol/L was added in all the test systems before experiments [START_REF] Fang | White rot fungi pretreatment to advance volatile fatty acid production from solid-state fermentation of solid digestate: efficiency and mechanisms[END_REF]. All chemical reagents used in this study were purchased from Sigma-Aldrich.

To investigate the effect of feedstock proportion on the VFA production, the mixed substrate contents labelled as sludge/champost ratio of 100%:0, 75%:25%, 50%:50%, 25%:75% and 0:100% (Table S2). A sludge/champost ratio of 100%:0 and 0:100% represented only sewage sludge and Oyster champost as single substrate, respectively.

Analytic methods

TS and VS were determined on weight base (g/kg) according to the Standard Methods [START_REF] Apha | Standard Methods for the Examination of Water and Wastewater[END_REF]. About 15 g samples was put in aluminum dish at 105 °C for 8 h to determine the TS. After recording the weights, the samples were kept in an oven at 600 °C for 2 h to determine the VS. The C/N ratio was calculated by the ratio of total carbon and total nitrogen weight, which were detected by element analyzer (vario MACRO cube, Elementar, German). For SCOD, NH 4 + eN, PO 4 3--P and VFA measurements, the samples were centrifuged at 12,000 r/min at 4 °C for 15 min, and then filtered by syringe membrane with 0.45 μm (Whatman, Germany). The SCOD, NH 4 + eN and PO 4 3--P concentration in fermentation broth were measured using photometric cell tests (Hach-Lange, Germany). The details of VFA measurement was displayed in the Supporting Materials.

Kinetic modeling of VFA production

Logistic-based model was applied to fit the observed VFA production in this study, which is shown as Eq. (1) [START_REF] Fang | Solid-state anaerobic fermentation of spent mushroom compost for volatile fatty acids production by pH regulation[END_REF]:

= ⎛ ⎝ - ⎞ ⎠ dC dt C Cmax μC 1 VFA VFA VFA (1)
where t refers to the fermentation time (d), C VFA is the VFA concentration, C max is maximum VFA concentration, and μ represents the maximal specific VFA production rate.

Results and discussion

VFA production during anaerobic fermentation

VFA production

VFA yield is an obvious index to evaluate anaerobic fermentation efficiency. The VFA yield in terms of COD under different feedstock proportions during anaerobic fermentation is illustrated in Fig. 1. As shown in Fig. 1, the VFA yield first increased quickly in all fermentation systems and gradually began to a plateau. For single-substrate fermentation systems, the sewage sludge showed obviously higher VFA accumulation compared to that of Oyster champost after 20-day fermentation. The maximal VFA yield of sewage sludge was 521 mgCOD/ gVS added on the 18th day, which was 19.5% higher than that of Oyster champost (436 mgCOD/gVS added ). The VFA yield was within the widely reported range of VFA production from sewage sludge [START_REF] Ferreiro | Anaerobic hydrolysis of primary sludge: influence of sludge concentration and temperature[END_REF][START_REF] Higgins | Pretreatment of a primary and secondary sludge blend at different thermal hydrolysis temperatures: impacts on anaerobic digestion, dewatering and filtrate characteristics[END_REF][START_REF] Yuan | VFA generation from waste activated sludge: effect of temperature and mixing[END_REF]. For co-fermentation system, the maximal VFA yield with a sludge/champost ratio of 75%:25%, 50%:50% and 25%:75% was 512, 596 and 505 mgCOD/ gVS added , respectively.

The results in this study indicated that the sewage sludge had a higher ability of VFA production than the Oyster champost due to the higher biodegradability of sewage sludge than that of lignocellulosic the co-fermentation of sewage sludge with organic wastes such as lignocellulosic biomass is a feasible option to improve the VFA production [START_REF] Guo | Enhanced short chain fatty acids production from waste activated sludge conditioning with typical agricultural residues: carbon source composition regulates community functions[END_REF][START_REF] Huang | Volatile fatty acids produced by co-fermentation of waste activated sludge and henna plant biomass[END_REF][START_REF] Zhou | Volatile fatty acids productivity by anaerobic co-digesting waste activated sludge and corn straw: effect of feedstock proportion[END_REF]. [START_REF] Guo | Enhanced short chain fatty acids production from waste activated sludge conditioning with typical agricultural residues: carbon source composition regulates community functions[END_REF] investigated the improvement of VFA production from sewage sludge by co-fermentation with straw, and around 3-fold improvement in maximal VFA production was observed compared to that from single sewage sludge fermentation. However, most recent tested lignocellulosic biomass usually presents a high content of lignified component, which limits the accessibility of cellulose and hemicellulose to be digested during anaerobic fermentation [START_REF] Shirkavand | Pretreatment of radiata pine using two white rot fungal strains Stereum hirsutum and Trametes versicolor[END_REF]. Therefore, most of these agricultural residues have to be pretreated by mechanical, thermal, chemical methods before co-fermentation [START_REF] Huang | Volatile fatty acids produced by co-fermentation of waste activated sludge and henna plant biomass[END_REF][START_REF] Zhou | Volatile fatty acids productivity by anaerobic co-digesting waste activated sludge and corn straw: effect of feedstock proportion[END_REF][START_REF] Li | Applying rhamnolipid to enhance hydrolysis and acidification of waste activated sludge: retarded methanogenic community evolution and methane production[END_REF]. For example, [START_REF] Zhou | Volatile fatty acids productivity by anaerobic co-digesting waste activated sludge and corn straw: effect of feedstock proportion[END_REF] carried out co-fermentation of waste activated sludge with corn straw to increase the VFA production. The results showed that the maximal VFA yield increased by 69% with 50% corn straw pretreated by ultrasound of 0.5 kW/L for 10 min. Apparently, an efficient and sustainable pretreatment method should be conducted with a maximal VFA productivity and a minimal input of energy and/or chemical reagents, otherwise, the extensive consumption of energy and/or chemicals will restrict their application due to the increase of production cost and operation complexity, as well as potential negative impacts on microorganisms.

Therefore, selection of the suitable agricultural residues with high C/N ratio and low resource input for pretreatment is beneficial to the VFA production from co-fermentation. In addition to above mentioned substrates, Oyster champost, a lignocellulosic byproduct of commercial mushroom industry, may be a promising candidate for VFA production due to its high content of cellulose, hemicellulose and relatively low content of lignin. Besides, the mushroom champost is decomposed and permeated by fungal mycelia during mushroom cultivation, therefore, it is more digestible compared with other lignocellulosic biomass [START_REF] Fang | Volatile fatty acid production from spent mushroom compost: effect of total solid content[END_REF][START_REF] Lin | Integration of Shiitake cultivation and solid-state anaerobic digestion for utilization of woody biomass[END_REF]. Unfortunately, due to limited sustainable disposal strategies, most champost are discarded as low value products in China [START_REF] Shi | Modeling of the methane production and pH value during the anaerobic co-digestion of dairy manure and spent mushroom substrate[END_REF]. In the view of improving treatment and resource recovery from Oyster champost, it is also necessary to find an effective approach to catch up with the treatment capacity of champost. It is hypothesized that the addition of Oyster champost into sewage sludge may improve C/N ratio and prevent the negative impacts of added lignin on the fermentative system. However, so far there is no information reported about the co-fermentation of Oyster champost and sewage sludge for improving the VFA production.

Based on above considerations, the added cellulose-rich champost was expected to increasing an efficiency of co-fermentation. The primary objective of this study was to investigate the feasibility of cofermentation of Oyster champost and sewage sludge for improving the VFA production. Secondly, the effect of feedstock proportion on hydrolytic solubilization of organics, VFA yield and composition was explored. The pH variations and the release of ammonium and phosphate were also observed. Finally, the kinetics of VFA production was analyzed by Logistic-based model.

Materials and methods

Characteristics of Oyster champost and sewage sludge

The Oyster mushroom champost was obtained from one mushroom research plant. The Oyster champost was dried in oven at 70 °C until a constant weight and then stored at room temperature prior to use. The thickened sewage sludge used in this study was taken from a local wastewater treatment plant, which has a treatment capacity of 1.3 million pollution equivalents. Anaerobic sludge used as inoculum was taken from the mesophilic anaerobic digester in the same plant. These two fermentation materials were stored at 4 °C for further use. The main characteristics of these materials are displayed in Table S1. biomass [START_REF] Zhou | VFAs bioproduction from waste activated sludge by coupling pretreatments with Agaricus bisporus substrates conditioning[END_REF]. Hence, it is reasonable that more sewage sludge addition in the mixed substrate would be beneficial to the increase of VFA yield during co-fermentation. The results also consisted with that the partial addition of sewage sludge in Oyster champost improved the VFA yield compared to single-substrate fermentation of Oyster champost. However, it was not always positively correlated with the sewage sludge addition in the feedstock. When the sludge/champost ratio was 50%:50%, the maximal VFA yield was obtained, which was approximately 37% and 14% higher than that of single-champost and single-sludge fermentation. When the sludge/champost ratio was over 50%:50%, less VFAs were produced. The other factors might also influence the VFA production except the substrate ratio, such as the substrate characteristics and C/N ratio. It is worth noticing that the addition of sewage sludge in champost changed initial C/N of mixed substrate, which might be provided more suitable C/N ratio for microbe growth and metabolism [START_REF] Rughoonundun | Influence of carbon-to-nitrogen ratio on the mixed-acid fermentation of wastewater sludge and pretreated bagasse[END_REF]. Generally, a C/N ratio range of 20-30 is considered as the optimum condition for anaerobic fermentation [START_REF] Rughoonundun | Influence of carbon-to-nitrogen ratio on the mixed-acid fermentation of wastewater sludge and pretreated bagasse[END_REF][START_REF] Zhang | Reviewing the anaerobic digestion of food waste for biogas production[END_REF]. The C/N ratio for a sludge/champost ratio of 100%:0, 75%:25%, 50%:50%, 25%:75% and 0:100% was 6.0、12.7、19.3、26.0 and 32.6, respectively. Therefore, the addition of sewage sludge could make C/N ratio was closer to the optimal value. When the sludge/champost ratio was 25%:75%, the initial C/N (26.0) of this system was indeed more suitable than that (19.3) with a higher sludge/champost ratio of 50%:50%, however, the maximum VFA yield was achieved at the sludge/champost ratio of 50%:50%. Possibly the more VFA production was attributed to more easily biodegradable organic matters in sewage sludge rather than the suitable initial C/N.

Table 1 shows the comparison of VFA yield in this study with the published data from co-fermentation of sewage sludge with other organic matters. The maximal VFA yield of 596 mgCOD/gVS added in this study was much higher than that from other combination of sewage sludge with agriculture wastes and alkaline pretreated bagasse. The lower VFA yield in this study than the fermentation of sludge with kitchen wastes was probably due to the fact that the kitchen wastes consist of more easily biodegradable components than the lignocellulosic biomass [START_REF] Vavilin | Hydrolysis kinetics in anaerobic degradation of particulate organic material: an overview[END_REF].

VFA composition during fermentation

In this study, acetate, propionate, butyrate, valerate and hexanate were all detected in all fermentation systems. Table 2 summaries the percentage of individual VFA accounting for total VFAs by the end of anaerobic fermentation. The results indicated that the acetate was the dominant products accounting for 36%-39% in all fermentation systems. And the individual VFA percentage was in the sequence of acetate ˃ propionate ˃ butyrate ˃ valerate ˃ hexanate.

This result coincided with the results from co-fermentation of sewage sludge with rice straw and bagasse [START_REF] Kim | Hydrogen production by anaerobic co-digestion of rice straw and sewage sludge[END_REF][START_REF] Liu | Enhanced volatile fatty acid production by a modified biological pretreatment in anaerobic fermentation of waste activated sludge[END_REF][START_REF] Rughoonundun | Influence of carbon-to-nitrogen ratio on the mixed-acid fermentation of wastewater sludge and pretreated bagasse[END_REF]. The percentage of propionate significantly decreased with the increase of sewage sludge addition, and the decrease was about 12%. However, the percentage of butyrate and velarate increased by about 4% and 8% with the increase of sewage sludge addition. The results can be probably explained by reduction in chain elongation during fermentation process because of the change of C/N ratio [START_REF] Agler | Waste to bioproduct conversion with undefined mixed cultures: the carboxylate platform[END_REF]. The initial C/N ratio can affect the metabolic pathways of microbe for VFA production [START_REF] Lee | A review of the production and applications of waste-derived volatile fatty acids[END_REF]. With a high C/N ratio, the main pathway of propionate production was converted into the glycolytic pyruvate pathway [START_REF] Agler | Waste to bioproduct conversion with undefined mixed cultures: the carboxylate platform[END_REF][START_REF] Rughoonundun | Influence of carbon-to-nitrogen ratio on the mixed-acid fermentation of wastewater sludge and pretreated bagasse[END_REF]. When the C/N ratio decreased, the acetate was mainly produced by the Stickland reaction from amino acids. Besides, all the system showed a lowest hexanate production, which accounted for less than 1.5% in the total VFAs.

Discussion on possible mechanisms

SCOD variation during co-fermentation

Anaerobic digestion is a multi-stage process which consists of hydrolysis, acidogensis, acetogensis and methanogenesis [START_REF] Fang | Effect of alkaline addition on anaerobic sludge digestion with combined pretreatment of alkaline and high pressure homogenization[END_REF]. In the hydrolysis step, insoluble organic materials and higher molecular compounds are degraded into smaller and soluble organic materials, which are further transformed into various VFAs, H 2 and CO 2 during the acidogenesis. SCOD is an important and effective parameter to evaluate the release of organics from substrate to the liquid phase [START_REF] Ma | Novel insight into the relationship between organic substrate composition and volatile fatty acids distribution in acidogenic co-fermentation[END_REF][START_REF] Wang | Rumen fluid fermentation for enhancement of hydrolysis and acidification of grass clipping[END_REF]. As shown in Fig. 2, the SCOD in all systems significantly increased in the first two days, and then slowly increased or remained steady till the end of anaerobic fermentation. The increased SCOD was possibly attributed to the release of protein, polysaccharide and lipid from sewage sludge, and cellulose, hemicellulose from Oyster champost [START_REF] Huang | Volatile fatty acids produced by co-fermentation of waste activated sludge and henna plant biomass[END_REF][START_REF] Wang | Rumen fluid fermentation for enhancement of hydrolysis and acidification of grass clipping[END_REF]. Apparently, the feedstock proportion influenced the release of organic matter from the substrates. For the single-substrate fermentation, it's obvious that the champost released less organic matter and led to lower efficiency of hydrolysis, compared to the sewage sludge. After 20-day anaerobic fermentation, the maximum SCOD of sewage sludge and Oyster champost was 15,873 and 14,450 mg/L, respectively. The complex structure of lignocellulosic biomass, especially the existence of a large amount of lignin in Oyster champost, resulted in the resistance to hydrolysis in this study [START_REF] Fang | Solid-state anaerobic fermentation of spent mushroom compost for volatile fatty acids production by pH regulation[END_REF]. On the other hand, protein and polysaccharide, as main components of sewage sludge, were more easily and quickly biodegraded than the cellulose and hemicellulose in Oyster champost [START_REF] Fang | Solid-state anaerobic fermentation of spent mushroom compost for volatile fatty acids production by pH regulation[END_REF][START_REF] Mata-Alvarez | A critical review on anaerobic co-digestion achievements between 2010 and 2013[END_REF].

In the co-fermentation systems, the SCOD increased with the addition of sewage sludge, and the maximum SCOD of 18,288 mg/L was achieved with a sludge/champost ratio of 50%:50%, which was 13.2% and 26.6% higher than that of single-sludge and single-champost fermentation, respectively. The more hydrolysates could offer more organic matters for further acidification process and lead to higher VFA production. Previous studies have also reported that co-fermentation of lignocellulosic biomass, such as corn straw, bagasse with sewage sludge can improve the solubilization of substrates [START_REF] Rughoonundun | Influence of carbon-to-nitrogen ratio on the mixed-acid fermentation of wastewater sludge and pretreated bagasse[END_REF][START_REF] Zhang | Excess sludge and herbaceous plant co-digestion for volatile fatty acids generation improved by protein and cellulose conversion enhancement[END_REF]. However, the SCOD with a sludge/champost ratio of 75%:25% decreased, which might be attributed to the decrease of C/N ratio of mixed substrate to 12.7. [START_REF] Chen | Enhanced production of short-chain fatty acid by co-fermentation of waste activated sludge and kitchen waste under alkaline conditions and its application to microbial fuel cells[END_REF] investigated the enhancement of VFA production by co-fermentation of waste activated sludge and kitchen wastes, and also found that the organic solubilization was lower at a C/N ratio of 14 than that at a C/N ratio of 22.

VFA/SCOD ratio variation during co-fermentation

VFA/SCOD ratio can reflect the conversion extent of SCOD to VFA during anaerobic fermentation. After anaerobic fermentation, the VFA concentrations with a sludge/champost ratio of 100%:0, 75%:25%, 50%:50%, 25%:75% and 0:100% was 5202, 5019, 5904, 5058 and 4548 mg/L, correspondingly, the VFA/SCOD was 32.8%, 29.8%, 32.3%, 33.3% and 31.5%, respectively. This results revealed that cofermentation could not increase VFA/SCOD ratio, although it increased the VFA concentration in the fermentation broth and VFA yield. Therefore, there were large fraction components in fermentation broth which could not be converted to VFAs during anaerobic fermentation.

To further characterize the organics in fermentation broth, EEM analysis was carried out. As shown in Fig. 3, three peak were detected in the fermentation broth with a sludge/champost ratio of 50%:50% after anaerobic fermentation. According to [START_REF] Chen | Fluorescence excitation[END_REF], these detected peaks corresponded to tryptophan and protein-like (Ex/ Em = 270 nm/350 nm), fulvic-like acids (Ex/Em = 250 nm/460 nm) and humic-like (Ex/Em = 400 nm/460 nm), respectively. It seemed that the residual organics such as protein-like and humic-like components had poor biodegradability, and even negatively impacted the VFA production [START_REF] Gonzalez | Pre-treatments to enhance the biodegradability of waste activated sludge: elucidating the rate limiting step[END_REF]. One of the evidences is that the residual proteins after sludge fermentation were mainly detected as outer membrane proteins, which were mainly from Gram-positive bacteria and difficult to be degraded [START_REF] Tan | Effect of heat-alkaline treatment as a pretreatment method on volatile fatty acid production and protein degradation in excess sludge, pure proteins and pure cultures[END_REF]. [START_REF] Yuan | VFA generation from waste activated sludge: effect of temperature and mixing[END_REF] demonstrated that around 54% of proteins could not be converted to VFAs in the acidogenic stage during anaerobic sludge fermentation. [START_REF] Yin | Improving volatile fatty acids production by exploiting the residual substrates in post-fermented sludge: protease catalysis of refractory protein[END_REF] also reported that poor biodegradability of protein-like materials in the residual fermented sludge limited the further VFA production from sludge. Furthermore, the humic-like substances showed almost no anaerobical biodegradablity [START_REF] Zahmatkesh | A novel approach for application of white rot fungi in wastewater treatment under non-sterile conditions: immobilization of fungi on sorghum[END_REF]. Meanwhile, the existence of humic-like substances could decrease the substrate biodegradation through immobilization enzymes such as protease, cellulase during anaerobic digestion process [START_REF] Dang | Impact of fulvic acids on bio-methanogenic treatment of municipal solid waste incineration leachate[END_REF][START_REF] Gonzalez | Pre-treatments to enhance the biodegradability of waste activated sludge: elucidating the rate limiting step[END_REF].

pH and release of ammonium and phosphate

pH is another important influencing parameter in anaerobic fermentation. Fig. 4 shows the pH variation during anaerobic fermentation. As shown in Fig. 4, the initial pH increased with increasing the sludge addition in the mixed substrate. The pH changes in all fermentation systems were similar: quickly dropping within the first 2 days and then slowly decreasing in the remaining digestion period. After 20day anaerobic fermentation, the pH values reduced to 6.18, 6.06, 6.04, 5.95 and 5.89 with a sludge/champost ratio of 100%:0, 75%:25%, Table 2 Individual VFA percentage of anaerobic fermentation with different sludge/champost ratios.

50%:50%, 25%:75% and 0:100%, respectively, probably due to the VFA accumulations [START_REF] Fang | White rot fungi pretreatment to advance volatile fatty acid production from solid-state fermentation of solid digestate: efficiency and mechanisms[END_REF]. Moreover, as also shown in Fig. 4, the pH of single-substrate champost decreased lower than 6.0 after 12-day anaerobic fermentation. This result could explain why the SCOD of single-champost fermentation did not significantly increase after 12-day anaerobic fermentation (as shown in Fig. 2). It has been reported that the activities of cellulolytic bacteria and hydrolysis of lignocellulosic biomass were totally inhibited at a pH lower than 6.0 [START_REF] Mould | Associative effects of mixed feeds. I. Effects of type and level of supplementation and the influence of the rumen fluid pH on cellulolysis in vivo and dry matter digestion of various roughages[END_REF][START_REF] Russell | Why are ruminal cellulolytic bacteria unable to digest cellulose at low pH?[END_REF]. Besides, it is also worthy noticing that the pH of 5.95 at a sludge/champost ratio of 25%:75% was lower than 6.0, which could inhibit the hydrolysis of lignocellulosic biomass [START_REF] Russell | Why are ruminal cellulolytic bacteria unable to digest cellulose at low pH?[END_REF]. The lower pH might be another reason for the lower VFA production at a sludge/champost ratio of 25%:75% than that at a sludge/ champost ratio of 50%:50%. On the other hand, the pH of single-sludge fermentation was always higher than that of single-champost fermentation, indicating that the sewage sludge had better buffer capacity than the Oyster champost. In the co-fermentation systems, the system pH was always higher than 6.0 during the whole anaerobic fermentation, which met the minimum pH requirement for organic hydrolysis. Hence, the co-fermentation system had enough buffer capacity for anaerobic fermentation, and it was not necessary to dose chemicals to keep a stable pH for VFA production.

Ammonia released from the substrate during hydrolysis can act as a pH buffer. The initial ammonium concentrations in all tests were in a range from 80 to 110 mg/L at a pH below 7.0. Hence, the free ammonia concentration was not enough high to inhibit anaerobic digestion process [START_REF] Appels | Principles and potential of the anaerobic digestion of waste-activated sludge[END_REF]. After anaerobic fermentation, the ammonium concentrations of systems increased with the increase of sewage sludge addition, and reached about 2660, 2380, 2210, 2180 and 1820 mg/L with a sludge/champost ratio of 100%:0, 75%:25%, 50%:50%, 25%:75% and 0:100%, respectively. More ammonium might be mainly released from the degradation of proteins and amino acids of sewage sludge [START_REF] Nagase | Interactions between amino-acid-degrading bacteria and methanogenic bacteria in anaerobic digestion[END_REF]. Interestingly, the variation of ammonium concentration showed similar trend with pH variations with different sludge proportions. Probably the suitable increase of ammonium concentration provided a better buffer capacity for the co-fermentation systems, ensuring that the system pH was in a suitable range during anaerobic fermentation process. Besides, after anaerobic fermentation phosphate concentration of systems increased with the increase of sewage sludge addition, and was observed approximately 570, 480, 470, 480 and 390 mg/L with a sludge/champost ratio of 100%:0, 75%:25%, 50%:50%, 25%:75% and 0:100%, respectively. The higher phosphate concentration with addition of sewage sludge was probably contributed to biodegradation of phosphorus compounds, which was stored as polyphosphates in sewage sludge, such as cell wall and lipid.

The excessive ammonium and phosphate in fermentation broth may influence the VFA recovery and the quality of subsequent products [START_REF] Lee | A review of the production and applications of waste-derived volatile fatty acids[END_REF]. The ammonium and phosphate concentration with a sludge/champost ratio of 50%:50% were higher than those of singlechampost fermentation, but about 17% and 18% lower than those of single-sludge fermentation, respectively. Considering the purpose of VFA production in this study, the co-fermentation with a sludge/ champost ratio of 50%:50% produced maximal VFA yield with the lowest release of ammonium and phosphate. The optimal substrate proportion of sludge/champost ratio = 50%:50% for co-fermentation should be selected. In the view of resource recovery of nitrogen and phosphorus from fermentation broth, the simultaneous recovery of ammonium and phosphate in a form of struvite or dry ammonium can be considered as a competitive method, and the products can be utilized as a fertilizer [START_REF] Liu | Enhanced volatile fatty acid production by a modified biological pretreatment in anaerobic fermentation of waste activated sludge[END_REF].

Kinetic modeling of co-fermentation

In this study, the modified-Logistic model was used to assess VFA production during anaerobic fermentation with different sludge/ champost ratios. According to VFA concentration obtained from experiments, we fitted and calculated various kinetic parameters by Origin 8.0. The relevant results are presented in Table 3 and Fig. 5. It revealed that the VFA production from all fermentation systems were well fitted by modified-Logistic model with a R 2 from 0.9940 to 0.9994. The VFA production from champost was improved by co-fermentation with sewage sludge addition in different proportions, and the maximum VFA production was 6003 mg/L was obtained with a sludge/champost ratio of 50%:50%. The high maximal specific VFA production rate of 4.04 with a sludge/champost ratio of 50%:50% indicated a faster rate and higher efficiency of VFA production. The modeling results indicated that the co-fermentation with sewage sludge addition was significantly enhanced the VFA production.

Conclusions

This study showed hydrolysis and VFA production from celluloserich Oyster champost was successfully enhanced by the addition of sewage sludge. The maximal VFA yield of 596 mgCOD/gVS added was achieved with a sludge/champost ratio of 50%:50%, which was approximately 37% and 14% higher than that of single-champost and single-sludge fermentation. The Oyster champost and sewage sludge played a critical role in regulation initial C/N rate for improving hydrolysis rate and biodegradation, as well as variations of VFA composition during anaerobic fermentation. The maximum SCOD in all fermentation systems was obtained with a sludge/champost ratio of 50%:50%, which was 13.2% and 26.6% higher than that of singlesludge and single-champost fermentation, respectively. The addition proportion of sewage sludge did not change fermentative type, and the acetate was dominant VFA product accounting for 36%-39%. During the co-fermentation process, ammonium and phosphate were released because of degradation of organic matters in sewage sludge. A Logisticbased model well described the VFA production process, showing that the co-fermentation with sewage sludge addition was significantly enhanced the VFA production from Oyster champost. The above co-fermentation process provides a promising way to simultaneously recover the high-value bioproducts from cellulose-rich Oyster champost and sewage sludge.

Fig. 1 .

 1 Fig. 1. Effect of feedstock proportion on VFA yield anaerobic fermentation.

Fig. 2 .

 2 Fig. 2. Effect of feedstock proportion SCOD concentration during anaerobic fermentation.Fig.3. Three-dimensional fluorescence pattern of fermentation broth with a sludge/champost ratio of 50%:50% by the end of anaerobic fermentation.

Fig. 4 .

 4 Fig. 4. pH variation during anaerobic fermentation.

Table 1

 1 Comparison of VFA yield from sludge with different organic substrates.

	Substrate	Average VFA yield	Operation conditions	References
	Dewatered sludge + kitchen waste	392 mg/gVSS added	Batch test, 35 °C, initial pH = 7.0 ± 0.1, fermentation time = 9 d	Hong and Haiyun (2010)
	Waste activated sludge + agriculture wastes	487 mgCOD/	Continuously stirred-tank reactors, mesophilic condition,	Guo et al. (2016)
		gVSS added	pH = 10.0 ± 0.5, Sludge retention time = 5 d
	Waste activated sludge + kitchen waste	670 mgCOD/	Semi-continuous-flow reactors, 37 °C, pH = 8.0, fermentation time = 6 d	Chen et al. (2013)
		gVS added
	Waste activated sludge + pretreated bagasse	360 mg/gVSS added	Batch test, 55 °C, pH = 7.0, fermentation time = 20 d	Rughoonundun et al. (2012)
	Thickened sludge + Oyster champost	596 mgCOD/
		gVS

added Batch test, 30 °C, without pH control, fermentation time = 18 d This study

Table 3

 3 Main fitted kinetics parameters of Logistic model with different sludge/champost ratios.

	Sludge/champost ratio	Logistic model
		C max (mg/L)	μ (d -1 )	R 2
	100%:0	5242 ± 80.5	3.98 ± 0.29	0.9940
	75%:25%	5196 ± 78.9	4.09 ± 0.28	0.9993
	50%:50%	6003 ± 96.3	4.04 ± 0.33	0.9970
	25%:75%	4971 ± 78.8	3.66 ± 0.18	0.9952
	0:100%	4631 ± 69.2	3.75 ± 0.23	0.9994

Acknowledgments

The authors acknowledge the National Natural Science Foundation of China (51578068) and the "One Thousand Talent Plan" Youth Program for funding this research.

Appendix A. Supplementary data

Supplementary data to this article can be found online at https://