19 Search Results for "Mahoney, Michael W."


Document
Unified Acceleration Method for Packing and Covering Problems via Diameter Reduction

Authors: Di Wang, Satish Rao, and Michael W. Mahoney

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)


Abstract
In a series of recent breakthroughs, Allen-Zhu and Orecchia [Allen-Zhu/Orecchia, STOC 2015; Allen-Zhu/Orecchia, SODA 2015] leveraged insights from the linear coupling method [Allen-Zhu/Oreccia, arXiv 2014], which is a first-order optimization scheme, to provide improved algorithms for packing and covering linear programs. The result in [Allen-Zhu/Orecchia, STOC 2015] is particularly interesting, as the algorithm for packing LP achieves both width-independence and Nesterov-like acceleration, which was not known to be possible before. Somewhat surprisingly, however, while the dependence of the convergence rate on the error parameter epsilon for packing problems was improved to O(1/epsilon), which corresponds to what accelerated gradient methods are designed to achieve, the dependence for covering problems was only improved to O(1/epsilon^{1.5}), and even that required a different more complicated algorithm, rather than from Nesterov-like acceleration. Given the primal-dual connection between packing and covering problems and since previous algorithms for these very related problems have led to the same epsilon dependence, this discrepancy is surprising, and it leaves open the question of the exact role that the linear coupling is playing in coordinating the complementary gradient and mirror descent step of the algorithm. In this paper, we clarify these issues, illustrating that the linear coupling method can lead to improved O(1/epsilon) dependence for both packing and covering problems in a unified manner, i.e., with the same algorithm and almost identical analysis. Our main technical result is a novel dimension lifting method that reduces the coordinate-wise diameters of the feasible region for covering LPs, which is the key structural property to enable the same Nesterov-like acceleration as in the case of packing LPs. The technique is of independent interest and that may be useful in applying the accelerated linear coupling method to other combinatorial problems.

Cite as

Di Wang, Satish Rao, and Michael W. Mahoney. Unified Acceleration Method for Packing and Covering Problems via Diameter Reduction. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 50:1-50:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.ICALP.2016.50,
  author =	{Wang, Di and Rao, Satish and Mahoney, Michael W.},
  title =	{{Unified Acceleration Method for Packing and Covering Problems via Diameter Reduction}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{50:1--50:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.50},
  URN =		{urn:nbn:de:0030-drops-63308},
  doi =		{10.4230/LIPIcs.ICALP.2016.50},
  annote =	{Keywords: Convex optimization, Accelerated gradient descent, Linear program, Approximation algorithm, Packing and covering}
}
Document
Approximating the Solution to Mixed Packing and Covering LPs in Parallel O˜(epsilon^{-3}) Time

Authors: Michael W. Mahoney, Satish Rao, Di Wang, and Peng Zhang

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)


