•A new centrality measure for attributed multiplex networks is proposed.•It solves the drawback of the existence of isolated nodes in any of the layers.
A new algorithm for attributed multiplex ...networks is proposed and analysed with the main objective to compute the centrality of the nodes based on the original PageRank model used to establish a ranking in the Web pages network. Taking as a basis the Adapted PageRank Algorithm for monoplex networks with data and the two-layer PageRank approach, an algorithm for biplex networks is designed with two main characteristics. First, it solves the drawback of the existence of isolated nodes in any of the layers. Second, the algorithm allows us to choose the value of the parameter α controlling the importance assigned to the network topology and the data associated to the nodes in the Adapted PageRank Algorithm, respectively. The proposed algorithm inherits this ability to determine the importance of node attribute data in the calculation of the centrality; yet, going further, it allows to choose different α values for each of the two layers. The biplex algorithm is then generalised to the case of multiple layers, that is, for multiplex networks. Its possibilities and characteristics are demonstrated using a dataset of aggregate origin-destination flows of private cars in Rome. This dataset is augmented with attribute data describing city locations. In particular, a biplex network is constructed by taking the data about car mobility for layer 1. Layer 2 is generated from data describing the local bus transport system. The algorithm establishes the most central locations in the city when these layers are intertwined with the location attributes in the biplex network. Four cases are evaluated and compared for different values of the parameter that modulates the importance of data in the network.
PageRank Beyond the Web Gleich, David F.
SIAM review,
01/2015, Letnik:
57, Številka:
3
Journal Article
Recenzirano
Google's PageRank method was developed to evaluate the importance of web-pages via their link structure. The mathematics of PageRank, however, are entirely general and apply to any graph or network ...in any domain. Thus, PageRank is now regularly used in bibliometrics, social and information network analysis, and for link prediction and recommendation. It's even used for systems analysis of road networks, as well as biology, chemistry, neuroscience, and physics. We'll see the mathematics and ideas that unite these diverse applications.
Personalized PageRank (PPR) is a traditional measure for node proximity on large graphs. For a pair of nodes <inline-formula><tex-math notation="LaTeX">\boldsymbol{s}</tex-math></inline-formula> and ...<inline-formula><tex-math notation="LaTeX">\boldsymbol{t}</tex-math></inline-formula>, the PPR value <inline-formula><tex-math notation="LaTeX">\boldsymbol{\pi_{s}(t)}</tex-math></inline-formula> equals the probability that an <inline-formula><tex-math notation="LaTeX">\boldsymbol{\alpha }</tex-math></inline-formula>-discounted random walk from <inline-formula><tex-math notation="LaTeX">\boldsymbol{s}</tex-math></inline-formula> terminates at <inline-formula><tex-math notation="LaTeX">\boldsymbol{t}</tex-math></inline-formula> and reflects the importance between <inline-formula><tex-math notation="LaTeX">\boldsymbol{s}</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">\boldsymbol{t}</tex-math></inline-formula> in a bidirectional way. As a generalization of Google's celebrated PageRank centrality, PPR has been extensively studied and has found multifaceted applications in many fields, such as network analysis, graph mining, and graph machine learning. Despite numerous studies devoted to PPR over the decades, efficient computation of PPR remains a challenging problem, and there is a dearth of systematic summaries and comparisons of existing algorithms. In this paper, we recap several frequently used techniques for PPR computation and conduct a comprehensive survey of various recent PPR algorithms from an algorithmic perspective. We classify these approaches based on the types of queries they address and review their methodologies and contributions. We also discuss some representative algorithms for computing PPR on dynamic graphs and in parallel or distributed environments.
In this paper, we present Google, a prototype of a large-scale search engine which makes heavy use of the structure present in hypertext. Google is designed to crawl and index the Web efficiently and ...produce much more satisfying search results than existing systems. The prototype with a full text and hyperlink database of at least 24million pages is available at http://google.stanford.edu/
To engineer a search engine is a challenging task. Search engines index tens to hundreds of millions of web pages involving a comparable number of distinct terms. They answer tens of millions of queries every day. Despite the importance of large-scale search engines on the web, very little academic research has been done on them. Furthermore, due to rapid advance in technology and web proliferation, creating a web search engine today is very different from 3years ago. This paper provides an in-depth description of our large-scale web search engine – the first such detailed public description we know of to date.
Apart from the problems of scaling traditional search techniques to data of this magnitude, there are new technical challenges involved with using the additional information present in hypertext to produce better search results. This paper addresses this question of how to build a practical large-scale system which can exploit the additional information present in hypertext. Also we look at the problem of how to effectively deal with uncontrolled hypertext collections, where anyone can publish anything they want.
•A centrality model for urban street networks is proposed.•Non-local random walks are used to extend the Adapted PageRank Algorithm model.•The non-local movement of the random walker is more ...intuitive.
In the urban street network domain, there is growing interest in extending conventional centrality measures to incorporate node-specific information (such as georeferenced socioeconomic data) in order to help identify important locations in an urban environment. One such centrality measure that is gaining attention is the Adapted PageRank Algorithm (APA) model. However, a fundamental concern with the APA model is the notion of teleportation because it means the random walker is equally likely to jump or ‘teleport’ to any intersection (node) in the street network, regardless of how far away it is. In this paper, we propose a centrality model that overcomes this counterintuitive idea. More specifically, we extend the APA model by modifying the jumping probabilities so that the random walker is more inclined to jump to a nearby intersection than a distant intersection. We accomplish this using non-local random walks which allow a random walker to jump to any node in the network with probabilities that depend on the distance separating the nodes. To demonstrate the differences between the two models, we present and discuss experimental results for a small ten node graph and a real-world urban street network.
•A centrality measure, with a practical application in urban network, has been proposed.•The measure establishes a ranking of nodes focused on the topological data distribution.•The amount of data ...associated with the nodes of the network has a great importance.•The topology of the network and the information associated to the nodes are involved.
The Adapted PageRank Algorithm (APA) proposed by Agryzkov et al. provides us a method to establish a ranking of nodes in an urban network. We can say that it constitutes a centrality measure in urban networks, with the main characteristic that is able to consider the importance of data obtained from the urban networks in the process of computing the centrality of every node. Starting from the basic idea of this model, we modify the construction of the matrix used for the classification of the nodes in order of importance. In the APA model, the data matrix is constructed from the original idea of PageRank vector, given an equal chance to jump from one node to another, regardless of the topological distance between nodes. In the new model this idea is questioned. A new matrix with the data network is constructed so that now the data from neighboring nodes are considered more likely than data from the nodes that are farther away. In addition, this new algorithm has the characteristic that depends on a parameter α, which allows us to decide the importance attached, in the computation of the centrality, to the topology of the network and the amount of data associated with the node. Various numerical experiments with a network of very small size are performed to test the influence of the data associated with the nodes, depending always on the choice of the parameter α. Also we check the differences between the values produced by the original APA model and the new one. Finally, these measures are applied to a real urban network, in which we perform a visual comparison of the results produced by the various measures calculated from the algorithms studied.
PDF
