Monte Carlo Based Personalized PageRank on Dynamic Networks

Abstract

In large-scale networks, the structure of the underlying network changes frequently, and thus the power iteration method for Personalized PageRank computation cannot deal with this kind of dynamic network efficiently. In this paper, we design a Monte Carlo-based incremental method for Personalized PageRank computation. In a dynamic network, first, we do a random walk starting from each node and save the performed walks into a fingerprint database; second, we update the fingerprint database in a fixed time interval with our proposed update algorithm; finally, when a query is issued by a user, we estimate the Personalized PageRank vector by our proposed approximation algorithm. Experiments on real-world networks show that our method can handle multichanges of the underlying network at a time and is more efficient than related work, so it can be used in real incremental Personalized PageRank-based applications.

1. Introduction

Large-scale networks are ubiquitous in today's world, such as World Wide Web, online social networks, and huge search and query-click logs regularly collected and processed by search engines. PageRank [1], which is the stability distribution of a random walk in a Markov chain, has emerged as an effective measure for ranking on large-scale networks. In addition, Personalized PageRank [2, 3], which is the stability distribution of a random walk with restart in a Markov chain, has been proved to be an effective method of personalized ranking in many applications, such as link prediction [4–6], friend recommendation [7–9], and personalized searching [10, 11]. Given a network, there are two main methods for computing the PageRank or Personalized PageRank vector: one is power iteration applying the linear algebra proposed by Page et al. [1] and the other is the Monte Carlo approximation methods proposed by Litvak [12] and Fogaras and Rácz [13].

In practice, the structure of the underlying network is dynamic, such that Webpages join or leave frequently in World Wide Web and following relations appear or disappear frequently in an online social network. Recomputing PageRank or Personalized PageRank for every change, that appears or disappears in an edge, of the structure is impossible in large-scale networks, so incremental PageRank or Personalized PageRank algorithms are necessary for this situation.

1.1. Background

Given a graph $G = (V, E)$ , where V is the set of nodes, E is the set of edges, and the number of nodes and edges is n and m, respectively; the adjacent matrix M of the graph G is

