$\newcommand{\Cat}{{\rm Cat}}$ $\newcommand{\A}{\mathcal A}$ $\newcommand{\freestar}{ \framebox[7pt]{\star} }$

## 1. Problem session

This (below) was an attempt to record the problem session (Tuesday, November 1st), the way it proceeded. Your additions and comments are welcome.

- Dan
1. #### Problem 1.05.

[Serrano] How do we measure the curvature of real networks?
• #### Problem 1.1.

[Shavitt] Need ways to compute geodesics on spaces where curvature is variable (using embedded graphs).
• #### Problem 1.15.

[Krioukov] Why measure it? (What are the real-world applications?)
1. Remark. [Weinberger] Wasn’t that your result, that the internet has curvature $-1$ and dimension $2$?
• Remark. [Krioukov] So, yes, we need more examples like that, showing the significance of curvature.
• #### Problem 1.2.

[Holmes] Find (different) notions of distance on the space of graphs, or perhaps measures on this space. In particular: how far is a given graph from being a tree?
1. Remark. [Holmes] perhaps need to look at non-dense graphs; I have the impression that the problem is solved for dense ones.
• Remark. [Gao] How about tree-width?
• Remark. [Sullivan] Tree-width is not good enough. There is a relation to tree-length.
• #### Problem 1.25.

[Saniee] Is curvature related to clustering?
1. Remark. [Baryshnikov] What is meant by clustering?
• #### Problem 1.3.

[Bonnahon] What is the curvature of a network? How to define it?
• #### Problem 1.35.

[Mahoney] For random graphs, is there an idea for a degree of heterogeneity that could indicate hyperbolicity
1. Remark. [Weinberger] Similar to the question of frequency of hyperbolic groups among finitely generated/presented groups: could ask –

* What is a set of conditions ensuring hyperbolicity of an ensemble of random graphs (i.e., the set of hyperbolic graphs in the ensemble has probability one)?

* (Mahoney) important to emphasize randomness.
• #### Problem 1.4.

[Krioukov(?)] What would be meant by a graph having *positive* curvature? (Grids don’t have it; trees don’t; how about spheres?)
1. Remark. [Baryshnikov, Weinberger] That depends on a choice of scale.
• #### Problem 1.45.

[Krioukov/Jonckheere] What precise notions of negative curvature imply congestion?
1. Remark. [Weinberger] What price are you willing to pay to avoid congestion?
• Remark. [Bonahon/Saniee] *Where* does congestion occur? (something analogous to convex core?)
• #### Problem 1.5.

What are the data required to define congestion?
1. Remark. [Holmes] Do weights on the network or some such affect this?
• #### Problem 1.55.

[Baryshnikov] Is there a scale at which the structure of a (real) network “looks like” a manifold? (e.g., Krioukov’s result)
1. Remark. [Krioukov] This relates to the (previous) questions about how to define hyperbolicity or curvature for a single finite graph.

Cite this as: AimPL: Geometry of large networks, available at http://aimpl.org/largenetworks.