A Survey on Personalized PageRank Computation Algorithms <s> B. SOCIAL NETWORK ANALYSIS <s> How closely related are two nodes in a graph? How to compute this score quickly, on huge, disk-resident, real graphs? Random walk with restart (RWR) provides a good relevance score between two nodes in a weighted graph, and it has been successfully used in numerous settings, like automatic captioning of images, generalizations to the "connection subgraphs", personalized PageRank, and many more. However, the straightforward implementations of RWR do not scale for large graphs, requiring either quadratic space and cubic pre-computation time, or slow response time on queries. We propose fast solutions to this problem. The heart of our approach is to exploit two important properties shared by many real graphs: (a) linear correlations and (b) block- wise, community-like structure. We exploit the linearity by using low-rank matrix approximation, and the community structure by graph partitioning, followed by the Sherman- Morrison lemma for matrix inversion. Experimental results on the Corel image and the DBLP dabasets demonstrate that our proposed methods achieve significant savings over the straightforward implementations: they can save several orders of magnitude in pre-computation and storage cost, and they achieve up to 150x speed up with 90%+ quality preservation. <s> BIB001 </s> A Survey on Personalized PageRank Computation Algorithms <s> B. SOCIAL NETWORK ANALYSIS <s> Given Q nodes in a social network (say, authorship network), how can we find the node/author that is the center-piece, and has direct or indirect connections to all, or most of them? For example, this node could be the common advisor, or someone who started the research area that the Q nodes belong to. Isomorphic scenarios appear in law enforcement (find the master-mind criminal, connected to all current suspects), gene regulatory networks (find the protein that participates in pathways with all or most of the given Q proteins), viral marketing and many more.Connection subgraphs is an important first step, handling the case of Q=2 query nodes. Then, the connection subgraph algorithm finds the b intermediate nodes, that provide a good connection between the two original query nodes.Here we generalize the challenge in multiple dimensions: First, we allow more than two query nodes. Second, we allow a whole family of queries, ranging from 'OR' to 'AND', with 'softAND' in-between. Finally, we design and compare a fast approximation, and study the quality/speed trade-off.We also present experiments on the DBLP dataset. The experiments confirm that our proposed method naturally deals with multi-source queries and that the resulting subgraphs agree with our intuition. Wall-clock timing results on the DBLP dataset show that our proposed approximation achieve good accuracy for about 6:1 speedup. <s> BIB002 </s> A Survey on Personalized PageRank Computation Algorithms <s> B. SOCIAL NETWORK ANALYSIS <s> Identification of nodes relevant to a given node in a relational network is a basic problem in network analysis with great practical importance. Most existing network analysis algorithms utilize one single relation to define relevancy among nodes. However, in real world applications multiple relationships exist between nodes in a network. Therefore, network analysis algorithms that can make use of more than one relation to identify the relevance set for a node are needed. In this paper, we show how the Random Walk with Restart (RWR) approach can be used to study relevancy in a bi-relational network from the bibliographic domain, and show that making use of two relations results in better results as compared to approaches that use a single relation. As relational networks can be very large, we also propose a fast implementation for RWR by adapting an existing Iterative Aggregation and Disaggregation (IAD) approach. The IAD-based RWR exploits the block-wise structure of real world networks. Experimental results show significant increase in running time for the IAD-based RWR compared to the traditional power method based RWR. <s> BIB003 </s> A Survey on Personalized PageRank Computation Algorithms <s> B. SOCIAL NETWORK ANALYSIS <s> The problem of missing link prediction in complex networks has attracted much attention recently. Two difficulties in link prediction are the sparsity and huge size of the target networks. Therefore, the design of an efficient and effective method is of both theoretical interests and practical significance. In this Letter, we proposed a method based on local random walk, which can give competitively good prediction or even better prediction than other random-walk-based methods while has a lower computational complexity. <s> BIB004 </s> A Survey on Personalized PageRank Computation Algorithms <s> B. SOCIAL NETWORK ANALYSIS <s> Predicting the occurrence of links is a fundamental problem in networks. In the link prediction problem we are given a snapshot of a network and would like to infer which interactions among existing members are likely to occur in the near future or which existing interactions are we missing. Although this problem has been extensively studied, the challenge of how to effectively combine the information from the network structure with rich node and edge attribute data remains largely open. We develop an algorithm based on Supervised Random Walks that naturally combines the information from the network structure with node and edge level attributes. We achieve this by using these attributes to guide a random walk on the graph. We formulate a supervised learning task where the goal is to learn a function that assigns strengths to edges in the network such that a random walker is more likely to visit the nodes to which new links will be created in the future. We develop an efficient training algorithm to directly learn the edge strength estimation function. Our experiments on the Facebook social graph and large collaboration networks show that our approach outperforms state-of-the-art unsupervised approaches as well as approaches that are based on feature extraction. <s> BIB005 </s> A Survey on Personalized PageRank Computation Algorithms <s> B. SOCIAL NETWORK ANALYSIS <s> In this paper new results on personalized PageRank are shown. We consider directed graphs that may contain dangling nodes. The main result presented gives an analytical characterization of all the possible values of the personalized PageRank for any node.We use this result to give a theoretical justification of a recent model that uses the personalized PageRank to classify users of Social Networks Sites. We introduce new concepts concerning competitivity and leadership in complex networks. We also present some theoretical techniques to locate leaders and competitors which are valid for any personalization vector and by using only information related to the adjacency matrix of the graph and the distribution of its dangling nodes. <s> BIB006 </s> A Survey on Personalized PageRank Computation Algorithms <s> B. SOCIAL NETWORK ANALYSIS <s> In this paper we present a new framework to identify leaders on an SNS using the Personalized PageRank vector. The methodology is based in the concept of Leadership group recently introduced by one of the authors. We show how to analyze the structure of the Leadership group as a function of a single parameter. Zachary’s network and a Facebook university network are used to illustrate the applicability of the model. As an application we introduce some new concepts such as the probability to be a leader, a classication of networks and the concept of best potential friend. <s> BIB007 </s> A Survey on Personalized PageRank Computation Algorithms <s> B. SOCIAL NETWORK ANALYSIS <s> At present, most link prediction algorithms are based on the similarity between two entities. Social network topology information is one of the main sources to design the similarity function between entities. But the existing link prediction algorithms do not apply the network topology information sufficiently. For lack of traditional link prediction algorithms, we propose two improved algorithms: CNGF algorithm based on local information and KatzGF algorithm based on global information network. For the defect of the stationary of social network, we also provide the link prediction algorithm based on nodes multiple attributes information. Finally, we verified these algorithms on DBLP data set, and the experimental results show that the performance of the improved algorithm is superior to that of the traditional link prediction algorithm. <s> BIB008 </s> A Survey on Personalized PageRank Computation Algorithms <s> B. SOCIAL NETWORK ANALYSIS <s> Although criticized for some of its limitations, modularity remains a standard measure for analyzing social networks. Quantifying the statistical surprise in the arrangement of the edges of the network has led to simple and powerful algorithms. However, relying solely on the distribution of edges instead of more complex structures such as paths limits the extent of modularity. Indeed, recent studies have shown restrictions of optimizing modularity, for instance its resolution limit. We introduce here a novel, formal and well-defined modularity measure based on random walks. We show how this modularity can be computed from paths induced by the graph instead of the traditionally used edges. We argue that by computing modularity on paths instead of edges, more informative features can be extracted from the network. We verify this hypothesis on a semi-supervised classification procedure of the nodes in the network, where we show that, under the same settings, the features of the random walk modularity help to classify better than the features of the usual modularity. Additionally, the proposed approach outperforms the classical label propagation procedure on two data sets of labeled social networks. <s> BIB009 </s> A Survey on Personalized PageRank Computation Algorithms <s> B. SOCIAL NETWORK ANALYSIS <s> How can we rank users in signed social networks? Relationships between nodes in a signed network are represented as positive (trust) or negative (distrust) edges. Many social networks have adopted signed networks to express trust between users. Consequently, ranking friends or enemies in signed networks has received much attention from the data mining community. The ranking problem, however, is challenging because it is difficult to interpret negative edges. Traditional random walk based methods such as PageRank and Random Walk with Restart cannot provide effective rankings in signed networks since they assume only positive edges. Although several methods have been proposed by modifying traditional ranking models, they also fail to account for proper rankings due to the lack of ability to consider complex edge relations. In this paper, we propose Signed Random Walk with Restart, a novel model for personalized ranking in signed networks. We introduce a signed random surfer so that she considers negative edges by changing her sign for walking. Our model provides proper rankings reflecting signed edges based on the signed surfer. Through extensive experiments, we demonstrate that SRWR achieves the best accuracy (up to 87%) for sign prediction, and predicts trolls 4× more accurately than other ranking models. <s> BIB010
PPR is used for measuring importance of each users in SNSs to analyze social network structures. Garcia et al. BIB006 analytically characterized all the possible values of PPR for any node, and introduced a new concept concerning the competitivity and leadership in networks. Pedroche et al. BIB007 introduced a new parameter, the frequency, to the Leadership group, which is a group of nodes that have higher PageRanks than others. Then, they analyzed some graphs using the Leadership group while controlling the biasing factor . Additionally, PPR has been used as a link prediction tool of SNSs BIB008 . Backstrom and Leskovec BIB005 developed an algorithm called the ''Supervised Random Walk'' that combines the information of a network structure and edge attributes to predict the links in social network. They used the node and edge attributes to guide the random walks toward the target node. Liu and Lu BIB004 proposed a link prediction method based on the local random walk that has much lower computational complexity. Xia et al. BIB003 showed that Random Walk with Restart (RWR) can be utilized to determine the relevancy in a birelational network in the bibliographicdomain. BIB001 Open Directory Project, http://odp.org/ Tong and Faloutsos BIB002 introduced the ''center-piece subgraphs'' problem of a social network and proposed a fast subgraph extraction algorithm. Jung et al. BIB010 proposed Signed Random Walk with Restart (SRWR) for personalized rankings in signed networks using a signed surfer. Devooght et al. BIB009 introduced a random walk based modularity measure, which is computed using the paths instead of the traditionally used edges, for analyzing social networks.