Skip to main content
added 26 characters in body
Source Link
hulun
  • 33
  • 3

It is known that A δ-hyperbolic space is a geodesic metric space in which every geodesic triangle is δ-thin. (http://en.wikipedia.org/wiki/%CE%94-hyperbolic_space)

The question is that if we remove the word "geodesic" from the above definition, is it still acceptable? Or does the sentence a δ-hyperbolic space is a metric space in which every geodesic triangle is δ-thin still make sense?

@Seirios @mhull @YCor:

This question actually comes from applications. It is observed that the network models of many real world systems, such biological networks and social networks, have small hyperbolicity[http://www.stat.berkeley.edu/~mmahoney/pubs/treelike-icdm13.pdf]. This property enables more efficient algorithm design for some network problems.

However, sometimes the chosen path in reality between a pairs of nodes in the network is not necessarily the shortest path(geodesic distance). But it is possible that the actual distance function is satisfying the four conditions of metric. Then the question is that does it still make sense to measure the hyperbolicty of graph with the new distance function? And if the obtained hyperbolicty is small, does the algorithm leveraging the small hyperbolicty of graphs still work efficiently?

Many thanks!

It is known that A δ-hyperbolic space is a geodesic metric space in which every geodesic triangle is δ-thin. (http://en.wikipedia.org/wiki/%CE%94-hyperbolic_space)

The question is that if we remove the word "geodesic" from the above definition, is it still acceptable? Or does the sentence a δ-hyperbolic space is a metric space in which every geodesic triangle is δ-thin still make sense?

This question actually comes from applications. It is observed that the network models of many real world systems, such biological networks and social networks, have small hyperbolicity[http://www.stat.berkeley.edu/~mmahoney/pubs/treelike-icdm13.pdf]. This property enables more efficient algorithm design for some network problems.

However, sometimes the chosen path in reality between a pairs of nodes in the network is not necessarily the shortest path(geodesic distance). But it is possible that the actual distance function is satisfying the four conditions of metric. Then the question is that does it still make sense to measure the hyperbolicty of graph with the new distance function? And if the obtained hyperbolicty is small, does the algorithm leveraging the small hyperbolicty of graphs still work efficiently?

Many thanks!

It is known that A δ-hyperbolic space is a geodesic metric space in which every geodesic triangle is δ-thin. (http://en.wikipedia.org/wiki/%CE%94-hyperbolic_space)

The question is that if we remove the word "geodesic" from the above definition, is it still acceptable? Or does the sentence a δ-hyperbolic space is a metric space in which every geodesic triangle is δ-thin still make sense?

@Seirios @mhull @YCor:

This question actually comes from applications. It is observed that the network models of many real world systems, such biological networks and social networks, have small hyperbolicity[http://www.stat.berkeley.edu/~mmahoney/pubs/treelike-icdm13.pdf]. This property enables more efficient algorithm design for some network problems.

However, sometimes the chosen path in reality between a pairs of nodes in the network is not necessarily the shortest path(geodesic distance). But it is possible that the actual distance function is satisfying the four conditions of metric. Then the question is that does it still make sense to measure the hyperbolicty of graph with the new distance function? And if the obtained hyperbolicty is small, does the algorithm leveraging the small hyperbolicty of graphs still work efficiently?

Many thanks!

added 8 characters in body
Source Link
hulun
  • 33
  • 3

It is known that A δ-hyperbolic space is a geodesic metric space in which every geodesic triangle is δ-thin. (http://en.wikipedia.org/wiki/%CE%94-hyperbolic_space)

The question is that if we remove the word "geodesic" from the above definition, is it still acceptable? Or does the sentence a δ-hyperbolic space is a metric space in which every geodesic triangle is δ-thin still make sense?

This question actually comes from applications. It is observed that the network models of many real world systems, such biological networks and social networks, have small hyperbolicity[http://www.stat.berkeley.edu/~mmahoney/pubs/treelike-icdm13.pdf]. This property enables more efficient algorithm design for some network problems.

However, sometimes the chosen path in reality between a pairs of nodes in the network is not necessarily the shortest path(geodesic distance). But it is possible that the actual distance function is satisfying the four conditions of metric. Then the question is that does it still make sense to measure the hyperbolicty of graph with the actualnew distance function? And if the obtained hyperbolicty wasis small, does the algorithm leveraging the small hyperbolicty of graphs still holdwork efficiently?

Many thanks!

It is known that A δ-hyperbolic space is a geodesic metric space in which every geodesic triangle is δ-thin. (http://en.wikipedia.org/wiki/%CE%94-hyperbolic_space)

The question is that if we remove the word "geodesic" from the above definition, is it still acceptable? Or does the sentence a δ-hyperbolic space is a metric space in which every geodesic triangle is δ-thin still make sense?

This question actually comes from applications. It is observed that the network models of many real world systems, such biological networks and social networks, have small hyperbolicity[http://www.stat.berkeley.edu/~mmahoney/pubs/treelike-icdm13.pdf]. This property enables more efficient algorithm design for some network problems.

However, sometimes the chosen path in reality between a pairs of nodes in the network is not necessarily the shortest path(geodesic distance). But it is possible that the actual distance function is satisfying the four conditions of metric. Then the question is it still make sense to measure the hyperbolicty of graph with the actual distance function? And if the obtained hyperbolicty was small, does the algorithm leveraging the small hyperbolicty of graphs still hold?

Many thanks!

It is known that A δ-hyperbolic space is a geodesic metric space in which every geodesic triangle is δ-thin. (http://en.wikipedia.org/wiki/%CE%94-hyperbolic_space)

The question is that if we remove the word "geodesic" from the above definition, is it still acceptable? Or does the sentence a δ-hyperbolic space is a metric space in which every geodesic triangle is δ-thin still make sense?

This question actually comes from applications. It is observed that the network models of many real world systems, such biological networks and social networks, have small hyperbolicity[http://www.stat.berkeley.edu/~mmahoney/pubs/treelike-icdm13.pdf]. This property enables more efficient algorithm design for some network problems.

However, sometimes the chosen path in reality between a pairs of nodes in the network is not necessarily the shortest path(geodesic distance). But it is possible that the actual distance function is satisfying the four conditions of metric. Then the question is that does it still make sense to measure the hyperbolicty of graph with the new distance function? And if the obtained hyperbolicty is small, does the algorithm leveraging the small hyperbolicty of graphs still work efficiently?

Many thanks!

added 812 characters in body
Source Link
hulun
  • 33
  • 3

It is known that A δ-hyperbolic space is a geodesic metric space in which every geodesic triangle is δ-thin. (http://en.wikipedia.org/wiki/%CE%94-hyperbolic_space)

The question is that if we remove the word "geodesic" from the above definition, is it still acceptable? Or does the sentence a δ-hyperbolic space is a metric space in which every geodesic triangle is δ-thin still make sense?

This question actually comes from applications. It is observed that the network models of many real world systems, such biological networks and social networks, have small hyperbolicity[http://www.stat.berkeley.edu/~mmahoney/pubs/treelike-icdm13.pdf]. This property enables more efficient algorithm design for some network problems.

However, sometimes the chosen path in reality between a pairs of nodes in the network is not necessarily the shortest path(geodesic distance). But it is possible that the actual distance function is satisfying the four conditions of metric. Then the question is it still make sense to measure the hyperbolicty of graph with the actual distance function? And if the obtained hyperbolicty was small, does the algorithm leveraging the small hyperbolicty of graphs still hold?

Many thanks!

It is known that A δ-hyperbolic space is a geodesic metric space in which every geodesic triangle is δ-thin. (http://en.wikipedia.org/wiki/%CE%94-hyperbolic_space)

The question is that if we remove the word "geodesic" from the above definition, is it still acceptable? Or does the sentence a δ-hyperbolic space is a metric space in which every geodesic triangle is δ-thin still make sense?

Many thanks!

It is known that A δ-hyperbolic space is a geodesic metric space in which every geodesic triangle is δ-thin. (http://en.wikipedia.org/wiki/%CE%94-hyperbolic_space)

The question is that if we remove the word "geodesic" from the above definition, is it still acceptable? Or does the sentence a δ-hyperbolic space is a metric space in which every geodesic triangle is δ-thin still make sense?

This question actually comes from applications. It is observed that the network models of many real world systems, such biological networks and social networks, have small hyperbolicity[http://www.stat.berkeley.edu/~mmahoney/pubs/treelike-icdm13.pdf]. This property enables more efficient algorithm design for some network problems.

However, sometimes the chosen path in reality between a pairs of nodes in the network is not necessarily the shortest path(geodesic distance). But it is possible that the actual distance function is satisfying the four conditions of metric. Then the question is it still make sense to measure the hyperbolicty of graph with the actual distance function? And if the obtained hyperbolicty was small, does the algorithm leveraging the small hyperbolicty of graphs still hold?

Many thanks!

Source Link
hulun
  • 33
  • 3
Loading