Abstract
We study the problem of approximately solving positive linear programs (LPs). This class of LPs models a wide range of fundamental problems in combinatorial optimization and operations research, such as many resource allocation problems, solving non-negative linear systems, computing tomography, single/multi commodity flows on graphs, etc. For the special cases of pure packing or pure covering LPs, recent result by Allen-Zhu and Orecchia [Allen/Zhu/Orecchia, SODA'15] gives O˜(1/(epsilon^3))-time parallel algorithm, which breaks the longstanding O˜(1/(epsilon^4)) running time bound by the seminal work of Luby and Nisan [Luby/Nisan, STOC'93]. We present new parallel algorithm with running time O˜(1/(epsilon^3)) for the more general mixed packing and covering LPs, which improves upon the O˜(1/(epsilon^4))-time algorithm of Young [Young, FOCS'01; Young, arXiv 2014]. Our work leverages the ideas from both the optimization oriented approach [Allen/Zhu/Orecchia, SODA'15; Wang/Mahoney/Mohan/Rao, arXiv 2015], as well as the more combinatorial approach with phases [Young, FOCS'01; Young, arXiv 2014]. In addition, our algorithm, when directly applied to pure packing or pure covering LPs, gives a improved running time of O˜(1/(epsilon^2)).

Cite as

Michael W. Mahoney, Satish Rao, Di Wang, and Peng Zhang. Approximating the Solution to Mixed Packing and Covering LPs in Parallel O˜(epsilon^{-3}) Time. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 52:1-52:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{mahoney_et_al:LIPIcs.ICALP.2016.52,
  author =	{Mahoney, Michael W. and Rao, Satish and Wang, Di and Zhang, Peng},
  title =	{{Approximating the Solution to Mixed Packing and Covering LPs in Parallel O˜(epsilon^\{-3\}) Time}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{52:1--52:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.52},
  URN =		{urn:nbn:de:0030-drops-63335},
  doi =		{10.4230/LIPIcs.ICALP.2016.52},
  annote =	{Keywords: Mixed packing and covering, Linear program, Approximation algorithm, Parallel algorithm}
}
Document
07071 Abstracts Collection – Web Information Retrieval and Linear Algebra Algorithms

Authors: Andreas Frommer, Michael W. Mahoney, and Daniel B. Szyld

Published in: Dagstuhl Seminar Proceedings, Volume 7071, Web Information Retrieval and Linear Algebra Algorithms (2007)


Abstract
From 12th to 16th February 2007, the Dagstuhl Seminar 07071 ``Web Information Retrieval and Linear Algebra Algorithms'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Andreas Frommer, Michael W. Mahoney, and Daniel B. Szyld. 07071 Abstracts Collection – Web Information Retrieval and Linear Algebra Algorithms. In Web Information Retrieval and Linear Algebra Algorithms. Dagstuhl Seminar Proceedings, Volume 7071, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{frommer_et_al:DagSemProc.07071.1,
  author =	{Frommer, Andreas and Mahoney, Michael W. and Szyld, Daniel B.},
  title =	{{07071 Abstracts Collection – Web Information Retrieval and Linear Algebra Algorithms}},
  booktitle =	{Web Information Retrieval and Linear Algebra Algorithms},
  pages =	{1--20},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7071},
  editor =	{Andreas Frommer and Michael W. Mahoney and Daniel B. Szyld},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07071.1},
  URN =		{urn:nbn:de:0030-drops-10743},
  doi =		{10.4230/DagSemProc.07071.1},
  annote =	{Keywords: Information retrieval, Markov chains, PageRank, numerical linear algebra, low rank approximations, sparsity, ranking}
}
Document
07071 Report on Dagstuhl Seminar – Web Information Retrieval and Linear Algebra Algorithms

Authors: Andreas Frommer, Michael W. Mahoney, and Daniel B. Szyld

Published in: Dagstuhl Seminar Proceedings, Volume 7071, Web Information Retrieval and Linear Algebra Algorithms (2007)


Abstract
A seminar concentrating on the intersection of the fields of information retrieval and other web-related aspects with numerical and applied linear algebra techniques was held with the attendance of scientists from industry and academia.

Cite as

Andreas Frommer, Michael W. Mahoney, and Daniel B. Szyld. 07071 Report on Dagstuhl Seminar – Web Information Retrieval and Linear Algebra Algorithms. In Web Information Retrieval and Linear Algebra Algorithms. Dagstuhl Seminar Proceedings, Volume 7071, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{frommer_et_al:DagSemProc.07071.2,
  author =	{Frommer, Andreas and Mahoney, Michael W. and Szyld, Daniel B.},
  title =	{{07071 Report on Dagstuhl Seminar – Web Information Retrieval and Linear Algebra Algorithms}},
  booktitle =	{Web Information Retrieval and Linear Algebra Algorithms},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7071},
  editor =	{Andreas Frommer and Michael W. Mahoney and Daniel B. Szyld},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07071.2},
  URN =		{urn:nbn:de:0030-drops-10709},
  doi =		{10.4230/DagSemProc.07071.2},
  annote =	{Keywords: Information retrieval, Markov chains, PageRank, numerical linear algebra, low rank approximations, sparsity , ranking}
}
Document
A Deeper Investigation of PageRank as a Function of the Damping Factor

Authors: Paolo Boldi, Massimo Santini, and Sebastiano Vigna

Published in: Dagstuhl Seminar Proceedings, Volume 7071, Web Information Retrieval and Linear Algebra Algorithms (2007)


