PageRank with Priors: An Influence Propagation Perspective

1 Introduction

As people becoming more inextricably linked through the power of information technology, huge social network data have been collected. These network data provide unparallel opportunities for researchers to understand the human world and generate useful knowledge. Indeed, tremendous efforts have been made for measuring authority [Farahat et al., 2006] and modelling social influence [Aggarwal, 2011].

Generally, in traditional social network analysis, the term authority is used for estimating the endorsement that is received by the node from its inlinks, and the classic models include PageRank [Page et al., 1999] and HITS [Kleinberg, 1999], which were first proposed for ranking web pages. However, social influence (or influence for short) is the impact that an individual has on others (e.g., leading to the change of their opinions or behaviors) from their outlinks. The Independent Cascade (IC) model [Goldenberg et al., 2001] and the Linear Threshold (LT) model [Granovetter, 1978] are two of the most popular models for describing influence propagation. In fact, a web page is ranked highly if many authoritative pages point to it, and an individual is valued most if he/she influences many influential people. While authority and influence appear quite different at a first glance, several researchers have sensed that they are essentially the same: The individual earns authority by influencing others. This is also the reason that the PageRank algorithm has been used as a solid baseline for evaluating social influence related applications [Aggarwal et al., 2011; Chen et al., 2010; Goyal et al., 2010b; 2011; Liu et al., 2012; Tang et al., 2009].

Nonetheless, there are still two questions to answer. First, what is the connection between PageRank and social influence models. Second, can social influence models help better understand the authority values obtained by PageRank? To answer these two questions, in this paper, we first propose a linear and tractable social influence model which is an approximation of the IC model (which is untractable). Then, we show that this linear model is essentially PageRank with prior, i.e., the PageRank algorithm is actually a special case of this linear model. Therefore, we argue that the authority of each node is essentially the collection of its influences on the network or a specific subnetwork. Based on this finding, we reveal that many similar and effective authority computation methods, which consider more prior knowledge, can be obtained by simply changing the parameter settings in the proposed linear model. Meanwhile, we show that the PageRank value can be used to form an upper bound, which is further used to develop an efficient algorithm for finding the most authoritative nodes with general priors. Finally, we validate these discoveries by performing experiments on a real-world collaboration network. To the best of our knowledge, this is the first comprehensive attempt for exploring and building connections between the researches on PageRank and influence, with a focus on understanding both the traditional and topic-sensitive PageRanks in an influence perspective.

2 Background and RelatedWork

Let G = (V,A,W, T) be a network (as shown in Figure 1), where node set V = {1, 2, ..., n} and edge set A represents all the connections between nodes. W = [wi j]n∗n is the PageRank matrix, wi j represents the strength of the endorsement from node i to node j. T = [ti j]n∗n is a transmission matrix for influence propagation, ti j represents the propagation probability from node i to node j. If there is an edge from j to i in A (i.e., j trusts i), then wji > 0 and ti j > 0 1 , otherwise wji = ti j = 0. Since learning the non-zero ti j and wi j [Goyal et al., 2010a] is beyond the scope of this paper, we assume they are known and usually n∑ i=1 ti j ≤ 1 [Yang et al., 2012] and n∑ j=1 wi j = 1 [Bianchini et al., 2005]. Notably, W ′ is actually a specification of T in mathematics. Here, we present W and T simultaneously because we will study both PageRank and influence model through a common network framework. G is assumed to be directed, as influence propagation is specific to direction in the most general case [Aggarwal et al., 2011] 2 .

Authority Computation by PageRank. PageRank [Page et al., 1999] has been widely known as a reputable way to obtain an authority score for a node based on the network connectivity. The general PageRank values x = [x1, x2, ..., xn] ′ of the nodes in a network could be formalized as:

where d ∈ (0, 1) is a damping factor, and e = [1, 1, ...1] ′ . It has been proved that the above iterative process is stable and the linear system always converges [Bianchini et al., 2005]. There are also some improvements for PageRank to better measure nodes' authorities by including domain knowledge. A typical way is to add different edge weights to get a more precise W [Ding et al., 2009]. Also, an alternative way is to use priors to obtain a nonuniform personalization vector instead of 1 n e [Haveliwala, 2003]. As an effective and efficient algorithm, PageRank has been applied to a number of applications for authority computation, such as Web search [Page et al., 1999], bibliometrics analysis [Ding, 2011], item recommendations [Liu et al., 2012], link predictions [LibenNowell and Kleinberg, 2007] and expert finding [Zhu et al., 2011]. Langville et al. presented a comprehensive survey of the issues related to PageRank [Langville and Meyer, 2004]. To the best of our knowledge, most of the existing works use PageRank to get an overall or topic-based single value for measuring the node's importance, and have limited focuses on understanding PageRank by exploiting the authority endorsement between nodes.

