Geometry of Dynamic Large Networks: A Scaling and Renormalization Group Approach
Final rept. 15 Sep 2011-14 Sep 2013
LUCENT TECHNOLOGIES INC MURRAY HILL NJ
Pagination or Media Count:
The research conducted during the period of performance of this grant concerned investigation of large-scale geometry of prototypical and real-life large graphs, and their analyticalnumeric estimation of their core congestion. The research included demonstration of delta-hyperbolicity in a large variety of communication and social networks via scaling of the curvature plots through renormalization, detection of graph bottlenecks using a novel techniques based on the Dirichlet eigenvectors of the normalized graph Laplacian, proof of the fact that remetrization by factors away from zero and infinity does not eliminate ON sq core congestion in delta-hyperbolic graphs, derivation of an analytical expression for the average nodal congestion involving the sum of the inverses of the non-zero eigenvalues of the graph Laplacian when random walk routing replaces geodesic routing, and finally determination of the threshold for bootstrap percolation in periodic trees as an upper bounding mechanism for the threshold for more general graphs.
- Theoretical Mathematics
- Computer Systems