\begin{matrix} m_{i, j} = {\begin{cases} 1 & (i, j) \in V, \\ 0 & (i, j) \notin V, \end{cases} \end{matrix}

(1)

where $i, j \in V$ , and $(i, j)$ are a directed edge from i to j.

The transition possibility matrix P of the graph G is

\begin{matrix} p_{i, j} = \frac{m_{i, j}}{\sum_{j = 1}^{n} m_{i, j}}, \end{matrix}

(2)

where the weights on the outgoing edges of each node sum up to 1.

PageRank is the stability distribution of a random walk in a Markov chain. The main idea of random walk on a graph is that starting from a source node, at each step, jump to a random node with a probability ε (usually called the teleport probability), and follow a random outgoing edge from the current with the probability $1 - ε$ . If the number k of random steps tends to be infinite, that is, $k \to + \infty$ , then the probability that the random walk stops at each node is a constant, and, no matter how we choose the source node, the probability of stopping at each node does not change.

Personalized PageRank is the same as PageRank, except that the random walk jumps to the source node with a probability ε at each step. Given a source (or called personalized) node u, the Personalized PageRank score of node v is

\begin{matrix} π_{u} (v) = ε δ_{u} (v) + (1 - ε) \sum_{i = 1}^{n} p_{i, v} \cdot π_{u} (i), \end{matrix}

(3)

where $δ_{u} (v) = 1$ if and only if $u = v$ , and $δ_{u} (v) = 0$ , otherwise.

1.2. Problem Statement

In this paper, we study the incremental computation of Personalized PageRank based on the Monte Carlo method; that is, given a graph, we do a random walk of fixed length starting from each node update the performed walks incrementally in fixed time interval, and approximate Personalized PageRank with the performed walks whenever needed.

Here, the core of the problem is designing an incremental update algorithm and a Personalized PageRank approximation algorithm.

1.3. Our Contribution

First, we design an approximation method for Personalized PageRank based on Monte Carlo method. We do a random walk of fixed length starting from each node, and save the performed walks in a fingerprint database.

Second, we propose an incremental algorithm, which updates the performed walks in fixed time interval, while the structure of underlying graph changes.

Third, we propose an approximation algorithm for computing Personalized PageRank vector based on the performed walks.

Finally, we do some experiments on real world graphs, and the experiments show that our proposed method is more efficient than related researches in estimating Personalized PageRank on dynamic networks.

2. Related Work

Matrix Computation. Matrix computation, which applies power iteration of linear algebra to compute the PageRank vector [1], is the most popular method for PageRank computation. In order to accelerate the convergence of power iteration, Borgs et al. [14] propose a sublinear time algorithm for PageRank computations. Because the graphs in real applications are usually sparse, del Corso et al. [15] and Fujiwara et al. [16] all apply sparse matrices to speed up the PageRank computation. Though these algorithms can accelerate the Personalized PageRank computation, they cannot be used in dynamic networks.

Monte Carlo Method. The Monte Carlo approximation methods [12, 13] are efficient for estimating Personalized PageRank on large-scale graphs. The basic idea is that starting from the source node, do a number R of random walks (called fingerprints); at each step, stop the random walk with a probability ε, and follow a random outgoing edge from the current node with the probability $1 - ε$ . The lengths of the R random walks from each node are subject to the geometrical distribution Geom(ε). Then, use the frequencies of visit to different nodes in the performed walks to approximate the Personalized PageRank vector. The lengths of the performed walks conform to geometrical distribution, and thus there should be some long walks, so Sarma et al. [17] propose to do all random walks with length $1 / ε$ . In addition, Bahmani et al. [18] study the Personalized PageRank problem on MapReduce [19], and propose an optimal algorithm for constructing single random walk on MapReduce. In dynamic networks, Bahmani et al. [20] propose to store the performed walks in database and update them when an edge joins or leaves the underlying network. They consider that there is only one joining or leaving edge at a time, and update the fingerprints whenever the underlying network changes. However, in this paper, we study the same problem as [20], but we assume that there should be multichanges (multijoining and leaving edges) in a network.

Personalized PageRank Application. Personalized PageRank and other random walk with restart-based measures are the most well-known graph computation problems, and they have proved to be very effective in a variety of applications, such as link prediction [5, 21] and friend recommendation [22, 23], Webpage retrieval [1–3, 24–27], and trust-based recommendation systems [28–31] in large-scale networks. A similar work is [32], which uses dynamic GPS data to recommend an individual with interesting locations or travel sequences matching her travel preferences. But, the difference is that although they use the dynamic dataset, they do not mention how they handle this dynamic dataset incrementally. However, in this paper, we focus on the incremental update of recommendations, and the results can be used in any Personalized PageRank-based applications.

3. Monte Carlo-Based Incremental Personalized PageRank Computation

In this section, we describe our proposed system for incremental Personalized PageRank computation and illustrate the system in detail.

3.1. System Overall Design

Our system answers users’ Personalized PageRank queries or recommend Personalized PageRank results to the specific users, and the architecture of the system is in Figure 1. First, we initialize the fingerprints and save them in a fingerprint database, and then, in a fixed time interval, we update the fingerprint database. These two phases are done automatically by the system. When a query is issued by a personalized user, the searching engine retrieves related fingerprints from the fingerprint database, estimates the Personalized PageRank vector, and then returns nodes with highest score to the user. Some of the main phases of the system work as follows.

(i)

Initializing Fingerprint Database. Given a graph $G = (V, E)$ , we first do a random walk (fingerprint) with fixed length λ starting from each node in the graph, and save all the performed walks in the fingerprint database.

(ii)

Updating Fingerprint Database. The structure of the graph changes frequently, and it is impossible to update the fingerprint database with every change, so we update the fingerprint database with a fixed time interval t.

(iii)

Computing Personalized PageRank. When a query is issued from a user, the searching engine generates SQL queries according to the specified user, retrieves related results from the fingerprint database, computes the Personalized PageRank vector, and returns a top-k list to the user.

Figure 1

System architecture.

3.2. Initializing Fingerprint Database

Given a graph $G = (V, E)$ , for each node $u \in V$ , do a random walk $w_{u}$ of length λ starting from the node u, and the details are given in Algorithm 1.

Algorithm 1: Initialization ( $G, λ$ ).

Input: G, the input graph, and λ, the length of fingerprints.

Output: $W = {w_{i} ∣ 1 \leq i \leq n \land i \in V \land | w_{i} | = λ}$ , where for each

node $i \in V$ , return a random walk $w_{i}$ of length λ.

(1) For each $u \in V$ do

(2) Let $l a s t = u, w_{u} = {} . a p p e n d (l a s t)$ ;

(3) For $i = 1$ to n do

(4) $c u r r e n t = l a s t . r a n d o m S u c c e s s o r ()$ ;

(5) $w_{u} = w_{u} . a p p e n d (c u r r e n t)$

(6) $l a s t = c u r r e n t$ ;

(7) End for;

(8) End for;

(9) Return W;

After doing the performed random walks, we save the performed walks in the fingerprint database.

3.3. Updating Fingerprint Database

In dynamic networks, Bahmani et al. [20] propose a model to update the fingerprint database whenever there is a joining edge or leaving edge. However, the structure of the underlying graph changes frequently, so it is impossible to update the fingerprint database for very change. In this paper, we propose an update algorithm that handles multichanges while updating the fingerprint database.

In a time interval t, there will be k changes in the structure of the underlying network. These k changes include joining edges and leaving edges in any order. We can apply the algorithm proposed in [20] k times, but this will consume lots of computation resources. In this paper, we propose an update algorithm, which could handle multichanges at a time, and the details of the algorithm are in Algorithm 2.

Algorithm 2: Update ( $G, k, W$ ).

Input: G, the input graph, k, the changes of graph structure,

and W, the set of fingerprints.

(1) Reorder $k = [\underset{k}{\underset{︸}{+, -, -, +, -, \dots, +}}]$ in order to obtain

$k^{'} = [\underset{k_{1}}{\underset{︸}{-, \dots, -}}, \underset{k_{2}}{\underset{︸}{+, \dots, +}}]$ , where $k = k_{1} + k_{2}$ ;

(2) Let $L = null$ ;

(3) For each $e \in k_{1}$ do

(4) Let $l e \leftarrow$ select all fingerprints which contain e in W;

(5) $L = L \cup l e$

(6) End for;

(7) For each $l \in L$ do

(8) For each $e \in k_{1}$ do

(9) If e in l then

(10) Let $l \leftarrow$ cut off l at e, and keep the start node of e;

(11) End if;

(12) End for;

(13) End for;

(14) Let $J = null$ ;

(15) Let $S \leftarrow$ all start nodes in $k_{2}$ ;

(16) For each $s \in S$ do

(17) Let $l s \leftarrow$ select all fingerprints which contain s in W;

(18) $J = J \cup l s$ ;

(19) End for;

(20) For each $j \in J$ do

(21) For each $s \in S$ do

(22) If s in j then

(23) Let $j \leftarrow$ cut off j after s;

(24)End if;

(25) End for;

(26) End for;

(27) For each $w \in L \cup J$ do

(28) Let $w \leftarrow$ go on walking randomly from the end node

of w until the length reaches λ;

(29) End for;

(30) Update W with $L \cup J$ ;

Given a series of changes $k = [\underset{k}{\underset{︸}{+, -, -, +, -, \dots, +}}]$ , where + means a joining edge, and − means a leaving edge we can reorder them into $k^{'} = [\underset{k_{1}}{\underset{︸}{-, \dots, -}}, \underset{k_{2}}{\underset{︸}{+, \dots, +}}]$ , where $k = k_{1} + k_{2}$ .

For the $k_{1}$ leaving edges, we search in the fingerprint database for the fingerprints which contain one of these leaving edges, and the results are presented with L. For each $l \in L$ , if it contains one leaving edge e from its beginning, then we delete e and its following edges but keep the start node of e.

For the $k_{2}$ joining edges, we collect all start nodes in S, search in the fingerprint database for the fingerprints which contain any node $s \in S$ , and the results are presented with J. For each $j \in J$ , if it contains one node s from its beginning, then, with a probability $1 / (d + 1)$ , we delete the following nodes of s.

Finally, for both L and J, the lengths of fingerprints are smaller than λ, so we go on walking randomly on $G^{'} = G - k_{1} \cup k_{2}$ until their lengths reach λ.

3.4. Computing Personalized PageRank

In this subsection, we propose an approximation method for estimating Personalized PageRank vector based on the performed walks, and the details are in Algorithm 3.

Algorithm 3: Computing PPR ( $W, u, ε$ ).

Input: W, the set of fingerprints, u, a personalized node for

Personalized PageRank, and ε, the teleport probability.

Output: $π_{u}$ , the Personalized PageRank vector for u.

(1) Let $r e s u l t = {}, π_{u} (v) = 0$ for $1 \leq v \leq n$ ;

(2) For each $w \in W$ do

(3) Scan w, find all sub-fingerprints of length $1 / ε$ starting

from u, and add these sub-fingerprints to $r e s u l t$ ;

(4) End for;

(5) For each $w \in r e s u l t$ do

(6) For each node $v \in w$ do

(7) $π_{u} (v) = π_{u} (v) + 1$ ;

(8)End for;

(9) End for;

(10) For $v = 1$ to n do

(11) $π_{u} (v) = \frac{π_{u} (v)}{\sum_{v = 1}^{n} π_{u} (v)}$ ;

(12) End for;

(13) Return $π_{u}$ ;

For each fingerprint $w \in W$ , we find the subfingerprints which start from the personalized node u, and have the length of $1 / ε$ . In order to make these subfingerprints independent of each other, we must make sure that these subfingerprints do not overlap. After finding out those subfingerprints, we can estimate the Personalized PageRank vector with visit frequencies of the nodes.

4. Experiments

In this section, we do some experiments to validate the efficiency of our proposed method. We use the method proposed by the Bahmani et al. [20] as baseline algorithm, and compare it with our method in execution time.

4.1. Dataset

To validate the performance of both algorithms, we use two real-world datasets of networks, Dianping [33] and Gowalla [34]. The details of the datasets are in Table 1.

Table 1

Details of datasets.

Dataset	n	m	$n / m$
Dianping	204074	926720	4.5
Gowalla	196591	1900654	9.7

4.2. Experimental Setup

Our experimental environment is a personal computer with a 4-core processor and 4 GB memory. All algorithms are implemented by Java on the Ubuntu operation system. Our toolkit for dealing with graph is Jung [35], and the database for storing fingerprints is MySQL.

4.3. Experimental Results

For each graph G, we choose 90% of the dataset as already known graph A, and the other 10% as B. When an edge joins A, we randomly choose an edge e from B, delete it from B, and add it to A. When an edge leaves A, we randomly choose an edge e from A, delete it from A, and add it to B. The probabilities of joining and leaving are equal. We build an extra thread that changes the structure of the underlying graph once per ten seconds.

First, we compare the update time between our method with the method proposed by Bahmani et al. We update the fingerprint database in a fixed time interval from 1 to 10 second, and the results for two datasets are in Figures 2 and 3. From these two figures we can see that our update algorithm executes only once, but the Bahmani's algorithm need to update the fingerprint database multitimes that is proportional to the time interval. Moreover, we find that the time used in updating the fingerprint database contains a nearly constant time retrieving the related fingerprints.

Figure 2

Comparison of update time (Dianping).

Figure 3

Comparison of update time (Gowalla).

Second, we compare the execution time of Personalized PageRank approximation between the proposed method and Bahmani's method. Both of the algorithms retrieve fingerprints from the fingerprint database first and then estimate the Personalized PageRank vector with the fingerprints. The Bahmani's algorithm retrieves related fingerprints starting from the personalized node, and there are millions of fingerprints, so the searching process takes a lot of time. Our algorithm returns all fingerprints, and it needs only one pass of scanning the whole fingerprints to compute the Personalized PageRank vector. We randomly choose 10 personalized nodes and compare the average approximation time of Personalized PageRank, and the details are in Figure 4.

Figure 4

Average approximation time comparison of Personalized PageRank (PPR) approximation.

Third, we compare the overall performance between the two methods. The update time and Personalized PageRank approximation time of our method are all shorter than the Bahmani's method, and thus it is obvious that the overall time used by our method should be shorter. Here, using the multithreading technology of Java, we compare the throughput of the two methods, and the results are in Figure 5. In this experiment, one thread is used to generate changes of the structure of underlying graph, one thread is used to update fingerprints, and other threads are generated dynamically to compute the Personalized PageRank vector. We use the number of finished Personalized PageRank vectors per minute as the throughput. From the figure we can see that our proposed method is more efficient than the Bahmani's method in throughput.

Figure 5

Comparison of throughput.

Finally, we compare the accuracy of the two algorithms. To measure the quality of the results, for a node u and a value k, we define $Z_{u}^{k}$ to be the set of nodes with the k largest Personalized PageRank scores for u. In most Personalized PageRank-based applications, only nodes in $Z_{u}^{k}$ are of interest. For example, in recommending top-k friends in online social networks or returning top-k documents for a query, Personalized PageRank usually acts as one of the most important features. In this experiment, we assume Personalized PageRank as standard and compare how much approximation methods approximate it by the following equation:

\begin{matrix} Err (u, k) = \frac{\sum_{u \in Z_{u}^{k}}^{} | π_{u} (v) - {\hat{π}}_{u} (v) |}{\sum_{u \in Z_{u}^{k}}^{} π_{u} (v)}, \end{matrix}

(4)

where ${\hat{π}}_{u} (v)$ is the approximate Personalized PageRank by either Bahmani's or our algorithm. For the ground truth of $π_{u} (v)$ , we use 100 iterations of power iteration. For testing the efficiency of the algorithms for different nodes, we divide nodes in a graph into 4 buckets, where bucket $i (1 \leq i \leq 4)$ contains nodes with degree in $[1 0^{i - 1}, 1 0^{i})$ . There is no node with degree larger than 10000 in our datasets, so bucket 4 equals to $[1000, + \infty)$ . We randomly choose 10 nodes from each bucket and average the error defined by (4). We return top 10 and 100 results for each node and observe how approximation error changes along with the degree of nodes. Figures 6 and 7 illustrate the top-10 recommender results on both datasets, and Figures 8 and 9 illustrate the top-100 recommender results on both datasets. From these four figures we can see that, for both top 10 and top 100, our algorithm is more accurate in approximating Personalized PageRank than Bahmani's algorithm.

Figure 6

Bucket versus $\bar{Err}$ (·, 10), Dianping.

Figure 7

Bucket versus $\bar{Err}$ (·, 10), Gowalla.

Figure 8

Bucket versus $\bar{Err}$ (·, 100), Dianping.

Figure 9

Bucket versus $\bar{Err}$ (·, 100), Gowalla.

5. Conclusion

Personalized PageRank is very important for complex networks, and it has been proved to be effective in many real applications, such as link prediction, entity recommendation, and social searching. However, in these applications, the underlying networks are usually dynamic, and traditional power iteration method cannot deal with them efficiently.

In this paper, we design a Monte Carlo-based incremental method for Personalized PageRank approximation in dynamic networks. We propose an efficient update algorithm to handle changes of the structure of the underlying network, and an efficient Personalized PageRank approximation algorithm with the performed walks. Experiments on real-world networks show that our method can handle multichanges of the underlying network structure at one time and is more efficient than related work, so can be used in real incremental Personalized PageRank-based applications.

Footnotes

Acknowledgments

This work was supported in part by the National Significant Science and Technology Special Project of China and the National Natural Science Foundation of China.

References

Page

Brin

Motwani

Winograd

The PageRank citation ranking: bringing order to the web

1999

Stanford InfoLab

Haveliwala

T. H.

Topic-sensitive PageRank

Proceedings of the 11th International Conference on World Wide Web (WWW ′02)

May 2002

517 526

2-s2.0-77953061730

10.1145/511446.511513

Haveliwala

Kamvar

Jeh

An analytical comparison of approaches to personalizing PageRank

2003

Stanford

Liu

Lü

Link prediction based on local random walk

Europhysics Letters 2010 89 5

2-s2.0-79051470531

10.1209/0295-5075/89/58007

58007

Liben-Nowell

Kleinberg

The link-prediction problem for social networks

Journal of the American Society for Information Science and Technology 2007 58 7 1019 1031

2-s2.0-34249751638

10.1002/asi.20591

Song

H. H.

Cho

T. W.

Dave

Zhang

Qiu

Scalable proximity estimation and link prediction in online social networks

Proceedings of the 9th ACM SIGCOMM Conference on Internet Measurement Conference

2009

322 335

10.1145/1644893.1644932

Jiang

Wang

Pagerank-based collaborative filtering recommendation

Information Computing and Applications 2010

Springer

597 604

10.1007/978-3-642-16167-4_76

J. H.

Wang

B. W.

Tseng

V. S.

Effective ranking and recommendation on web page retrieval by integrating association mining and PageRank

Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT Workshops ′08)

December 2008

455 458

2-s2.0-62949170853

10.1109/WIIAT.2008.49

Ramezani

Improving graph-based approaches for personalized tag recommendation

Journal of Emerging Technologies in Web Intelligence 2011 3 2 168 176

2-s2.0-84858040785

10.4304/jetwi.3.2.168-176

10.

Yan

Yang

Ding

Yang

Research on micro-blog search and sorting algorithm based on improved PageRank

Proceedings of the International Conference on Information Engineering and Applications (IEA ′13)

2013

811 817

10.1007/978-1-4471-4850-0_103

11.

Bhushan

Kumar

Searching the most authoritative & obscure sources from the web

International Journal of Computer Science and Network Security 2010 10 8 149 153

12.

Litvak

Monte Carlo Methods of PageRank Computation 2004

Department of Applied Mathematics, University of Twente

13.

Fogaras

Rácz

Towards scaling fully personalized pagerank

Algorithms and Models for the Web-Graph 2004

Springer

105 117

10.1007/978-3-540-30216-2_9

14.

Borgs

Brautbar

Chayes

Teng

A sublinear time algorithm for pagerank computations

Algorithms and Models for the Web Graph 2012

Springer

41 53

10.1007/978-3-642-30541-2_4

15.

del Corso

G. M.

Gullí

Romani

Fast PageRank computation via a sparse linear system

Internet Mathematics 2005 2 3 251 273

10.1080/15427951.2005.10129108

16.

Fujiwara

Nakatsuji

Onizuka

Kitsuregawa

Fast and exact top-k search for random walk with restart

Proceedings of the VLDB Endowment 2012 5 5 442 453

17.

Sarma

A. D.

Gollapudi

Panigrahy

Estimating Pagerank on graph streams

Proceedings of the 27th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS ′08)

June 2008

69 78

2-s2.0-57349088162

10.1145/1376916.1376928

18.

Bahmani

Chakrabarti

Xin

Fast personalized PageRank on MapReduce

Proceedings of the ACM SIGMOD and 30th PODS 2011 Conference

June 2011

973 984

2-s2.0-79959919123

10.1145/1989323.1989425

19.

Dean

Ghemawat

MapReduce: simplified data processing on large clusters

Communications of the ACM 2008 51 1 107 113

2-s2.0-37549003336

10.1145/1327452.1327492

20.

Bahmani

Chowdhury

Goel

Fast incremental and personalized pagerank

Proceedings of the VLDB Endowment 2010 4 3 173 184

21.

Liu

Lü

Link prediction based on local random walk

Europhysics Letters 2010 89 5

2-s2.0-79051470531

10.1209/0295-5075/89/58007

58007

22.

Weng

Lim

E. P.

Jiang

TwitterRank: finding topic-sensitive influential twitterers

Proceedings of the 3rd ACM International Conference on Web Search and Data Mining (WSDM ′10)

February 2010

261 270

2-s2.0-77950897279

10.1145/1718487.1718520

23.

Kwak

Lee

Park

Moon

What is Twitter, a social network or a news media?

Proceedings of the 19th International World Wide Web Conference (WWW ′10)

April 2010

591 600

2-s2.0-77954619566

10.1145/1772690.1772751

24.

Brin

The anatomy of a large-scale hypertextual Web search engine

Computer Networks 1998 30 1–7 107 117

2-s2.0-0038589165

25.

Xing

Ghorbani

Weighted PageRank algorithm

Proceedings of the 2nd Annual Conference on Communication Networks and Services Research

May 2004

305 314

2-s2.0-4544264847

26.

Dominich

Skrop

PageRank and interaction information retrieval

Journal of the American Society for Information Science and Technology 2005 56 1 63 69

2-s2.0-11144269696

10.1002/asi.20102

27.

Taneja

Gupta

WEB information retrieval using query independent Page Rank algorithm

Proceedings of the International Conference on Advances in Computer Engineering (ACE ′10)

June 2010

178 182

2-s2.0-77956161889

10.1109/ACE.2010.72

28.

Kim

Y. A.

Song

H. S.

Strategies for predicting local trust based on trust propagation in social networks

Knowledge-Based Systems 2011 24 8 1360 1371

2-s2.0-80051470135

10.1016/j.knosys.2011.06.009

29.

King

Lyu

M. R.

Learning to recommend with social trust ensemble

Proceedings of the 32nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR ′09)

July 2009

203 210

2-s2.0-72249094128

10.1145/1571941.1571978

30.

Jamali

Ester

TrustWalker: a random walk model for combining trust-based and item-based recommendation

Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ′09)