Influence Models and Computation. Several models [Kimura and Saito, 2006; Chen et al., 2010; Aggarwal et al., 2011] were provided to describe the dynamics of influence propagation. Among them, the IC model [Goldenberg et al., 2001] is widely used. In IC model, the activated/influenced nodes have a single chance to influence their neighbors independently with a probability. This iterative propagation process will not stop until there is no newly influenced node. The IC model where each link shares the same propagation probability is called the Uniform IC Model, and the one with edge weights is called the Weighted Cascade (WC) Model [Kempe et al., 2003].

1 If j trusts i, then j will endorse i while i influences j.

2 The proposed techniques can be applied to undirected networks.

An ultimate goal of social influence models is to find the most influential nodes by computing the spread of their influences. However, most of the existing models are usually untractable. To that end, a large number of Monte Carlo simulations are needed. To improve computational efficiency, many heuristics have been proposed. For instance, Leskovec et al. [Leskovec et al., 2007] designed the cost-effective lazy forward (CELF) optimization, and Chen et al. [Chen et al., 2009; 2010] proposed both the Degree Discount heuristic and the Maximum Influence Path heuristic. Similarly, Kimura et al. [Kimura and Saito, 2006] proposed the shortest-path based influence algorithm. Aggarwal et al. [Aggarwal et al., 2011] proposed the SteadyStateSpread method by solving a system of nonlinear equations for computing the influence spread under the IC model. Moreover, Yang et al. [Yang et al., 2012] observed that propagation probabilities in realworld networks are usually quite small, and thus proposed a quick approximation of influence spread by solving a linear system. In addition, many researchers also consider some constraints in practice. For instance, both Chen et al. [Chen et al., 2012] and Goyal et al.[Goyal et al., 2010b] included time constraints into their approximation algorithms, and Tang et al. [Tang et al., 2009] proposed topical affinity propagation to model the topic-level social influence.

3 Social influence modelling

In this section, we propose a linear social influence model which is both tractable and efficient. For better illustration, Table 1 shows some math notations.

ProblemFormulation. In the literature of influence propagation, there are two well-known assumptions [Goldenberg et al., 2001; Granovetter, 1978]: 1) if one is the initiator of something (e.g. opinion, behavior), he/she will spread that with 100% probability; 2) otherwise, this probability will depend on his/her neighbors' influence. However, in the realworld each initiator may not spread the thing with 100% probability (e.g., for lack of self-confidence), i.e., we should take prior knowledge into the first assumption for describing how much probability the node spreads influence to the neighbors. Thus, we could propose an influence model as follows:

Definition 1 Denote the influence from i to j by fi→j, then

where Nj = { j1, j2, ... jm} is j's trust-friends set (i.e., ∀k ∈ Nj, there is a connection ( j, k) ∈ A). In this definition, we assign each node i a prior probability value αi. If i has a full probability to spread the information, this value should be the maximum (e.g., 1) 3 . In another direction, if i has no interest at all, it will be 0. Meanwhile, another major difference from the traditional models is that we assume the influence flowing to node j is proportional to the linear combination of the influence to j's neighbors (see Equation (3)). Thus, the computation of influence will be a linear efficient way. Here, the parameter λj is the damping coefficient of j for the influence propagation. It locates in range (0, +∞), and the smaller λj is, the less influence will be blocked by node j. For simplicity, we choose the same λ for each node, and name λI as the damping matrix. Similarly, we denote fi→T= ∑ j∈T fi→j as the

influence spread from node i to a group of nodes T; that is, it stands for the total influence to the entire network if T = V.

Influence Computation. Under the above model definition, we can solve the influence spread vector fi = [ fi→1, fi→2, ... fi→n] ′ for each node i as follows. First, we can rewrite Equation (2) and Equation (3) as

where νi = [0, 0, ..., νi,i, ...0] ′ is a vector with only the i-th entry νi,i is nonzero; that is, νi,i should be equal to a number to guarantee fi→i = αi as described in Equation (2). In this equation, (I + λI - T ′ ) is invertible because its transpose is strictly diagonally dominant, and n ∗ n matrix P = (I + λI - T ′ ) -1 . As νi is a vector with only νi,i is nonzero, Equation (5) could be rewritten as fi = νi,iP·i. Specifically, fi→i = νi,i pii, with Equation (2), we could get

