PageRank Revisited: On the Relationship between Node Degrees and Node Significances in Different Applications ∗ Jung Hyun Kim K. Selçuk Candan Maria Luisa Sapino Arizona State University Arizona State University University of Torino Tempe, AZ 85287, USA Tempe, AZ 85287-8809 I-10149 Torino, Italy jkim294@asu.edu candan@asu.edu marialuisa.sapino@unito.it ABSTRACT dation tasks [1, 7, 9, 12, 26]. The significance of a node in a given Random-walk based techniques, such as PageRank, encode the graph often needs to reflect the topology of the graph. Measures structure of the graph in the form of a transition matrix of a stochas- like the betweenness measure [27] and the centrality/cohesion [5], tic process from which significances of the graph nodes can be in- help quantify how significant any node is on a given graph based on ferred. Recommendation systems leverage such node significance the underlying graph topology. The betweenness measure [27], for measures to rank the objects in the database. Context-aware recom- example, quantifies whether deleting the node would disconnect or mendation techniques complement the data graph with additional disrupt the graph. Centrality/cohesion [5] measures quantify how data that provide the recommendation context. However, despite close to a clique the given node and its neighbors are. Other au- their wide-spread use in many graph-based knowledge discovery thority, prestige, and prominence measures [1, 5, 6] quantify the and recommendation applications, conventional PageRank-based significance of the node through eigen-analysis or random walks, measures have various shortcomings. As we experimentally show which help measure how reachable a node is in the graph. in this paper, one such shortcoming is that PageRank scores are 1.1 PageRank as a Measure of Significance tightly coupled with the degrees of the graph nodes, whereas in Since enumerating all paths among the graph nodes would re- many applications the relationship between the significance of the quire time exponential in the size of the graph, random-walk based node and its degree in the underlying network may not be as im- techniques encode the structure of the network in the form of a tran- plied by PageRank-based measures. In fact, as we also show in sition matrix of a stochastic process from which the node signifi- the paper, in certain applications, the significance of the node may cance can be inferred.PageRank [6] is one of the most widely-used be negatively correlated with the node degree and in such appli- random-walk based methods for measuring node significance and cations a naive application of PageRank may return poor results. has been used in a variety of application domains, including web To address these challenges, in this paper, we propose degree de- search, biology, and social networks. The basic thesis of PageR- coupled PageRank (D2PR) techniques to improve the effectiveness ank is that a node is important if it is pointed to by other important of PageRank based knowledge discovery and recommendation sys- nodes – it takes into account the connectivity of nodes in the graph tems. These suitably penalize or (if needed) boost the transition by defining the score of the node vi ∈ V as the amount of time strength based on the degree of a given node to adapt the node sig- spent on vi in a sufficiently long random walk on the graph. More nificances based on the network and application characteristics. specifically, given a graph G(V, E), the PageRank scores are rep- resented as ~r, where 1. INTRODUCTION In recent years, there has been considerable interest in measuring ~r = αTG~r + (1 − α)~t the significance of a node in a graph and relatedness between two where TG is a transition matrix corresponding to the graph G, ~t is nodes in the graph, as if measured accurately, these can be used a teleportation vector (such that ~t[i] = kV1 k ), and α is the residual for supporting many knowledge discovery, search, and recommen- probability (or equivalently, (1 − α) is the so-called teleportation ∗ probability). Unless the graph is weighted, the transition matrix, This work is supported by NSF Grants 1339835 ”E-SDMS: Energy Sim- ulation Data Management System Software”, 1318788 ”Data Manage- TG , is constructed such that for a node v with k (outgoing) neigh- ment for Real-Time Data Driven Epidemic Spread Simulations”, 1518939 bors, the transition probability from v to each of its (outgoing) ”RAPID: Understanding the Evolution Patterns of the Ebola Outbreak in neighbors will be 1/k. If the graph is weighted, then the transi- West-Africa and Supporting Real-Time Decision Making and Hypothesis Testing through Large Scale Simulations”, and 1430144 ”Fraud Detection tion probabilities are adjusted in a way to account for the relative via Visual Analytics: An Infrastructure to Support Complex Financial Pat- weights of the (outgoing) edges. terns (CFP) based Real-Time Services Delivery”. 1.2 Tight Coupling of PageRank Scores of Nodes and their Degrees Let us consider an undirected graph G(V, E). There are two factors that contribute to the PageRank of a given node, v ∈ V : • Factor 1: Significance of Neighbors: The more significant c 2016, Copyright is with the authors. Published in the Workshop Pro- the neighbors of a node are, the higher its likelihood to be ceedings of the EDBT/ICDT 2016 Joint Conference (March 15, 2016, Bor- also significant. deaux, France) on CEUR-WS.org (ISSN 1613-0073). Distribution of this paper is permitted under the terms of the Creative Commons license CC- • Factor 2: Number of Neighbors (Degree of the Node) : Even by-nc-nd 4.0 if the neighbors are not all significant, a large number of Listener Graph Article Graph Movie Graph Data Set (Friendship (co-author (co-contributor of PageRank based knowledge discovery and recommendation sys- edges, Last.fm) edges, DBLP) edges, DBLP) tems. These techniques suitably penalize or (if needed) boost1 the Correlation between 0.988 0.997 0.848 transition strength based on the degree of a given node to adapt the PageRank and Degree node significances based on the network and application charac- Table 1: Spearman’s rank correlation between the node degree teristics. This paper is organized as follows: Next, we discuss the ranks and the node ranks’ based on PageRank scores for vari- related literature. In Sections 3, we introduce the proposed degree- ous data graphs (see Section 4 for details of the data sets) decoupled PageRank techniques. We evaluate the proposed tech- niques in Section 4 and conclude in Section 5. neighbors would imply that the node, v, is well-connected and, thus, likely to be structurally important. 2. RELATED WORKS In theory, these two factors should complement each other. In prac- tice, however, the PageRank formulation described above implies 2.1 Context-Sensitive PageRank that there is a very tight coupling between the degrees of the nodes Path-length based definitions of node relatedness, such as those in the graph and their PageRank scores (see Table 1). proposed by [4, 24] help capture the relatedness of a pair of nodes solely based on the properties of the nodes and edges on the shortest 1.2.1 Problem I: When a Large Node Degree Does path between the pair. Random-walk based definitions, such as Not Indicate High Node Significance hitting distance [10,21] and personalized page rank (PPR) score [1, In this paper, we highlight (and experimentally show) that, 9, 16], of node relatedness further take into account the density of in many applications, node degree and node significance are in fact the edges: as in path-length based definitions, random-walk based inversely related and that the tight-coupling between node degrees definitions also recognize that a node is more related to another and PageRank scores might be counter-productive in generating ac- node if there are short paths between them; however, random walk- curate recommendations. based definitions of relatedness also consider how well the given E XAMPLE 1. Consider, for example, a recommendation appli- pair of nodes are connected. cation where a movie graph, consisting of movie and actor In [7], authors construct a transition matrix, TS , where edges nodes, is used for generating movie recommendations. In this ap- leading away from the seed nodes are weighted less than those plication, the first factor (significance of neighbors) clearly has a edges leading towards the seed nodes. An alternative approach for positive contribution: a movie with good actors is likely to be a contextualizing PageRank scores is to use the PPR techniques [1,9] good movie and an actress playing in good movies is likely to be discussed in the introduction. One key advantage of this tele- a good actress. On the other hand, the second factor (number of portation vector modification based approach over modifying the neighbors) may in fact be a negative contributor to node signif- transition matrix, as in [7], is that the term α can be used to di- icance: the fact that an actor has played in a large number of rectly control the degree of seeding (or personalization) of the PPR movies may be a sign that he is a non-discriminating (’B movie’) score. [10, 21] rely on a random walk hitting time based approach, actor, whereas an actress with relatively fewer movies may be a where the hitting time is defined as the expected number of steps a more discriminating (’A movie’) actress. random walk from the source vertex to the destination vertex will take. [17] leveraged these properties of PPR to develop locality- As we see in Section 4, this observation turns out to be true in many sensitive algorithms to rank nodes of graphs which are relative to a applications, where (a) acquiring additional edges has a cost that is given set of seed nodes efficiently. correlated with the significance of the neighbor (e.g. the effort one needs to invest to a high quality movie) and (b) each node has a 2.2 Improvements to the PageRank Function limited budget (e.g. total effort an actor/actress can invest in his/her Due to the obvious relationship between ranking and monetary work). rewards (e.g. through selling of advertisements on web search ap- 1.2.2 Problem II: When PageRank Does Not Suffi- plications), there has been considerable effort in engineering (or ciently Account for Contributions of Degrees manipulating) graphs in a way to maximize ranking scores of par- ticular nodes. This is commonly referred to as PageRank optimiza- The mismatch between PageRank and node significance is not tion. One way to achieve this goal is carefully adding or removing limited to the cases where node degrees are inversely related to the certain links: If, for example, one or more colluding webmasters node significance. As we see in Section 4, there are other scenarios can add or remove edges, PageRank scores of target web pages where PageRank may, in fact, fail to sufficiently account for the or domains can be increased [23]. [20] established several bounds contribution of the node degrees to their significances. indicating to what extent the rank of the pages of a website can 1.3 PageRank Revisited: De-coupling Node be changed and the authors derived an optimal referencing strat- Significance from Node Degrees egy to boost PageRank scores. A related, but opposite, problem is to protect the PageRank scores against negative links (which may As we discussed above, one key shortcoming of the conventional indicate, for example, negative influence or distrust in a social net- PageRank scores is that they are often tightly coupled with the de- work), artificial manipulation, and spam. [3], for example, focused grees of the graph nodes and in many applications the relationship on identifying spam pages and link farms and showed that better between the significance of the node and its degree in the underly- PageRank scores can be obtained after filtering spam pages and ing network may not be as implied by PageRank-based measure: in links. In [14], authors show that PPR algorithms that do not dif- certain applications, the significance of the node may be negatively ferentiate among the seed nodes may not properly rank nodes and correlated with the node degree, whereas in others PageRank may present robust personalized PageRank (RPR) strategies, which are not be sufficient in accounting for degree contributions. Naturally, insensitive to noise in the set of seed nodes. in such applications a naive application of PageRank in generating recommendations may return poor results. 1 In this context, de-coupled does not necessarily imply de- To address these challenges, in this paper, we propose degree de- correlated. In fact, D2PR can boost correlation between node de- coupled PageRank (D2PR) techniques to improve the effectiveness gree and PageRank if that is required by the application. There are some efforts to change the impact of degrees on the B E Dest. deg. Transition probability PageRank computation. [2] proposed a way to boost the power of vj (vj ) from A to its neighbors vj A C F p=0 2 −2 low-degree nodes in a network. The impact from nodes which are B 2 0.33 0.18 0.29 important but are not hubs is relatively small compared to other D C 3 0.33 0.08 0.64 nodes which are less important with high degrees. To boost the D 1 0.33 0.74 0.07 low-degree important nodes for equal opportunity, the teleportation (a) A sample graph (b) Transition probabilities from A vector is modified with being proportional to the degrees of nodes. [11] boosted the degrees of nodes to reduce the expected cover time Figure 1: In conventional PageRank (p = 0), the transition of the entire graph by the biassed random-walk. probabilities from node vi = A to all its neighbors vj are the same. In degree de-coupled PageRank (D2PR), the value of p 3. DEGREE DE-COUPLED PAGERANK can be used to penalize (p > 0) or boost (p < 0) transition The key difficulty of de-coupling node degrees from the PageR- probabilities based on the degree of the destination ank scores is that the definition of the PageRank, based on random Ranks of the graph nodes walk transitions, is inherently dependent on the number of transi- node node for different de-coupling weights (p) tions available from one node to the other. As we mentioned above, id degree −4 −2 0 2 4 the more ways there are to reach into a node, the higher will be its 53608 883 1 1 69 5549 6793 351 739 2 12 425 1992 1935 PageRank score. ... ... ... ... ... ... ... 79538 1 7661 7545 4149 195 182 3.1 Desideratum 79917 1 7793 7790 7522 2443 2043 Therefore, to de-couple the PageRank score from node degrees, we need to modify the transition matrix. In particular, for each node Table 2: Ranks of graph nodes of different degrees on a sam- vi in the graph, we would like to be able to control the transition ple graph for different de-coupling weights, p: as we see in this process with a single parameter (p), such that figure, when p > 0, high degree nodes are pushed down in the rankings (reducing the correlation between degree and rank), • if p ≪ −1, transitions from node vi are ∼ 100% towards while when p < 0, they are pulled up (improving the correla- the neighbor with the highest degree, • if p = −1, transition probabilities from node vi are propor- tion between degree and rank) tional to the degrees of its neighbors, • p ∈ R is a degree de-coupling weight. • if p = 0, the transition probabilities mirror the standard PageRank probabilities (assuming undifferentiated neigh- Intuitively, the numerator term, deg(vj )−p , ensures that the edge bors), incoming to vj is weighted by its degree: if p > 0, then its de- • if p = 1, transition probabilities from node vi are inversely gree negatively impacts (reduces) transition probabilities into vj , if proportional to the degrees of its neighbors, p < 0 then its degree positively impacts (boosts2 ) transition prob- • if p ≫ 1, transitions from node vi are ∼ 100% towards the abilities into vj , and if p = 0, we obtain the standard PageRank neighbor with the lowest degree. formulation without degree de-coupling. In other words, the tran- sition function satisfies our desideratum of de-coupling the tran- In other words, the transition function should de-couple the transi- sition process from node-degrees and penalizing or boosting the tion process from node-degrees and penalize or boost the contribu- contributions of node degrees on-demand. Note that, since all tions of node degrees in the transition process, as needed. transitions from the node vi are degree de-coupled individually based P on the degrees of their destinations, the denominator term, 3.2 Degree De-coupling Transition Matrix −p vk ∈neighbor(vi ) deg(vk ) , ensures that the transition probabil- In this subsection, we will consider degree de-coupling of the ities from node vi add up to 1.0. Note also that when there is no transition matrix as implied by the above desideratum. edge between node vi and vj , TD (j, i) = 0 and, consequently, the term TD (j, i) is not affected by the degree de-coupling process. 3.2.1 Undirected Unweighted Graphs Let G = (V, E) be an undirected and unweighted graph. Let E XAMPLE 2. Figure 1 shows how the random walk probabili- ties are differentiated in a degree de-coupled transition matrix on α also be a given residual probability parameter, and deg(v) be a function which returns the number of edges on the node v. We a sample graph where a node A has three neighbors, B (with de- represent degree de-coupled PageRank (D2PR) scores in the form gree 2), C (with degree 3), and D (with degree 1). In conven- of a vector tional PageRank, the transition probabilities from node A to all its neighbor nodes are equal to 0.33. In degree de-coupled PageRank d~ = αTD d~ + (1 − α)~t, (D2PR), however, the value of p is used for explicitly accounting for the impact of node degree on the transition probabilities: When where ~t is the teleportation vector, such that ~t[i] = kV1 k for all i p = 2, the transition probabilities from A to its neighbors are 0.18, and TD is a degree de-coupled transition matrix, 0.08, and 0.74, which penalizes nodes which have larger degrees, deg(vj )−p whereas when p = −2, D2PR boosts the transition probabilities TD (j, i) = P −p , (1) to large degree nodes leading to transition probabilities 0.29, 0.64, vk ∈neighbor(vi ) deg(vk ) and 0.07, respectively. ⋄ where This example shows that, in degree de-coupled PageRank • TD (j, i) denotes the degree de-coupled transition probabil- (D2PR), as we also see in Table 2, the value of p can be used to ity from node vi to node vj over an edge eij = [vi → vj ] penalize (p > 0) or boost (p < 0) transition probabilities based on when there exists at least one edge between two nodes, the degree of the destination, vj . • neighbor(vi ) is the set of all neighbors of the source node, 2 In fact, a similar function was used in [11] to quickly locate nodes vi , and with higher degrees in a given graph. 3.2.2 Directed Unweighted Graphs accounts for the connection strength (as in the conventional PageR- The semantics of degree de-coupling is slightly different in di- ank) whereas TD is a degree de-coupled transition matrix, rected graphs. In particular, edges incoming to vi often do not re- Θ(vj )−p quire a particular effort from vi to establish and hence are often out TD (j, i) = P −p , of the control of vi , but indicate a certain degree of interestingness, [vi →vk ]∈out_edges(vi ) Θ(vk ) usefulness, or authority as perceived by others. The same is not such that, TD (j, i) denotes the degree de-coupled transition prob- true for edges outgoing from vi ; in particular, a vertex with a large ability from node vi to node vj over an edge eij = [vi → vj ], number of outgoing edges may either indicate a potential hub or p ∈ R is a degree de-coupling weight, and simply indicate a non-discerning connection maker. The distinction between these two situations gains importance especially in appli- X Θ(v) = w(v → vh ). cations where establishing a new connection has a non-negligible [v→vh ]∈out_edges(v) cost to the source node and, thus, a large number of outgoing edges may indicate either (a) a very strong participant to the network or Note that, above, β controls whether accounting for the connec- (b) a very poor participant with a large number of weak linkages. tion strength or degree de-coupling is more critical in a given appli- Let G = (V, E) be a directed graph and for the simplicity of the cation. In Section 4, we will study the impact of degree de-coupling discussion, without any loss of generality, let us assume that G is in weighted graphs for different scenarios. unweighted. Let us also be given a residual probability parameter, α and let outdeg(v) be a function which returns the number of outgoing edges from the node v. The degree de-coupled PageRank 4. CASE STUDIES (D2PR) scores can be represented in the form of a vector d, ~ d~ = In this section, we present case studies assessing the effective- ~ αTD d + (1 − α)~t, where ~t is the teleportation vector, such that ness of the degree de-coupling process and the relationship between ~t[i] = 1 for all i and the degree de-coupling weight p and recommendation accuracy for kV k different data graphs. outdeg(vj )−p TD (j, i) = P −p , 4.1 Setup [vi →vk ]∈out_edges(vi ) outdeg(vk ) For all experiments, the degree de-coupling weight, p, is varied between -4 and 4 with increments of 0.5. The residual probability, where TD (j, i) denotes the degree de-coupled transition proba- α, is varied between 0.5 and 0.9, with default value chosen as 0.85. bility from node vi to node vj over an edge eij = [vi → vj ], We also varied the β parameter, which controls whether accounting out_edges(vi ) is the set of out-going edges from the source node, for the connection strength or degree de-coupling is more critical vi , and p ∈ R is a degree de-coupling weight. in a given application, between 0.0 and 1.0, with the default value E XAMPLE 3. Figure 2 (a) in Section 4 provides an example il- set to 0 (indicating full decoupling). lustrating the correlations between the degree de-coupled PageR- 4.1.1 Datasets ank (D2PR) scores and external evidence for different values of p Four real data sets are used for the experiments. Each data set for some application: here, the higher the correlation, the better re- is used to create two distinct data graphs and corresponding ratings sulting ranking reflects the application semantics. As we see in this data. Table 3 provides further details about the various graphs cre- example, which we will investigate in greater detail in Section 4, ated using these four data sets. These recommendation tasks based the optimal de-coupling weight is not always p = 0 as implied by on these data graphs are detailed below: the conventional PageRank measure. In this particular case, for example, the correlation between D2PR and external evidence of • For the IMDB [15] data set, we created (a) a movie-movie graph, significance is maximized when the de-coupling weight, p, is equal where movie nodes are connected by an edge if they share common to 0.5, implying that in this application a moderate degree of pe- contributors, such as actors, directors, writers, composers, editors, nalization based on the node degrees is needed to align PageRank cosmetic designers, and producers and (b) an actor-actor graph scores and application semantics. ⋄ based on whether two actors played in the same movie. Appli- cations: For this data set, we consider applications where movies 3.2.3 Weighted Graphs are rated by the users: thus, we merged the IMDB data with the Once again, the semantics of degree de-coupling need to be re- MovieLens 10M [22] data (based on movie names) to identify user considered for weighted graphs. Let G = (V, E, w) be a directed, ratings (between 1 and 5) for the movies in the graph. We con- weighted graph, where w(e) is a function which returns the weight sider the (a) average user rating as the significance of the movies of the edge associated with edge e. It is important to note that, in in the movie-movie graph and (b) average user rating of the movies such a graph, the weight of an edge can 1) indicate the strength played in as the significance of the actors in the actor-actor graph. of the connection between two nodes (thus positively contributing • For the DBLP [26] data set, we constructed (a) an article-article to the significance of the destination node); and at the same time graph where scientific articles were connected to each other if they and 2) contribute to the degree of a node as a multiplier (thus posi- shared a co-author and (b) an author-author graph based on co- tively or negatively contributing to the node significance depending authorship. Applications: (a) In the article-article graph, the num- on the degree-sensitivity of the application). In other words, given ber of citations to an article is used to indicate its significance. Sim- an edge eij = [vi → vj ], from node vi to node vj , the transition ilarly, (b) in the author-author graph, average number of citations probability from vi to vj can be written as to an author’s papers is used as his/her significance. T(j, i) = βTconn_strength (j, i) + (1 − β)TD (j, i), • For the Last.fm [18], we constructed (a) a listener-listener graph, where the nodes are Last.FM listeners and undirected edges reflect where friendship information among these listeners. We also constructed w(vi → vj ) (b) an artist-artist graph based on shared listeners. Applications: Tconn_strength (j, i) = P , [vi →vh ]∈out_edges(vi ) w(vi → vh ) (a) In the listener-listener graph, we considered the total listening Data Graph # of # of Average Standard deviation of Median standard deviation of nodes edge node degree node degrees neighbors’ node degrees IMDB movie-movie 191,602 4,465,272 23.30 51.86 2.89 actor-actor 32,208 2,493,574 77.42 67.15 114.41 DBLP article-article 8,808 951,798 108.06 171.25 309.92 author-author 47,252 310,250 6.57 8.89 6.39 Last.fm listener-listener 1,892 25,434 13.44 17.31 22.37 artist-artist 17,626 2,640,150 149.79 299.66 998.53 Epinions commenter-commenter 6,703 2,395,176 425.05 438.97 609.39 product-product 13,384 2,355,460 175.99 224.12 202.78 Table 3: Data sets and data graphs activity of a given listener as his/her significance. (b) In the artist- when the degrees are over-penalized (i.e., when p ≫ 0.5). The artist graph, the number of times an artist has been listened is con- Epinions product-product graph (based on common commenters, sidered as his/her significance. Figure 2(c)) also provides the highest correlations with p > 0, but • For the Epinions [25]: We constructed (a) a commenter- behaves somewhat differently from the other two cases: the corre- commenter graph based on the products on which two individuals lations stabilize and do not deteriorate significantly when degrees both commented and (b) a product-product graph based on shared are over-penalized, indicating that the need for degree penalization commenters. Applications: (a) For the nodes on the commenter- is especially critical in this case: this is due to the fact that, the commenter graph, the number of trusts the commenter received larger the number of comments a product has, the more likely it from others is used as his/her commenter significance. (b) For is that the comments are negative (Figure 5). In fact, we see that, each product in the product-product graph, its average rating by among the three graphs, this is the only graph where the traditional the commenters is used as its node significance. PageRank (with p = 0) leads to negative correlations between node ranks and node significances. 4.2 Measures These results indicate that actors who have had many co-actors, In this section, our goal is to observe the impact of differ- commenters who commented on products also commented by ent D2PR degree de-coupling weights on the relationship between many others, or products which received comments from individ- D2PR rankings and application specific significance measures for uals who also commented on many other products are not good the above data sets3 . We also aim to verify whether de-coupling candidates for transition during random walk. This aligns with weights can also be used to improve recommendation accuracies. our expectation that, in applications where each new movie role or In order to measure the relationship between the degree de- comment requires additional effort, high degree may indicate lower coupled PageRank (D2PR) scores and the application-specific node per-movie or per-comment effort and, hence, lower significance. significance, we used Spearman’s rank correlation, P 4.3.2 Application Group B: When Conventional (xi − x̄)(yi − ȳ) PageRank is Ideal pP i , 2 2 P i (xi − x̄) i (yi − ȳ) Figure 3 shows that, for movie-movie (based on common actors) which measures the agreement between the D2PR ranks of the and author-author (based on common articles) graphs, the peak nodes in the graph and their application-specific significances. correlation is at p = 0 indicating that the conventional PageRank Here, x are rankings by D2PR and y are significances for an ap- which gives positive weight to node degree, is appropriate. plication and x̄ and ȳ are averages of two values. This perhaps indicates that movies with a lot of actors tend to be big-budget products and that authors with a large number of co- 4.3 Impact of De-Coupling in Different Appli- authors tend to be experts with whom others want to collaborate. cations (Unweighted Graphs) Note that, in these applications, additional boosting, with p < 0, In this subsection, we present results that aim to assess D2PR un- negatively affects the correlation, indicating that the relationship der the settings described above. For these experiments, the resid- between node degree and significance is not very strong (Figure 5). ual probability, α, and the parameter, β, are set to the default val- The quick change when p < 0 is because, as we see in Table 3, ues, 0.85 and 0, respectively. In these experiments, we consider median standard deviations of neighbors’ degrees are low; i.e., de- only unweighted graphs (we will study the weighted graphs and grees of neighbors of a node are comparable: there is no dominant the impact of parameter β later in Section 4.5). contributor to TD (j, i) in Equation 1 (Section 3) and, thus, the Figures 2 through 4 include charts showing the Spearman’s cor- transition probabilities are sensitive to changes in p, when p < 0. relations between the D2PR ranks and application specific node significances for different values of p and for different data graphs. 4.3.3 Application Group C: When Degree Boosting These figures clearly illustrate that different data graphs require dif- Helps ferent degrees of de-coupling4 to best match the application specific Figure 4 shows that there are scenarios where additional boost- node significance criterion. ing based node degrees provides some benefits. The article-article (based on common authors), listener-listener (based on common 4.3.1 Application Group A: When Degree Penaliza- artists), and artist-artist (based on common listeners) graphs reach tion Helps their peaks around p ∼ −1, indicating that these also benefit from The actor-actor (based on common movies) and commenter- large node degrees though improvements over p = 0 are slight. commenter (based on common products) graphs have highest cor- A significant difference between applications in Group B and relation at p = 0.5, with the correlations dropping significantly Group C is that, for p < 0, the correlation curve is more or less 3 In this paper, we are not proposing a new PageRank computation stable. This is because, as we see in Table 3, in these graphs median mechanism. Because of this (and since the focus is not improving standard deviations of neighbors’ degrees are high: in other words, scalability of PR), we do not report execution times and compare for each node, there is a dominant neighbor with a high degree and our results with other PageRank computation mechanisms. this neighbor has the highest contribution to TD (j, i); thus, the 4 Degree penalization or degree-based boosting rankings are not very sensitive to p, when p < 0. +,%%#-$.,'*,:*;<=>*>$'?)*$'/*@,/#*!40'4A2$'2#*8BC;DE*$27,%1$27,%* +,%%#-$.,'*,:*;<=>*>$'?)*$'/*@,/#*!40'4A2$'2#*8B"4'4,')C*2,&&#'7#%1 +,%%#-$.,'*,:*;<=>*>$'?)*$'/*@,/#*!40'4A2$'2#*8B"4'4,')C*"%,/3271"%,/327* 3'5#4067#/*0%$"69** 2,&&#'7#%*3'5#4067#/*0%$"69* 3'5#4067#/*0%$"69* !"&'# "#"$% !"#$%&$'()*+,%%#-$.,'* "#"'% !"#$%&$'()*+,%%#-$.,'* !"#$%&$'()*+,%%#-$.,'* "#"&% !"!%# "#""% "#"&% !&% !'#(% !'% !)#(% !)% !*#(% !*% !"#(% "% "#(% *% *#(% )% )#(% '% '#(% &% !"!$# /#0%##*/#12,3"-4'0*5#4067*8"9* !(% !'#)% !'% !$#)% !$% !&#)% !&% !"#)% "% "#)% &% &#)% $% $#)% '% '#)% (% !"#"&% /#0%##*/#12,3"-4'0*5#4067*8"9* !"!!# ($# ()"*# ()# ('"*# ('# (&"*# (&# (!"*# !# !"*# &# &"*# '# '"*# )# )"*# $# !"#"$% !"#"$% /#0%##*/#12,3"-4'0*5#4067*8"9* ;#0%##*/#12,3"-#/* +,'F#'.,'$-*8"GH9* ;#0%##*/#12,3"-#/* +,'D#'.,'$-*8"EF9* ;#0%##*/#12,3"-#/* +,'D#'.,'$-*8"EF9* (a) IMDB (actor-actor) (b) Epinions (commenter-commenter) (c) Epinions (product-product) Figure 2: Application Group A: p > 0 is optimal (i.e., node degrees need to be penalized) +,%%#-$.,'*,:*;<=>*>$'?)*$'/*@,/#*!40'4A2$'2#*8;BC=D*$376,%1$376,%* +,%%#-$.,'*,:*;<=>*>$'?)*$'/*@,/#*!40'4A2$'2#*8BC;DE*&,F4#1&,F4#* 3'5#4067#/*0%$"69** 3'5#4067#/*0%$"69* "#$% "#"(& !"#$%&$'()*+,%%#-$.,'* !"#$%&$'()*+,%%#-$.,'* "#&% "#""& !(& !)#*& !)& !%#*& !%& !$#*& !$& !"#*& "& "#*& $& $#*& %& %#*& )& )#*& (& /#0%##*/#12,3"-4'0*5#4067*8"9* "#"% !"#"(& !'% !(#)% !(% !$#)% !$% !&#)% !&% !"#)% "% "#)% &% &#)% $% $#)% (% (#)% '% /#0%##*/#12,3"-4'0*5#4067*8"9* !"#&% !"#"'& !"#$% !"#$%& ;#0%##*/#12,3"-#/* +,'E#'.,'$-*8"FG9* ;#0%##*/#12,3"-#/* +,'F#'.,'$-*8"GH9* (a) DBLP (author-author) (b) IMDB (movie-movie) Figure 3: Application Group B: p = 0 is optimal 01++)2*31-%1?%@ABC%C*-D/%*-4%E14)%'95-9F7*-7)%=@GHBI%*+372)6*+372)% 01++)2*31-%1?%@#AB%B*-C/%*-4%D14)%'95-9E7*-7)%%=F*/<"?,G%29/<)-)+629/<)-)+% 12,,*3+42.&2@&A%BC&C+.D0&+.5&E25*&(:6.:F8+.8*&>G+0="@-H&+,40=7+,40=& 8-:)95;<)4%5+*(;>%% 8-:)95;<)4%5+*(;>% 9.;*:6<=*5&6,+))?& !)% !"#(% "% "#(% )% )#(% &% &#(% '% '#(% $% !'% !(#&% !(% !)#&% !)% !$#&% !$% !"#&% "% "#&% $% $#&% )% )#&% (% (#&% '% !'% !(#)% !(% !$#)% !$% !&#)% !&% !"#)% "% "#)% &% &#)% $% $#)% (% (#)% '% 4)5+))%4)6718(29-5%:)95;<%=(>% 4)5+))%4)6718(29-5%:)95;<%=(>% !"#&% !"#"&% !"#&% !"#$"% !"#$% !"#$% @)5+))%4)6718(2)4% 01-J)-31-*2%=(K!>% @)5+))%4)6718(2)4% 01-H)-31-*2%=(I!>% A*6,**&5*7829)3*5& 12.I*.42.+3&>)J!?& (a) DBLP (article-article) (b) Last.fm (listener-listener) (c) Last.fm (artist-artist) Figure 4: Application Group C: p < 0 is optimal (i.e., node degrees need to be boosted) "#'&% p<0 2/3'+,+"( the weighted graphs are similar). ),$(,#$+(3/5,/6&),&+( &#""-((#4((,#$+($+5"++( "#'"% First thing to notice in these figures is that the grouping of the "#$&% )%'0#"( applications (into those where, respectively, p > 0, p = 0, or p < 0 "#$"% )"13'( is useful) is preserved when different values of α are considered. *#./+( )"1&2+( "#"&% &#**+,'-( Figure 6 studies the impact of the value of α in application group p=0 A, where degree penalization helps (p > 0). As we see here, "#""% )&'#"( for the IMDB actor-actor (Figure 6(a)) and Epinions commenter- !"#"&% !"#$%&'( p>0 commenter (Figure 6(b)) graphs, having a lower value of α (i.e., !"#$"% lower probability of forward movement during the random walk) Figure 5: Correlations between node degrees and applica- provides the highest possible correlations between D2PR ranks and tion specific significances for different data graphs (each color node significance (with the optimal value of p being ∼ 0.5 inde- group is a distinct pattern in Figures 2 through 4). pendent of the value of α). This indicates that in these graphs, it is not necessary to traverse far during the random walk. Inter- 4.3.4 Summary: Correlations between Node De- estingly, though, when degrees are over-penalized (i.e., p ≫ 0), grees and Application Specific Significances smaller values of α start leading to worse correlations, indicating The experiments reported above show that degree de-coupling that (while not being optimal) severe penalization of node degrees is important as different applications, even on the same data set, helps make random traversals more useful than random jumps. As may associate different semantics to node degrees and the conven- we have already observed in Figure 2(c), the Epinions product- tional PageRank scores are too tightly coupled with node degrees product graph (Figure 6(c)) behaves somewhat differently from the to be effective in all scenarios. Figure 5, which plots correlations other two cases where degree penalization (p > 0) leads to larger between node degrees and application specific significances for dif- correlations: in this case, unlike the other two graphs, the highest ferent data graphs, re-confirms that the ideal value of the p is related possible correlations between D2PR ranks and node significance to the usefulness of the node degree in capturing the application are obtained for large values of α, indicating that this application specific definition of node significance. benefits from longer random walks (though the differences among the correlations for different α values are very small). 4.4 Relationship between α and p Figure 7 shows that the pattern is different for application group In Figures 6 through 8, we investigate the relationship between B, where conventional PageRank is ideal (p = 0): in this case, hav- the value α and the degree de-coupling parameter p for different ing a larger value of α (i.e., larger probability of forward movement application types. Here we use the default value, 0, for the param- during the random walk) provides the highest correlations between eter β and present the results for unweighted graphs (the results for ranks and significance. Interestingly, in these applications, when +,%%#-$.,'*,:*;<=>*>$'?)*$'/*@,/#*!40'4A2$'2#*,'*/4B#%#'7*C*D$-3#)* +,%%#-$.,'*,:*;<=>*>$'?)*$'/*@,/#*!40'4A2$'2#*,'*/4B#%#'7*C*D$-3#)** +,%%#-$.,'*,:*;<=>*>$'?)*$'/*@,/#*,'*/4A#%#'7*B*C$-3#)* 8EF;GH*$27,%1$27,%*3'5#4067#/*0%$"69* 8E"4'4,')F*2,&&#'7#%12,&&#'7#%*3'5#4067#/*0%$"69* 8D"4'4,')E*"%,/3271"%,/327*3'5#4067#/*0%$"69* "#')% "#"(% "#"$% !"#$%&$'()*+,%%#-$.,'* !"#$%&$'()*+,%%#-$.,'* !"#$%&$'()*+,%%#-$.,'* "#"'% "#'(% "#"&% "#"$% "#"&% "#"&% "#""% "#"$% !&% !'#(% !'% !)#(% !)% !*#(% !*% !"#(% "% "#(% *% *#(% )% )#(% '% '#(% &% "#""% !(% !'#)% !'% !$#)% !$% !&#)% !&% !"#)% "% "#)% &% &#)% $% $#)% '% '#)% (% "#""% !"#"&% !"#"&% !$% !*#+% !*% !(#+% !(% !'#+% !'% !"#+% "% "#+% '% '#+% (% (#+% *% *#+% $% /#0%##*/#12,3"-4'0*5#4067*8"9* /#0%##*/#12,3"-4'0*5#4067*8"9* /#0%##*/#12,3"-4'0*5#4067*8"9* !"#"$% !"#"$% !"#"$% CIJKL* CIJKM* CIJKNL* CIJKO* CGHIJ* CGHIK* CGHILJ* CGHIM* BFGHI* BFGHJ* BFGHKI* BFGHL* (a) IMDB (actor-actor) (b) Epinions (commenter-commenter) (c) Epinions (product-product) Figure 6: Relationship between p and α, for application group A, where p > 0 is optimal (i.e., degrees need to be penalized) +,%%#-$.,'*,:*;<=>*>$'?)*$'/*@,/#*!40'4A2$'2#*,'*/4B#%#'7*C*D$-3#)* +,%%#-$.,'*,:*;<=>*>$'?)*$'/*@,/#*!40'4A2$'2#*,'*/4B#%#'7*C*D$-3#)* 8;EF=G*$376,%1$376,%*3'5#4067#/*0%$"69* 8EF;GH*&,D4#1&,D4#*3'5#4067#/*0%$"69* "#&% "#"(% !"#$%&$'()*+,%%#-$.,'* !"#$%&$'()*+,%%#-$.,'* "#")% "#'% "#""% !(% !*#+% !*% !)#+% !)% !$#+% !$% !"#+% "% "#+% $% $#+% )% )#+% *% *#+% (% "#"% !"#")% !(% !$#)% !$% !&#)% !&% !'#)% !'% !"#)% "% "#)% '% '#)% &% &#)% $% $#)% (% /#0%##*/#12,3"-4'0*5#4067*8"9* /#0%##*/#12,3"-4'0*5#4067*8"9* !"#"(% !"#'% !"#"'% !"#&% !"#"&% !"#$% !"#$"% CHIJK* CHIJL* CHIJMK* CHIJN* CIJKL* CIJKM* CIJKNL* CIJKO* (a) DBLP (author-author) (b) IMDB (movie-movie) Figure 7: Relationship between p and α, for application group B, where p = 0 is optimal +,%%#-$.,'*,:*;<=>*>$'?)*$'/*@,/#*!40'4A2$'2#*,'*/4B#%#'7*C*D$-3#)** +,%%#-$.,'*,:*;<=>*>$'?)*$'/*@,/#*!40'4A2$'2#*,'*/4B#%#'7*C*D$-3#)* +,%%#-$.,'*,:*;<=>*>$'?)*$'/*@,/#*!40'4A2$'2#*,'*/4B#%#'7*C*D$-3#)* 8;EF=G*$%.2-#1$%.2-#*3'5#4067#/*0%$"69* 8E$)7F:&G*-4)7#'#%1-4)7#'#%*3'5#4067#/*0%$"69* 8E$)7F:&G*$%.)71$%.)7*3'5#4067#/*0%$"69* "#$%& "#'% "#$% !"#$%&$'()*+,%%#-$.,'* !"#$%&$'()*+,%%#-$.,'* "#$"& !"#$%&$'()*+,%%#-$.,'* "#$% "#&% "#"%& "#&% "#""& "#"% !'& !(#%& !(& !)#%& !)& !$#%& !$& !"#%& "& "#%& $& $#%& )& )#%& (& (#%& '& "#"% !$% !'#(% !'% !&#(% !&% !)#(% !)% !"#(% "% "#(% )% )#(% &% &#(% '% '#(% $% !"#"%& !(% !'#)% !'% !$#)% !$% !&#)% !&% !"#)% "% "#)% &% &#)% $% $#)% '% '#)% (% /#0%##*/#12,3"-4'0*5#4067*8"9* /#0%##*/#12,3"-4'0*5#4067*8"9* /#0%##*/#12,3"-4'0*5#4067*8"9* !"#&% !"#&% !"#$"& !"#$%& !"#$% !"#$% CHIJK* CHIJL* CHIJMK* CHIJN* CHIFJ* CHIFK* CHIFLJ* CHIFM* CHIFJ* CHIFK* CHIFLJ* CHIFM* (a) DBLP (article-article) (b) Last.fm (listener-listener) (c) Last.fm (artist-artist) Figure 8: Relationship between p and α, for application group C, where p < 0 is optimal (i.e., node degrees need to be boosted) p ≪ 0 or p ≫ 0, higher probabilities of random walk traversal the greater β is), the larger is the optimal value of p. (i.e., larger α) stop being beneficial and lower values of α lead to Figure 10 shows that, for applications in group B, where p ∼ 0 larger correlations. This re-confirms that, for these applications, is ideal, when the connection strength is given significantly more p ∼ 0 leverages the random walk traversal the best. weight than degree de-coupling (i.e., β ∼ 0), we observe high rank- As we see in Figure 8, in application group C, where degree significance correlations. Interestingly however, for the movie- boosting helps (p < 0), it is also the case that larger values of α movie graph (where the edge weights denote common actors) the (i.e., larger probabilities of forward transitions during the random highest correlations are obtained not with p = 0, but with p = 0.5 walk) provides the highest correlations between node ranks and sig- and β = 0.75, indicating that degree penalization is actually ben- nificance. On the other hand, in these applications, p ∼ 0.5 serves eficial in this case: movies that share large numbers of actors with as a balance point where the value of α stops being relevant; in other movies are likely to be B-movies, which are not good candi- fact, for p > 0.5 the higher values of α stops being beneficial and dates for transitions during the random walk. lower values of α lead to larger correlations. This re-confirms that Figure 11 shows that in application group C, where degree boost- smaller values of p (which provides degree boosting) help leverage ing (p < 0) helps, giving more weight to connection strength (i.e., the random walk traversal the best. β ∼ 1.0) is a good, but not necessarily the best strategy. In fact, in these graphs, the highest overall correlations are obtained with 4.5 Relationship between β and p in β = 0 or β = 0.25, indicating that degree de-coupling is bene- Weighted Graphs ficial also in these cases. Interestingly, (unlike the case with the Finally, in Figures 9 through 11, we investigate the relation- unweighted listener-listener graph, where the best correlation was ship between the value β (which controls whether accounting for obtained when p < 0) for the weighted version of the listener- the connection strength or degree de-coupling is more critical in a listener graph (where edge weights denote the number of shared given application) and the degree de-coupling parameter p for dif- friends), when β = 0 through 0.5, p = 0 provides the highest ferent application types. Here we use the default value, 0.85, for correlation and when β = 0.75, p = 0.5 provides the highest cor- the parameter α and present the results for weighted graphs: relation – these indicate that listeners who have large numbers of Figure 9 depicts the impact of the value of the parameter β in ap- shared friends with others are good candidates for random walk. plication group A, where degree penalization helps (p > 0). As we Note that a key observation from the above results is that the see here, for all three weighted graphs, performing degree penal- conventional PageRank, based on connection strength (i.e., β = ization (i.e., β < 1.0) provides better rank-significance correlation 1.0), is not always the best strategy for the applications considered. than relying solely on the connection strength (i.e., β = 1.0). Note that the value of β impacts the optimal value of degree penalization 5. CONCLUSIONS parameter p: the more weight is given to connection strength (i.e., In this paper, we noted that in many applications the relation- +,%%#-$.,'*,:*;<=>*>$'?)*$'/*@,/#*!40'4A2$'2#*,'*/4B#%#'7*C*D$-3#)* +,%%#-$.,'*,:*;<=>*>$'?)*$'/*@,/#*!40'4A2$'2#*,'*/4B#%#'7*C*D$-3#)*8E"4'4,')F* +,%%#-$.,'*,:*;<=>*>$'?)*$'/*@,/#*,'*/4A#%#'7*B*C$-3#)** 8EF;GH*$27,%1$27,%*5#4067#/*0%$"69*I#/0#15#4067J*K*,:*2,&&,'*&,D4#)L* 2,&&#'7#%12,&&#'7#%*5#4067#/*0%$"69*G#/0#15#4067H*I*,:*)6$%#/*"%,/327)J* 8D"4'4,')E*"%,/3271"%,/327*5#4067#/*0%$"69*F#/0#15#4067G*H*,:*)6$%#/*2,&&#'7#%)I* "#)"% "#$&% "#")% !"#$%&$'()*+,%%#-$.,'* !"#$%&$'()*+,%%#-$.,'* !"#$%&$'()*+,%%#-$.,'* "#"(% "#"(% "#$"% "#"'% "#"'% "#"$% "#"&% "#"$% "#"&% "#"&% "#""% !'% !(#&% !(% !)#&% !)% !$#&% !$% !"#&% "% "#&% $% $#&% )% )#&% (% (#&% '% "#""% "#""% !$% !*#+% !*% !&#+% !&% !)#+% !)% !"#+% "% "#+% )% )#+% &% &#+% *% *#+% $% !(% !'#)% !'% !$#)% !$% !&#)% !&% !"#)% "% "#)% &% &#)% $% $#)% '% '#)% (% !"#"&% !"#"&% !"#"&% /#0%##*/#12,3"-4'0*5#4067*8"9* /#0%##*/#12,3"-4'0*5#4067*8"9* /#0%##*/#12,3"-4'0*5#4067*8"9* !"#"$% !"#"$% !"#$"% CMN* CMNO 0 is optimal (i.e., node degrees need to be penalized) +,%%#-$.,'*,:*;<=>*>$'?)*$'/*@,/#*!40'4A2$'2#*,'*/4B#%#'7*C*D$-3#)* +,%%#-$.,'*,:*;<=>*>$'?)*$'/*@,/#*!40'4A2$'2#*,'*/4B#%#'7*C*D$-3#)* 8;EF=G*$376,%1$376,%*5#4067#/*0%$"69*H#/0#15#4067I*J*,:*2,"$"#%)K* 8EF;GH*&,D4#1&,D4#*5#4067#/*0%$"69*I#/0#15#4067J*K*,:*2,&&,'*$27,%)L* "#$% "#"(% !"#$%&$'()*+,%%#-$.,'* !"#$%&$'()*+,%%#-$.,'* "#")% "#&% "#""% !(% !*#+% !*% !)#+% !)% !$#+% !$% !"#+% "% "#+% $% $#+% )% )#+% *% *#+% (% !"#")% "#"% /#0%##*/#12,3"-4'0*5#4067*8"9* !'% !(#)% !(% !$#)% !$% !&#)% !&% !"#)% "% "#)% &% &#)% $% $#)% (% (#)% '% !"#"(% /#0%##*/#12,3"-4'0*5#4067*8"9* !"#"'% !"#&% !"#"&% !"#$% !"#$"% CLM* CLMN*>$'?)*$'/*@,/#*!40'4A2$'2#*,'*/4B#%#'7*C*D$-3#)* +,%%#-$.,'*,:*;<=>*>$'?)*$'/*@,/#*!40'4A2$'2#*,'*/4B#%#'7*C*D$-3#)* +,%%#-$.,'*,:*;<=>*>$'?)*$'/*@,/#*!40'4A2$'2#*,'*/4B#%#'7*C*D$-3#)** 8;EF=G*$%.2-#1$%.2-#*5#4067#/*0%$"69**H#/0#15#4067I*J*,:*2,$376,%)K* 8E$)7F:&G*-4)7#'#%1-4)7#'#%*5#4067#/*0%$"69*H#/0#15#4067I*J*,:*)6$%#/*:%4#'/)K* 8E$)7F:&G*$%.)71$%.)7*5#4067#/*0%$"69*H#/0#15#4067I*J*,:*)6$%#/*-4)7#'#%)K* "#$&% "#'% "#$% !"#$%&$'()*+,%%#-$.,'* !"#$%&$'()*+,%%#-$.,'* !"#$%&$'()*+,%%#-$.,'* "#$"% "#$% "#&% "#"&% "#&% "#"% "#""% "#"% !$% !'#(% !'% !&#(% !&% !)#(% !)% !"#(% "% "#(% )% )#(% &% &#(% '% '#(% $% !'% !(#&% !(% !)#&% !)% !$#&% !$% !"#&% "% "#&% $% $#&% )% )#&% (% (#&% '% !(% !'#)% !'% !$#)% !$% !&#)% !&% !"#)% "% "#)% &% &#)% $% $#)% '% '#)% (% /#0%##*/#12,3"-4'0*5#4067*8"9* /#0%##*/#12,3"-4'0*5#4067*8"9* /#0%##*/#12,3"-4'0*5#4067*8"9* !"#&% !"#"&% !"#&% !"#$"% !"#$% !"#$% CLM* CLMN