Optimal oblivious routing in polynomial time

By Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke, Harald Räcke. 2003

3,342 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Networks and Communications

In Mathematical Optimization

Citations in the corpus

node2vec: Scalable Feature Learning for Networks (2016, background): “For example, in a social network, we might be interested in predicting interests of users, or in a protein-protein interaction network we might be interested in predicting functional labels of proteins [25, 37].”
Dependence Makes You Vulnberable: Differential Privacy Under Dependent Tuples (2016, background): “For example, in a social network graph (with nodes representing users, and edges representing ‘friendship’ relations), the ‘friendship’ between two nodes, not explicitly connected in the graph, can be inferred from the existence of edges between other nodes [28].”
Mutual exclusivity analysis identifies oncogenic network modules. (2012, background): “Multiple metrics have been developed for assessing network proximity of two nodes in a graph (reviewed in (Liben-Nowell and Kleinberg 2003)).”
Discovering Latent Network Structure in Point Process Data (2014, methodology): “A rich literature has arisen in recent years for applying statistical machine learning models to this type of problem, e.g., Liben-Nowell & Kleinberg (2007); Hoff (2008); Goldenberg et al. (2010).”
Exploiting homophily effect for trust prediction (2013, neutral): “We follow the common metric for unsupervised trust prediction in [9] to evaluate the performance of trust prediction.”
Optimal hierarchical decompositions for congestion minimization in networks (2008, background): “[9] (see also [3]) who gave a polynomial time algorithm to construct an optimal oblivious routing scheme for a given graph without using a hierarchical decomposition.”
Inferring social ties across heterogenous networks (2012, methodology): “[21] present a unsupervised method for link prediction.”
Simplicial closure and higher-order link prediction (2018, methodology): “Methodologically, asking whether one model is better than another at predicting new links provides a data-driven way of assessing the effectiveness of the models (32, 36, 37).”
From Duels to Battlefields: Computing Equilibria of Blotto and Other Games (2016, methodology): “We address this issue by transforming the solution space to a new space in which an LP equivalent to LP 1 becomes tractable (See, e.g., (Azar et al. 2003), for similar technique).”
Making intra-domain routing robust to changing and uncertain traffic demands: understanding fundamental tradeoffs (2003, methodology): “What can we take from this observation ? Can we expect it to prevail when network sizes scale up? It is known that some graphs with asymmetric link capacities have optimal oblivious ratio that is Ω(n) [3] (n is the number of nodes in the graph).”
Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction (2021, methodology): “Many link prediction methods, such as Katz index [30], personalized PageRank [42], graph distance [37], as well as graph theory algorithms like widest path [4] and most reliable path [4], are special instances of this path formulation with different summation and multiplication operators.”
A Deep Learning Approach to Link Prediction in Dynamic Networks (2014, methodology): “Most of the heuristic methods (e.g. [1], [12], [20]) ignore dynamics and evolutionary patterns of networks but rather predict links from one static snapshot of the graph.”
Beyond the hype: Big data concepts, methods, and analytics (2015, background): “Link prediction techniques utperform pure chance by factors of 40–50, suggesting that the urrent structure of the network surely contains latent information bout future links (Liben-Nowell & Kleinberg, 2003).”
Halting in Random Walk Kernels (2015, methodology): “Related similarity measures have also been employed in link prediction [6, 10] as a similarity score between vertices [8].”
Predicting positive and negative links in signed social networks by transfer learning (2013, background): “Previous research [15] has shown that, the structural information is a powerful and reliable source for the purpose of link prediction in unsigned networks, when applied in a traditional machine learning framework.”