Since P is a positive definite matrix, pii > 0. Then, the total influence from node i to the entire network G should be

Given two types of parameters αi and λ, and the influence transmission matrix T, to get the influence vector fi, we only need to compute the i-th column of P (P·i), which can be computed in O(|A|) since P -1 P·i = ei is a linear system which satisfies the Gauss-Seidel condition.

This linear influence model has close relationship with the traditional ones. For instance, it is easy to prove that the linear approximation method for the IC model [Yang et al., 2012] is actually a specialization of our linear model when λ = 0 and αi = 1. Also, the non-linear stochastic model [Aggarwal et al., 2011] can be well approximated by our model when λi ∈ [0, 1) and αi = 1. The detailed proof is omitted due to the space limit. For the same reason, in the experiments, we just provide the evaluation results on authority measurement rather than finding the most influential nodes.

3 If initially αi > 1, we could normalize it into (0,1].

4 PageRank with Prior

Here, we find that this linear model is essentially PageRank with prior. Let us first solve Equation (1) algebraically:

SinceW ′ is actually a specification of influence transmission matrix T (Section 2), we could further replace matrix (I+λIW ′ ) -1 by the matrix P ′ (Equation (4)), that is

Comparing with Equation (7), we find that

which proves the following theorem.

Theorem 1 The PageRank value of one node (xi) is actually its total influence to the entire network ( fi→V) under linear influence model when 1) T = W ′ , 2) αi = λ n pii.

If we further use [xi,1, xi,2, ..., xi,n] ′ to denote the authority obtained by node i from each endorsement, we can have xi = n∑ j=1 xi, j, and xi, j = λ n pji. Based on the above, we know:

• PageRank is actually a special case of our linear social influence model. Thus, PageRank has strong connections with existing social influence models and this is also the reason that PageRank serves as a strong baseline in social influence related applications. Meanwhile, setting αi = λ n pii enables the computation of the PageRank values to be linear time (we will explain this later). However, is λ n pii an appropriate prior? Do there exist more accurate ones? In the following, we will present other possible priors along this line;
• When computing authority and influence, the major difference is just using wji or ti j. In most of existing works, they are determined in the same way, i.e., equal to or proportional to Weight(Aji) OutWeight( j) [Bianchini et al., 2005; Kempe et al., 2003], so the authority and influence computed are actually the same thing. In other words, the amount of authority endorsement given from node j to node i is depending on the number of influence flows from i to j (xi, j ∝ fi→j), and vice versa. One step further, we argue that each node's authority (influence) is essentially the collection of its influence (authority) on the network or a subnetwork (e.g., topic-sensitive).

In the following, we use the expression in Equation (8) to represent PageRank. Since influence spread and authority are essentially one concept and they can be distinguished from the context, we use authority/authoritative to stand for both of them. Also, as λ n is a constant and we mainly focus on finding the nodes' relative ranks rather than estimating their true PageRank value, we consider αi to be pii in PageRank.

Implications. From the above discussions, we know that the PageRank value xi is actually fi→V with a specific αi (i.e., αi ∝ pii). Since the traditional PageRank algorithm just considers the total authority (or influence spread) of each node, and αi ∝ pii is the only way to make the computation of authority is linear time. Let f = [ f1→V, ..., fn→V] ′ , and vector

n∑ j=1

on Equation (6) and Equation (7): f = [ α1 p11 P·1, ..., αn pnn P·n] ′ e.

To solve f, if αi is not proportional to pii (i.e., αi ̸ ∝ pii), we have to compute the matrix P which is O(n 2 ). Otherwise, just as PageRank does, we can get f ∝ P ′ e = p. Then based on the Gauss-Seidel method, this linear system can be solved in O(|A|), and both f and p can be quickly computed, e.g.,