Abstract
PageRank is defined as the stationary state of a Markov chain. The chain is obtained by perturbing the transition matrix induced by a web graph with a damping factor $alpha$ that spreads uniformly part of the rank. The choice of $alpha$ is eminently empirical, and in most cases the original suggestion $alpha=0.85$ by Brin and Page is still used. In this paper, we give a mathematical analysis of PageRank when $alpha$ changes. In particular, we show that, contrarily to popular belief, for real-world graphs values of $alpha$ close to $1$ do not give a more meaningful ranking. Then, we give closed-form formulae for PageRank derivatives of any order, and by proving that the $k$-th iteration of the Power Method gives exactly the PageRank value obtained using a Maclaurin polynomial of degree $k$, we show how to obtain an approximation of the derivatives. Finally, we view PageRank as a linear operator acting on the preference vector and show a tight connection between iterated computation and derivation.

Cite as

Paolo Boldi, Massimo Santini, and Sebastiano Vigna. A Deeper Investigation of PageRank as a Function of the Damping Factor. In Web Information Retrieval and Linear Algebra Algorithms. Dagstuhl Seminar Proceedings, Volume 7071, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{boldi_et_al:DagSemProc.07071.3,
  author =	{Boldi, Paolo and Santini, Massimo and Vigna, Sebastiano},
  title =	{{A Deeper Investigation of PageRank as a Function of the Damping Factor}},
  booktitle =	{Web Information Retrieval and Linear Algebra Algorithms},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7071},
  editor =	{Andreas Frommer and Michael W. Mahoney and Daniel B. Szyld},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07071.3},
  URN =		{urn:nbn:de:0030-drops-10722},
  doi =		{10.4230/DagSemProc.07071.3},
  annote =	{Keywords: PageRank, damping factor, Markov chains}
}
Document
A Fast Algorithm for Matrix Balancing

Authors: Philip A. Knight and Daniel Ruiz

Published in: Dagstuhl Seminar Proceedings, Volume 7071, Web Information Retrieval and Linear Algebra Algorithms (2007)


Abstract
As long as a square nonnegative matrix A contains sufficient nonzero elements, then the matrix can be balanced, that is we can find a diagonal scaling of A that is doubly stochastic. A number of algorithms have been proposed to achieve the balancing, the most well known of these being the Sinkhorn-Knopp algorithm. In this paper we derive new algorithms based on inner-outer iteration schemes. We show that the Sinkhorn-Knopp algorithm belongs to this family, but other members can converge much more quickly. In particular, we show that while stationary iterative methods offer little or no improvement in many cases, a scheme using a preconditioned conjugate gradient method as the inner iteration can give quadratic convergence at low cost.

Cite as

Philip A. Knight and Daniel Ruiz. A Fast Algorithm for Matrix Balancing. In Web Information Retrieval and Linear Algebra Algorithms. Dagstuhl Seminar Proceedings, Volume 7071, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{knight_et_al:DagSemProc.07071.4,
  author =	{Knight, Philip A. and Ruiz, Daniel},
  title =	{{A Fast Algorithm for Matrix Balancing}},
  booktitle =	{Web Information Retrieval and Linear Algebra Algorithms},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7071},
  editor =	{Andreas Frommer and Michael W. Mahoney and Daniel B. Szyld},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07071.4},
  URN =		{urn:nbn:de:0030-drops-10735},
  doi =		{10.4230/DagSemProc.07071.4},
  annote =	{Keywords: Matrix balancing, Sinkhorn-Knopp algorithm, doubly stochastic matrix, conjugate gradient iteration}
}
Document
An Inner/Outer Stationary Iteration for Computing PageRank

Authors: Andrew P. Gray, Chen Greif, and Tracy Lau

Published in: Dagstuhl Seminar Proceedings, Volume 7071, Web Information Retrieval and Linear Algebra Algorithms (2007)


Abstract
We present a stationary iterative scheme for PageRank computation. The algorithm is based on a linear system formulation of the problem, uses inner/outer iterations, and amounts to a simple preconditioning technique. It is simple, can be easily implemented and parallelized, and requires minimal storage overhead. Convergence analysis shows that the algorithm is effective for a crude inner tolerance and is not particularly sensitive to the choice of the parameters involved. Numerical examples featuring matrices of dimensions up to approximately $10^7$ confirm the analytical results and demonstrate the accelerated convergence of the algorithm compared to the power method.

Cite as