July 2009

397 405

2-s2.0-70350656351

10.1145/1557019.1557067

31.

Meyffret

Médini

Laforest

Trust-based local and social recommendation

Proceedings of the 4th ACM RecSys Workshop on Recommender Systems and the Social Web

2012

53 60

10.1145/2365934.2365945

32.

Zheng

Xie

Learning travel recommendations from user-generated GPS traces

ACM Transactions on Intelligent Systems and Technology 2011 2 1, article 2

2-s2.0-79955148008

10.1145/1889681.1889683

33.

Jin

Shi

Yan

Fan

LBSNRank: personalized pagerank on location-based social networks

Proceedings of the 2012 ACM Conference on Ubiquitous Computing

2012

980 987

10.1145/2370216.2370430

34.

Cho

Myers

S. A.

Leskovec

Friendship and mobility: user movement in location-based social networks

Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ′11)

August 2011

1082 1090

2-s2.0-80052648113

10.1145/2020408.2020579

35.

Jung, http://jung.sourceforge.net/

Monte Carlo Based Personalized PageRank on Dynamic Networks

Abstract

1. Introduction

1.1. Background

1.2. Problem Statement

1.3. Our Contribution

2. Related Work

3. Monte Carlo-Based Incremental Personalized PageRank Computation

3.1. System Overall Design

3.2. Initializing Fingerprint Database

Algorithm 1: Initialization ( G , λ ).

3.3. Updating Fingerprint Database

Algorithm 2: Update ( G , k , W ).

3.4. Computing Personalized PageRank

Algorithm 3: Computing PPR ( W , u , ε ).

4. Experiments

4.1. Dataset

4.2. Experimental Setup

4.3. Experimental Results

5. Conclusion

Footnotes

Acknowledgments

References

Algorithm 1: Initialization ( $G, λ$ ).

Algorithm 2: Update ( $G, k, W$ ).

Algorithm 3: Computing PPR ( $W, u, ε$ ).