We know why PageRank is efficient. However, it seems that it is more reasonable to set each αi to be a positive constant when lacking of prior knowledge, or having some prior domain knowledge for guiding this value. For instance, to mine the most influential researchers, we can use the number of their publications as a prior (e.g., αi = log(#Publicationi)).

However, if αi ̸ ∝ pii, we have to compute each P·i to get fi→V (or xi), which will take O(|A|) for each i. In total, it takes O(n|A|) to compute f, which is the n times of the PageRank computation time. In practice, we usually are more interested in finding Top-K authoritative ones, the problem then becomes how to quickly estimate each node's authority and filter out insignificant nodes. Indeed, we find out that, for each possible α, the aforementioned p, which can be computed in O(|A|), can be used to form an upper bound for speedup.

Upper Bound and Selection of Top-K Nodes. For a given prior αi, node i's total authority/influence (for consistency, we note it as fi→V rather than xi) is no larger than (1 + λ)αi pi.

This upper bound can be proved in the following way. By Equation (5), we have P -1 fi = (I + λI - T ′ )fi = νi, and thus (1+λ)αi - ∑knequali tki fi→k = νi,i. Since both tki ≥ 0 and fi→k ≥ 0, we can get νi,i ≤ (1 + λ)αi. Meanwhile, as fi→j = pjiνi,i,

For finding the Top-K authoritative nodes (when αi ̸ ∝ pii), we first compute all [(1+λ)αi pi]s in O(|A|), and then use them to save computations. Algorithm 1 describes the proposed framework. In a nutshell, if we only have to compute the pairwise authority value for N nodes, the time complexity of Algorithm 1 is O((N + 1)|A|).

General Applications. As our linear model can generalize the PageRank based authority computation by introducing more prior knowledge (αi), Algorithm 1 is also a general framework that will be useful in a number of scenarios. For instance, based on the finding that each node's total authority is actually a collection of its pairwise authorities, we can easily get the most authoritative ones to a specific subnetwork (e.g., the gray nodes in Figure 1) given the whole network structure (or topic/domain-sensitive authority) [Haveliwala, 2003]. Indeed, with the help of generalized authority and Algorithm 1, we can now effectively and efficiently solve this topic-sensitive authority computation as long as we collect the topic profiles (e.g., age, country) of each individual. Specifically, in Algorithm 1, we just need to change the target node set (V) from the entire network to the ones that we are

Algorithm 1: Top-K Nodes Selection (G, λ, α, K)

input : G = (V,A, T,W), λ, [α1, ..., αn], K output: S: the set of Top-K authoritative nodes. S=∅; Compute p = [p1, ..., pn] ′ in O(|A|) time; //Equation (9) for each node i do Ui = (1 + λ)αi pi; // Upper bound IsBoundi = True; while |S| < K do Find node d with the biggest Ud in U; if IsBoundd == True then Compute fd→j = αd pdd pjd for all js in O(|A|) time; //Solve P -1 P·d = e·d by Gauss-Seidel method Ud = fd→V; //Equation (7) IsBoundd = False; else S = S ⋃ d; Ud =MINIM; //E.g., 0 return S;

interested in (e.g., a subgroup T) by summarizing and comparing fd→T= ∑ j∈T fd→j for each authoritative candidate node d.

5 Experimental Results

We provide empirical validation on a real-world collaboration network from DBLP (http://dblp.uni-trier.de/xml/).

Experimental Setup.We focus on six research domains related to Artificial Intelligence, which are noted as "Artificial Intelligence" (AI), "Computer Vision" (CV), "Database" (DB), "Data Mining" (DM), "Information Retrieval" (IR) and "Machine Learning" (ML). We select the research papers published before January 2013 in several topranked journals and conferences from each domain, and the authors are used as nodes to construct the scientific collaboration network G (shown in Table 2). Specifically, an edge Aji is added when two researchers have one co-authored paper, and the weight is accumulated by the contribution of this author pair on each of their collaborated paper; that is, their contribution for one paper with k authors is 1 C 2 . Finally, each

Aji is normalized intowji by Weight(Aji) OutWeight( j) . In this way, there are total 53, 872 nodes and 160, 968 edges in G. Meanwhile, for domain-sensitive authority, if the researcher has publications in the conferences/journals of this research domain, then this researcher is classified into the target group T of this research topic/domain, and the nodes' authorities on T are computed.

k

Since we focus on evaluating the effectiveness of the linear model with respect to different priors (αi) and Algorithm 1, we choose five methods listed in Table 3 for comparison, where PageRank can be also viewed as a baseline. One of the simply designed prior Con f (i) is computed by log(1+CDi+∑j wjiCDj), whereCDi is the observed contribution of researcher i in this specific domain denoted by ∑ pDi 1 #AuthorspDi and pDi is one publication of i in this domain. For each method, we choose the same λ = 0.176, and d = 1 1+λ = 0.85.

Selection of Top-K Researchers. In the following, we show a performance comparison by mining top authoritative researchers in each domain. Since the methods only work on a scientific collaboration network with limited information, the results may not ideally reflect the real situation.

First, we show a case study by illustrating the names of the authoritative researchers in each research domain for K=10 in Table 4, where "Total" means the entire collaboration network G. In Table 4, we can see that the results contain influential researchers from different research domains. Even though the methods(or priors) are quite different from each other, the authoritative nodes determined are quite similar, which has been reported before [Aggarwal et al., 2011]. Meanwhile, though the results obtained by Random(α) are comparatively different from others, its output are also wellknown researchers which demonstrate that not only the prior but also the network structure contributes to the final result.

In addition, since it is impossible to present more researchers for manual analysis, we provide the average Hindex results as an alternative. Though there are several limitations for evaluating researchers by H-index, we have two reasons to choose it as a metric. First, H-index can measure both quality and quantity of the published works of researchers based on the number of citations. As we don't include the citation information for the collaboration network, it is reasonable to use a citation metric; Second, among all the metrics for measuring researchers, H-index is well accepted, and it has been widely used in bibliometric analysis [Ding et al., 2009]. Thus, Table 5 lists the average H-index results for Top-50 ranked researchers, where the H-indexes are collected simultaneously in May, 2012. In Table 5, we can see that the methods considering reasonable prior knowledge (e.g., S ame(α), Prior(α) and WPageRank) generally perform better than those not (i.e, PageRank and Random(α)). Also, Same(α) outperforms others by setting the prior probability of each candidate as the same value. This indicates that without useful prior knowledge, it is more reasonable to assign αi to be the same rather than pii as PageRank does.

Figure 2 shows the pii values (PageRank priors) of the Top-

50 researchers (ordered by nodes' degrees), from which we cannot find any meaningful patterns, and the results again demonstrate that it is not the best choice to use these values as the prior αi for each candidate node. For instance, it is improper to set the prior of Charu C. Aggarwal much lower. However, this does help us understand the results in Table 4.

Upper Bound Evaluation. To evaluate the upper bound in Algorithm 1, we present the number of searched candidates (N) for finding the Top-50 researchers in Table 6. We can observe that this number is quite small with respect to the entire search space (n), which indicates that Algorithm 1 is scalable. Another interesting observation is that the selected upper bound is tight for the Prior(α) method, as it takes the least time for Prior(α) to return the Top-50 researchers. For better understanding, we also illustrate the true authority value (computed by Same(α) and Prior(α) respectively) and the upper bounds for 1, 500 randomly selected researchers in Figure 3, where we can observe that the upper bounds are always close to the real authority values and this is the reason that each method just has to scan a limited number of candidates for finding the most authoritative researchers (Table 6).

Correlation Demonstration. For the purpose of further understanding the research domains and the priors, Figure 4 shows the Jaccard similarity coefficient of the selected top researchers (Top-50 for each research domain by each method).

Specifically, Figure 4.(a) demonstrates the coefficient of the top authoritative researcher set between different research domains, and Figure 4.(b) are the coefficient of the top authoritative researcher set output by different methods. In Figure 4.(a) all the five methods' output researchers for one domain are summarized together to stand for this domain, and similarly, in Figure 4.(b) all the six research domains' top researchers gained by the given method are used to stand for this specific method. From Figure 4.(a) we can see that the top researchers mined from the entire network are selected from each single domain which is supported by the similar coefficients between Total domain with six single domains. Among these six domains, CV is the most independent one and has few research connections with others, and the top researchers in AI only have limited connections with those in ML. It is also very interesting to observe that DB, DM and IR are close to each other and have the most top authoritative researchers in common. The different types of coefficient between different methods are more clear as shown in Figure 4.(b), and the most distinctive method is Random(α). In contrast, the the most similar two pairs of methods are (PageRank, WPageRank) and (Same(α), Prior(α)), due to the similarity of their priors.

6 Conclusion

In this paper, we provided an understanding of PageRank and authority from an influence propagation perspective. Along this line, we first developed a linear social influence model, which generalizes the authority computation of PageRank by introducing priors. Also, we revealed that the authority of each node is essentially the collection of its influence on the network or a specific subnetwork. Furthermore, we showed that many similar and effective authority computation methods, which consider more prior knowledge, can be obtained by different parameter settings in the proposed linear social influence model. Meanwhile, we found that the PageRank value can be used to form an upper bound for efficiently computing the most authoritative nodes. Finally, an empirical study was conducted on a real-world DBLP data set to show the effectiveness of the proposed social influence model. In the future, we plan to further evaluate our finding using more data and analyze the connection between authority and influence on other influence models (e.g., IC model, LT model).

Acknowledgements

The work was partially supported by grants from Natural Science Foundation of China (Grant No. 61073110), the Key Program of National Natural Science Foundation of China

(Grant No. 60933013), Research Fund for the Doctoral Program of Higher Education of China (20113402110024), and National Science Foundation (NSF) via grant numbers CCF1018151 and IIS-1256016.