Andrew P. Gray, Chen Greif, and Tracy Lau. An Inner/Outer Stationary Iteration for Computing PageRank. In Web Information Retrieval and Linear Algebra Algorithms. Dagstuhl Seminar Proceedings, Volume 7071, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{gray_et_al:DagSemProc.07071.5,
  author =	{Gray, Andrew P. and Greif, Chen and Lau, Tracy},
  title =	{{An Inner/Outer Stationary Iteration for Computing PageRank}},
  booktitle =	{Web Information Retrieval and Linear Algebra Algorithms},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7071},
  editor =	{Andreas Frommer and Michael W. Mahoney and Daniel B. Szyld},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07071.5},
  URN =		{urn:nbn:de:0030-drops-10628},
  doi =		{10.4230/DagSemProc.07071.5},
  annote =	{Keywords: PageRank, power method, stationary method, inner/outer iterations, damping factor}
}
Document
Asynchronous Computation of PageRank computation in an interactive multithreading environment

Authors: Giorgios Kollias and Efstratios Gallopoulos

Published in: Dagstuhl Seminar Proceedings, Volume 7071, Web Information Retrieval and Linear Algebra Algorithms (2007)


Abstract
Numerical Linear Algebra has become almost indispensable in Web Information Retrieval. In this presentation we suggest that the asynchronous computation model is an attractive paradigm for organizing concurrent computations spanning data on Web scale. This suggestion is supported by experiments which highlight some interesting characteristics of this model as applied to 'page ranking' methods. After an introduction on asynchronous computing in general and 'page ranking' in particular, we present results from the asynchronous compution of PageRank using typical combinations of execution units (processes, threads) and communication mechanisms (message passing, shared memory). Sound convergence properties predicted by theory are numerically verified and interesting patterns of behavior are unveiled. Our experiments were performed on Jylab, an evolving environment enabling interactive multithreading and multiprocessing computations. This work is supported by a Pythagoras-EPEAEK-II grant and is conducted in collaboration with Daniel Szyld.

Cite as

Giorgios Kollias and Efstratios Gallopoulos. Asynchronous Computation of PageRank computation in an interactive multithreading environment. In Web Information Retrieval and Linear Algebra Algorithms. Dagstuhl Seminar Proceedings, Volume 7071, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{kollias_et_al:DagSemProc.07071.6,
  author =	{Kollias, Giorgios and Gallopoulos, Efstratios},
  title =	{{Asynchronous Computation of PageRank computation in an interactive multithreading environment}},
  booktitle =	{Web Information Retrieval and Linear Algebra Algorithms},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7071},
  editor =	{Andreas Frommer and Michael W. Mahoney and Daniel B. Szyld},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07071.6},
  URN =		{urn:nbn:de:0030-drops-10651},
  doi =		{10.4230/DagSemProc.07071.6},
  annote =	{Keywords: Asynchronous, pagerank, multithreading, multiprocessing}
}
Document
Convergence of iterative aggregation/disaggregation methods based on splittings with cyclic iteration matrices

Authors: Ivo Marek, Ivana Pultarová, and Petr Mayer

Published in: Dagstuhl Seminar Proceedings, Volume 7071, Web Information Retrieval and Linear Algebra Algorithms (2007)


Abstract
Iterative aggregation/disaggregation methods (IAD) belong to competitive tools for computation the characteristics of Markov chains as shown in some publications devoted to testing and comparing various methods designed to this purpose. According to Dayar T., Stewart W.J., ``Comparison of partitioning techniques for two-level iterative solvers on large, sparse Markov chains,'' SIAM J. Sci. Comput., Vol.21, No. 5, 1691-1705 (2000), the IAD methods are effective in particular when applied to large ill posed problems. One of the purposes of this paper is to contribute to a possible explanation of this fact. The novelty may consist of the fact that the IAD algorithms do converge independently of whether the iteration matrix of the corresponding process is primitive or not. Some numerical tests are presented and possible applications mentioned; e.g. computing the PageRank.

Cite as

