| Register
\(\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. Add remark

      Problem 1.05.

      [Serrano] How do we measure the curvature of real networks?


        • Add remark

          Problem 1.1.

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


            • Add remark

              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.


                        • Add remark

                          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.


                                        • Add remark

                                          Problem 1.25.

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


                                                • Add remark

                                                  Problem 1.3.

                                                  [Bonnahon] What is the curvature of a network? How to define it?


                                                    • Add remark

                                                      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.


                                                            • Add remark

                                                              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.


                                                                    • Add remark

                                                                      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?)


                                                                                • Add remark

                                                                                  Problem 1.5.

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


                                                                                        • Add remark

                                                                                          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.