Ivo Marek, Ivana Pultarová, and Petr Mayer. Convergence of iterative aggregation/disaggregation methods based on splittings with cyclic iteration matrices. In Web Information Retrieval and Linear Algebra Algorithms. Dagstuhl Seminar Proceedings, Volume 7071, pp. 1-27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{marek_et_al:DagSemProc.07071.7,
  author =	{Marek, Ivo and Pultarov\'{a}, Ivana and Mayer, Petr},
  title =	{{Convergence of iterative aggregation/disaggregation methods based on splittings with cyclic iteration matrices}},
  booktitle =	{Web Information Retrieval and Linear Algebra Algorithms},
  pages =	{1--27},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7071},
  editor =	{Andreas Frommer and Michael W. Mahoney and Daniel B. Szyld},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07071.7},
  URN =		{urn:nbn:de:0030-drops-10679},
  doi =		{10.4230/DagSemProc.07071.7},
  annote =	{Keywords: Iterative aggregation methods, stochastic matrix, stationary probability vector, Markov chains, cyclic iteration matrix, Google matrix, PageRank.}
}
Document
Exploiting Community Behavior for Enhanced Link Analysis and Web Search

Authors: Julia Luxenburger and Gerhard Weikum

Published in: Dagstuhl Seminar Proceedings, Volume 7071, Web Information Retrieval and Linear Algebra Algorithms (2007)


Abstract
Methods for Web link analysis and authority ranking such as PageRank are based on the assumption that a user endorses a Web page when creating a hyperlink to this page. There is a wealth of additional user-behavior information that could be considered for improving authority analysis, for example, the history of queries that a user community posed to a search engine over an extended time period, or observations about which query-result pages were clicked on and which ones were not clicked on after a user saw the summary snippets of the top-10 results. We study enhancements of link analysis methods by incorporating additional user assessments based on query logs and click streams, including negative feedback when a query-result page does not satisfy the user demand or is even perceived as spam. Our methods use various novel forms of Markov models whose states correspond to users and queries in addition to Web pages and whose links also reflect the relationships derived from query-result clicks, query refinements, and explicit ratings.

Cite as

Julia Luxenburger and Gerhard Weikum. Exploiting Community Behavior for Enhanced Link Analysis and Web Search. In Web Information Retrieval and Linear Algebra Algorithms. Dagstuhl Seminar Proceedings, Volume 7071, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{luxenburger_et_al:DagSemProc.07071.8,
  author =	{Luxenburger, Julia and Weikum, Gerhard},
  title =	{{Exploiting Community Behavior for Enhanced Link Analysis and Web Search}},
  booktitle =	{Web Information Retrieval and Linear Algebra Algorithms},
  pages =	{1--17},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7071},
  editor =	{Andreas Frommer and Michael W. Mahoney and Daniel B. Szyld},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07071.8},
  URN =		{urn:nbn:de:0030-drops-10660},
  doi =		{10.4230/DagSemProc.07071.8},
  annote =	{Keywords: Query logs, link analysis, Markov reward model}
}
Document
Extrapolation and minimization procedures for the PageRank vector

Authors: Claude Brezinski and Michela Redivo-Zaglia

Published in: Dagstuhl Seminar Proceedings, Volume 7071, Web Information Retrieval and Linear Algebra Algorithms (2007)


Abstract
An important problem in Web search is to determine the importance of each page. This problem consists in computing, by the power method, the left principal eigenvector (the PageRank vector) of a matrix depending on a parameter $c$ which has to be chosen close to 1. However, when $c$ is close to 1, the problem is ill-conditioned, and the power method converges slowly. So, the idea developed in this paper consists in computing the PageRank vector for several values of $c$, and then to extrapolate them, by a conveniently chosen rational function, at a point near 1. The choice of this extrapolating function is based on the mathematical considerations about the PageRank vector.

Cite as

Claude Brezinski and Michela Redivo-Zaglia. Extrapolation and minimization procedures for the PageRank vector. In Web Information Retrieval and Linear Algebra Algorithms. Dagstuhl Seminar Proceedings, Volume 7071, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{brezinski_et_al:DagSemProc.07071.9,
  author =	{Brezinski, Claude and Redivo-Zaglia, Michela},
  title =	{{Extrapolation and minimization procedures for the PageRank vector}},
  booktitle =	{Web Information Retrieval and Linear Algebra Algorithms},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7071},
  editor =	{Andreas Frommer and Michael W. Mahoney and Daniel B. Szyld},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07071.9},
  URN =		{urn:nbn:de:0030-drops-10682},
  doi =		{10.4230/DagSemProc.07071.9},
  annote =	{Keywords: Extrapolation, PageRank, Web matrix, eigenvector computation.}
}
Document
Google Pageranking Problem: The Model and the Analysis

Authors: Stefano Serra Capizzano

Published in: Dagstuhl Seminar Proceedings, Volume 7071, Web Information Retrieval and Linear Algebra Algorithms (2007)


Abstract
Let $A$ be a given $n$-by-$n$ complex matrix with eigenvalues $lambda ,lambda _{2},ldots ,lambda _{n}$. Suppose there are nonzero vectors $% x,yin mathbb{C}^{n}$ such that $Ax=lambda x$, $y^{ast }A=lambda y^{ast }$, and $y^{ast }x=1$. Let $vin mathbb{C}^{n}$ be such that $v^{ast }x=1$% , let $cin mathbb{C}$, and assume that $lambda eq clambda _{j}$ for each $j=2,ldots ,n$. Define $A(c):=cA+(1-c)lambda xv^{ast }$. The eigenvalues of $% A(c)$ are $lambda ,clambda _{2},ldots ,clambda _{n}$. Every left eigenvector of $A(c)$ corresponding to $lambda $ is a scalar multiple of $% y-z(c)$, in which the vector $z(c)$ is an explicit rational function of $c$. If a standard form such as the Jordan canonical form or the Schur triangular form is known for $A$, we show how to obtain the corresponding standard form of $A(c)$. The web hyper-link matrix $G(c)$ used by Google for computing the PageRank is a special case in which $A$ is real, nonnegative, and row stochastic (taking into consideration the dangling nodes), $cin (0,1)$, $x$ is the vector of all ones, and $v$ is a positive probability vector. The PageRank vector (the normalized dominant left eigenvector of $G(c)$) is therefore an explicit rational function of $c$. Extrapolation procedures on the complex field may give a practical and efficient way to compute the PageRank vector when $c$ is close to $1$. A discussion on the model, on its adherence to reality, and on possible variations is also considered.

Cite as

Stefano Serra Capizzano. Google Pageranking Problem: The Model and the Analysis. In Web Information Retrieval and Linear Algebra Algorithms. Dagstuhl Seminar Proceedings, Volume 7071, pp. 1-34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{serracapizzano:DagSemProc.07071.10,
  author =	{Serra Capizzano, Stefano},
  title =	{{Google Pageranking Problem: The Model and the Analysis}},
  booktitle =	{Web Information Retrieval and Linear Algebra Algorithms},
  pages =	{1--34},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7071},
  editor =	{Andreas Frommer and Michael W. Mahoney and Daniel B. Szyld},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07071.10},
  URN =		{urn:nbn:de:0030-drops-10693},
  doi =		{10.4230/DagSemProc.07071.10},
  annote =	{Keywords: Google matrix, rank-one perturbation, Jordan canonical form, extrapolation formulae.}
}
Document
Graph matching with type constraints on nodes and edges

Authors: Catherine Fraikin and Paul Van Dooren

Published in: Dagstuhl Seminar Proceedings, Volume 7071, Web Information Retrieval and Linear Algebra Algorithms (2007)


Abstract
In this paper, we consider two particular problems of directed graph matching. The first problem concerns graphs with nodes that have been subdivided into classes of different type. The second problem treats graphs with edges of different types. In the two cases, the matching process is based on a constrained projection of the nodes and of the edges of both graphs in a lower dimensional space. The procedures are formulated as non-convex optimization problems. The objective functions use the adjacency matrices and the constraints on the problem impose the isometry of the so-called projections. Iterative algorithms are proposed to solve the optimization problems. As illustration, we give an example of graph matching for graphs with two types of nodes and graphs with two types of edges.

Cite as

Catherine Fraikin and Paul Van Dooren. Graph matching with type constraints on nodes and edges. In Web Information Retrieval and Linear Algebra Algorithms. Dagstuhl Seminar Proceedings, Volume 7071, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{fraikin_et_al:DagSemProc.07071.11,
  author =	{Fraikin, Catherine and Van Dooren, Paul},
  title =	{{Graph matching with type constraints on nodes and edges}},
  booktitle =	{Web Information Retrieval and Linear Algebra Algorithms},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7071},
  editor =	{Andreas Frommer and Michael W. Mahoney and Daniel B. Szyld},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07071.11},
  URN =		{urn:nbn:de:0030-drops-10716},
  doi =		{10.4230/DagSemProc.07071.11},
  annote =	{Keywords: Graph matching, Optimization, Typed nodes, Typed edges}
}
Document
Iteration at Different Levels: Multi-Level Methods fro Structured Markov Chains

Authors: Peter Buchholz

Published in: Dagstuhl Seminar Proceedings, Volume 7071, Web Information Retrieval and Linear Algebra Algorithms (2007)


Abstract
For the stationary analysis of large Markov chains in continuous and discrete time a wide variety of solution techniques has been applied in the past. Empirical comparisons show that in particular so called multi-level approaches that perform iterations at different levels are the most efficient solvers for a wide class of Markov chains. The methods combine ideas from aggregation disaggregation methods and algebraic multigrid. The talk gives an overview of the basic ideas of multi level approaches and shows which design alternatives for the algorithms exist. In particular it considers different forms of defining levels, available alternatives to realize prolongation and interpolation operations, different cycle types and different stopping criteria for the smoothing operations at each level. The last part of the talk is devoted to implementation issues and data structures that are necessary for an efficient realization of multi-level methods.

Cite as

Peter Buchholz. Iteration at Different Levels: Multi-Level Methods fro Structured Markov Chains. In Web Information Retrieval and Linear Algebra Algorithms. Dagstuhl Seminar Proceedings, Volume 7071, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{buchholz:DagSemProc.07071.12,
  author =	{Buchholz, Peter},
  title =	{{Iteration at Different Levels: Multi-Level Methods fro Structured Markov Chains}},
  booktitle =	{Web Information Retrieval and Linear Algebra Algorithms},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7071},
  editor =	{Andreas Frommer and Michael W. Mahoney and Daniel B. Szyld},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07071.12},
  URN =		{urn:nbn:de:0030-drops-10590},
  doi =		{10.4230/DagSemProc.07071.12},
  annote =	{Keywords: Stationary Analysis, Multi-Level Techniques, Kronecker Representation}
}
Document
Multidamping simulation framework for link-based ranking

Authors: Giorgios Kollias and Efstratios Gallopoulos

Published in: Dagstuhl Seminar Proceedings, Volume 7071, Web Information Retrieval and Linear Algebra Algorithms (2007)


Abstract
We review methods for the approximate computation of PageRank. Standard methods are based on the eigenvector and linear system characterizations. Our starting point are recent methods based on series representation whose coefficients are damping functions, for example Linear Rank, HyperRank and TotalRank, etc. We propose a multidamping framework for interpreting PageRank and these methods. Multidamping is based on some new useful properties of Google type matrices. The approach can be generalized and could help in the exploration of new approximations for list-based ranking. This is joint work with Georgios Kollias and is supported by a Pythagoras-EPEAEK-II grant.

Cite as

Giorgios Kollias and Efstratios Gallopoulos. Multidamping simulation framework for link-based ranking. In Web Information Retrieval and Linear Algebra Algorithms. Dagstuhl Seminar Proceedings, Volume 7071, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{kollias_et_al:DagSemProc.07071.13,
  author =	{Kollias, Giorgios and Gallopoulos, Efstratios},
  title =	{{Multidamping simulation framework for link-based ranking}},
  booktitle =	{Web Information Retrieval and Linear Algebra Algorithms},
  pages =	{1--17},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7071},
  editor =	{Andreas Frommer and Michael W. Mahoney and Daniel B. Szyld},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07071.13},
  URN =		{urn:nbn:de:0030-drops-10606},
  doi =		{10.4230/DagSemProc.07071.13},
  annote =	{Keywords: PageRank, Google, power method, eigenvalues, teleportation, list-based ranking, TotalRank}
}
  • Refine by Author
  • 4 Mahoney, Michael W.
  • 2 Frommer, Andreas
  • 2 Gallopoulos, Efstratios
  • 2 Greif, Chen
  • 2 Knight, Philip A.
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 9 PageRank
  • 4 Markov chains
  • 2 Approximation algorithm
  • 2 Google matrix
  • 2 Information retrieval
  • Show More...

  • Refine by Type
  • 19 document

  • Refine by Publication Year
  • 17 2007
  • 2 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail